2009 單鏈表（雙指針）

分析：首先呢，給我們的數據結構是一個帶有表頭結點的單鏈表，也不允許我們改變鏈表的結構。鏈表的長度不是直接給出的啊，所以這個倒數也很棘手。那我們該如何解決這個“k”呢，我們并不能一下子就知道這個倒數第k位置在哪里，不過不妨倒著想一下，如果現在有一個指針指向尾結點，又有一個指針指向倒數第k個。那我們再逆推一下過程這兩個指針一起往回走，當先前指向倒數第k個結點的指針走到表頭與list相會時，后面那個指針是不是也到正數第k個結點的頭上了？那是不是我們的問題就解決了。

思路：設置兩個指針p、q，初始時都指向list，讓q先往后走k步（計數器實現），這時再讓p、q同時朝后走，直至q到達尾指針（所指的next為空），那么此時此刻的p所指向的結點既是我們所需要的倒數第k個結點，將其data值輸出。

詳細實現步驟：

1. 初始化指針: 設置兩個指針p和q，初始時都指向鏈表的頭節點list。
2. 移動快指針: 讓指針q向前移動k步。這里需要注意的是，如果k大于鏈表的長度，那么查找失敗，因為不存在倒數第k個節點。
3. 同步移動雙指針: 當q成功移動了k步并且q不為空（即沒有到達鏈表末尾）時，開始同步移動p和q兩個指針。每次循環，p和q都同時向后移動一步，即p = p->next;和q = q->next;。
4. 查找結束條件: 當指針q到達鏈表的末尾（即q->next為NULL）時，停止移動。此時，p所指向的節點就是鏈表中倒數第k個節點。
5. 檢查并輸出結果: 檢查指針p是否為NULL。如果p不為空，說明找到了倒數第k個節點，輸出該節點的data域的值，并返回1表示成功。如果p為空，說明沒有找到倒數第k個節點，返回0表示失敗。
6. 返回結果: 函數返回查找的結果，即1或0。

注：有可能參考答案里頭并不是這樣寫的呀，我還沒搞懂這個評分細則。（大概是這樣）

// 假設LinkList是如下定義的結構體
typedef struct LinkNode {int data;struct LinkNode *next;
} LinkList;int findKthFromEnd(LinkList list, int k) {LinkList p, q;p = list;q = list;int cnt = 0;// 讓q先向后走k步while (cnt < k && q != NULL) {q = q->next;cnt++;}// 當q到達第k+1個節點或鏈表尾部時，p和q一起向后移動while (q != NULL) {p = p->next;q = q->next;}// 此時p指向的就是倒數第k個節點，如果存在的話if (p != NULL) {printf("%d", p->data);return 1; // 查找成功} else {return 0; // 查找失敗}
}

2010 順序表

分析：

“循環”左移，那這個循環就應該是我們需要重點思考的點。先考慮最簡單的我們可以設置兩個數組，其中一個數組保存的是原數據，另一個初始為空。接著想要實現循環左移就只需要找出相對應的位置再一一賦值即可。（我比較笨只會右移，就把左移模擬成右移了）

到這會兒又可以開始想一下如何在時間和空間上優化了。空間的話，我們是可以只用一個數組（＋一個中間變量＋循環遍歷）來實現的。原本我覺得已經可以了啊，然后看了書上覺得比較秒也更好實現。在時間上呢，也是能夠發現一個規律。

1、算法思想

1. 反轉數組：首先反轉整個數組?R。
2. 反轉前?n?p?個元素：接著反轉數組的前?n?p?個元素。
3. 反轉后?p 個元素：最后反轉數組的后?p?個元素。

2、算法實現

