408王道数据结构强化——算法题

int D_min = MAX_INT;    //将D_min初始化为int类型的最大值
for (int i = 0; i < n; i++){    //遍历数组找到数组中的最小值
    if (arr[i] < D_min) D_min = arr[i];
}

int D_max = MIN_INT;    //将D_max设置为int类型的最小值

②还有一种思路：初始化时，将arr[0]赋值给D_min

1.2.比大小函数max(a,b) min(a,b)

加注释直接用（与1.1中代码相比较）

int D_min = MAX_INT;    //将D_min初始化为INT类型的最大值
for (int i = 0; i < n; i++) {
    D_min = min(D_min, arr[i]);    //D_min = D_min和arr[i]中的较小值
}

1.3.使用CIN、COUT代替PRINTF、SCANF

cin >> A[0];
cout << A[0];

1.4.i++和++i

i++先对i进行处理，再自增；++i先自增再对i处理

1.5.交换函数swap(a,b)

①直接用，加注释

②原定义中是采用的指针方式，因此交换的是两个地址空间内的内容

if (arr[i] < arr[j]) swap(arr[i],arr[i+1]);    //arr[i] < arr[j]时，交换A[i]和A[i+1]的值

//等价于
if (arr[i] < arr[j]) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

2.复杂度

1.时间上尽可能高效→不管空间

2.时间和空间两方面都尽可能高效（等价于尽可能高效）→时间优先，空间次要

3.空间复杂度为O（1）且时间上尽可能高效→时间优先，限定空间O（1）

4.什么都没说→能做出来就行

5.只考虑递归和循环

①循环：

②递归：时间复杂度为递归的层数；时间复杂度为递归的次数

3.数组

3.1.暴力求解

1.枚举：穷尽所有可能→for循环

2.对无序数组排序→快速排序

3.2.优化

1.考虑没有使用到的条件

2.过度使用条件：例如并没有要求排序的条件下却使用排序的方法做

3.考虑别的思路：

①折半算法：

（1）要求：有序（根据当前查找的结果方便下次查找）；数组；一个

（2）代码实现：时间复杂度O（logn），空间复杂度O（1）

int Binary_Search(int arr[], int key, int n) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid == key) return mid;    //mid指向的元素和key相等，返回mid，即数组下标
        else if (arr[mid] < key) low = mid + 1;    //mid指向的元素比key小，去右半部分
        else high = mid - 1;    //mid指向的元素比key大，去左半部分
    }
    //如果数组中有和key相等的元素，则一定会在while循环中return
    //while循环结束后还没有执行return，则说明数组中没有和key相等的元素，return-1
    return -1;
}

②指针后移：要求：有序（利用有序性，当前指向的元素是各自表中的最小值，在它们中取最小值即是当前表中所有元素的最小值）；多个；线性表（可以是数组，也可以是链表）

③贪心算法：局部最优

④动态规划：以空间换时间，空间保存状态

4.单链表

1.不能快排，不能折半查找（没有数组随机存取的特性）

2.注意条件：空间复杂度O（1），不可以改变链表结构

3.数据结构定义：

typedef struct LNode{    //单链表
    struct LNode *next;
    int data;
}LNode, *LinkList;

typedef struct LNode{    //双链表
    struct LNode *prior, *next;
    int data;
}LNode, *LinkList;

4.注意是否有头结点

5.暴力解法：①枚举 ②利用数组保存链表元素（注意使用条件）

6.优化方向：

①前后指针：前后指针相差n个距离，同时向后移动，距离不变（查找倒数第k个）

②快慢指针：链表存在回路，走得快的指针会追上走得慢的指针

③头插法：逆置链表（从头结点后的第一个元素取，然后将该元素用头插法插入头结点后）

④数组指针后移

⑤以空间换时间（长度为n的数组）

5.树

1.递归方式实现，不用记忆非递归

2.定义：左右孩子表示法最常用

3.树的遍历

6.真题（只考虑次优解和暴力解）

6.1.数组

6.1.1.（2010）

