题解

#include <iostream>
#include <vector>

using namespace std;

void showVector(vector<int> v) {
    for (int i: v) {
        cout << i << " ";
    }
    cout << endl;
}

void func1(vector<int> &A, vector<int> &A1, vector<int> &A2) { // N^2复杂度
    // 选出最大的 n/2 个元素放入A1
    bool flag[A.size()];
    for (int i = 0; i < A.size(); i++)flag[i] = false;

    for (int i = 0; i < A.size() / 2; i++) { // 选择出前 n/2 个最大的元素
        int max = -1, index = -1;
        for (int j = 0; j < A.size(); j++) {
            if (A[j] > max and not flag[j]) {
                max = A[j], index = j;
            }
        }
        A1.push_back(max);
        flag[index] = true;
    }
    for (int j = 0; j < A.size(); j++) {
        if (!flag[j]) {
            A2.push_back(A[j]);
        }
    }
}

int main() {
    vector<int> A = {21, 35, 5, 17, 15};
    vector<int> A1, A2;
    showVector(A1), showVector(A2);
    func1(A, A1, A2);
    showVector(A1), showVector(A2);
}

#include <iostream>
#include <vector>

#define N 100

using namespace std;
struct LinkNode {
    int data;
    LinkNode *next;
};

void createLinkNode(LinkNode *link, vector<int> v) {
    LinkNode *head = link;
    for (int i: v) {
        LinkNode *temp = new LinkNode();
        temp->next = nullptr;
        temp->data = i;
        head->next = temp;
        head = head->next;
    }
}

void showLinkNode(LinkNode *link) {
    link = link->next;
    while (link != nullptr) {
        cout << link->data << " ";
        link = link->next;
    }
    cout << endl;
}

int abs(int a) {
    return a > 0 ? a : -a;
}

void delSameAbsNode(LinkNode *link) {
    LinkNode *head = link->next, *pre = link;
    bool flag[N];
    for (int i = 0; i < N; i++) {
        flag[i] = false;
    }
    while (head != nullptr) {
        if (flag[abs(head->data)]) { //出现过，删除当前节点
            pre->next = head->next;
        } else {
            flag[abs(head->data)] = true;
        }
        pre = head;
        head = head->next;
    }
}


int main() {
    vector<int> v = {21, -15, -15, -7, 15};
    LinkNode *head = new LinkNode();
    createLinkNode(head, v);
    showLinkNode(head);
    delSameAbsNode(head);
    showLinkNode(head);
}

#include <iostream>

using namespace std;

int findMain(int *array, int n) {
    int map[n];
    int maxN = -1, maxT = -1;
    for (int i = 0; i < n; i++) {
        map[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        map[array[i]]++;
    }
    for (int i = 0; i < n; i++) {
        if (map[i] > maxT) {
            maxT = map[i];
            maxN = i;
        }
    }
    return maxT > n / 2 ? maxN : -1;
}

int main() {
    int array[] = {0, 5, 5, 3, 5, 7, 5, 5};
    cout << findMain(array, 8);
}

#include <iostream>
#include <vector>

using namespace std;
struct LinkNode {
    char data;
    LinkNode *next;
};

void createLinkNode(LinkNode *link, vector<char> v) {
    LinkNode *head = link;
    for (char i: v) {
        LinkNode *temp = new LinkNode();
        temp->next = nullptr;
        temp->data = i;
        head->next = temp;
        head = head->next;
    }
}

void showLinkNode(LinkNode *link) {
//    link = link->next;
    while (link != nullptr) {
        cout << link << " ";
        link = link->next;
    }
    cout << endl;
}

LinkNode *findSuffix(LinkNode *A, LinkNode *B) {
    int lenA = 0, lenB = 0;
    LinkNode *pA = A->next, *pB = B->next;
    while (pA != nullptr) {
        lenA++;
        pA = pA->next;
    }
    while (pB != nullptr) {
        lenB++;
        pB = pB->next;
    }
    pA = A->next, pB = B->next;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            pA = pA->next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            pB = pB->next;
        }
    }
    while (pA != nullptr || pB != nullptr) {
        if (pA->data == pB->data) {
            return pA;
        }
        pA = pA->next, pB = pB->next;
    }
    return new LinkNode();
}

