注意：因為有可能會有重復數字出現在數組中，所以被拆分的左邊數組的前端和右邊數組的后端可能會是重復的元素。但是這就不滿足左數組中的數字都>nums.back()了，所以我們需要將右邊數組后半段重復的數字去掉，這樣就可以使得nums.back()都小于左邊數組中的所有數組了。

class Solution {public:    int minArray(vector<int>& nums) {        int n = nums.size();        if (nums[0] < nums.back()) return nums[0];        int l = 0, r = n - 1;        while (l < r && nums[0] == nums[r]) r --;        int target = nums[r];        while (l < r) {            int mid = l + (r - l) / 2;            if (nums[mid] <= target) r = mid;            else l = mid + 1;        }        return nums[l];    }};

611. 有效三角形的個數

（雙指針）

最暴力的方法應該是三重循環枚舉三個數字。但是這樣會超時。

經過觀察可以發現，如果數組經過排序，那么從前往后判斷三角形是否有效就可以利用最小的兩條邊相加是否大于最大的一條邊來判斷。

而且如果我們先枚舉最大的一個數字nums[i]的話，那么nums[j] + nums[k]的和一定需要大于nums[i]，而且因為數組是有序的，所以如果nums[j]減小的話，那么nums[k]就需要增大，這樣才可以使得nums[j] + nums[k] > nums[i]，因此可以利用這個單調性的原則使得我們可以使用雙指針算法來解決本題。

class Solution {public:    int triangleNumber(vector<int>& nums) {        int n = nums.size();        sort(nums.begin(), nums.end());        int ans = 0;        for (int i = 2; i < n; i ++) {            for (int j = i - 1, k = 0; k < j; j --) {                while (k < j && nums[k] + nums[j] <= nums[i]) k ++;                ans += j - k;            }        }        return ans;    }};

總結：本題和「三數之和」很像，都是三個數加和為某一個值。然后我們可以通過排序過后，只用枚舉其中一個數字和利用雙指針就可以通過。

這么做的原因是因為已經有了排序和三個數的關系，所以只需要枚舉一個數字，那么另兩個數字的總和會是一個相對固定的值。利用總和不變和數組有序的原理，所以可以利用雙指針解決這個問題。

劍指 Offer 29. 順時針打印矩陣

（偏移量）

其實本題就是一個偏移量的問題，我們需要數組轉動起來，這可以使用偏移量數組來解決。利用int xd[4] = {0, 1, 0, -1}, yd[4] = {1, 0, -1, 0};使得數組可以順時針旋轉起來。除非越界或者已經被訪問過了，否則按照原來的方向繼續前進，否則的話，我們就需要手動的將轉動的方向調整一下。

class Solution {public:    const int INF = 0x3f3f3f3f;    vector<int> spiralOrder(vector<vector<int>>& matrix) {        if (matrix.empty()) return {};        int n = matrix.size(), m = matrix[0].size();        vector<int> ans;        int x = 0, y = 0, d = 0;        int xd[4] = {0, 1, 0, -1}, yd[4] = {1, 0, -1, 0};        vector<vector<bool>> vis(n, vector<bool>(m));        for (int i = 0; i < n * m; i ++) {            ans.push_back(matrix[x][y]);            vis[x][y] = true;            int a = x + xd[d], b = y + yd[d];            if (a < 0 || b < 0 || a >= n || b >= m || vis[a][b]) {                d = (d + 1) % 4;                a = x + xd[d], b = y + yd[d];            }                        x = a, y = b;        }        return ans;    }};

199. 二叉樹的右視圖

（廣搜）

我們提取出每一層的最后一個節點，所以我們只需要使用層序遍歷找到每一層的最后一個節點，然后放入ans中即可。

class Solution {public:    vector<int> rightSideView(TreeNode* root) {        vector<int> ans;        if (!root) return ans;        queue<TreeNode*> q;        q.push(root);        while (!q.empty()) {            int size = q.size();            while (size --) {                TreeNode* top = q.front();                q.pop();                if (!size) ans.push_back(top->val);                if (top->left) q.push(top->left);                if (top->right) q.push(top->right);            }        }        return ans;    }};

（深搜）

class Solution {public:    vector<int> ans;    void dfs(TreeNode* root, int depth) {        if (!root) return ;        if (depth == ans.size()) {            ans.push_back(root->val);        }        depth ++;        dfs(root->right, depth);        dfs(root->left, depth);    }    vector<int> rightSideView(TreeNode* root) {        if (!root) return ans;        dfs(root, 0);        return ans;    }};

148. 排序鏈表

（排序鏈表）

class Solution {public:    const int INF = 0x3f3f3f3f;    ListNode* Sort(ListNode* head) {        if (!head->next) return head;        ListNode* newHead = Sort(head->next);        ListNode* dummy = new ListNode(INF);        dummy->next = newHead;        ListNode* cur = newHead, *prev = dummy;        while (cur && cur->val < head->val) {            prev = cur;            cur = cur->next;        }        head->next = cur;        prev->next = head;        ListNode* ans = dummy->next;        delete dummy;        return ans;    }    ListNode* sortList(ListNode* head) {        if (!head) return nullptr;        return Sort(head);    }};

（歸并排序鏈表）

如果想要實現nlogn的時間復雜度的話，就必須使用二分的策略。所以我們可以使用歸并排序來解決這個問題。

歸并排序的核心思想就是合并兩個一半的鏈表，所以我們先將鏈表從中間分割開來，然后將分割后的兩個鏈表二路歸并起來就可以了。

核心步驟：

1.利用快慢指針將鏈表從中間分成兩半，并且兩個鏈表需要成為獨立的鏈表（尾指針都指向空）。

2.二路歸并，每次都挑選出兩個鏈表中較小節點作為鏈表的下一個節點。

注意：因為歸并排序需要遞歸，所以空間復雜度為logn

class Solution {public:    ListNode* sortList(ListNode* head) {        if (!head || !head->next) return head;
            
                     

                 

                                                                                                                    
                         GPU云服務器
                                             
                         云服務器
                                                                                                                                                 
                                      
                     
                    
                                                                                               TOP100summit
                                                                                                           面試題
                                                                                                           棧面試題
                                                                                                           筆試面試題
                                                         
                 
               
              
             
               

                   
 文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
                 
                   
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123347.html
               
                      
               

                 
                                  
上一篇：3年軟件測試經驗突顯迷茫...不知道我這種測試人員是不是被淘汰？??
  
                                                
                                       
下一篇：程序人生之周記