// 反轉數組的輔助函數
void reverse(int arr[], int start, int end) {while (start < end) {// 交換元素int temp = arr[start];arr[start] = arr[end];arr[end] = temp;start++;end--;}
}// 循環左移 p 個位置
void rotate(int arr[], int n, int p) {// 反轉整個數組reverse(arr, 0, n - 1);// 反轉前 n - p 個元素reverse(arr, 0, n - p - 1);// 反轉后 p 個元素reverse(arr, n - p, n - 1);
}

3、復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(1)?
  • 常數空間使用：該算法僅使用了幾個額外的變量（如 temp、start 和 end），這些變量的數量與輸入數組的大小無關。
  • 不使用額外數組：算法在進行反轉時，直接在原數組上進行操作，而不需要創建新的數組來存放中間結果。

2011 順序表

分析：

先不考慮細節問題，最簡單的做法當然是先將兩個數組合并啦然后直接找中位數。

但是我們仔細想想我們只需要找出來并不需要實際的再花額外空間去合并，故只需設置一個計數器和兩個指針從兩個數組頭開始遍歷比大小，小的放行，大的留著下一趟比，然后再將計數器加1，加到一個數組的長度時即是我們所求的答案。那這樣的話，時間復雜度就是O(n)，空間復雜度就是O(1) 。

int findMedian(int A[], int B[], int n) {    //n是一個升序序列的長度int i = 0, j = 0;int cnt = 0;int temp = 0;while (cnt < n) {if (i < n && (j >= n || A[i] <= B[j])) {temp = A[i++];} else {temp = B[j++];}cnt++;}return temp;
}

書里頭給了這種就是二分咯，沒有往這個方面想，那時間復雜度就會縮減到O(log2n)，空間復雜度就還是一樣的。

#include <stdio.h>int findMedian(int A[], int B[], int n) {int s1 = 0, d1 = n - 1;int s2 = 0, d2 = n - 1;while (s1 < d1 || s2 < d2) {int ml = (s1 + d1) / 2;int m2 = (s2 + d2) / 2;if (A[ml] == B[m2]) {return A[ml]; // 找到中位數}if (A[ml] < B[m2]) {if ((d1 - s1 + 1) % 2 == 1) { // 奇數個元素s1 = ml; // 保留中間點} else { // 偶數個元素s1 = ml + 1; // 舍棄前半部分}d2 = m2; // 舍棄 B 的后半部分} else {if ((d2 - s2 + 1) % 2 == 1) { // 奇數個元素d1 = ml; // 舍棄 A 的后半部分} else { // 偶數個元素d1 = ml - 1; // 保留中間點}s2 = m2 + 1; // 舍棄 B 的前半部分}}// 返回中位數if (s1 > d1) return B[s2]; // A 完全被舍棄if (s2 > d2) return A[s1]; // B 完全被舍棄return (A[s1] < B[s2]) ? A[s1] : B[s2]; // 返回較小的
}// 測試函數
int main() {int A[] = {1, 3, 8, 9, 15};int B[] = {7, 11, 18, 19, 21};int n = sizeof(A) / sizeof(A[0]);int median = findMedian(A, B, n);printf("中位數是: %d\n", median);return 0;
}

2012 單鏈表（雙指針）

分析：最簡單的應該是，直接安排兩個指針遍歷兩個鏈表，再將其數據域的值賦給兩個輔助數組，然后根據數組可以比較簡單的先把共同后綴比出來，再利用兩個index值來判斷除去共同后綴之后的長度為多少，再讓指針遍歷一遍鏈表，到相對應的位置之后讓其中一個指向另一個所指向的結點。（不考慮釋放另一邊所占用的空間）

（書里那個方法我想不到啊?q"o"q）

算法的基本設計思想：

1. 確定較長鏈表: 首先確定兩個鏈表中較長的一個，因為共同后綴不可能長于較短的鏈表。
2. 移動較短鏈表的指針: 將較短鏈表的指針移動到與較長鏈表相同長度的位置。
3. 同時遍歷: 從這個點開始，同時遍歷兩個鏈表，比較每個節點的值。
4. 找到共同后綴: 當兩個指針同時到達鏈表末尾或者發現不匹配的節點時，停止遍歷。如果到達末尾，說明找到了共同后綴；否則，記錄下不匹配時兩個鏈表的指針位置。

算法的詳細實現步驟：

1. 計算兩個鏈表的長度。
2. 使用較長鏈表的長度減去較短鏈表的長度，得到需要前進的步數。
3. 將較長鏈表的頭指針移動到倒數第k個節點，其中k為需要前進的步數。
4. 同時遍歷兩個鏈表，直到兩個指針都到達末尾或者發現不匹配的節點。
5. 如果兩個指針都到達末尾，返回較長鏈表的當前節點，即為共同后綴的起始位置。
6. 如果發現不匹配的節點，返回nullptr，表示沒有共同后綴。