int main() {
    vector<char> c1 = {'l', 'o', 'a', 'd', 'i', 'n', 'g'};
    vector<char> c2 = {'b', 'e', 'i', 'n', 'g'};

    LinkNode *headA = new LinkNode();
    LinkNode *headB = new LinkNode();
    createLinkNode(headA, c1);
    createLinkNode(headB, c2);

    showLinkNode(headA);
    showLinkNode(headB);

    cout << findSuffix(headA, headB);
}

#include <iostream>

using namespace std;

int mSearch(int *A, int *B, int n) {
    int s1, d1, m1, s2, d2, m2;
    s1 = 0;
    d1 = n - 1;
    s2 = 1;
    d2 = n - 1;
    while (s1 != d1 || s2 != d2) {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == B[m2])return A[m1];
        if (A[m1] < B[m2]) {
            if ((s1 + d1) % 2 == 0) {
                s1 = m1;
                d2 = m2;
            } else {
                s1 = m1 + 1;
                d2 = m2;
            }
        } else {
            if ((s1 + d1) % 2 == 0) {
                s2 = m2;
                d1 = m1;
            } else {
                s2 = m2 + 1;
                d1 = m1;
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];
}

int mSearch2(int *A, int *B, int n) {
    int mid = (int) (2 * n + 1) / 2;
    int mA = 0, mB = 0;
    bool flag = false;
    for (int i = 0; i < mid; i++) {
        if (A[mA] < B[mB]) {
            mA++;
            flag = true;
        } else {
            mB++;
            flag = false;
        }
    }
    return flag ? A[--mA] : B[--mB];
}

int main() {
    int array1[] = {1, 9, 11, 17, 19};
    int array2[] = {2, 4, 7, 8, 20};
    cout << mSearch(array1, array2, 5) << endl;
    cout << mSearch2(array1, array2, 5) << endl;
}
// 8 8

#include <iostream>

using namespace std;

void showArray(int *array, int n) {
    for (int i = 0; i < n; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void leftTurn(int *array, int n, int p) {
    int temp[p];
    for (int i = 0; i < p; i++) {
        temp[i] = array[i]; //临时数组存储前p个元素
    }
    for (int i = 0; i < n - p; i++) {
        array[i] = array[i + p]; //将其余的元素往前移动
    }
    for (int i = n - p; i < n; i++) {
        array[i] = temp[i - p - 1];
    }
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 57, 8};
    showArray(array, 7);
    leftTurn(array, 7, 3);
    showArray(array, 7);
}
// 1 2 3 4 5 57 8
// 4 5 57 8 1 2 3

#include <iostream>
#include <vector>

using namespace std;
struct LinkNode {
    int data;
    LinkNode *next;
};

void createLinkNode(LinkNode *link, vector<int> v) {
    LinkNode *head = link;

    for (int i: v) {
        LinkNode *temp = new LinkNode();
        temp->next = nullptr;
        temp->data = i;
        head->next = temp;
        head = head->next;
    }
}

void showLinkNode(LinkNode *link) {
    link = link->next;
    while (link != nullptr) {
        cout << link->data << " ";
        link = link->next;
    }
    cout << endl;
}

int searchReversedK(LinkNode *link, int k) {
    LinkNode *l1, *l2;
    int count = 0;
    l1 = link;
    l2 = link;
    for (int i = 0; i < k; i++) {
        l1 = l1->next;
        count++;
    }
    while (l1 != nullptr) {
        l1 = l1->next;
        l2 = l2->next;
        count++;
    }
    if (count < k)return 0;
    return l2->data;
}

int main() {
    vector<int> v = {1, 3, 4, 2, 5};
    LinkNode *link = new LinkNode();
    createLinkNode(link, v);
    showLinkNode(link);
    cout << searchReversedK(link, 6);
}