Arktische

题解

/ 注册

全部文章 / 题解（共9篇）

C++ 链表k个一组翻转

思路由于题目要求空间复杂度，说明不可以递归，那么时间复杂度就只能是了，即遍历的同时一边分组一边翻转。这样思路就清晰了，组内直接套链表翻转的模板，组间注意要保存上一组的tail（上一组翻转前的head）。考虑最后一组不满k的情况，这时只需要再翻转一次最后一组就可以了，总体时间复杂度就是。当然，求链...

2020-11-22

0 865

bfs-二叉树层序遍历

思路二叉树层序遍历可以用bfs，而且由于是树结构所以不需要哈希表记录访问过的节点，直接套模板即可。模板可见：bfs/dfs模板 class Solution { public: vector<vector<int> > levelOrder(TreeNode* ro...

2020-11-18

0 878

c++ 验证ip地址

思路这题没什么技巧也没什么算法，就是处理字符串...IPv6的错误形式可能有如下：多了0 出现:: 字符不在0-9 a-f A-F之间 IPv4错误形式可能有如下：多了首位'0' 超过0-255范围出现的.. 别的暂时没想到，有遗漏欢迎补充 class Solution { pub...

2020-11-18

12 1621

合并有序链表

思路比合并有序数组更简单，归并有序链表逐个比较即可。此外，用dummy node来指向实际链表头能使代码简化。 class Solution { public: /** * * @param l1 ListNode类 * @param l2 ListNod...

2020-11-18

0 546

bfs/dfs-岛屿数量

思路以每个grid[i][j]为起点搜索（访问过的跳过），套bfs或者dfs的模板，注意边界条件。这个题不用额外维护一个visited的表，可以原地把grid[i][j]置为'0' bfs: class Solution { public: /** * 判断岛屿数量 *...

2020-11-18

0 593

分治/快排思想-最小的k个数

思路最好写的办法自然是先qsort，然后取第k个元素，但这样把另外n-k个无关的元素也排了序。这题仍然使用升序快排的模板，但是当找到的pivot枢纽元比k大的时候只排它左边的子数组。另外这题给出的k可能比数组size还大，需要单独处理，代码如下： class Solution { public:...

2020-11-18

0 588

栈-合法的括号序列

思路遇到左括号就压栈，遇到右括号就判断栈顶是否匹配，不匹配就直接false，栈为空也直接false,匹配的话说明能配对则出栈。最后遍历完看栈里是否还有元素，有则说明有落单的左括号，否则就是合法的括号序列。 class Solution { public: /** * ...

2020-11-18

0 682

动态规划-最长公共子串

思路一看到两个字符串的“最值”问题，一般想到二维dp。很自然地想到把str1前i个字符和str2前j个字符最长公共子串的长度作为dp[i][j]，但由于子串定义必须是原字符串连续的序列，这样定义无法找到递推关系，因此需要加限定条件——以str1[i-1]和str2[j-1]结尾的最长公共子串长度。...

2020-11-18

53 3840

按圈螺旋遍历矩阵

思路观察可知螺旋遍历每圈的遍历模式是一样的,每一圈一般可以分解为下图的四步，这样就方便放入for循环。设每一圈遍历的起始点为matrix[z][z]，可以总结出每圈的遍历模式如下，其中r c分别为本圈行列数： for(int i = 0; i < c - 1; i++) res.push_b...

2020-10-27

23 1452