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

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. 有效三角形的個數(shù)

（雙指針）

最暴力的方法應該是三重循環(huán)枚舉三個數(shù)字。但是這樣會超時。

經(jīng)過觀察可以發(fā)現(xiàn)，如果數(shù)組經(jīng)過排序，那么從前往后判斷三角形是否有效就可以利用最小的兩條邊相加是否大于最大的一條邊來判斷。

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

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;    }};

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

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

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

（偏移量）

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

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. 二叉樹的右視圖

（廣搜）

我們提取出每一層的最后一個節(jié)點，所以我們只需要使用層序遍歷找到每一層的最后一個節(jié)點，然后放入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);    }};

（歸并排序鏈表）

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

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

核心步驟：

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

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

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

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

                 

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

                   
 文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
                 
                   
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/123347.html
               
                      
               

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