注意：因为有可能会有重复数字出现在数组中，所以被拆分的左边数组的前端和右边数组的后端可能会是重复的元素。但是这就不满足左数组中的数字都>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
                                                                                                           面试题
                                                                                                           栈面试题
                                                                                                           笔试面试题
                                                         
                 
               
              
             
               

                   
 文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
                 
                   
转载请注明本文地址：https://www.ucloud.cn/yun/123347.html
               
                      
               

                 
                                  
上一篇：3年软件测试经验突显迷茫...不知道我这种测试人员是不是被淘汰？​​
  
                                                
                                       
下一篇：程序人生之周记