摘要:有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像,都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归,所以空间复杂度为
本题其实就是层序遍历一个二叉树的升级版,我们需要要将二叉树层序遍历的结果放入答案中,然后将偶数层的节点结果逆置一遍即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> ans; queue<TreeNode*> q; q.push(root); int step = 1; while (!q.empty()) { int size = q.size(); vector<int> path; while (size --) { auto top = q.front(); q.pop(); path.push_back(top->val); if (top->left) q.push(top->left); if (top->right) q.push(top->right); } if (step % 2 == 0) reverse(path.begin(), path.end()); ans.push_back(path); step ++; } return ans; }};
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ans; if (!root) return ans; stack<TreeNode*> odd; stack<TreeNode*> even; odd.push(root); int flag = 1; while (!odd.empty() || !even.empty()) { vector<int> path; if (flag > 0) { while (!odd.empty()) { auto top = odd.top(); odd.pop(); path.push_back(top->val); if (top->left) even.push(top->left); if (top->right) even.push(top->right); } } else { while (!even.empty()) { auto top = even.top(); even.pop(); path.push_back(top->val); if (top->right) odd.push(top->right); if (top->left) odd.push(top->left); } } flag *= -1; ans.push_back(path); } return ans; }};
本题因为数组是有序数组拆分而成,所以数组局部还是具有单调性的。
如果一个数组没有被拆分成两个数组的话,那么直接返回这个有序数组的开头即可。
如果一个数组被拆分成了两个数组的话,那么被拆分后的数组的左右两边都是是一段有序的数组,并且左边一段数组都>nums.back()
,右边一段数组都<=nums.back()
。
根据这个特点就可以二分答案了,我们需要从左向右找出第一个
注意:因为有可能会有重复数字出现在数组中,所以被拆分的左边数组的前端和右边数组的后端可能会是重复的元素。但是这就不满足左数组中的数字都>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]; }};
最暴力的方法应该是三重循环枚举三个数字。但是这样会超时。
经过观察可以发现,如果数组经过排序,那么从前往后判断三角形是否有效就可以利用最小的两条边相加是否大于最大的一条边来判断。
而且如果我们先枚举最大的一个数字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; }};
总结:本题和「三数之和」很像,都是三个数加和为某一个值。然后我们可以通过排序过后,只用枚举其中一个数字和利用双指针就可以通过。
这么做的原因是因为已经有了排序和三个数的关系,所以只需要枚举一个数字,那么另两个数字的总和会是一个相对固定的值。利用总和不变和数组有序的原理,所以可以利用双指针解决这个问题。
其实本题就是一个偏移量的问题,我们需要数组转动起来,这可以使用偏移量数组来解决。利用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; }};
我们提取出每一层的最后一个节点,所以我们只需要使用层序遍历找到每一层的最后一个节点,然后放入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; }};
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;
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/123347.html
摘要:值得一提的是每篇文章都是我用心整理的,编者一贯坚持使用通俗形象的语言给我的读者朋友们讲解机器学习深度学习的各个知识点。今天,红色石头特此将以前所有的原创文章整理出来,组成一个比较合理完整的机器学习深度学习的学习路线图,希望能够帮助到大家。 一年多来,公众号【AI有道】已经发布了 140+ 的原创文章了。内容涉及林轩田机器学习课程笔记、吴恩达 deeplearning.ai 课程笔记、机...
摘要:每天会折腾一道及以上题目,并将其解题思路记录成文章,发布到和微信公众号上。三汇总返回目录在月日月日这半个月中,做了汇总了数组知识点。或者拉到本文最下面,添加的微信等会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...
摘要:经过半年的沉淀,加上对,和分布式这块的补齐,终于开始重拾面试信心,再次出征。面试官提示没有提到线程的有内核态的切换,程只在用户态调度。三面综合技术面这面面的是阵脚大乱,面试官采用刨根问底的方式提问,终究是面试经验不够,导致面试的节奏有点乱。 经过半年的沉淀,加上对MySQL,redis和分布式这块的补齐,终于开始重拾面试信心,再次出征。 鹅厂 面试职位:go后端开发工程师,接受从Jav...
阅读 2163·2021-11-15 11:38
阅读 1128·2021-09-06 15:02
阅读 3346·2021-08-27 13:12
阅读 1258·2019-08-30 14:20
阅读 2360·2019-08-29 15:08
阅读 612·2019-08-29 14:08
阅读 1703·2019-08-29 13:43
阅读 1431·2019-08-26 12:11