// 定義鏈表節點結構
struct ListNode {int data;ListNode* next;ListNode(int val) : data(val), next(nullptr) {}
};// 計算鏈表長度
int getLength(ListNode* head) {int length = 0;ListNode* temp = head;while (temp != nullptr) {length++;temp = temp->next;}return length;
}// 找到共同后綴的起始位置
ListNode* findCommonSuffix(ListNode* str1, ListNode* str2) {int len1 = getLength(str1);int len2 = getLength(str2);// 確定較長的鏈表并移動指針ListNode* longer = (len1 > len2) ? str1 : str2;ListNode* shorter = (len1 > len2) ? str2 : str1;// 計算步數并移動較長鏈表的指針int steps = std::abs(len1 - len2);for (int i = 0; i < steps; ++i) {if (longer == nullptr) return nullptr; // 防止鏈表為空longer = longer->next;}// 同時遍歷兩個鏈表while (longer != nullptr && shorter != nullptr) {if (longer->data != shorter->data) {return nullptr; // 如果發現不匹配的節點，返回nullptr}longer = longer->next;shorter = shorter->next;}// 如果遍歷結束于鏈表末尾，返回共同后綴的起始位置if (longer == nullptr && shorter == nullptr) {return nullptr; // 兩個鏈表都到達末尾，表示沒有共同后綴}// 如果 shorter 先到達末尾，返回 longer 的當前節點return longer; // 此時 longer 指向共同后綴的起始位置
}

2013 順序表

分析：

最簡單的做法應該可能大概是直接rua個大數組（n范圍沒講，就只能盡量大咯）然后對這個整數數列進行掃描，將其值映射到大數組中的下標，然后大數組該對應下標的元素值加1（也就是遍歷一遍整數數列，用大數組統計這個整數數列的每個數都出現了多少次）最后如果大數組中元素最大的值未能大于長度的一般則輸出-1。

int MajorityElement(int A[], int n) {// 創建大小為 n 的統計數組并初始化為 0int *count = (int *)calloc(n, sizeof(int));// 遍歷整數序列，統計每個數的出現次數for (int i = 0; i < n; i++) {count[A[i]]++;}// 查找出現次數最多的元素int majorityElement = -1;int maxCount = 0;for (int i = 0; i < n; i++) {if (count[i] > maxCount) {maxCount = count[i];majorityElement = i;}}// 檢查是否為主元素if (maxCount > n / 2) {free(count); // 釋放內存return majorityElement;} else {free(count); // 釋放內存return -1; // 不存在主元素}
}

書里這個應該是一種特殊的算法蛤，沒必要背，了解即可。

int fMajorityElement(int A[], int n) {int candidate = -1; // 候選元素int count = 0;      // 計數器// 第一步：選取候選元素for (int i = 0; i < n; i++) {if (count == 0) {candidate = A[i]; // 更新候選元素count = 1;        // 重置計數器} else if (A[i] == candidate) {count++; // 候選元素的支持度加一} else {count--; // 其他元素的支持度減一}}// 第二步：驗證候選元素count = 0; // 重置計數器for (int i = 0; i < n; i++) {if (A[i] == candidate) {count++; // 統計候選元素出現的次數}}// 檢查候選元素是否為主元素if (count > n / 2) {return candidate; // 返回主元素} else {return -1; // 不存在主元素}
}

原理來自 Boyer-Moore 投票算法，它是一種高效的尋找主元素的算法。

1. 候選元素的選取：

   • 使用一個計數器來記錄當前候選元素的“支持度”。
   • 遍歷數組時，如果計數器為零，選擇當前元素作為新的候選元素，并將計數器設為1。
   • 如果當前元素與候選元素相同，增加計數器；如果不同，減少計數器。

2. 為什么有效：

   • 如果存在一個元素的出現次數超過?n/2，那么在遍歷過程中，該元素將始終保持為候選元素。
   • 計數器的增加和減少保證了在元素數量相等時，候選元素的優勢可以保持。

具體步驟：

1. 初始化：

   • 設置一個候選元素?candidate?和一個計數器?count，初始值為 0。

2. 遍歷數組：

   • 對于每個元素：
     • 如果?count?為 0，更新?candidate?為當前元素，并將?count?設置為 1。
     • 如果當前元素等于?candidate，則?count?加 1。
     • 如果當前元素不等于?candidate，則?count?減 1。

3. 驗證候選元素：

   • 遍歷數組，統計?candidate?的出現次數，確認是否超過?n/2。

2014 二叉樹（WPL）

1. 算法基本設計思想

帶權路徑長度（WPL）是二叉樹中所有葉結點的權值與其到根節點的路徑長度的乘積之和。為了計算 WPL，可以采用深度優先遍歷（DFS）的方法，遍歷樹的每一個節點：

• 對于每個節點，記錄當前深度。
• 當到達葉節點時，計算其帶權路徑長度?WPL+=weight×depth? WPL+=weight×depth

2. 二叉樹節點的數據類型定義

typedef struct BiNode {struct BiNode* left;   // 指向左子樹的指針struct BiNode* right;  // 指向右子樹的指針int weight;       // 節點的權值（僅在葉節點有效）
};

