算法工程师笔试 -剑指offer-习题详细解答
生活随笔
收集整理的這篇文章主要介紹了
算法工程师笔试 -剑指offer-习题详细解答
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
說明
- 主要編程語言為 C/C++
- 涉及字符串的問題可能會使用 Python
- 題目編號以原書為準，如“面試題 3：數組中重復的數字”
- 因為題目不多，所以就不做分類了
- 所有代碼均通過 OJ 測試
在線 OJ 地址：劍指Offer_編程題 - 牛客網
Reference
- 《劍指 Offer（第二版）》 - 何海濤
- Interview-Notebook/劍指 offer 題解.md · CyC2018/Interview-Notebook
- 牛客網相關問題討論區
3.1 數組中重復的數字
數組中重復的數字 - NowCoder
題目描述
在一個長度為 n 的數組里的所有數字都在 0 到 n-1 的范圍內。 數組中某些數字是重復的，但不知道有幾個數字是重復的，也不知道每個數字重復幾次。 請找出數組中任意一個重復的數字。- 要求：時間復雜度O(N)，空間復雜度O(1)
- 示例Input: {2, 3, 1, 0, 2, 5}Output: 2
思路
- 復雜度要求表明不能使用排序，也不能使用 map/set
- 注意到 n 個數字的范圍為 0 到 n-1，考慮類似選擇排序的思路，通過一次遍歷將每個數交換到排序后的位置，如果該位置已經存在相同的數字，那么該數就是重復的
- 示例position-0 : (2,3,1,0,2,5) // 2 <-> 1(1,3,2,0,2,5) // 1 <-> 3(3,1,2,0,2,5) // 3 <-> 0(0,1,2,3,2,5) // already in position position-1 : (0,1,2,3,2,5) // already in position position-2 : (0,1,2,3,2,5) // already in position position-3 : (0,1,2,3,2,5) // already in position position-4 : (0,1,2,3,2,5) // nums[i] == nums[nums[i]], exit
Code
class Solution { public:bool duplicate(int numbers[], int length, int* duplication) {if(numbers == nullptr || length <= 0)return false;for(int i = 0; i < length; ++i) {while(numbers[i] != i) {if(numbers[i] == numbers[numbers[i]]) {*duplication = numbers[i];return true;}// 交換numbers[i]和numbers[numbers[i]]swap(numbers[i], numbers[numbers[i]]);}}return false;} };3.2 不修改數組找出重復的數字
題目描述
在一個長度為n+1的數組里的所有數字都在1到n的范圍內，所以數組中至少有一個數字是重復的。 請找出數組中任意一個重復的數字，但不能修改輸入的數組。 例如，如果輸入長度為8的數組{2, 3, 5, 4, 3, 2, 6, 7}，那么對應的輸出是重復的數字2或者3。- 要求：時間復雜度O(NlogN)，空間復雜度O(1)
思路
- 二分查找
- 以長度為 8 的數組 {2, 3, 5, 4, 3, 2, 6, 7} 為例，那么所有數字都在 1~7 的范圍內。中間的數字 4 將 1~7 分為 1~4 和 5~7。統計 1~4 內數字的出現次數，它們一共出現了 5 次，說明 1~4 內必要重復的數字；反之，若小于等于 4 次，則說明 5~7 內必有重復的數字。
- 因為不能使用額外的空間，所以每次統計次數都要重新遍歷整個數組一次
Code
int countRange(const int* numbers, int length, int start, int end);int getDuplication(const int* numbers, int length) {if(numbers == nullptr || length <= 0)return -1;int start = 1;int end = length - 1;while(end >= start) {int middle = ((end - start) >> 1) + start;int count = countRange(numbers, length, start, middle);if(end == start) {if(count > 1)return start;elsebreak;}if(count > (middle - start + 1))end = middle;elsestart = middle + 1;}return -1; }// 因為不能使用額外的空間，所以每次統計次數都要重新遍歷整個數組一次 int countRange(const int* numbers, int length, int start, int end) {if(numbers == nullptr)return 0;int count = 0;for(int i = 0; i < length; i++)if(numbers[i] >= start && numbers[i] <= end)++count;return count; }4. 二維數組中的查找
二維數組中的查找 - NowCoder
題目描述
在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。- 示例Consider the following matrix: [[1, 4, 7, 11, 15],[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30] ]Given target = 5, return true. Given target = 20, return false.
思路
- 從左下角開始查找，它左邊的數都比它小，下邊的數都比它大；因此可以根據 target 和當前元素的大小關系來縮小查找區間
- 同理，也可以從右上角開始查找
- 時間復雜度：O(M + N)
Code
class Solution { public:bool Find(int target, vector<vector<int> > array) {int N = array.size(); // 行數int M = array[0].size(); // 列數int i = N - 1;int j = 0;while (i >= 0 && j < M) {if (array[i][j] > target)i--;else if (array[i][j] < target)j++;elsereturn true;}return false;} };5. 替換空格
替換空格 - NowCoder
題目描述
請實現一個函數，將一個字符串中的空格替換成“%20”。 例如，當字符串為 "We Are Happy". 則經過替換之后的字符串為 "We%20Are%20Happy"。思路
- 先遍歷一次，找出空格的數量，得到替換后的長度；然后從后往前替換
Code
class Solution { public:void replaceSpace(char *str, int length) {if (str == nullptr || length < 0)return;int l_old = strlen(str); // == lengthint n_space = count(str, str + l_old, ' '); // <algorithm>int l_new = l_old + n_space * 2;str[l_new] = '\0';int p_old = l_old-1;int p_new = l_new-1;while (p_old >= 0) {if (str[p_old] != ' ') {str[p_new--] = str[p_old--];}else {p_old--;str[p_new--] = '0';str[p_new--] = '2';str[p_new--] = '%';}}} };6. 從尾到頭打印鏈表
從尾到頭打印鏈表 - NowCoder
題目描述
輸入鏈表的第一個節點，從尾到頭反過來打印出每個結點的值。思路
- 棧
- 頭插法
Code
class Solution { public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> ret;ListNode *p = head;while (p != NULL) {ret.insert(ret.begin(), p->val); // 頭插p = p->next;}return ret;} };7. 重建二叉樹
重建二叉樹 - NowCoder
題目描述
根據二叉樹的前序遍歷和中序遍歷的結果，重建出該二叉樹。 假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。思路
- 涉及二叉樹的問題，應該條件反射般的使用遞歸（無優化要求時）
- 前序遍歷的第一個值為根節點的值，使用這個值將中序遍歷結果分成兩部分，左部分為左子樹的中序遍歷結果，右部分為右子樹的中序遍歷的結果。
Code - 無優化
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} };class Solution { public:TreeNode * reConstructBinaryTree(vector<int> pre, vector<int> vin) {if (pre.size() <= 0)return NULL;TreeNode* root = new TreeNode{ pre[0] };for (auto i = 0; i < vin.size(); i++) {if (vin[i] == pre[0]) {root->left = reConstructBinaryTree(vector<int>(pre.begin() + 1, pre.begin() + 1 + i), vector<int>(vin.begin(), vin.begin() + i));root->right = reConstructBinaryTree(vector<int>(pre.begin() + 1 + i, pre.end()), vector<int>(vin.begin() + 1 + i, vin.end()));}}return root;} };Code - 優化
class Solution { public:TreeNode * reConstructBinaryTree(vector<int> pre, vector<int> vin) {return reConstructCore(pre, 0, pre.size(), vin, 0, vin.size());}TreeNode * reConstructCore(vector<int> &pre, int pre_beg, int pre_end, vector<int> &vin, int vin_beg, int vin_end) {if (pre_end - pre_beg <= 0)return NULL;TreeNode* root = new TreeNode{ pre[pre_beg] };for (auto i = 0; i < vin_end-vin_beg; i++) {if (vin[i+vin_beg] == pre[pre_beg]) {root->left = reConstructCore(pre, pre_beg+1, pre_beg+1+i, vin, vin_beg, vin_beg+i);root->right = reConstructCore(pre, pre_beg+1+i, pre_end, vin, vin_beg+1+i, vin_end);}}return root;} };8. 二叉樹的下一個結點
二叉樹的下一個結點 - NowCoder
題目描述
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且返回。 注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。思路
- 回顧中序遍歷的順序
- 如果一個節點的右子樹不為空，那么下一個節點是該節點右子樹的最左葉子；
- 否則（右子樹為空），沿父節點向上直到找到某個節點是其父節點的左孩子，那么該父節點就是下一個節點
Code
struct TreeLinkNode {int val;struct TreeLinkNode *left;struct TreeLinkNode *right;struct TreeLinkNode *next;TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {} };class Solution { public:TreeLinkNode * GetNext(TreeLinkNode* pNode) {if (pNode == nullptr)return nullptr;if(pNode->right != nullptr) {auto p = pNode->right;while(p->left != nullptr)p = p->left;return p;}else {auto p = pNode; // 當前節點while(p->next != nullptr) { // 當前節點的父節點不為空if (p->next->left == p) // 當前節點是其父節點的左海子return p->next; // 那么下一個節點就是當前節點的父節點p = p->next;}}return nullptr; // 當前節點是根節點且沒有右孩子，即沒有下一個節點} };9. 用兩個棧實現隊列
用兩個棧實現隊列 - NowCoder
題目描述
用兩個棧來實現一個隊列，完成隊列的 Push 和 Pop 操作。思路
- 假設 stack_in 用于處理入棧操作，stack_out用于處理出棧操作
- stack_in 按棧的方式正常處理入棧數據；
- 關鍵在于出棧操作
- 當stack_out為空時，需要先將每個stack_in中的數據出棧后壓入stack_out
- 反之，每次彈出stack_out棧頂元素即可
Code
class Solution { public:void push(int node) {stack_in.push(node);}int pop() {if(stack_out.size() <= 0) {while (stack_in.size() > 0) {auto tmp = stack_in.top();stack_in.pop();stack_out.push(tmp);}}auto ret = stack_out.top();stack_out.pop();return ret;}private:stack<int> stack_in;stack<int> stack_out; };10.1 斐波那契數列
斐波那契數列 - NowCoder
題目描述
寫一個函數，輸入n，求斐波那契（Fibonacci）數列的第n項。 數列的前兩項為 0 和 1思路
- 遞歸
- 遞歸可能會重復計算子問題——例如，計算 f(10) 需要計算 f(9) 和 f(8)，計算 f(9) 需要計算 f(8) 和 f(7)，可以看到 f(8) 被重復計算了
- 可以利用額外空間將計算過的子問題存起來
- 查表
- 因為只需要前 40 項，所以可以先將值都求出來
Code - 遞歸
// 該代碼會因復雜度過大無法通過評測 class Solution { public:int Fibonacci(int n) {if(n <= 0)return 0;if(n == 1)return 1;return Fibonacci(n - 1) + Fibonacci(n - 2);} };Code - 循環
class Solution { public:int Fibonacci(int n) {int f = 0;int g = 1;while (n--) {g = g + f;f = g - f;}return f;} };Code - 查表
class Solution { public:Solution(){fib = new int[40];fib[0] = 0;fib[1] = 1;for (int i = 2; i < 40; i++)fib[i] = fib[i - 1] + fib[i - 2];}int Fibonacci(int n) {return fib[n];}private:int* fib; };10.2 跳臺階（遞歸）
跳臺階 | 變態跳臺階 - NowCoder
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。 求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果）。思路
- 遞歸
- 記跳 n 級臺階有 f(n) 種方法
- 如果第一次跳 1 級，那么之后的 n-1 級有 f(n-1) 種跳法
- 如果第一次跳 2 級，那么之后的 n-2 級有 f(n-2) 種跳法
- 實際上就是首兩項為 1 和 2 的斐波那契數列
Code
10.3 變態跳臺階（動態規劃）
變態跳臺階 - NowCoder
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。 求該青蛙跳上一個n級的臺階總共有多少種跳法。思路
- 動態規劃
- 遞推公式f(1) = 1 f(n) = 1 + f(1) + .. + f(n-1)
Code - DP
class Solution { public:int jumpFloorII(int number) {vector<int> dp(number+1, 1);for (int i=2; i<=number; i++)for(int j=1; j<i; j++)dp[i] += dp[j];return dp[number];} };Code - 空間優化
class Solution { public:int jumpFloorII(int number) {int f = 1;int sum = 1 + f;for (int i = 2; i <= number; i++) {f = sum;sum += f;}return f;} };10.4 矩形覆蓋（動態規劃）
矩形覆蓋 - NowCoder
題目描述
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。 請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？思路
- 動態規劃
- 遞推公式f(1) = 1 f(2) = 2 f(n) = f(n-1) + f(n-2)
- 即前兩項為 1 和 2 的斐波那契數列
Code
class Solution { public:int rectCover(int number) {if (number == 0)return 0;int f = 1;int g = 2;for (int i = 2; i <= number; i++) {g = g + f;f = g - f;}return f;} };11. 旋轉數組的最小數字（二分查找）
旋轉數組的最小數字 - NowCoder
題目描述
把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組 {3, 4, 5, 1, 2} 為 {1, 2, 3, 4, 5} 的一個旋轉，該數組的最小值為 1。 NOTE：給出的所有元素都大于 0，若數組大小為 0，請返回 0。思路
- 二分查找
- 二分查找需要有一個目標值 target，這里的 target 可以選 nums[hi] 或 nums[lo]，這里使用過的是 nums[hi]
- 注意有重復的情況，特別是 {3, 4, 5, 1, 2, 3}，這里有一個簡單的處理方法
Code
class Solution { public:int minNumberInRotateArray(vector<int> rotateArray) {if (rotateArray.empty())return 0;int lo = 0;int hi = rotateArray.size() - 1;// 完全旋轉，或者說沒有旋轉（不需要）//if (rotateArray[lo] < rotateArray[hi])// return rotateArray[lo];while (lo + 1 < hi) {int mid = lo + (hi - lo) / 2;if (rotateArray[mid] > rotateArray[hi])lo = mid;else if (rotateArray[mid] < rotateArray[hi])hi = mid;elsehi--; // 防止這種情況 {3,4,5,1,2,3}}return rotateArray[hi];} };12. 矩陣中的路徑（DFS）
矩陣中的路徑 - NowCoder
題目描述
請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子。- 例如下面的矩陣包含了一條 bfce 路徑。
思路
- 深度優先搜索（DFS）
- 注意邊界判斷
Code
class Solution { public:bool hasPath(char* matrix, int rows, int cols, char* str) {bool *visited = new bool[rows * cols]{false};for (int i=0; i<rows; i++) {for (int j=0; j<cols; j++) {if (dfs(matrix, rows, cols, str, visited, i, j, 0))return true;}}return false;}bool dfs(char* matrix, int rows, int cols, char* str, bool* visited, int i, int j, int step) { // l 為當前已找到的長度// 結果存在if(step == strlen(str))return true;// 邊界條件if(i<0 || i>=rows || j<0 || j>cols || matrix[i*cols+j]!=str[step] || visited[i*cols+j])return false;// 定義 4 個方向；int next[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 最好的做法是作為成員變量，但是 C++ 成員變量的初始化比較麻煩，// 而且這還是個二維數組，更麻煩，所以每次都重新定義一次，所幸不大visited[i*cols+j] = true; // 訪問標記for (auto k : next)if (dfs(matrix, rows, cols, str, visited, i+k[0], j+k[1], step+1))return true;visited[i*cols+j] = false; // 清除訪問標記return false;} };13. 機器人的運動范圍（DFS） TODO
機器人的運動范圍 - NowCoder
題目描述
地上有一個 m 行和 n 列的方格。 一個機器人從坐標 (0, 0) 的格子開始移動，每一次只能向左右上下四個方向移動一格， 但是不能進入行坐標和列坐標的數位之和大于 k 的格子。例如，當 k 為 18 時，機器人能夠進入方格（35, 37），因為 3+5+3+7=18。 但是，它不能進入方格（35, 38），因為 3+5+3+8=19。請問該機器人能夠達到多少個格子？思路
- 深度優先搜索（DFS）
- 注意邊界條件判斷
Code
14. 剪繩子（動態規劃 | 貪心）
整數拆分 - LeetCode
題目描述
把一根長度為 n 的繩子剪成 m 段，并且使得每段的長度的乘積最大（n, m 均為整數）。思路
- 動態規劃
-
遞推公式
f(n) = 0 n = 1 f(n) = 1 n = 2 f(n) = 2 n = 3 f(n) = max{dp(i) * dp(n-i)} n > 3, 1<=i<=n-1 -
注意：當 n <= 3 時因為必須剪至少一次的緣故，導致 f(1)=0, f(2)=1*1=1, f(3)=1*2=2；但是當 n>=4 時，將n<=3的部分單獨作為一段能提供更大的乘積
因此，初始化時應該 dp[1]=1≠f(1), dp[2]=2≠f(2), dp[3]=3≠f(3)，同時將 f(1), f(2), f(3) 單獨返回
-
時間復雜度：O(N^2)，空間復雜度：O(N)
-
- 貪心
- 當 n>=5 時，盡可能多剪長度為 3 的繩子；當 n=4 時，剪成兩段長度為 2 的繩子
- 證明當 n >= 5 時，可以證明： 3(n-3) > 2(n-2) > n 當 n == 4 時，2*2 > 3*1
- 時間復雜度：O(1)，空間復雜度：O(1)
Code - 動態規劃
class Solution { public:int integerBreak(int n) {if(n < 2) return 0;if(n == 2) return 1;if(n == 3) return 2;int dp[n+1]{0}; // 記得初始化為 0dp[1] = 1;dp[2] = 2;dp[3] = 3;for (int i=4; i<=n; i++) {for (int j=1; j<=i/2; j++) {int p = dp[j] * dp[i-j];if (dp[i] < p)dp[i] = p;}}return dp[n];}};Code - 貪心
class Solution { public:int integerBreak(int n) {if(n < 2) return 0;if(n == 2) return 1;if(n == 3) return 2;int n3 = n / 3; // 切成 3 的數量if (n%3 == 1) // 如果余下的長度為 4n3--;int n2 = (n - 3*n3) / 2; // 切成 2 的數量return (int)pow(3, n3) * (int)pow(2, n2);} };15. 二進制中 1 的個數（位運算）
二進制中1的個數 - NowCoder
題目描述
輸入一個整數，輸出該數二進制表示中1的個數。 其中負數用補碼表示。思路
- 位運算 - 移位計數
- 時間復雜度：O(N)，N 為整型的二進制長度
- 注意移位判斷有兩種方式：一是移動 n，一是移動"1"，后者更好
- 當 n 為 負數時，移動 n 可能導致死循環
- 位運算 - 利用 n&(n-1)
- 該運算的效果是每次除去 n 的二進制表示中最后一個 1n : 10110100 n-1 : 10110011 n&(n-1) : 10110000
- 時間復雜度：O(M)，M 為二進制中 1 的個數
Code - 移位計數
class Solution { public:int NumberOf1(int n) {int ret = 0;int N = sizeof(int) * 8;while(N--) {if(n & 1)ret++;n >>= 1;}return ret;} };Code - 移位計數（改進）
class Solution { public:int NumberOf1(int n) {int ret = 0;int N = sizeof(int) * 8;int flag = 1;while(N--) {if(n & flag)ret++;flag <<= 1; // 移動 1 而不是 n}return ret;} };Code - n&(n-1)
class Solution { public:int NumberOf1(int n) {int ret = 0;while(n) {ret++;n = (n-1)&n;}return ret;} };16. 數值的整數次方（位運算）
數值的整數次方 - NowCoder
題目描述
給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。思路
-
位運算 - 快速冪
-
示例
求 `3^20 = 9^10 = 81^5 (= 81*81^4) = 81*6561^2 = 81*43046721` 循環次數 = `bin(20)`的位數 = `len(10100)` = 5 -
時間復雜度 O(logN)
Code
class Solution { public:double Power(double base, int exponent) {int p = abs(exponent);double ret = 1.0;while (p != 0) {if (p & 1) // 如果是奇數ret *= base;base *= base;p >>= 1;}return exponent < 0 ? 1 / ret : ret;} };17. 打印從 1 到最大的 n 位數（字符串 + DFS）
題目描述
輸入數字 n，按順序打印出從 1 到最大的 n 位十進制數。 比如輸入 3，則打印出 1、2、3 一直到最大的 3 位數即 999。思路
- 由于 n 可能會非常大，因此不能直接用 int 表示數字，包括 long, long long
- 正確的做法是用 char 數組進行存儲。
- 由于使用 char 存儲數字，那么就不適合使用普通的運算操作了，此時可以使用 DFS 來獲取所有的數字
Code
void printOneToMax(int n) {if (n <= 0) return;char* number = new char[n + 1];number[n] = '\0';dfs(number, n, 0); // DFSdelete[] number; }void dfs(char* number, int length, int index) {if (index == length) { // 遞歸最重要的就是結束條件要正確PrintNumber(number);return;}for (int i = 0; i < 10; ++i) {number[index] = i + '0';dfs(number, length, index + 1);} }// 打印出這個數字，忽略開頭的 0 void PrintNumber(char* number) {bool isBeginning0 = true;int nLength = strlen(number);for (int i = 0; i < nLength; ++i) {if (isBeginning0 && number[i] != '0')isBeginning0 = false;if (!isBeginning0) {printf("%c", number[i]);}}printf("\t"); }18.1 在 O(1) 時間內刪除鏈表節點（鏈表）
題目描述
給定單向鏈表的頭指針和需要刪除的指針，定義一個函數在 O(1) 時間內刪除該節點 前提：該節點在鏈表中思路
-
因為不能遍歷，所以只能通過修改節點的值來實現這個操作
-
簡單來說，就是將該節點的值修改為其下一個節點的值，實際上刪除的是該節點的下一個節點（題目的描述可能會帶來誤導）
-
如果該節點不是尾節點，那么按上述操作即可——時間的復雜度為 O(1)
-
如果該節點是尾節點，此時必須通過遍歷來找到該節點的前一個節點，才能完成刪除——時間復雜度為 O(N)
-
如果是 C++，一定要注意 delete 指針指向的內存后，必須將指針重新指向 nullptr
delete p; p = nullptr; -
總的時間復雜度：[(n-1)O(1) + O(n)] / n = O(1)
Code
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted) {if(!pListHead || !pToBeDeleted)return;if(pToBeDeleted->next != nullptr) { // 要刪除的結點不是尾結點ListNode* p = pToBeDeleted->next;pToBeDeleted->val = p->val;pToBeDeleted->next = p->next;delete p; // delete 指針指向的內存后，必須將指針重新指向 nullptrp = nullptr; }else if(*pListHead == pToBeDeleted) { // 鏈表只有一個結點，刪除頭結點delete pToBeDeleted;pToBeDeleted = nullptr; *pListHead = nullptr;}else { // 鏈表中有多個結點，刪除尾結點ListNode* p = *pListHead;while(p->next != pToBeDeleted)p = p->next; p->next = nullptr;delete pToBeDeleted;pToBeDeleted = nullptr;} }18.2 刪除鏈表中重復的結點（鏈表）
刪除鏈表中重復的結點 - NowCoder
題目描述
在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點； 重復的結點不保留，返回鏈表頭指針。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5思路
- 注意重復的節點不保留，所以要特別注意頭結點也重復的情況——最好的做法是新設一個頭結點
- delete 指針指向的內存后，必須將指針重新指向 nullptr
Code
class Solution { public:ListNode * deleteDuplication(ListNode* pHead){ if (pHead == NULL) return pHead;ListNode* head = new ListNode{-1}; // 設置一個頭結點head->next = pHead;ListNode* pre = head;ListNode* cur = pHead;while (cur != NULL && cur->next != NULL) {if (cur->val != cur->next->val) { // 不重復時向后遍歷pre = cur;cur = cur->next;}else { // 發現重復int val = cur->val;while (cur != NULL && cur->val == val) { // 循環刪除重復auto tmp = cur;cur = cur->next;delete tmp; // delete + nullptrtmp = nullptr;}pre->next = cur;}}auto ret = head->next;delete head; // delete + nullptrhead = nullptr;return ret;} };19. 正則表達式匹配（自動機：動態規劃 | DFS）
正則表達式匹配 - NowCoder
題目描述
請實現一個函數用來匹配包括'.'和'*'的正則表達式。 模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。 例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配，但是與"aa.a"和"ab*a"均不匹配思路
- ‘.’ 用于當做一個任意字符，’*’ 用于重復前面的字符，注意兩者區別
- 下面提供 dfs(C++) 和 dp(Java) 兩種做法
Code - dfs
class Solution { public:bool match(char* str, char* pattern) {if(str==NULL||pattern==NULL)return false;return dfs(str,pattern);}bool dfs(char* str, char* pattern) {if(*str=='\0'&&*pattern=='\0')return true;if(*str!='\0'&&*pattern=='\0')return false;if(*(pattern+1)=='*') {if(*pattern==*str||(*pattern=='.'&&*str!='\0'))/*dfs(str,pattern+2): 模式串不匹配dfs(str+1,pattern): 模式串已經匹配成功，嘗試匹配下一個字符串dfs(str+1,pat+2)： 模式串已經成功匹配，并且不匹配下一個字符串內容 */return dfs(str+1,pattern)||dfs(str,pattern+2);elsereturn dfs(str,pattern+2);}if(*str==*pattern||(*pattern=='.'&&*str!='\0'))return dfs(str+1,pattern+1);return false;} };Code - dp
public boolean match(char[] str, char[] pattern) {int m = str.length, n = pattern.length;boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;for (int i = 1; i <= n; i++)if (pattern[i - 1] == '*')dp[0][i] = dp[0][i - 2];for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')dp[i][j] = dp[i - 1][j - 1];else if (pattern[j - 1] == '*')if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {dp[i][j] |= dp[i][j - 1]; // a* counts as single adp[i][j] |= dp[i - 1][j]; // a* counts as multiple adp[i][j] |= dp[i][j - 2]; // a* counts as empty} elsedp[i][j] = dp[i][j - 2]; // a* only counts as emptyreturn dp[m][n]; }20. 表示數值的字符串（自動機 | 正則）
表示數值的字符串 - NowCoder
題目描述
請實現一個函數用來判斷字符串是否表示數值（包括整數和小數）。 例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。思路
- if 判斷 - 自動機
- 正則表達式
Code - 自動機
class Solution { public:// 數字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，其中A和C都是// 整數（可以有正負號，也可以沒有），而B是一個無符號整數bool isNumeric(const char* str) {if(str == nullptr)return false;bool numeric = scanInteger(&str);// 如果出現'.'，接下來是數字的小數部分if(*str == '.') {++str;// 下面一行代碼用||的原因：// 1. 小數可以沒有整數部分，例如.123等于0.123；// 2. 小數點后面可以沒有數字，例如233.等于233.0；// 3. 當然小數點前面和后面可以有數字，例如233.666numeric = scanUnsignedInteger(&str) || numeric;}// 如果出現'e'或者'E'，接下來跟著的是數字的指數部分if(*str == 'e' || *str == 'E') {++str;// 下面一行代碼用&&的原因：// 1. 當e或E前面沒有數字時，整個字符串不能表示數字，例如.e1、e1；// 2. 當e或E后面沒有整數時，整個字符串不能表示數字，例如12e、12e+5.4numeric = numeric && scanInteger(&str);}return numeric && *str == '\0';}bool scanUnsignedInteger(const char** str) {const char* before = *str;while(**str != '\0' && **str >= '0' && **str <= '9')++(*str);// 當str中存在若干0-9的數字時，返回truereturn *str > before;}// 整數的格式可以用[+|-]B表示, 其中B為無符號整數bool scanInteger(const char** str) {if(**str == '+' || **str == '-')++(*str);return scanUnsignedInteger(str);} };Code - 正則（Python）
import re class Solution:# s字符串def isNumeric(self, s):# Python 中完全匹配需要以 ^ 開頭，以 $ 結尾# r"" 表示不轉義# if re.match("^[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?$", s):if re.match(r"^[+-]?\d*(\.\d+)?([eE][+-]?\d+)?$", s):return Trueelse:return FalseCode - 正則（C++）
#include <regex>class Solution { public:bool isNumeric(char* string) {regex reg("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");return regex_match(string, reg);} };Code - 正則（Java）
public class Solution {public boolean isNumeric(char[] str) {if (str == null)return false;return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");} }21. 調整數組順序使奇數位于偶數前面（數組）
調整數組順序使奇數位于偶數前面 - NowCoder
題目描述
輸入一個整數數組，實現一個函數來調整該數組中數字的順序， 使得所有的奇數位于數組的前半部分，所有的偶數位于數組的后半部分， 并保證奇數和奇數，偶數和偶數之間的相對位置不變。- 要求：空間復雜度 O(1)
- 本題與原書不同，這里要求相對順序不變，原書的側重點在于函數指針
思路
- 如果可以使用額外空間，那么問題就很簡單
- 如果不想使用額外空間，那么只能通過循環移位來達到避免覆蓋的目的，時間復雜度 O(N^2)
- 可以利用“冒泡排序”的思想避免循環位移
Code - 使用額外空間
class Solution { public:void reOrderArray(vector<int> &array) {vector<int> odd; // 存奇數vector<int> eve; // 存偶數for (auto i : array) {if (i & 1) // 是奇數odd.push_back(i);elseeve.push_back(i);}array.swap(odd);array.insert(array.end(), eve.begin(), eve.end());} };Code - 不使用額外空間
討論區第二個回答
class Solution { public:void reOrderArray(vector<int> &array) {for(int i = 0; i < array.size() / 2; i++)for(int j = 0; j < array.size()-i; j++)if((array[j]%2 == 0) && (array[j+1]%2 == 1))swap(array[j] ,array[j+1]);} };22. 鏈表中倒數第 K 個結點（鏈表 + 雙指針）
鏈表中倒數第k個結點 - NowCoder
題目描述
輸入一個鏈表，輸出該鏈表中倒數第k個結點。思路
- 設置快慢指針快指針先走 k-1 步，然后慢指針開始走，當快指針到達鏈表尾時，慢指針即指向倒數第 k 個節點
- 健壯性檢驗：
- 輸入是一個空鏈表
- 鏈表長度小于 k
Code
class Solution { public:ListNode * FindKthToTail(ListNode* pListHead, unsigned int k) {if(pListHead == nullptr)return nullptr;ListNode * slow = pListHead;ListNode * fast = pListHead;//先讓 fast 走 k-1 步while (k && fast) {fast = fast->next;k--;}// 如果 k > 0，說明 k 大于鏈表長度if (k > 0)return nullptr;// 接著讓兩個指針一起往后走，當 fast 到最后時，slow 即指向倒數第 k 個while (fast) {fast = fast->next;slow = slow->next;}return slow;} };23. 鏈表中環的入口結點（鏈表 + 雙指針）
鏈表中環的入口結點 - NowCoder
題目描述
給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null。- 要求：不使用額外空間
思路
-
快慢雙指針
-
快指針 fast 每次移動 2 步，慢指針 slow 每次 1 步；因為存在環，fast 和 slow 總會相遇，此時 fast 剛好比 slow 多走一圈（？）
-
如圖，假設他們相遇在 z1 點，此時將 fast/slow 之一重新指向頭結點，繼續每次一步移動，它們再次相遇的點就是入口
Code
class Solution { public:ListNode * EntryNodeOfLoop(ListNode* pHead) {if (pHead == NULL) return nullptr;ListNode* slow = pHead;ListNode* fast = pHead;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) { // 找到環中相遇點slow = pHead; // 將 fast/slow 中的任一個重新指向頭指針while (slow != fast) { // 直到他們再次相遇，相遇的這個點就是入口slow = slow->next;fast = fast->next;}return slow;}}return nullptr;} };24. 反轉鏈表（鏈表）
反轉鏈表 - NowCoder
題目描述
輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。- 要求：不使用額外空間
思路
- 可以輔助圖示思考
Code - 迭代
class Solution { public:ListNode * ReverseList(ListNode* pHead) {if (pHead == NULL)return NULL;ListNode* cur = pHead;ListNode* pre = NULL;ListNode* nxt = cur->next;cur->next = NULL; // 斷開當前節點及下一個節點while (nxt) {pre = cur;cur = nxt;nxt = nxt->next;cur->next = pre;}return cur;} };Code - 遞歸
class Solution { public:ListNode * ReverseList(ListNode* pHead) {if (pHead == nullptr || pHead->next == nullptr)return pHead;auto nxt = pHead->next;pHead->next = nullptr; // 斷開當前節點及下一個節點auto newHead = ReverseList(nxt);nxt->next = pHead;return newHead;} };25. 合并兩個排序的鏈表（鏈表）
合并兩個排序的鏈表 - NowCoder
題目描述
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。Code - 迭代
class Solution { public:ListNode * Merge(ListNode* pHead1, ListNode* pHead2) {ListNode head{-1};ListNode *cur = &head;while (pHead1 && pHead2) {if (pHead1->val <= pHead2->val) {cur->next = pHead1;pHead1 = pHead1->next;} else {cur->next = pHead2;pHead2 = pHead2->next;}cur = cur->next;}if (pHead1) cur->next = pHead1;if (pHead2) cur->next = pHead2;return head.next;} };Code - 遞歸
class Solution { public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if (!pHead1) return pHead2;if (!pHead2) return pHead1;if(pHead1->val <= pHead2->val){pHead1->next = Merge(pHead1->next, pHead2);return pHead1;} else {pHead2->next = Merge(pHead1, pHead2->next);return pHead2;}} };26. 樹的子結構（二叉樹）
樹的子結構 -NowCoder
題目描述
輸入兩棵二叉樹A，B，判斷B是不是A的子結構。 約定空樹不是任意一個樹的子結構。- 圖示
思路
- 遞歸
- 有兩個遞歸的點：一、遞歸尋找與子樹根節點相同的點；二、遞歸判斷子結構是否相同
Code
class Solution { public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (pRoot2 == NULL || pRoot1 == NULL)return false;// 遞歸尋找與子樹根節點相同的點return isSubTree(pRoot1, pRoot2)|| HasSubtree(pRoot1->left, pRoot2)|| HasSubtree(pRoot1->right, pRoot2);}bool isSubTree(TreeNode* pRoot1, TreeNode* pRoot2) {if (pRoot2 == NULL) return true;if (pRoot1 == NULL) return false;// 遞歸判斷子結構是否相同if (pRoot1->val == pRoot2->val)return isSubTree(pRoot1->left, pRoot2->left)&& isSubTree(pRoot1->right, pRoot2->right);elsereturn false;} };27. 二叉樹的鏡像（二叉樹）
二叉樹的鏡像 - NowCoder
題目描述
操作給定的二叉樹，將其變換為源二叉樹的鏡像。- 圖示
思路
- 前序遍歷，每次交換節點的左右子樹；即必須先交換節點的左右子樹后，才能繼續遍歷
Code
class Solution { public:void Mirror(TreeNode *pRoot) {if (pRoot == nullptr) return;auto tmp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = tmp;Mirror(pRoot->left);Mirror(pRoot->right);} };28 對稱的二叉樹（二叉樹）
對稱的二叉樹 NowCoder
題目描述
請實現一個函數，用來判斷一顆二叉樹是不是對稱的。 注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。 空樹也認為是對稱的思路
- 遞歸
- 同時遍歷左子樹和右子樹，然后是“左子樹的左子樹和右子樹的右子樹”，及左子樹的右子樹和右子樹的左子樹，遞歸以上步驟
Code
class Solution { public:bool isSymmetrical(TreeNode* pRoot) {if (pRoot == nullptr) return true;return dfs(pRoot->left, pRoot->right);}bool dfs(TreeNode* l, TreeNode* r) {if (l == nullptr && r == nullptr)return true;if (l == nullptr || r == nullptr) // 注意這個條件return false;if (l->val == r->val)return dfs(l->left, r->right)&& dfs(l->right, r->left);elsereturn false;} };29. 順時針打印矩陣（二維數組）
順時針打印矩陣 - NowCoder
題目描述
下圖的矩陣順時針打印結果為：1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10-
圖示
-
注意，不是蛇形打印，而是一層一層順時針打印
思路
- 二維數組遍歷
Code
class Solution { public:vector<int> printMatrix(vector<vector<int> > matrix) {vector<int> ret;int rl = 0, rr = matrix.size()-1;int cl = 0, cr = matrix[0].size()-1;while(rl <= rr && cl <= cr) {for (int i = cl; i <= cr; i++)ret.push_back(matrix[rl][i]);for (int i = rl+1; i <= rr; i++)ret.push_back(matrix[i][cr]);if (rl != rr)for (int i = cr - 1; i >= cl; i--)ret.push_back(matrix[rr][i]);if (cl != cr)for (int i = rr - 1; i > rl; i--)ret.push_back(matrix[i][cl]);rl++; rr--; cl++; cr--;}return ret;} };30. 包含 min 函數的棧（數據結構：棧）
包含min函數的棧 - NowCoder
題目描述
定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數- 要求：時間復雜度 O(1)
思路
- 因為要求在常數時間內完成所有操作，所以不能有排序操作
- 使用一個輔助棧保存最小、次小、…
Code
class Solution {stack<int> s;stack<int> s_min;public:void push(int value) {s.push(value);if (s_min.empty())s_min.push(value);if (value <= s_min.top()) // 注意是小于等于s_min.push(value);}void pop() {if (s.top() == s_min.top())s_min.pop();s.pop();}int top() {return s.top();}int min() {return s_min.top();}};31. 棧的壓入、彈出序列（數據結構：棧）
棧的壓入、彈出序列 -NowCoder
題目描述
輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。 假設壓入棧的所有數字均不相等。 例如序列 1,2,3,4,5 是某棧的壓入順序，序列 4,5,3,2,1 是該壓棧序列對應的一個彈出序列， 但 4,3,5,1,2 就不可能是該壓棧序列的彈出序列。思路
- 使用一個輔助棧
- 依次將入棧序列入棧，如果棧頂元素等于出棧序列的棧頂元素，則彈出
- 當流程無法繼續時，如果輔助棧是空的，則出棧序列是符合的
Code
class Solution { public:bool IsPopOrder(vector<int> pushV, vector<int> popV) {if (pushV.empty()) return false;stack<int> tmp;int j = 0;for (int i = 0; i < pushV.size(); i++) {tmp.push(pushV[i]);while (!tmp.empty() && tmp.top() == popV[j]) {tmp.pop();j++;}}return tmp.empty();} };32.1 從上往下打印二叉樹（BFS）
從上往下打印二叉樹 - NowCoder
題目描述
從上往下打印出二叉樹的每個節點，同層節點從左至右打印。 例如，以下二叉樹層次遍歷的結果為：1,2,3,4,5,6,7- 圖示
思路
- 廣度優先搜索 + 隊列
- 注意入隊時先左子節點，后右節點
- 注意不需要修改原二叉樹
Code
class Solution {queue<TreeNode*> q; // 輔助隊列 public:vector<int> PrintFromTopToBottom(TreeNode* root) {if (root == nullptr) return vector<int>();q.push(root);vector<int> ret;while (!q.empty()) {auto cur = q.front();q.pop();ret.push_back(cur->val);if (cur->left != nullptr)q.push(cur->left);if (cur->right != nullptr)q.push(cur->right);}return ret;} };32.2 分行從上到下打印二叉樹（BFS）
把二叉樹打印成多行 - NowCoder
題目描述
從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。思路
- 除了利用隊列和 BFS
- 為了分行輸出，還需要兩個變量：一個表示在當前層中還沒有打印的節點數、一個表示下一層的節點數
- 注意根節點為空的情況
Code
class Solution {queue<TreeNode*> q; public:vector<vector<int>> Print(TreeNode* pRoot) {if (pRoot == nullptr) return vector<vector<int>>();q.push(pRoot);int curL = 1; // 當前層的節點數，初始化為 1，根節點int nxtL = 0; // 下一層的節點數vector<vector<int>> ret;vector<int> tmp;while (!q.empty()) {auto node = q.front();q.pop();curL--;tmp.push_back(node->val);if (node->left != nullptr) {q.push(node->left);nxtL++;}if (node->right != nullptr) {q.push(node->right);nxtL++;}if (curL == 0) {ret.push_back(tmp);tmp.clear();curL = nxtL;nxtL = 0;}}return ret;} };32.3 按之字形順序打印二叉樹（BFS）
按之字形順序打印二叉樹 - NowCoder
題目描述
請實現一個函數按照之字形打印二叉樹， 即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印， 第三行按照從左到右的順序打印，其他行以此類推。思路
Code - 兩個棧
class Solution { public:vector<vector<int>> Print(TreeNode* pRoot) {if(pRoot == nullptr)return vector<vector<int>>();// 定義兩個棧，s[0] 始終存放偶數層的節點，s[1] 始終存放奇數層的節點stack<TreeNode*> s[2];int cur = 0; // 當前層（假設根節點所在的第0層是偶數層）s[cur & 1].push(pRoot); // 第 0 層入棧vector<vector<int>> ret;vector<int> tmp;while(!s[0].empty() || !s[1].empty()) {auto pNode = s[cur & 1].top();s[cur & 1].pop();tmp.push_back(pNode->val);if(cur & 1) { // 當前是奇數層// 下一層是偶數層// 先壓右節點if(pNode->right != nullptr)s[0].push(pNode->right);if(pNode->left != nullptr)s[0].push(pNode->left);}else {// 下一層是奇數層，壓入 s1// 先壓左節點if(pNode->left != nullptr)s[1].push(pNode->left);if(pNode->right != nullptr)s[1].push(pNode->right);}if(s[cur & 1].empty()) {ret.push_back(tmp);tmp.clear();cur++; // 累計層數}}return ret;} };Code - 層反轉
class Solution {queue<TreeNode*> q; public:vector<vector<int>> Print(TreeNode* pRoot) {if (pRoot == nullptr) return vector<vector<int>>();q.push(pRoot);int cur = 0; // 當前層int curL = 1; // 當前層的節點數，初始化為 1，根節點int nxtL = 0; // 下一層的節點數vector<vector<int>> ret;vector<int> tmp;while (!q.empty()) {auto node = q.front();q.pop();curL--;tmp.push_back(node->val);if (node->left != nullptr) {q.push(node->left);nxtL++;}if (node->right != nullptr) {q.push(node->right);nxtL++;}if (curL == 0) {if (cur & 1) // 如果是奇數層，就反轉中間結果reverse(tmp.begin(), tmp.end());cur++;ret.push_back(tmp);tmp.clear();curL = nxtL;nxtL = 0;}}return ret;} };33. 二叉搜索樹的后序遍歷序列（二叉樹：遞歸）
二叉搜索樹的后序遍歷序列 - NowCoder
題目描述
輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。 如果是則輸出Yes，否則輸出No。假設輸入的數組的任意兩個數字都互不相同。思路
- 二叉搜索樹：左子樹都小于根節點，右子樹都大于根節點，遞歸定義
- 后序遍歷：會先輸出整個左子樹，再輸出右子樹，最后根節點；也就是說，數組可以被劃分為三個部分
- 示例：1,2,3 | 5,6,7 | 4 第一部分都小于最后的元素，第二部分都大于最后的元素——雖然這不是一顆二叉搜索樹，但是它滿足第一次判斷的結果，后序再遞歸判斷左右子樹
Code
class Solution { public:bool VerifySquenceOfBST(vector<int> s) {if (s.empty()) return false;return dfs(s, 0, s.size()-1);}bool dfs(vector<int> &s, int l, int r) {if (l >= r) return true;int base = s[r]; // 根節點int mid = 0; // 尋找第一個大于根節點的元素for (; mid < r; mid++)if (s[mid] > base)break;bool flag = true; // 如果第一個大于根節點的元素到根節點之間的元素都大于根節點for (int i = mid; i<r; i++)if (s[i] < base) {flag = false;break;}return flag && dfs(s, l, mid-1) && dfs(s, mid, r-1); // 遞歸判斷} };34. 二叉樹中和為某一值的路徑（DFS）
二叉樹中和為某一值的路徑 - NowCoder
題目描述
輸入一顆二叉樹的跟節點和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。 路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。 (注意: 在返回值的list中，數組長度大的數組靠前)思路
- 注意，必須要從根節點到葉子節點，才叫一條路徑，中間結果都不算路徑
Code
class Solution { public:vector<vector<int>> ret;vector<int> trace;vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {if (root != nullptr)dfs(root, expectNumber);return ret;}void dfs(TreeNode* cur, int n) {trace.push_back(cur->val);// 結束條件if (cur->left == nullptr && cur->right == nullptr) {if (cur->val == n)ret.push_back(trace); // C++ 默認深拷貝}if (cur->left)dfs(cur->left, n - cur->val); // 這里沒有求和，而是用遞減的方式if (cur->right)dfs(cur->right, n - cur->val);trace.pop_back();} };35. 復雜鏈表的復制（鏈表）
復雜鏈表的復制 - NowCoder
題目描述
輸入一個復雜鏈表—— 每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點， 返回結果為復制后鏈表的頭節點。 （注意，輸出結果中請不要返回參數中的節點引用，否則判題程序會直接返回空）- 要求：時間復雜度 O(N)
思路
- 基本思路 O(N^2)
- 第一步，依次復制每個節點
- 第二步，對每個節點，尋找特殊指針指向的節點；因為特殊指針的位置不定，必須從頭開始找
- 假設經過 m 步找到了某個節點的特殊節點，那么在新鏈表中也走 m 步
- 問題的難點在于不知道特殊指針所指的節點在新鏈表中位置
- 一個經典的方法：
- 第一步，復制每個節點，如：原來是 A->B->C 變成 A->A'->B->B'->C->C'；
- 第二步，遍歷鏈表，使：A'->random = A->random->next；
- 第三步，拆分鏈表
Code
class Solution { public:RandomListNode * Clone(RandomListNode* pHead) {if (!pHead) return NULL;RandomListNode *cur = pHead;// 1. 復制每個節點，如：原來是A->B->C 變成A->A'->B->B'->C->C'while (cur) {RandomListNode* node = new RandomListNode(cur->label);node->next = cur->next; // 注意順序cur->next = node;cur = node->next;}// 2. 遍歷鏈表，使：A'->random = A->random->next;cur = pHead;RandomListNode* tmp;while (cur) {tmp = cur->next;if (cur->random != nullptr) {tmp->random = cur->random->next;}cur = cur->next->next; // 跳過復制的節點}// 3. 拆分鏈表cur = pHead;RandomListNode* ret = cur->next;while (cur->next) {tmp = cur->next;cur->next = tmp->next;cur = tmp;}return ret;} };36. 二叉搜索樹與雙向鏈表（DFS）
二叉搜索樹與雙向鏈表 - NowCoder
題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。 要求不能創建任何新的結點，只能調整樹中結點指針的指向。思路
- 因為要求是有序鏈表，因此考慮中序遍歷
- 利用兩個額外的指針保存前一個節點和頭結點，具體見代碼中注釋
Code
class Solution { public:TreeNode * pre; // 記錄上一個節點TreeNode * ret; // 雙向鏈表的頭結點TreeNode * Convert(TreeNode* pRootOfTree) {// C++ 小坑，不能在類類初始化，默認初始化不為 NULLpre = nullptr;ret = nullptr;dfs(pRootOfTree);return ret;}// 中序遍歷void dfs(TreeNode* node) {if (node == nullptr) return;dfs(node->left);if (ret == nullptr) // 到達最左葉子，即鏈表頭；只會執行一次ret = node;// 第一次執行該語句時，pre == nullptr；這并不矛盾。// 因為頭節點的前一個指針就是指向 nullptr 的node->left = pre;if (pre != nullptr)pre->right = node;pre = node;dfs(node->right);} };37. 序列化二叉樹（DFS）***
序列化二叉樹 - NowCoder
題目描述
請實現兩個函數，分別用來序列化和反序列化二叉樹。 接口如下：char* Serialize(TreeNode *root);TreeNode* Deserialize(char *str);- 比如中序遍歷就是一個二叉樹序列化
- 反序列化要求能夠通過序列化的結果還原二叉樹
- 空節點用 ‘#’ 表示，節點之間用空格分開
思路
- 一般在做樹的遍歷時，會以非空葉子節點作為最底層，此時還原二叉樹必須要前序遍歷+中序遍歷或后序遍歷
- 如果以空節點作為樹的最底層，那么只需要前序遍歷就能還原二叉樹，而且能與反序列化同步進行（這是最關鍵的一點）
Code
class Solution {// 因為接口限制，所以需要使用了兩個 ssstringstream ss;stringstream sd;char ret[1024];//char* ret;void dfs_s(TreeNode *node) {if (node == nullptr) {ss << "#";return;}ss << node->val;ss << " ";dfs_s(node->left);ss << " ";dfs_s(node->right);}TreeNode* dfs_d() {if (sd.eof())return nullptr;string val; // 只能用 string 接收，用 int 或 char 都會有問題sd >> val;if (val == "#")return nullptr;TreeNode* node = new TreeNode{ stoi(val) }; // node->left = dfs_d();node->right = dfs_d();return node;}public:char* Serialize(TreeNode *root) {dfs_s(root);// 這里耗了很久// return (char*)ss.str().c_str(); // 會出問題，原因未知return strcpy(ret, ss.str().c_str());}TreeNode* Deserialize(char *str) {if (strlen(str) < 1) return nullptr;sd << str;return dfs_d();} };38. 字符串的排列（DFS）
字符串的排列 - NowCoder
排列組合專題 TODO
題目描述
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。 例如輸入字符串 abc, 則打印出由字符 a,b,c 所能排列出來的所有字符串 abc, acb, bac, bca, cab 和 cba。思路
- 深度優先搜索
Code
class Solution {string s;string tmp;int strlen;vector<string> ret;vector<int> used;void dfs(int step) {if (step == strlen) {ret.push_back(tmp);return;}for (int i = 0; i<strlen; i++) {if (used[i]) continue;if (i > 0 && s[i] == s[i-1] && !used[i-1])continue;tmp[step] = s[i];used[i] = 1;dfs(step + 1);used[i] = 0;}}public:vector<string> Permutation(string str) {if (str.empty()) return vector<string>();// 當做全局變量s = str;strlen = s.length();sort(s.begin(), s.end()); // 因為可能存在重復，所以需要先排序，將重復的字符集合在一起// 初始化tmp.resize(strlen, '\0');used.resize(strlen, 0);dfs(0);return ret;} };39.1 數組中出現次數超過一半的數字（多數投票問題）
數組中出現次數超過一半的數字 - NowCoder
題目描述
數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。 例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。 由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。 如果不存在則輸出0。- 要求：時間復雜度 O(N)，空間復雜度 O(1)
思路
- 設置一個計數器 cnt 和保存最多元素的變量 majority
- 如果 cnt==0，則將 majority 設為當前元素
- 如果 majority 和當前元素值相同，則 cnt++，反之 cnt--
- 重復以上兩步，直到掃描完數組
- cnt 賦值為 0，再次掃描數組，如果數組元素與 majority 相同，cnt++
- 如果掃描結束后，cnt > nums.size() / 2，則返回 majority，否則返回 0。
Code
class Solution {int cnt;int majority; public:int MoreThanHalfNum_Solution(vector<int> nums) {if (nums.empty()) return 0;cnt = 0;for (int i=0; i<nums.size(); i++) {if (cnt == 0)majority = nums[i];if (nums[i] == majority)cnt++;elsecnt--;}cnt = 0;for (auto i : nums) {if (i == majority)cnt++;}return cnt > nums.size()/2 ? majority : 0;} };40. 找出數組中第 k 大的數字（數據結構：堆）***
數組中的第K個最大元素 - LeetCode
最小的K個數 - NowCoder
海量數據 Top K 專題 TODO
題目描述
找出數組中第 k 大的數/前 k 大的數/第 k 個最大的數- 正序找第 k 大的元素和逆序找第 k 大的元素方法是一致的；牛客是前者，LeetCode 是后者
- 可以改變原數組
- 要求：時間復雜度 O(N)，空間復雜度 O(1)
- 不可以改變原數組
- 要求：時間復雜度 O(NlogK)，空間復雜度 O(K)
- 實際上，找出數組中出現次數超過一半的數字可以看做是找出數組中第 n/2 大的數字
思路
- 可以改變原數組時：
- 參考快速排序中的 partition([pɑ:?t??n]) 過程
- 經過一次 partition 后，數組被 pivot 分成左右兩部分：l 和 r。
- 當 |l| = k-1 時，pivot 即是所找的第 k 大的數；
- 當 |l| < k-1，所找的數位于 r 中；
- 當 |l| > k-1，所找的數位于 l 中.
- 不可以改變原數組
- 使用額外空間 - 優先隊列（堆）或 multiset
Code - 優先隊列（無優化 O(NlogN)）（牛客）
class Solution {vector<int> ret; public:vector<int> GetLeastNumbers_Solution(vector<int>& nums, int k) {// 注意越界條件if (nums.empty() || k <= 0 || k > nums.size()) return vector<int>();if (k == nums.size())return vector<int>(nums);// 構造最小堆，注意：priority_queue 默認是最小堆 priority_queue<int, vector<int>, greater<int>> p;for (auto i : nums) // 缺點，需要完全放入數組，如果是從 100000 個中找前 2 個p.push(i);while (k--) {ret.push_back(p.top());p.pop();}return ret;} };Code - 優先隊列（優化 O(NlogK)）（牛客）
class Solution {vector<int> ret; public:vector<int> GetLeastNumbers_Solution(vector<int> &nums, int k) {// 注意越界條件if (nums.empty() || k <= 0 || k > nums.size()) return vector<int>();if (k == nums.size())return vector<int>(nums);// 注意使用堆與無優化的方法不同，這里要使用最大堆priority_queue<int> p;// 先把前 K 個數壓入int i = 0;for (; i < k; i++)p.push(nums[i]);// 判斷后面的數for (; i < nums.size(); i++) {if (nums[i] < p.top()) {p.pop();p.push(nums[i]);}}// 導出結果while (!p.empty()) {ret.push_back(p.top());p.pop();}return ret;} };Code - 可以改變數組（牛客）
class Solution {int partition(vector<int> &nums, int lo, int hi) {// 隨機選擇切分元素// srand(time(0));int base = rand() % (hi - lo + 1) + lo; // 隨機選擇 pivotswap(nums[base], nums[hi]); // 把 pivot 交換到末尾auto& pivot = nums[hi]; // 注意是引用int i = lo, j = hi; // j = hi-1; // errwhile (i < j) {while (nums[i] <= pivot && i < j) // 這里是求正序i++;while (nums[j] >= pivot && i < j) j--;if (i < j)swap(nums[i], nums[j]);}swap(nums[i], pivot);return i;} public:vector<int> GetLeastNumbers_Solution(vector<int> &nums, int k) {// 注意越界條件if (nums.empty() || k <= 0 || k > nums.size()) return vector<int>();if (k == nums.size())return vector<int>(nums);int lo = 0, hi = nums.size() - 1;int index = partition(nums, lo, hi);while(index != k-1) {if (index > k-1) {hi = index - 1;index = partition(nums, lo, hi);} else {lo = index + 1;index = partition(nums, lo, hi);}}return vector<int>(nums.begin(), nums.begin() + k);} };Code - 第 k 個最大的數（LeetCode）
class Solution {int partition(vector<int>& nums, int lo, int hi) {int base = rand() % (hi - lo + 1) + lo; // 隨機選擇 pivotswap(nums[base], nums[hi]); // 把 pivot 交換到末尾auto& pivot = nums[hi]; // 注意是引用int i = lo, j = hi; // j = hi-1; // errwhile (i < j) {while (nums[i] >= pivot && i < j) // 這里是求逆序i++;while (nums[j] <= pivot && i < j)j--;if (i < j)swap(nums[i], nums[j]);}swap(nums[i], pivot);return i;}public:int findKthLargest(vector<int>& nums, int k) {if (nums.empty() || k < 0) return 0;int lo = 0;int hi = nums.size() - 1;int index = partition(nums, lo, hi);while (index != k - 1) {if (index > k - 1) {hi = index - 1;index = partition(nums, lo, hi);}else {lo = index + 1;index = partition(nums, lo, hi);}}return nums[k - 1];} };41. 數據流中的中位數（數據結構：堆）
數據流中的中位數 - NowCoder
題目描述
如何得到一個數據流中的中位數？ 如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。 如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。 我們使用Insert()方法讀取數據流，使用GetMedian()方法獲取當前讀取數據的中位數。思路
- 使用平衡二叉樹 AVL
- 不推薦，因為一般沒有哪個語言會實現這個結構，它的綜合性能不如紅黑樹
- 使用兩個堆：一個最大堆，一個最小堆
- 保持兩個堆的大小平衡
Code - 使用*_heap系列函數
class Solution {// 用優先隊列會更方便，這里試試使用 C++ 的 *_heap() 系列函數vector<int> left; // 最大堆vector<int> right; // 最小堆，最小堆中的元素都大于最大堆中的元素int N; // 記錄讀入的元素數 public:Solution(): N(0) {} // 這一步不用也沒關系，默認會初始化為 0void Insert(int num) {N++; // 從 1 開始計數if (N & 1) { // 通過奇偶確保兩個堆中的元素數是平衡的// 如果是第奇數個就加入到 right// 為了保證 right 永遠大于 left，正確的添加方法是，// 先加入到 left，然后彈出 left 的堆頂元素加入到 rightleft.push_back(num);push_heap(left.begin(), left.end()); // push 后要重新調整堆，默認是最大堆num = left[0]; // 保存堆頂元素pop_heap(left.begin(), left.end()); // 在 pop 前，需要將堆頂元素移到末尾left.pop_back();right.push_back(num);push_heap(right.begin(), right.end(), greater<int>()); // 調整到最小堆，需要加入仿函數} else {// 如果是第偶數個就加入到左邊right.push_back(num);push_heap(right.begin(), right.end(), greater<int>());num = right[0];pop_heap(right.begin(), right.end(), greater<int>());right.pop_back();left.push_back(num);push_heap(left.begin(), left.end());}}double GetMedian() { if (N & 1) { // 如果是奇數，那么中位數就是 right 的堆頂return (double)right[0];} else {return (double)(left[0] + right[0]) / 2;}} };Code - 使用優先隊列
class Solution {priority_queue<int> left; // 最大堆priority_queue<int, vector<int>, greater<int>> right; // 最小堆，最小堆中的元素都大于最大堆中的元素int N; // 記錄讀入的元素數 public:Solution(): N(0) {} // 這一步不用也沒關系，默認會初始化為 0void Insert(int num) {N++; // 從 1 開始計數if(N & 1) { // 通過奇偶確保兩個堆中的元素數是平衡的// 如果是第奇數個就加入到 right// 為了保證 right 永遠大于 left，正確的添加方法是，// 先加入到 left，然后彈出 left 的堆頂元素加入到 rightleft.push(num);num = left.top();left.pop();right.push(num);} else { // 如果是第偶數個就加入到左邊right.push(num);num = right.top();right.pop();left.push(num);}}double GetMedian() { if (N & 1) { // 如果是奇數，那么中位數就是 right 的堆頂return (double)right.top();} else {return (double)(left.top() + right.top()) / 2;}} };42. 連續子數組的最大和
連續子數組的最大和 - NowCoder
題目描述
{6,-3,-2,7,-15,1,2,2}，連續子數組的最大和為 8（從第 0 個開始，到第 3 個為止）思路
- 因為不需要輸出路徑，所以不需要 DP
- 法1）暴力枚舉-兩層循環
- 法2）實際上，只要遍歷一次即可，首先用一個變量保存當前的最大值
- 如果當前和 sum 為負數，那么直接舍棄，用下一個值作為當前和
- 否則，加上下一個值（無論正負）
- 與當前最大值比較，保留最大的
Code - 法1
class Solution { public:int FindGreatestSumOfSubArray(vector<int>& array) {int _max = array[0]; // 存在全為負數的情況// 最安全的作法是賦值為數組的第一個數for (int i = 0; i < array.size(); i++) {int _sum = 0;for (int j = i; j < array.size(); j++) {_sum += array[j];_max = max(_max, _sum);}}return _max;} };Code - 法2
class Solution { public:int FindGreatestSumOfSubArray(vector<int>& array) {if (array.empty()) return int();if (array.size() == 1) return array[0];int _max = array[0]; // 存在全為負數的情況// 最安全的作法是賦值為數組的第一個數int _sum = array[0];for (int i = 1; i < array.size(); i++) {if (_sum < 0) {_sum = array[i];} else {_sum += array[i];}_max = max(_sum, _max);}return _max;} };43. 從 1 到 n 整數中 1 出現的次數（Trick）
整數中1出現的次數（從1到n整數中1出現的次數） - NowCoder
數字 1 的個數 - LeetCode
題目描述
給定一個整數 n，計算所有小于等于 n 的非負整數中數字 1 出現的個數。思路
- 暴力枚舉，時間復雜度 O(NlogN)
- 找規律 O(logN)
Code - 暴力枚舉
class Solution {int numberOf1(int i) {int cnt = 0;while(i) {if(i % 10 == 1)cnt++;i /= 10;}return cnt;} public:// int countDigitOne(int n) { // LeetCodeint NumberOf1Between1AndN_Solution(int n) {int cnt = 0;for (int i=1; i<=n; i++)cnt += numberOf1(i);return cnt;} };- LeetCode 會超時
Code - 找規律
class Solution { public:// int countDigitOne(int n) { // LeetCodeint NumberOf1Between1AndN_Solution(int n) {int cnt = 0;for (long m=1; m<=n; m*=10) { // 注意這里用 int m 在 LeetCode 會越界int a = n/m;int b = n%m;cnt += (a+8) / 10 * m + (a%10==1)*(b+1);}return cnt;} };LeetCode 討論區
44. 數字序列中的某一位數字（Trick）
題目描述
數字以 0123456789101112131415... 的格式序列化到一個字符串中，求這個字符串的第 index 位。 在這個序列中，第 5 位是 5（從 0 計數），第 13 位是 1，第 19 位是 4.思路
- 暴力求解
- 累加每個數的長度
- Trick-類似二分的思想
- 比如第 1001 位，
- 0~9 的長度為 10——10 < 1001
- 10~99 的長度為 180——10+180 < 1001
- 100~999 的長度 為 2700——10+180+2700 > 1001
- (1001 - 10 - 180) = 811 = 270*3 + 1
- 100 + 270 = 370 的第 1 位（從 0 計數），即 7
Code
int countOfIntegers(int digits); int digitAtIndex(int index, int digits); int beginNumber(int digits);int digitAtIndex(int index) {if(index < 0)return -1;int digits = 1;while(true) {int numbers = countOfIntegers(digits);if(index < numbers * digits)return digitAtIndex(index, digits);index -= digits * numbers;digits++;}return -1; }int countOfIntegers(int digits) {if(digits == 1)return 10;int count = (int) std::pow(10, digits - 1);return 9 * count; }int digitAtIndex(int index, int digits) {int number = beginNumber(digits) + index / digits;int indexFromRight = digits - index % digits;for(int i = 1; i < indexFromRight; ++i)number /= 10;return number % 10; }int beginNumber(int digits) {if(digits == 1)return 0;return (int) std::pow(10, digits - 1); }45. 把數組排成最小的數（排序）
把數組排成最小的數 - NowCoder
題目描述
輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。 例如輸入數組{3，32，321}，則打印出這三個數字能排成的最小數字為321323。思路
- 自定義排序
- 在比較兩個字符串 S1 和 S2 的大小時，應該比較的是 S1+S2 和 S2+S1 的大小，
- 如果 S1+S2 < S2+S1，那么應該把 S1 排在前面，否則應該把 S2 排在前面。
- 利用 stringstream 拼接數字
- C++ 中 int 轉 string 的函數
- to_string()
Code - 使用比較函數
class Solution {static bool cmp(const int &l, const int &r) {string ll = to_string(l) + to_string(r);string rr = to_string(r) + to_string(l);return ll < rr;} public:string PrintMinNumber(vector<int> numbers) {sort(numbers.begin(), numbers.end(), cmp);stringstream ss;for (auto i : numbers) ss << to_string(i);return ss.str();} };Code - 使用Lambda表達式
class Solution { public:string PrintMinNumber(vector<int> numbers) {sort(numbers.begin(), numbers.end(), [](const int &l, const int &r){return to_string(l) + to_string(r) < to_string(r) + to_string(l)});stringstream ss;for (auto i : numbers) ss << to_string(i);return ss.str();} };46. 把數字翻譯成字符串（解碼方法）（動態規劃）
解碼方法 - LeetCode
題目描述
給定一個數字，按照如下規則翻譯成字符串：1 翻譯成“a”，2 翻譯成“b”... 26 翻譯成“z”。 給定一個只包含數字的非空字符串，請計算解碼方法的總數。- 劍指Offer 上是數字范圍為 0~25，其他一致
思路
- 動態規劃
- 遞推公式dp[0] = 1 dp[1] = 0 int(s[0]) == 0= 1 其他 dp[i] += dp[i-1] int(s[i-1: i]) != 0 && int(s[i-2: i]) > 26+= dp[i-1] + dp[i-2] int(s[i-1: i]) != 0 && int(s[i-2: i]) <= 26
Code(Python)
class Solution:def numDecodings(self, s):""":type s: str:rtype: int"""if len(s) < 1: return 0n = len(s)dp = [0] * (n + 1)dp[0] = 1 # 注意初始化 dp[0] = 1dp[1] = 1 if s[0] != '0' else 0for i in range(2, n+1):if int(s[i-1]) != 0:dp[i] += dp[i-1]if int(s[i-2]) == 0:continueif int(s[i-2: i]) <= 26:dp[i] += dp[i-2]return dp[n]47. 禮物的最大價值（年終獎）（動態規劃）
年終獎_牛客網
題目描述
在一個 m*n 的棋盤的每一個格都放有一個禮物，每個禮物都有一定價值（大于 0）。 從左上角開始拿禮物，每次向右或向下移動一格，直到右下角結束。 給定一個棋盤，求拿到禮物的最大價值。例如，對于如下棋盤1 10 3 812 2 9 65 7 4 113 7 16 5 禮物的最大價值為 1+12+5+7+7+16+5=53。思路
- 深度優先搜索-復雜度大
- 動態規劃
- 二維遞推公式初始化
dp[0][0] = board[0][0]
dp[i][0] = dp[i-1][0] + board[i][0]
dp[0][j] = dp[0][j-1] + board[0][j]dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j]
- 注意邊界條件
- 一維遞推公式（優化版）TODO
Code - 二維DP
class Bonus { public:int getMost(vector<vector<int>>& board) {if (board.empty() || board[0].empty())return 0;int m = board.size();int n = board[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));dp[0][0] = board[0][0];for (int i=1; i<m; i++)dp[i][0] = dp[i-1][0] + board[i][0];for (int j=1; j<n; j++)dp[0][j] = dp[0][j-1] + board[0][j];for (int i=1; i<m; i++) {for (int j=1; j<n; j++) {dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j];}}return dp[m-1][n-1];} };Code - 一維DP
class Bonus { public:int getMost(vector<vector<int>>& board) {if (board.empty() || board[0].empty())return 0;int n = board[0].size();vector<int> dp(n, 0); // 注意不是 dp(0, n)for (auto& v: board) {dp[0] += v[0];for (int i=1; i<n; i++)dp[i] = max(dp[i], dp[i-1]) + v[i];}return dp[n-1];} };48. 最長不含重復字符的子字符串（動態規劃）
題目描述
輸入一個字符串（只包含 a~z 的字符），求其最長不含重復字符的子字符串的長度。 例如對于 arabcacfr，最長不含重復字符的子字符串為 acfr，長度為 4。思路
- 暴力枚舉，時間復雜度 O(N^3)，如果使用 set 的結構，可以降到 O(N^2)
- 動態規劃
- 遞推思路記：dp[i] := 以 s[i] 結尾的最長不重復子串注意：這并不是全局最長的結果，全局最長用另一個變量保存 遞推公式：dp[i] = dp[i-1] + 1 s[i] 之前沒有出現過= d s[i] 出現過，d == 兩次出現之間的距離，且 d <= dp[i-1]= dp[i-1] + 1 s[i] 出現過，d == 兩次出現之間的距離，但 d > dp[i-1]
Code - DP
int longestSubstringWithoutDuplication(const string& s) {if (s.length() < 1) return 0;int n = s.length();int maxLen = 0;vector<int> dp(n, 1); // 長度至少為 1vector<int> book(26, -1); // 模擬字典// dp[0] = 1;book[s[0] - 'a'] = 0;for (int i=1; i < n; i++) {int pre = book[s[i] - 'a'];if (pre < 0 || i - pre > dp[i-1]) {dp[i] = dp[i-1] + 1;maxLen = max(dp[i], maxLen);}else {maxLen = max(dp[i-1], maxLen);dp[i] = i - pre;}book[s[i] - 'a'] = i;}return maxLen; }int main() {cout << longestSubstringWithoutDuplication("abcacfrar") << endl; // 4cout << longestSubstringWithoutDuplication("acfrarabc") << endl; // 4cout << longestSubstringWithoutDuplication("arabcacfr") << endl; // 4cout << longestSubstringWithoutDuplication("aaaa") << endl; // 1 cout << longestSubstringWithoutDuplication("abcdefg") << endl; // 7 cout << longestSubstringWithoutDuplication("") << endl; // 0cout << longestSubstringWithoutDuplication("aaabbbccc") << endl; // 2cout << longestSubstringWithoutDuplication("abcdcba") << endl; // 4cout << longestSubstringWithoutDuplication("abcdaef") << endl; // 6return 0; }Code - 優化
int longestSubstringWithoutDuplication(const std::string& s) {if (s.length() < 1) return 0;int n = s.length();int curLen = 0;int maxLen = 0;vector<int> book(26, -1); // 模擬字典for (int i=0; i < n; i++) {int pre = book[s[i] - 'a'];if (pre < 0 || i - pre > curLen) {curLen++;maxLen = max(curLen, maxLen);}else {maxLen = max(curLen, maxLen);curLen = i - pre;}book[s[i] - 'a'] = i;}return maxLen; }int main() {cout << longestSubstringWithoutDuplication("abcacfrar") << endl; // 4cout << longestSubstringWithoutDuplication("acfrarabc") << endl; // 4cout << longestSubstringWithoutDuplication("arabcacfr") << endl; // 4cout << longestSubstringWithoutDuplication("aaaa") << endl; // 1 cout << longestSubstringWithoutDuplication("abcdefg") << endl; // 7 cout << longestSubstringWithoutDuplication("") << endl; // 0cout << longestSubstringWithoutDuplication("aaabbbccc") << endl; // 2cout << longestSubstringWithoutDuplication("abcdcba") << endl; // 4cout << longestSubstringWithoutDuplication("abcdaef") << endl; // 6return 0; }49. 丑數（動態規劃）
丑數 - NowCoder
題目描述
把只包含質因子2、3和5的數稱作丑數（Ugly Number）。 例如6、8都是丑數，但14不是，因為它包含質因子7。 習慣上我們把1當做是第一個丑數。求按從小到大的順序的第N個丑數。思路
- 動態規劃
Code
class Solution { public:int GetUglyNumber_Solution(int n) {// if (n <=6 ) return n;vector<int> dp(n+1, 0); // dp[0] = 0;int i2=1, i3=1, i5=1;dp[1] = 1;for (int i=2; i<=n; i++) {int nxt2 = dp[i2] * 2;int nxt3 = dp[i3] * 3;int nxt5 = dp[i5] * 5;dp[i] = min({nxt2, nxt3, nxt5});// 注意以下不能使用 else 結構，因為可能存在 nxtM == nxtN 的情況if (dp[i] == nxt2) i2++;if (dp[i] == nxt3) i3++;if (dp[i] == nxt5) i5++;}return dp[n];} };50.1 第一個只出現一次的字符位置（Hash）
第一個只出現一次的字符 - NowCoder
題目描述
在一個字符串 (1 <= 字符串長度 <= 10000，全部由字母組成) 中找到第一個只出現一次的字符，并返回它的位置。思路
- Hash 表
- 因為是字符，可以使用數組模擬哈希表
Code - 數組
class Solution { public:int FirstNotRepeatingChar(const string& s) {vector<int> m(256, 0);for (auto c : s)if (m[c] < 1)m[c] = 1;elsem[c] += 1;for (int i=0; i < s.length(); i++)if (m[s[i]] == 1)return i;return -1;} };Code - Hash(C++ map)
class Solution {map<char, int> m; public:int FirstNotRepeatingChar(const string& s) {for (auto c : s)if (m.count(c) < 1)m[c] = 1;elsem[c] += 1;for (int i=0; i < s.length(); i++)if (m[s[i]] == 1)return i;return -1;} };Code - Hash(Python dict)
class Solution:def FirstNotRepeatingChar(self, s):d = dict()for c in s:if c in d:d[c] += 1else:d[c] = 1for i in range(len(s)):if d[s[i]] == 1:return ireturn -150.2 字符流中第一個只出現一次的字符（數據結構：隊列）
字符流中第一個不重復的字符 - NowCoder
題目描述
請實現一個函數用來找出字符流中第一個只出現一次的字符。 例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現一次的字符是"g"。 當從該字符流中讀出前六個字符“google"時，第一個只出現一次的字符是"l"。思路
- 計數排序——使用一個數組數組保存出現元素的次數
- 使用隊列保存出現的元素
Code - 隊列
class Solution {int book[256];queue<char> q;public:Solution() {fill(book, book + 256, 0); // 初始化，實際不需要這步，默認全部初始化為 0}void Insert(char ch) {book[ch] += 1;q.push(ch);while (!q.empty() && book[q.front()] > 1) {q.pop();}}char FirstAppearingOnce() {return q.empty() ? '#' : q.front();} };51. 數組中的逆序對
數組中的逆序對 - NowCoder
題目描述
在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。 輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P%1000000007總結
以上是生活随笔為你收集整理的算法工程师笔试 -剑指offer-习题详细解答的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java.lang.NoClassDef
- 下一篇： 【数据挖掘】挖掘建模-回归分析（1）