（1）新建一个与arr数组等长的数组arr，先将arr的后p个元素依次存放到res数组的前p个元素中，然后再将arr的剩余元素依次存放到res的剩余元素中

int* Reverse(int arr[], int n, int p) {
    int *res = (int*)malloc(sizeof(n));
    memset(a, 0, sizeof(int) * n);
    int i, j;
    for (i = n - p + 1, j = 0; i < n; i++, j++) res[j] = arr[i];
    for (i = 0; i < n - p + 1; i++, j++) res[j] = arr[i];
}

（3）O（n），O（n）

6.1.2.（2011）

（1）都放入新数组中快速排序

int Partation(int arr[], int low, int high) {
    随机将数组中某一元素和arr[low]交换    //快排优化
    int pivot = arr[low];    //选择arr[low]为基准元素
    while (low < high) {    
        while (low < high && arr[high] >= pivot) high--;    
        arr[low] = arr[high];
        while (low < high && arr[low] < pivot) low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotPos = Partation(arr, low, high);
        QuickSort(arr, low, pivotPos - 1);
        QuickSort(arr, pivotPos + 1, high);
    }
}

int GetMidNum(int A[], int B[], int len){
    int* C = (int*)malloc((sizeof(int) * (2 * len))    //新建长度为2len的数组C
    int i,j;
    for (i = 0; i < len; i++) C[i] = A[i];    //将数组A复制到数组C的前半段中
    for (j = 0; j < len; i++, j++) C[i] = B[j];    //将数组B复制到数组C的后半段中
    QuickSort(C, 0, 2 * len - 1);    //对数组C进行快速排序
    cout << C[len - 1];    //输出中位数
}

（2）数组指针后移把数存入第三个数组（用count记录进行次数的方法并不能降低时间复杂度，省略系数后还是n的时间复杂度）

int GetMidNum(int A[], int B[], int len) {
    int *C = (int*)malloc(sizeof(int) * 2 * len);
    int i, j, k;
    for(i = 0, j = 0, k = 0; i < len && j < len; k++){    
        if (A[i] < B[j]) {    //比较A[i]和B[j]，更小的存入C，并且该数组的指针向后移
            C[k] = A[i];
            i++;
        }
        else {
            C[k] = B[j];
            j++;
        }
    }
    cout << C[len - 1];
}

（3）数组指针后移（本质上和2一样，都是控制指针后移）

int GetMidNum(int A[], int B[], int len) {
    int count = 0, i, j, res;
    while (i < len && j < len && count < len) {
        if (A[i] < B[j]) {
            i++;
            res = A[i];
        }
        else {
            j++;
            res = B[j];
        }
        count++;
    }
    cout << res;
}

int GetMidNum(int A[], int B[], int len) {
    int i, j, k;
    for (k = 1, i = 0, j = 0; k < n; k++) {    //一共移动n - 1次
        if (A[i] < B[j]) i++;
        else j++;
    }
    cout << min(A[i], B[j]);    //输出A和B数组中当前元素的较小值
}

6.1.3.（2013）

（1）枚举：逐个元素判断（两层循环）

void MainNum(int A[], int n) {
    int i, j, count;
    for (i = 0; i < n; i++) {
        for (j = 0, count = 0; j < n; j++) {
            if (A[j] == A[i]) count ++;    //当前A[j]等于A[i]，出现次数+1
        }
        if (count > n / 2) {
            cout << A[i];    //A[i]出现次数满足主元素要求，输出A[i]
            return;    //结束
        }
    }
    cout << -1;    //没有主元素，输出-1
    return;
}

（2）快速排序：

int Partation(int arr[], int low, int high) {
    随机选定数组下标low - high之间的元素和arr[low]对调    //快排优化
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <pivot) low++;
        arr[high] = arr[low;
    }
    arr[low] = pivot;
    return low;
}

void QuickSort(int arr[], int low, int high) {    //快速排序
    if (low < high) {
        int pivotPos = Partation(arr, low, high);
        QuickSort(arr, low, pivotPos - 1);
        QuickSort(arr, pivotPos + 1, high);
    }
}