3. WPL 計算的 C++ 實現

以下是計算二叉樹 WPL 的算法實現：

//Way1：先序遍歷
int ans=0;
void func(BiTree root,int depth){if(root==NULL)    return;if(root->left==NULL&&root->right==NULL){ans+=root->weight*depth;}func(root->left,depth+1);func(root->right,depth+1);
}int WPL(Bitree root){func(root,0);return ans;
}

• 時間復雜度：O(n)，其中?nn?是樹中節點的數量，因為每個節點都被訪問一次。
• 空間復雜度：O(h)，其中?hh?是樹的高度，遞歸調用棧的深度。

這樣就完成了 WPL 的計算算法設計與實現！

//Way2：層次遍歷
int func(BiTree root, int depth) {queue<BiTNode*> q;  // 創建隊列用于層次遍歷int ans = 0, depth = 0;  // 初始化結果ans和當前深度depthif (root != NULL) q.push(root);  // 如果根節點不為空，則入隊while (!q.empty()) {  // 當隊列不為空時循環int n = q.size();  // 獲取當前隊列的大小，即當前層的節點數for (int i = 0; i < n; i++) {  // 遍歷當前層的所有節點BiTNode* node = q.front();  // 獲取隊列前端的節點q.pop();  // 彈出隊列前端的節點if (node->left != NULL) q.push(node->left);  // 如果左孩子不為空，則入隊if (node->right != NULL) q.push(node->right);  // 如果右孩子不為空，則入隊// 如果當前節點為葉子節點（沒有左右孩子）if (node->left == NULL && node->right == NULL) {ans += node->weight * depth;  // 累加葉子節點的權重乘以當前深度}}depth++;  // 每遍歷完一層，深度增加}return ans;  // 返回最終計算的結果
}

2015 單鏈表（雙指針）

分析：首先，依然還是單鏈表所以其上的指針只能一條路走到黑，那我們其實可以設置兩個指針一個走慢一點，走在快指針的后一步。那這樣是不是就可以實現找前驅的工作了。然后我們可以再設置一個遍歷指針，在快慢指針行進過程中的每一步都從慢指針開始向后遍歷。在找到絕對值相同的結點時，利用快慢指針實現刪除操作（快指針走一步，慢指針直接指向快指針）。這樣實現起來很簡單對吧，但是時間復雜度有點點高，需要O(n^2)

不對不對是保留第一次出現的，那就固定一個指針用于遍歷，該指針每遍歷一個結點就發出一對快慢指針用于刪除后續絕對值重復的結點。但是時間復雜度也依舊是O(n^2)。

那如果我先遍歷一遍單鏈表將其數據域的值都用一個cnt記錄出現次數（初始為-1，出現1次自動加1）然后最后再用兩個指針進行遍歷，遍歷的同時比對所存放的cnt值是否大于0（重復程度）。所有數據第一次遇到均不會刪除只會cnt-1，若后續重復遇到即可根據cnt的值來判斷之后要刪除幾個結點（也同樣是用快慢指針來實現刪除結點的操作），這時候時間復雜度應該為O(n^2)。

不對不對，我們可以一趟就完成這個事情，直接邊遍歷邊記錄。只需要利用數組在遍歷的同時記錄下鏈表中已經出現的數值，后續都先過一遍數組（但是又因為數組是可以隨機存儲的所以不影響）看看該值是否出現過，再碰到直接一刪除不就完了。

（書里給的也是這樣蛤，但是是直接申請空間來表示）

注：真是優雅

2016 快速排序

分析：它既要n1-n2的絕對值盡可能小，又要S1-S2的絕對值盡可能大，那不就是最好分成兩份差不多均等的，大的放右邊，小的放左邊嘛，那這是啥？不就是快排嘛

算法思路：

1. 初始化變量，low?和?high?用于標記數組的邊界，low0?和?high0?用于在劃分過程中保存邊界，k?為要找的第k小的元素的位置，s1?和?s2?分別用于存儲前k小和后n-k小的元素之和。
2. 使用while循環進行快速選擇算法的劃分過程，直到找到第k小的元素。
3. 在每次迭代中，選擇low位置的元素作為樞軸（pivot），然后移動low和high指針來劃分數組，使得左邊的元素都不大于樞軸，右邊的元素都不小于樞軸。
4. 如果樞軸元素恰好位于第k小的位置，結束劃分；否則，根據樞軸的位置調整low0和high0，然后繼續劃分。
5. 找到第k小的元素后，遍歷數組，計算前k小的元素之和與后n-k小的元素之和，返回它們的差值。

