菜鸡的博客 | WTCL

79. Word Search

你快乐吗？

79. Word Search 89.63%，dfs对图深搜，进行剪枝和回溯，注意几个点。深搜的下一个点，可能在该点的上、下、左、右，所以可以利用两个数组dx、dy，以及操作int x = cur_x + dx[i];int y = cur_y + dy[i];确定下一；个点；下一个点必须在图中；下一个点不能在当前路径中被访问过，用vis数组进行标记；好像是不...

Posted by bbkgl on September 26, 2019

78. Subsets

你快乐吗？

78. Subsets 100%，开始想到了这个规律，但是翻评论一看，已经有大佬说了。就是先遍历给定数组中所有元素，然后遍历之前生成的答案序列，对每个子序列加上该元素，组成新的子序列，再加入到答案总序列中。。。以此类推 class Solution { public: vector<vector<int>> subsets(vector<int&g...

Posted by bbkgl on September 26, 2019

77. Combinations

你快乐吗？

# 77. Combinations dfs深搜，99%，需要处理一下的是剪枝，可以在一定程度上提高效率。 class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> ans; v...

Posted by bbkgl on September 26, 2019

75. Sort Colors

你快乐吗？

# 75. Sort Colors 84%，注意题目要求，不让用库函数，只能扫一路。其实就是扫一路，碰到0，与left所在位置的数交换，碰到2，与right所在位置的数交换，注意以下特殊情况交换后当前位数字不是1 left不能超过当前位 class Solution { public: void sortColors(vector<int> &...

Posted by bbkgl on September 26, 2019

74. Search a 2D Matrix

你快乐吗？

# 74. Search a 2D Matrix 98.74%，对二维数组进行二分查找。将二维数组看作一维数组通过整除和取模得到mid在二维数组的下标再进行普通的二分查找，可以用循环，也可以递归。 class Solution { public: bool searchMatrix(vector<vector<int>>&am...

Posted by bbkgl on September 26, 2019

73. Set Matrix Zeroes

你快乐吗？

73. Set Matrix Zeroes 99%，差不多100%，第一个版本解不是常数空间复杂度，这次更新常数复杂度的，讲一下思路。矩阵中某个数为零，则将该数所在行的第一个数置零，所在列的第一个数置零，即matrix[0][j] = matrix[i][0] = 0;，这样并不会影响该列该行首个数的取值，因为他们最后都会被置零。即让首行首列记录哪一列有零，哪一行有零遍...

Posted by bbkgl on September 26, 2019

71. Simplify Path

你快乐吗？

# 71. Simplify Path 90%，其实就是考察栈stack的使用，当然最重要看懂题目，看不懂的切换成中文。题意和思路分析如下：将绝对路径转化成规范的路径输出的时候每个目录之间只能相隔一道/，且开头必有一道/；如果有一层以上的目录的话，结尾必没有/ .表示上一层目录保留，且这个效果不累加，所以碰到这个直接continue; ..表示上一层目录不保留...

Posted by bbkgl on September 26, 2019

47. Permutations II

你快乐吗？

47. Permutations II C++，这道题和剑指offer中字符串全排列是一样的。思路如下：其实这个全排列算法就是固定一个数的位置(left)，然后从下一位数再开始全排列(递归过程)…直到最后一位数，模拟手动全排列的过程；所以如果要去重的话，只要控制每次排列时，固定的那个数是不一样的就行了；因为固定的数不一样，那从这个数开始产生的全排列就不一样。所以只...

Posted by bbkgl on September 26, 2019

33. Search in Rotated Sorted Array

你快乐吗？

33. Search in Rotated Sorted Array 虽然题目要求时间复杂度是O(logn)，但发现直接线性查找和二分查找的时间差不多。。。不过我们也要用二分啊(^▽^) 思路其实很简单，和平时的二分几乎没区别，但是注意边界条件。假设左边界为left，右边界为right，中点为mid：如果target == nums[mid]，那直接返回结果；如果num...

Posted by bbkgl on September 26, 2019

143.Reorder_List

你快乐吗？

143. Reorder List C++，链表。很显然，这道题如果用了数组/vector/栈/队列就是不及格的解法。怎么在不用额外空间的情况下求解呢？答案是递归。就拿题目中给的序列[1,2,3,4,5,6]举例，我们需要从中间往两边进行拆分：首先递归地遍历序列，直到序列中间位置，也就是3和4 定义两个指针，让指针指向3和4 然后我们返回4后面元素的地址，也就...

Posted by bbkgl on September 26, 2019

我太菜了

79. Word Search

你快乐吗？

78. Subsets

你快乐吗？

77. Combinations

你快乐吗？

75. Sort Colors

你快乐吗？

74. Search a 2D Matrix

你快乐吗？

73. Set Matrix Zeroes

你快乐吗？

71. Simplify Path

你快乐吗？

47. Permutations II

你快乐吗？

33. Search in Rotated Sorted Array

你快乐吗？

143.Reorder_List

你快乐吗？

FEATURED TAGS

ABOUT ME

FRIENDS