int MainNum(int arr[], int n) {
    //count标记当前元素的出现次数，current记录当前元素
    int i, current = arr[0], count = 1;    
    for (int i = 1; i < n; i++) {    //遍历数组
        if (arr[i] == current) count ++;    //当前元素和current相同，出现次数 + 1
        else {    //当前元素和current不同，用当前元素替换current，并且出现次数归1
            current = A[i];
            count = 1;
        }
        if (count > n / 2) return current;    //出现次数大于>n/2，则current为主元素
    }
    return -1;    //没有主元素，返回-1
}

（3）动态规划：空间换时间，A出现的元素范围是正整数且<n，申请一个长度为n的数组，

第一遍遍历A数组记录每个元素其值出现的次数：设A中出现i，则count[i]++

第二遍遍历count数组，找是否有元素的值 > n/2，即A中出现次数 > n/2

int GetMainNum(int A[], int n) {
    int *count = (int*)malloc(sizeof(int) * n);
    memset(count, 0 , sizeof(int) * n);
    //遍历数组，将当前元素的值作为下标在count中对应元素+1
    for (int i = 0; i < n; i++) count[A[i]]++;
    //count[i]元素的值即i在A中出现的次数
    for (int i = 0; i < n; i++) {
        if (count[i] > n / 2) return i;    //i出现次数>n/2，i为主元素
    }
    return -1;
}

6.1.4.（2016）

快速排序：先对数组进行排序即满足需求（向下取整，即数组个数为奇数时，右大左小）

int Partation(int arr[], int low, int high) {
    随机选择一个数组下标为low - high的元素和arr[low]交换    //快排优化
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] < pivot) low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void QuickSort(int arr[], int low, int high){
    if (low < high) {
        int pivotPos = Partation(arr, low , high);
        QuickSort(arr, low, pivotPos - 1);
        QuickSort(arr, pivotPos + 1, high);
    }
}

void Divid(int arr[], int n){
    QuickSort(arr, 0, n - 1);    //快速排序
    for (int i = 0; i < n / 2; i++) cout << arr[i] << endl;    //输出子集A1
    for (int i = n / 2; i < n; i++) cout << arr[i] << endl;    //输出子集A2
}

6.1.5.（2018）

（1）快速排序

int Partation(int arr[], int low,int high) {
    随机选择一个数组下标为low - high之间的元素和arr[low]交换    //快排优化
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] < pivot) low--;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotPos = Partation(arr, low, high);
        QuickSort(arr, low, pivotPos - 1);
        QuickSort(arr, pivotPos + 1, high);
    }
}

int GetNum(int arr[], int n) {
    QuickSort(arr, 0, n - 1);    //将数组排序成有序
    int i, j;
    while (arr[i] <= 0 && i < n) i++;
    if (i == n) return 1;    //数组中的没有正数
    if (arr[i] != 1) return 1;    //此时arr[i]为数组中最小正整数
    //如果不是1，则1是未出现的最小正整数
    else {    //arr[i]为1，找到第一个正数间断点
        j = i + 1; 
        while (j < n && arr[j] != arr[j - 1] && arr[j] != arr[j - 1] + 1);
        return arr[j - 1] + 1;    //返回上一个元素+ 1的值
    }
}

（2）空间换时间

int MinNum(int arr[], int n) {
    int *count = (int*)malloc(sizeof(int) * (n + 1));
    memset(count, 0, sizeof(int) * (n + 1));
    int i;
    //遍历数组，当前元素大于0，则在count数组以该元素为数组下标的元素自增1
    for (i = 0; i < n; i++) if (arr[i] > 0) count[arr[i]]++;
    //count数组元素的值即该下标在arr数组中出现的次数，返回第一个为0的下标
    for (i = 1; i < n + 1; i++) if (count[i] == 0) return i;
}

6.1.6.（2020）

int GetDis(int a, int b){
    int c = a - b;
    if (c >= 0) return c;
    else return -c;
}