int setPartition(int a[], int n) {int pivotkey, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n / 2, i;int s1 = 0, s2 = 0;while (flag) {pivotkey = a[low];// 選擇樞軸while (low < high && a[high] >= pivotkey) --high;if (low != high) a[low] = a[high];while (low < high && a[low] <= pivotkey) ++low;if (low != high) a[high] = a[low];// 基于樞軸對數據進行劃分if (low == k - 1) {// 如果樞軸是第n/2小元素，劃分成功，flag=0;flag = 0;} else {// 是否繼續劃分if (low < k - 1) {low0 = ++low;high = high0;} else {high0 = --high;low = low0;}}}// 計算前k小的元素之和與后n-k小的元素之和for (i = 0; i < k; i++) s1 += a[i];for (i = k; i < n; i++) s2 += a[i];return s2 - s1;
}

時間復雜度：O(n)

空間復雜度：O(1)

2017 二叉樹（InOrder）

分析：要實現將給定的二叉樹轉換成為等價的中綴表達式并輸出，那其實我們只需要中序遍歷就好了，一邊遍歷一邊輸出，最后的結果自然就是該題想要我們實現的。任務就轉換成為對中序遍歷稍加改變一下咯。

還有還有為了保證輸出出來的中綴表達式有正確的運算順序，我們還應該在合適的位置添加括號。（遍歷左子樹之前加上，遍歷完右子樹之后也加上）

typedef struct node{char data[];          struct node *left, *right; 
}BTree;//BreeToTree(root,1); //調用該程序 void BreeToTree(BTree *root,int deep){if(root!=NULL){if(root->left=NULL&&root->right=NULL){printf("%s",root->data);	}else{if(deep>1) printf("(");	//遍歷左子樹之前 BreeToTree(root->left,deep+1);	//遞歸遍歷左子樹printf("%s",root->data);BreeToTree(root->right,deep+1);	//遞歸遍歷右子樹if(deep>1) printf(")");	//遍歷右子樹之后 }     }else{return;	//空結點直接返回 }
}

2018 順序表

分析：

????????先想想最容易實現的是什么呢？自然也還是可以設置一個輔助數組專門記錄其下標是否出現過，最后在從小到大第一個未被標記過的不就是我們想找的最小正整數嗎。

????????然后我們再看回要求，這題只要求時間上高效喔，那就是極致的空間換時間，快就完事了唄。上述思路的時間復雜度為O(n)嘞，那我們思考下有沒有什么是可以更快做出來的呢？是不是也可以直接先過一遍排序（但在這個過程中遇到負數就直接跳過）然后遍歷再找一遍是不是也出結果了（不過要是想穩定的話，剩下的幾個排序算法的時間復雜度也為O(n)）。

注：

書里所給出的和我第一次的想法一樣蛤。?

int findMissMin(int A[], int n) {int i;int *B; // 標記數組// 分配空間，使用malloc而不是錯誤的malocB = (int *)malloc(sizeof(int) * (n + 1)); // 需要為1到n的整數分配空間// 賦初值為0，注意memset的第二個參數應該是字節數memset(B, 0, sizeof(int) * (n + 1));// 遍歷數組A，如果A[i]在1到n之間，則標記B[A[i] - 1]為1for (i = 0; i < n; i++) {if (A[i] > 0 && A[i] <= n) {B[A[i]] = 1; // 直接使用A[i]作為索引，因為我們要標記1到n的整數}}// 掃描數組B，找到第一個值為0的位置，即未出現的最小正整數for (i = 1; i <= n; i++) { // 從1開始，因為0不是正整數if (B[i] == 0) {break;}}// 返回結果，i是數組B中第一個未標記的位置，即未出現的最小正整數return i;
}

int findMissin(std::vector<int>& nums) {int n = nums.size();// 將每個正整數放到對應的索引位置for (int i = 0; i < n; i++) {// 只處理在范圍內的正整數while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {// 交換到正確的位置std::swap(nums[i], nums[nums[i] - 1]);}}// 查找第一個缺失的正整數for (int i = 0; i < n; i++) {if (nums[i] != i + 1) {return i + 1; // 返回缺失的最小正整數}}return n + 1; // 如果所有位置都正確，返回n+1
}

注：第二種的空間復雜度會較低，但是題目也并未要求。

2019?單鏈表（雙指針）

【2019統考真題】設線性表L=（a1,a2,a3,...,an-1,an-1,an）采用帶頭結點的單鏈表保存，鏈
表中的結點定義如下：

