142. 环形链表 II
我的思路
①fast = l + ak + x
②slow = l + bk + x
③fast = 2 * slow
2l + 2bk + 2x = l + ak + x ==> l = (a - 2b)k - x
所以：slow从相遇点出发，ptr从head出发，在入口处相遇
如图所示（图挂了）
141. 环形链表
我的思路
使用快慢指针，相遇则有环
139. 单词拆分
题解思路
1.使用unordered_set存储dict（因为set有find功能）
2.遍历字符串s.
3.遍历j从 0到i - 1,看是否在dict里面有对应的字符串.有,则dp[j] = true;
需要注意的是,必须是外循环递增i,内循环再递增j < i,我本来打算i = 0, j > i,这样的话需要从右往左遍历(应该).
128. 最长连续序列
题解思路
1.将数组放到unordered_set里去重
2.遍历数组,如果存在比当前数大1的,计数+1,tmpnum++直到没有为止
3.计算max
一个减少时间复杂度的小skill，如果存在比nums[i]小1的就continue了,因为在连续序列的最小数那里已经计算过了,比如说[1,2,3,4].到2的时候,1那里已经计算过整个len了,所以综合起来时间复杂度为O(n)
- unordered_set的count的平均时间复杂度为O(1),最坏为O(n),可以去了解下为什么
https://en.cppreference.com/w/cpp/container/unordered_set/count
136. 只出现一次的数字
我的思路
使用异或
124. 二叉树中的最大路径和
题解思路
1.递归，使用全局变量存储max。
2.节点存储到当前节点的最大值，root.val + max(leftmax, rightmax)
3.max 为root.val + leftmax + rightmax,
121. 买卖股票的最佳时机
我的思路
- 使用迭代的minnum，maxprofit
我的思路2：动态规划
dp[i] 表示当前最大利润，dp[i] = max(dp[i - 1], prices[i] - minnum);
我觉得反而复杂了
114. 二叉树展开为链表
题解思路
cur右侧移到左侧的最右侧，没有左侧的右侧，移到左侧
while (cur != nullptr) {
if (cur -> left != nullptr) {
TreeNode* pre = cur -> left;
while(pre -> right != nullptr) {
pre = pre -> right;
}
pre -> right = cur -> right;
cur -> right = cur -> left;
cur -> left = nullptr;
}
cur = cur -> right;
}
105. 从前序与中序遍历序列构造二叉树
我的思路
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int inleft, int preleft, int len) {
TreeNode* root;
if (len <= 0) {
return nullptr;
}
if (len > 0) {
root = new TreeNode(preorder[preleft]);
}
int index = inleft;
for (; index < len + index; ++index) {
if (preorder[preleft] == inorder[index]) {
break;
}
}
root -> left = buildTree(preorder, inorder, inleft, preleft + 1, index - inleft);
root -> right = buildTree(preorder, inorder, index + 1, preleft + index - inleft + 1, len - 1 - index + inleft);
return root;
}
注意细节，我在计算rightpreleft的时候使用len - 1 - preleft来计算了，忽略了right的长度
104. 二叉树的最大深度
我的思路
基础递归
if (root == nullptr) return 0;
return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
102. 二叉树的层序遍历
我的思路
BFS
可以尝试使用DFS<栈>实现
101. 对称二叉树
我的思路
- 使用两个dfs得到两个vector，因为空这个内容无法用数字代替，所以把数字转化为string类型，空用其他符号表示
- 比对两个vector
当然最后没有做，因为我觉得有些问题。
题解思路1：递归
- 在一个dfs内同时搜索左右两边，同时进行，传入左右两个节点。
题解思路2： 迭代
迭代用队列来做.
98. 验证二叉搜索树
我的思路
中序遍历，使用vec存。我打算用pre 和cur来做的，结果都是bug,改了一下，改好了
改前
if (root == nullptr) {
return;
}
if (root -> val <= pre) {
flag = false;
}
inorder(root -> left);
pre = root -> val;
inorder(root -> right);
改后
if (root == nullptr) {
return;
}
inorder(root -> left);
if (root -> val <= pre) {
flag = false;
}
pre = root -> val;
inorder(root -> right);
96. 不同的二叉搜索树
题解思路1
递归
for (int i = 1; i <= n; ++i) {
ans += numTrees(i - 1) * numTrees(n - i);
}
题解思路2
记忆化递归
把ans存起来
题解思路3
1.n个数组成的不同二叉树,分解为以1为root,左空右n - 1/以2为root 左1右n - 2/..,这样n种方式;
2.以i为root的方式有 [i - 1] * [n - i]种
i from 1 to n
j == 0 ==> 左 ans[0] * 右 ans[n]
j == 1 ==> 左 ans[1] * 右 ans[n - 1]
左[j - 1] 右 [n - j]
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; j++)
ans[i] += ans[j - 1] * ans[i - j];
}
94. 二叉树的中序遍历
我的思路
- 不会吧不会吧不会有人中序遍历还不能bug-free吧（指我调了很久的命名）
85. 最大矩形
思路
84的拓展，每一层加下来
84. 柱状图中最大的矩形
思路
单调栈
单调栈模板
for (int i = 0; i< nums.size(); ++i) {
while (!st.empty() && nums[st.top()] > nums[i]) {
st.pop();
}
st.push(i);
}
需要注意的地方
1.[1,2,3,4,5]
在末尾添0
2.[2,1,2]
在头添0
cur = st.top();
st.pop();
left = st.top() + 1;
79. 单词搜索
思路
回溯
注意的点
1.在主方法中得到true就返回，算是剪枝
2.走过的路用别的符号表示，例如“0”，使用临时变量存储四个方向的返回值，在返回之前把原字符填回去
78. 子集
思路
- 特点
1.每一个节点均返回
2.满足下一个节点比当前节点大.
""
1 2 3
2 3 3
思路2
无重复子集符合一下排列,假设n = 3
000 001 010 100 101 110 111
int n = 1 << nums.size();
for (int i = 0; i < n; ++i) {
tmp.clear();
int j = 0;
while (j < nums.size()) {
if (i & (1 << j)) {
tmp.push_back(nums[j]);
}
j++;
}
ans.push_back(tmp);
}
76. 最小覆盖子串
思路
再写也写不出来
1.建一个哈希表存t的字母在窗口内的出现次数，通过动态的窗口内包含字符数目（n = t.size()）来维护窗口
2.开滑
2.1 right滑到第一个完全囊括窗口的右边
2.1.1 滑过的哈希字母值均减1，如果遇到t中的字母，则n--;
2.2如果n为0了，窗口到位了，开始记录最短长度
2.2.1 滑左侧的，滑一个加一个哈希值，如果加到一个t中的字母,n++,就又开始滑右边了.
75. 颜色分类
我的思路
- sort
思路1
- 使用left right 和index
while (index <= right) {
// cout << nums[index] << endl;
if (nums[index] == 0) {
if (index != left) { 1 0 2 index ==> [1] left ==>[0]
swap(nums[index], nums[left]);
}
else {
index++;
}
left++;
}
else if (nums[index] == 2){
swap(nums[index], nums[right]); 2 0 1 index ==> [0] right ==> [2]
right--;
}
else {
index++;
}
}
思路2
记录0,1的数.全部为2,替换为1,替换为0
int num = nums[i];
nums[i] = 2;
if (num < 2) {
nums[n1] = 1;
n1++;
}
if (num == 0) {
nums[n0] = 0;
n0++;
}
72. 编辑距离
思路
- dp[i][j]为word1.substr(0, i) 到word2.substr(0,j)的距离
- 增
dp[i][j - 1] + 1 - 删
dp[i - 1][j] + 1这一行删一个相当于上一行增一个,反推 - 改
dp[i - 1][j - 1] + 1
求min
70. 爬楼梯
我的思路
- 像斐波那契那样迭代，递归超时
64. 最小路径和
我的思路
grid[i][j] = grid[i][j] + min(grid[i - 1][j], grid[i][j - 1]);
62. 不同路径
我的思路
- 从右下向左上,垓格子的路径数量等于right + down
56. 合并区间
我的思路
- sort
- cur[left][right] = [0][1]
- while : right > [i + 1][1] ==> right = max(right, [i + 1][1]) 向右延展right
55. 跳跃游戏
我的思路
例如nums[0] == 2那么到i = 1时就只能走1步,max(nums[i], num[i - 1] - 1)如果还没到最后一位就到0.，就到不了了
for (int i = 1; i < nums.size() - 1; ++i) {
nums[i] = max(nums[i - 1] - 1, nums[i]);
if (nums[i] == 0) {
return false;
}
}
return true;
题解思路
看i + nums[i]能不能覆盖最后一个下标
需要注意的是，遍历的右边界是cover，能到达的最远的地方。
int cover = 0;
for (int i = 0; i <= cover; ++i) {
cover = max(cover, i + nums[i]);
if (cover >= nums.size() - 1) return true;
}
53. 最大子序和
我的思路
我是傻逼
- 按nums[i] > 0 或< 0分类
for (int i = 1; i < nums.size(); ++i) {
// cout << "cur " << cur << " maxnum " << maxnum << endl;
if (nums[i] > 0) {
if (maxnum < 0) {
cur = nums[i];
maxnum = cur;
}
else {
cur = max(cur + nums[i], nums[i]);
maxnum = max(maxnum, cur);
}
}
else {
if (cur + nums[i] > 0) {
cur += nums[i];
}
else {
cur = nums[i];
maxnum = max(maxnum, cur);
}
}
}
思路1
按sum分.
- 我大于0就有资本暂时减去num为后面更大的sum做准备
- 小于0不如等待下一个大于0的num
- 使用max取的每个阶段的sum的最大值
if (sum > 0) {
sum += num;
}
else {
sum = num;
}
ans = max(ans, sum);
思路2 动态规划
-
dp[i - 1]表示到i - 1为止的最大连续子数组的和 - 那么在
i时,如果dp[i - 1] < 0则dp[i] = nums[i]反之则dp[i] = dp[i - 1] + nums[i] - 因为只有前后关系,所以可以优化成如下
dp = dp > 0 ? dp + nums[i] : nums[i];
ans = max(ans, dp);
49. 字母异位词分组
我的思路
sort string 得到string vec键值对
unordered_map<string, vector<string> > m;
for (string& str : strs) {
string s = str;
sort(s.begin(), s.end());
m[s].push_back(str);
}
值得注意的地方↓
第三行代码直接都进行初始化了
unordered_map<string, vector<string> > m;
s = str;
m[s].push_back(str); //直接都进行初始化了。
48. 旋转图像
我的思路
- 由外向内层序处理
matrix[layer][layer + index] = matrix[layer + slen - index][layer];
matrix[layer + slen - index][layer] = matrix[layer + slen][layer + slen - index];
matrix[layer + slen][layer + slen - index] = matrix[layer + index][layer + slen];
matrix[layer + index][layer + slen] = tmp;
思路2
- 先右上-左下翻转，再左右对称翻转
46. 全排列
思路1
-
[1,2,3]的全排列是1+[2,3]的全排列 + (2+ [1,2]) + (3 + [1,2]) - 使用continue和find来跳过已经使用过的数
for (int i = 0; i < nums.size(); ++i) {
auto it = find(tmp.begin(), tmp.end(), nums[i]);
if (it != tmp.end()) continue;
tmp.push_back(nums[i]);
dfs(nums);
tmp.pop_back();
}
思路2
https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
交换法
void dfs(vector<int>& nums, int index) {
if (index == nums.size()) {
ans.push_back(nums);
return;
}
for (int i = index; i < nums.size(); ++i) {
swap(nums[index], nums[i]);
dfs(nums, index + 1);
swap(nums[index], nums[i]);
}
39. 组合总和
我的思路
- 使用dfs,但是时间很长，内存很大。
遇到的问题
在引用的情况下使用sort函数导致答案出错。
void dfs(vector<int>& tmp, vector<int>& candidates, int target) {
if (target == 0) {
sortans.push_back(tmp);
return;
}
if (target < 0) {
return;
}
for (int i = 0; i < candidates.size(); i++) {
tmp.push_back(candidates[i]);
dfs(tmp, candidates, target - candidates[i]);
tmp.pop_back();
}
}
改进思路
增加一个下标变量，不往回加譬如[2,3,5] ,3分支就不加2了。也减少了去重操作，速度快了很多
void dfs(vector<int>& tmp, vector<int>& candidates, int target, int startIndex) {
if (target == 0) {
ans.push_back(tmp);
return;
}
if (target < 0) {
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
tmp.push_back(candidates[i]);
dfs(tmp, candidates, target - candidates[i], i);
tmp.pop_back();
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
我的想法
二分查找，一次找left一次找right
- 具体边界条件列一列看一看奇数偶数。
- 找左边界的时候，=放在right那，right大胆移 left = mid+1小心移
1,8,8,8,8,8,8,8,8最后分析一下1,81,8,8的情况，发现没有问题 最后left == right - 找右边界的时候, = 放在left那,left大胆移
1,8,8,8,8,8,8,8,9，分析一下，发现陷入循环，我们让mid靠右
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] >= target) {
right = mid;
}
}
32. 最长有效括号
思路1
- 正向逆向结合
- 左向右移动，筛出无效右括号
())()() - 右向左移动，筛出无效左括号
((((())()()
左向右有效括号长度:
1.为左括号，lcnt++，为右括号，rcnt++；
2.lcnt == rcnt； left有效括号 == cnt * 2；
3.rcnt > lcnt rcnt = lcnt = 0;
右向左同理
取max
思路2
正常人没法想出这种思路
stack<int> st;
st.push(-1);
int len = s.size();
int maxlen = 0;
int cntr = 0, cntl = 0;
for (int i = 0; i < len; ++i) {
if (s[i] == '(') {
st.push(i);
}
else {
st.pop();
if (st.empty()) {//只有新的无匹配右括号出现才会有空的情况
st.push(i);
}
else {
maxlen = max(maxlen, i - st.top());
}
}
}
栈底是最后一个没有被匹配的右括号的下标
42. 接雨水
思路1
- 动态规划，交叉区域
思路2
- 移动最短边
31. 下一个排列
思路：
三个步骤
1.找到从右往左的第一对降序pair
2.找到右侧第一个比left大的数，swap
3.将left右侧翻转