int MinDis(int A[], int B[], int C[], int lenA, int lenB, int lenC){
    int i, j, k, temp;
    int min = MAX_INT;    //将min初始化为INT类型的最大值
    for (i = 0; i < lenA; i++){
        for (j = 0; j < lenB; j++){
            for (k = 0; k < lenC; k++){
                //计算三个数组当前元素的距离
                temp = GetDis(A[i], B[j]) + GetDis(A[i], C[k]) + GetDis(B[j], C[k]);
                //更新min
                if (temp < min) min = temp;
            }
        }
    }
    return min;
}

6.2.链表

6.2.1.（2009）

（1）前后指针

int GetK(LNode *L, int k){
    LNode *p = L, *q = L;
    for (int i = 1; i < k; i++) p = p->link;    //p向前移动k - 1个结点
    while(p->link) {    //p和q同步移动，p移动至链表最后一个结点时，q就是倒数第k个结点
        p = p->link;
        q = q->link;
    }
    return q->data;    //返回q的data
}

（2）用数组保存每个结点的值

int GetK(LNode *L, int k){    
    int len = 0;    
    LNode *p = L;
    while (p) {    //遍历链表得到链表长度
        p = p->link;
        len++;
    }
    int *arr = (int*)malloc(sizeof(int) * len);    //申请和链表长度相同的数组
    int i = 0;
    p = L;
    while (p) {    //遍历链表，保存每个结点的值到数组中
        arr[i++] = p->data;
        p = p->link;
    }
    cout << arr[n - k];    //输出倒数第k个结点
}

（3）遍历数组两次，第一次得到数组的长度，第二次移动到倒数第k个

int ans(LNode *L, int k){
    int len = 0;
    LNode *p = L;
    while (p) {    //第一遍循环得到链表长度
        p = p->next;
        len++;
    }
    p = L;    //p重新指向头结点
    count = n - k + 1;
    while (count > 0) p = p->next;
    cout << p->data;
}

6.2.2.（2012）

（1）枚举

LNode* ans(LNode *str1, LNode *str2){
    LNode *p = str1->next, *q = str2->next;
    while (p) {
        q = str2->next;
        while (q) {
            if (p == q) return p;
            q = q->next;
        }
        p = p->next;
    }
}

（2）用数组保存每个结点的地址

void ans(LNode *str1, LNode *str2){
    LNode *p = str1->next, *q = str2->next;    //pq分别指向str1和str2的头结点
    LNode A[maxn], B[maxn];    //申明两个分别足够容纳下str1和str2结点数组
    int lenA = 0, lenB = 0;
    while (p) {
        A[lenA++] = p;
        p = p->next;
    }
    while (q) {
        B[lenB++] = q;
        q = q->next;
    }
    int i;
    for (i = 1; i < min(lenA, lenB); i++) {    //从后往前找
        if (A[lenA - i] != B[lenB - i]) {    //第一个不相同的后缀结点
            cout << A[lenA - i + 1];    //返回该结点的上一个结点
            return;
        }
    }
    cout << A[lenA - i];    //短的链表的元素都是长链表的公共部分 
    return;
}

（3）双指针：较长表的指针移动两表长度的差值，使得两表剩余长度一致，然后一一进行对比

void ans(LNode *str1, LNode *str2){
    int len1 = len2 = 0;
    LNode *p = str1->next, *q = str2->next;
    while (p) {    //分别遍历链表得到长度
        len1++;
        p = p->next;
    }
    while (q) {
        len2++;
        q = q->next;
    }
    if (len1 <= len2) {    //移动较长表的指针，并将较短表指针指向其第一个结点
        q = str2;
        for (int i = 0; i < len2 - len1; i++) q = q->next;
        p = str1->next;
    }
    else {
        p = str1;
        for (int i = 0; i < len1 - len2; i++) p = p->next;
        q = str2->next;
    }
    int len = min(len1, len2);    //len取len1和len2的较小值
    for (int i = 0; i < len; i++) {    //输出第一个相同结点
        if (p == q) {
            cout << p;
            return;
        }
        p = p->next;
        q = q->next;
    }
    return;
}