typedef struct node
{    int data;struct node* next;
}NODE

請設計一個空間復雜度為O(1）且時間上盡可能高效的算法，重新排列L中的各結點，得到線性表L=（a1,an,a2,an-1,a3,an-2,...）要求：
1）給出算法的基本設計思想。
2）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋，
3）說明你所設計的算法的時間復雜度。

分析：這題有硬性要求咯，空間復雜度要為O(1）才行。那其實我們可以借助之前做的10年真題的想法，你看目的是不是要從頭和從屁股開始交替形成一個新的鏈表，那其實我們可以先找到中間（向下取整的那個結點）然后反轉后半段，再交替將其插入頭結點之后的鏈表就完事了。

void changeList(NODE* h) {NODE *p, *q, *r, *s;p = q = h; // 初始化慢指針和快指針// 尋找中間節點while (q->next != NULL) {p = p->next; // 慢指針走一步q = q->next; // 快指針走一步if (q->next != NULL) {q = q->next; // 快指針再走一步}}// p所指節點為中間節點，q為后半段鏈表的首節點NODE* secondHalf = p->next; // 保存后半段鏈表p->next = NULL; // 切斷前半段鏈表// 將鏈表后半段逆置NODE* prev = NULL;while (secondHalf != NULL) {r = secondHalf->next; // 保存下一個節點secondHalf->next = prev; // 反轉指針prev = secondHalf; // 移動前驅secondHalf = r; // 移動到下一個節點}// prev 現在指向反轉后的后半段鏈表的頭s = h->next; // s指向前半段的第一個數據節點q = prev; // q指向后半段的第一個數據節點// 將鏈表后半段的節點插入到指定位置while (q != NULL) {r = q->next; // r指向后半段的下一個節點q->next = s->next; // 將q插入到s之后s->next = q; // 更新s的next指向qs = q->next; // s指向前半段的下一個插入點q = r; // 移動到下一個節點}
}

時間復雜度：O(n)

該算法需要遍歷鏈表三次：一次找到中間節點，一次反轉后半部分，一次合并兩個鏈表。

2020 最短路徑（Floyd）or 雙指針

【2020統考真題】定義三元組（a，b，c）（abc均為整數）的距離D=|a-b|+b-c|+|c-a|。給定3個非空整數集合S1、S2和S3，按升序分別存儲在3個數組中。請設計一個盡可能高效的算法，計算并輸出所有可能的三元組（a，b，c)（a∈S1，b∈S2，c∈S3）中的最小距離。例如S1={-1，0，9}，S2={-25，-10，10，11}，S3={2，9，17，30，41}，則最小距離為2，相應的三元組（9，10，9）。

要求：
? 1）給出算法的基本設計思想。
? 2）根據設計思想，采用C語言或C++語言描述算法，關鍵之處給出注釋。
? 3）說明你所設計算法的時間復雜度和空間復雜度。

分析：既然一沒要求時間二沒要求空間，那我們直接上暴力！！！

第一層循環遍歷S1，然后第二層是S2，第三層是S3（由外向內）然后再來個tempmin，暴力枚舉出所有的可能性，再隨著循環遍歷依次比較當前最小，直至結束選出最優解。

// 計算三個數組S1、S2和S3中元素之間的最小距離
int min_dist(int S1[], int S2[], int S3[]) {// 用于存儲產生最小距離的路徑int path[3];// 初始化路徑數組memset(path, 0, sizeof(path));// 計算數組S1的長度int l1 = sizeof(S1) / sizeof(*S1);// 計算數組S2的長度int l2 = sizeof(S2) / sizeof(*S2);// 計算數組S3的長度int l3 = sizeof(S3) / sizeof(*S3);// 初始化最小距離為一個很大的數int md = 0x3FFF; // 使用十六進制表示一個很大的數// 遍歷數組S1for (int i = 0; i < l1; i++) {// 遍歷數組S2for (int j = 0; j < l2; j++) {// 遍歷數組S3for (int k = 0; k < l3; k++) {// 計算當前路徑的總距離int td = std::abs(S1[i] - S2[j]) + std::abs(S2[j] - S3[k]) + std::abs(S3[k] - S1[i]);// 如果當前路徑的總距離小于已知的最小距離，則更新最小距離和路徑if (td < md) {md = td;path[0] = S1[i];path[1] = S2[j];path[2] = S3[k];}}}}// 輸出產生最小距離的路徑for (int i : path) {std::cout << i << std::endl;}// 返回最小距離return md;
}

更優解：暴力解法在集合大小較大時效率較低。一個可能的優化方法是使用雙指針技巧，首先固定一個集合中的元素，然后在另外兩個集合中使用雙指針來尋找最小距離。這種方法可以減少一些不必要的計算，但仍然需要O(n1 * n2 + n2 * n3 + n3 * n1)的時間復雜度。如果S1、S2和S3中的元素都是有序的，那么雙指針方法可以更有效地找到最小距離。（書里那個例圖其實畫的很清楚蛤）

int findMinDistance(const std::vector<int>& S1, const std::vector<int>& S2, const std::vector<int>& S3) {int minDist = std::numeric_limits<int>::max(); // 初始化最小距離為最大值int n1 = S1.size(), n2 = S2.size(), n3 = S3.size();// 遍歷S1中的每個元素for (int a : S1) {int i = 0, j = 0; // 初始化指針// 雙指針遍歷S2和S3while (i < n2 && j < n3) {int b = S2[i];int c = S3[j];// 計算當前三元組的距離int dist = std::abs(a - b) + std::abs(b - c) + std::abs(c - a);minDist = std::min(minDist, dist); // 更新最小距離// 移動指針，尋找更優解if (b < c) {i++; // b較小，向右移動S2的指針} else {j++; // c較小或相等，向右移動S3的指針}}}return minDist;
}

注：該算法的思維還是很重要的，很多場合都可以用得到。?

2021 圖（鄰接矩陣）

1）算法的基本設計思想

本算法題屬于送分題，題干已經告訴我們算法的思想。對于采用鄰接矩陣存儲的無向圖，在鄰接矩陣的每一行（列）中，非零元素的個數為本行（列）對應頂點的度。可以依次計算連通圖G中各頂點的度，并記錄度為奇數的頂點個數，若個數為0或2，則返回1，否則返回0。

2）算法實現

int IsExistEL(MGraph G)(//采用鄰接矩陣存儲，判斷圖是否存在EL路徑int degree, i, j, count=0;for(i=0;i<G. numVertices;i++){degree=0;for(int j=0;j<G.numVertices;j++){degree+=G.Edge[i][j];    //依次計算各個頂點的度 if(degree%2!=0)    count++;    //對度為奇數的頂點計數1}if(count==0||count==2)    return 1;    //存在EL路徑，返回1else    return 0;    //不存在EL路徑，返回0}
}    

3）時間復雜度和空間復雜度

算法需要遍歷整個鄰接矩陣，所以時間復雜度是O（n^2），空間復雜度是O（1）。

2022 二叉樹（BST）

?【2022統考真題】已知非空二叉樹T的結點值均為正整數，采用順序存儲方式保存，數據結構定義如下：?

分析：都說是二叉排序樹了嘛，那我就只需要在遍歷過程中看一下是否有不滿足定義（左邊大于中間或者右邊小于中間）的結點就好啦。那其實是不是也可以直接中序遍歷完看序列是不是遞增的就好啦。

// 檢查數組是否表示一個二叉搜索樹
int IsBST(int* SqBiTNode, int size) {int* pmax = (int*)malloc(size * sizeof(int));int* pmin = (int*)malloc(size * sizeof(int));if (!pmax || !pmin) {free(pmax);free(pmin);return 0;}// 初始化pmax和pmin數組for (int i = 0; i < size; i++) {int iLeft = 2 * i + 1;int iRight = 2 * i + 2;if (iLeft < size) pmax[i] = SqBiTNode[iLeft];if (iRight < size) pmin[i] = SqBiTNode[iRight];if (iLeft < size && SqBiTNode[i] <= pmax[iLeft]) return 0;if (iRight < size && SqBiTNode[i] >= pmin[iRight]) return 0;}free(pmax);free(pmin);return 1; // 所有節點都滿足BST的條件
}

// 檢查數組是否表示一個二叉搜索樹
int IsBST(int* SqBiTNode, int size) {int val = INT_MIN; // 初始化為最小整數for (int i = 0; i < size; i++) {if (SqBiTNode[i] <= val) return 0; // 如果當前節點值小于等于val，則不是BSTval = SqBiTNode[i]; // 更新val為當前節點值}return 1; // 中序遍歷得到的序列是升序的，因此是BST
}

2023 圖（鄰接矩陣）

(1）算法思想：

• 遍歷有向圖中所有頂點，并統計各頂點的出度和入度，輸出出度大于入度的KJ頁點，并使用變量 count 累計頂點的總數。
• 計算頂點i的出度: 遍歷鄰接矩陣的i行元素，即 Edge[i][0]~Edge[i][numVertex-1]，統計非零元素個數，即為頂點i的出度
• 計算頂點i的入度：遍歷鄰接矩陣的i列元素，即Edge[0][i]~ Edge[numVertex-1][i]，統計非零元素個數，即為頂點i的入度

(2)算法實現：

int printVertices (MGraph G){int count =0;//K頂點的總數for (int i=0; i<G.numVertex; i++){int outDegree = 0;//頂點i的出度int inDegree = 0;//頂點i的入度for (int j=0;j<G.numVertex; j++)if (G.Edge[i][j]>0)  outDegree++;}for (int j=0;j<G.numVertex; j++)if (G.Edge[j][i]>0)  outDegree++;//循環兩次方便理解}if (outDegree > inDegree) [//頂點i的出度大于入度printf ("c\n"，G.VertexList[i]);//輸出頂點icount++;//累加K頂點總數}}return count;//返回x頂點總數
}

2024 圖（鄰接矩陣）and 拓撲排序

41.已知有向圖G采用鄰接矩陣存儲，類型定義如下

typedef struct{    //圖的類型定義int numVertices,numEdges;    //圖的頂點數和有向邊數char VerticesList[MAXV];    //頂點表，MAXV為已定義常量int Edge[MAXV][MAXV];    //鄰接矩陣
}MGraph;

請設計算法：int uniquely(MGraph G)，判定G是否存在唯一的拓撲序列，若是，則返回1，否則返回0，要求如下：

1）給出算法的基本設計思想。

2）根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。

分析：因為給的是鄰接矩陣，那就是要求咱考慮一下怎么著才能根據鄰接矩陣的特性找到唯一的拓撲排序咯。首先我們想下拓撲排序是咋出來的呢，是不是找那個沒有人管的結點（入度為0的），然后將其輸出，重復這個過程。如果能夠全部輸出就表明存在拓撲排序。那很自然就順到要找入度為0的點了對吧，鄰接矩陣找入度為0還不簡單嗎，就拿一個數組專門存起來唄。然后再考慮一下這其中的細節問題就是當我輸出一個點的時候，相鄰結點的入度得減1，這個就是根據鄰接矩陣的特性我看看aij存不存在咯，存在就證明有邊嘛。那如何保證其唯一性呢？就是在同一時刻不允許出現兩個入度為0的結點。

基本思路：

• 創建一張入度表indegree[]用于記錄各個頂點的入度情況
• 選擇入度為0的點并將所有鄰接結點的入度-1（借助鄰接矩陣實現）
• 重復以上過程，若每次選中的入度為0的頂點有且僅有一個且全部遍歷完，則存在唯一的拓撲排序；反之不存在或存在多個拓撲排序。

// 聲明入度數組并分配內存
int *indegree;
indegree = (int *)malloc(G.numVertices * sizeof(int)); // 為入度數組分配內存// 初始化入度數組
for (int j = 0; j < G.numVertices; j++) {indegree[j] = 0; // 將每個頂點的入度初始化為0// 計算每個頂點的入度for (int i = 0; i < G.numVertices; i++) {indegree[j] += G.Edge[i][j]; // 累加所有指向頂點j的邊的數量}
}// 拓撲排序相關變量
int count = 0; // 已處理頂點的計數
int zero_count, zero_vertex; // 用于存儲入度為0的頂點數量和其索引while (count < G.numVertices) { // 當已處理的頂點數量小于總頂點數量時zero_count = 0; // 重置入度為0的頂點計數zero_vertex = -1; // 初始化入度為0的頂點索引// 尋找入度為0的頂點for (int j = 0; j < G.numVertices; j++) {if (indegree[j] == 0) { // 如果頂點j的入度為0zero_count++; // 增加入度為0的頂點計數zero_vertex = j; // 記錄該頂點的索引if (zero_count > 1) break; // 如果找到多個入度為0的頂點，退出循環}}// 如果有多個或沒有入度為0的節點if (zero_count != 1) { // 如果入度為0的頂點數量不等于1free(indegree); // 釋放內存return 0; // 返回錯誤碼，表示拓撲排序失敗}// 移除找到的入度為0的頂點，并更新相鄰節點的入度count++; // 增加已處理頂點的計數indegree[zero_vertex] = -1; // 標記該頂點為已處理for (int j = 0; j < G.numVertices; j++) {if (G.Edge[zero_vertex][j] > 0) { // 如果存在從zero_vertex到j的邊indegree[j]--; // 更新相鄰頂點j的入度}}
}