注意：因?yàn)橛锌赡軙?huì)有重復(fù)數(shù)字出現(xiàn)在數(shù)組中，所以被拆分的左邊數(shù)組的前端和右邊數(shù)組的后端可能會(huì)是重復(fù)的元素。但是這就不滿足左數(shù)組中的數(shù)字都>nums.back()了，所以我們需要將右邊數(shù)組后半段重復(fù)的數(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. 有效三角形的個(gè)數(shù)

（雙指針）

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

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

而且如果我們先枚舉最大的一個(gè)數(shù)字nums[i]的話，那么nums[j] + nums[k]的和一定需要大于nums[i]，而且因?yàn)閿?shù)組是有序的，所以如果nums[j]減小的話，那么nums[k]就需要增大，這樣才可以使得nums[j] + nums[k] > nums[i]，因此可以利用這個(gè)單調(diào)性的原則使得我們可以使用雙指針?biāo)惴▉斫鉀Q本題。

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ù)之和」很像，都是三個(gè)數(shù)加和為某一個(gè)值。然后我們可以通過排序過后，只用枚舉其中一個(gè)數(shù)字和利用雙指針就可以通過。

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

劍指 Offer 29. 順時(shí)針打印矩陣

（偏移量）

其實(shí)本題就是一個(gè)偏移量的問題，我們需要數(shù)組轉(zhuǎn)動(dòng)起來，這可以使用偏移量數(shù)組來解決。利用int xd[4] = {0, 1, 0, -1}, yd[4] = {1, 0, -1, 0};使得數(shù)組可以順時(shí)針旋轉(zhuǎn)起來。除非越界或者已經(jīng)被訪問過了，否則按照原來的方向繼續(xù)前進(jìn)，否則的話，我們就需要手動(dòng)的將轉(zhuǎn)動(dòng)的方向調(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. 二叉樹的右視圖

（廣搜）

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

（歸并排序鏈表）

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

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

核心步驟：

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

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

注意：因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為logn

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

                 

                                                                                                                    
                         云服務(wù)器
                                             
                         GPU云服務(wù)器
                                                                                                                                                 
                                      
                     
                    
                                                                                               TOP100summit
                                                                                                           面試題
                                                                                                           棧面試題
                                                                                                           筆試面試題
                                                         
                 
               
              
             
               

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

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