6.2.3.（2015）

（1）暴力解：每个结点都和剩余所有结点进行一次比较

void ans (LNode *L) {
    LNode *p = L, *qpre = L, *q = L->link;    
    while (p) {
        qpre = p;    //重置q和qpre结点，q指针指向p的下一个结点，qpre指向q的上一个结点
        q = qpre->link;
        while (q) {
            if (abs(p->data) == abs(q->data)) {    //q和p相等，则删除q结点
                qpre->link = q->link;
                free(q);
                q = qpre->link;
            }
            else {    //q和p不相等，q和qpre指针后移
                q = q->link;
                qpre = qpre->link;
            }
        }
        p = p->link;    //p指针后移
    }
    return;
}

（2）数组保存出现过的元素

void ans (LNode &L)
    LNode *p = L->link, *q = L;    //p指向头结点，q指向p的上一个结点
    bool mark[n + 1] = { false };
    while (p) {
        if (mark[abs(p->data)] == false) {    //该值第一次出现
            mark[abs(p->data)] = true;    //mark中对应下标改为true
            p = p->link;    //pq各自后移
            q = q->link;
        }
        else {    //该值已经在之前的结点中出现过，将该结点删除
            q->link = p->link;    
            free(p);
            p = q->link;
        }
    }
}

6.2.4.（2019）

（1）暴力解

void ans(node &L, int n){
    node *p = L->next, *q = L;
    int i;
    for (i = 0; i < n / 2; i++) {    //p指向后半链的第一个结点
        p = p->next;    
        q = q->next;
    }
    q->next = NULL;    //将前后半链分开
    node *k = L->next, *kpre = L;    //k指向第一个结点，kpre指向k的上一个结点
    while (k->next) {
        k = k->next;
        pre = pre->next;
        q = p;
        while (q->next) q = q->next;    //q指向后半链的最后一个结点
        q->next = k;    //将q插入到kpre后
        kpre->next = q;
        kpre = q;
    }
}

（2）逆置

void ans(node &L) {
    node *p = L->next, *pre = L, *q = L->next;    //q指向前半链第一个结点
    for (int i = 0; i < n / 2; i++) {    //p指向后半链第一个结点，pre指向前半链最后一个结点
        p = p->next;
        pre = pre->next;
    }
    q = pre;    //q指向前半链最后一个结点
    q->next = NULL;    //前后半链分开
    while (p) {    //采用头插法将后半链逆置
        pre = p;
        p = p->next;
        pre->next = q->next;
        q->next = pre;
    }
    p = q->next;    //p指向后半链第一个结点（逆置后）
    q = L->next;    //q指向第一个结点
    pre = L;    //pre指向L
    L->next = NULL;    //将L的next指针置空
    while (q) {    //尾插法循环插入L
        node* temp = q;    //选择前半链的第一个结点插入
        q = q->next;
        pre->next = temp;
        pre = pre->next;
        if (p) {    //选择后半链的第一个结点插入
            temp = p;
            p = p->next;
            pre->next = temp;
            pre = pre->next;
        }
    }
    pre->next = NULL;    //将pre的NEXT指针置空
    return;
}

6.3.树

6.3.1.（2014）

typedef struct BiTNode {
    struct BiTNode *lchild, *rchild;
    int weight;
}BiTNode;

int WPL = 0;    //记录整棵树的WPL

void PreOrder (BiTNode *T, int d) {    //先序遍历
    if (T) {    //当前结点非空
        if (!T->lchild && !T->child) {    //叶子结点
            WPL = WPL + T->weight * d;    //计算当前结点的WPL
        }
        PreOrder (T->lchild, d + 1);    //进入其左子树
        PreOrder (T->rchild, d + 1);    //进入其右子树
    }
}

void ans(BiTNode *T) {
    PreOrder (T, 0);    //根节点层高为0
}