bryce1010-ACM-Template
bryce1010-ACM-Template copied to clipboard
Bryce1010
Leetcode
第 178 场周赛
- [x] 5346. 二叉树中的列表
bfs+dfs - [ ] 5347. 使网格图至少有一条有效路径的最小代价
bfs+dfs最短路0-1BFS[题解]结论，复习树上搜索和图论
第 177场周赛
-
- 日期之间隔几天
-
- 验证二叉树
-
- 最接近的因数
-
- 形成三的最大倍数
第 176 场周赛
STL
- [ ] 10. 正则表达式匹配
- [x] (中等)Leetcode 17 电话号码的字母组合[problem]
- [x] (中等)Leetcode 22 括号生成[problem]
- [x] (中等)Leetcode 46 全排列[problem]
- [x] (中等)Leetcode 47 全排列II[problem]
动态规划
-
- 滚动数组
- 二维数组
-
[x] 72. 编辑距离 [problem]
-
[x] 85. 最大矩形 [problem] [[直方图O(N*N*M]] [[DP O(N*M)]]
-
[x] 91. 解码方法 [problem]
-
[x] 面试题 08.11. 硬币 [problem]
给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法 ? 完全背包, 对于硬币coins, 选择前coin个硬币构成的面值为i的数量能有多少种? dp[i]表示面值为i的数量;
-
[x] 983. 最低票价 [problem]
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
以天数作为状态, 转移方程为dp[i]=min(dp[i+1]+cost[0], min(dp[i+7]+cost[1], dp[i+30]+cost[2]) 然后采用记忆化搜索或者DP Table优化
01 背包
- [x] 416. 分割等和子集 [problem]
两个状态： 前i个数 和 当前和为j； 最终状态为n个数和为sum/2的状态
状态转移为 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]
双指针
-
[x] 12. (中等)leetcode 16. 最接近的三数之和[problem]
-
[x] 16. 最接近的三数之和
-
[x] 18. 四数之和
-
[x] 19. 删除链表的倒数第N个节点
-
[x] 3. 无重复字符的最长子串 [problem]
滑动窗口 利用一个数组存储滑动窗口内的元素的位置
二分
-
[ ] (困难)Leetcode 4. 寻找两个有序数组的中位数 [problem]
-
[x] (中等)Leetcode 29. 两数相除 [problem]
-
[x] (中等)Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置 [problem]
-
[x] (中等)Leetcode 50. Pow(x, n) [problem]
-
[x] (中等)Leetcode 74. 搜索二维矩阵 [problem]
-
[x] (中等)Leetcode 81. 搜索旋转排序数组 II [problem]
-
[ ] (中等)Leetcode 153. 寻找旋转排序数组中的最小值 [problem]
-
[ ] (困难)Leetcode 154. 寻找旋转排序数组中的最小值 II [problem]
-
[ ] (中等)Leetcode 162. 寻找峰值 [problem]
-
[x] 21. 合并两个有序链表 [problem]
-
[x] 23. 合并K个排序链表 [problem]
归并排序
Tree
- [x] 199. 二叉树的右视图 [problem]
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 先访问右儿子, 保存每层访问的第一个节点,就是题目要求的节点
- [x] 116. 填充每个节点的下一个右侧节点指针
填充 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则next 指针设置为 NULL。 层次序遍历
排序
- [ ] 面试题51. 数组中的逆序对 [problem]
求数组逆序对
左半部分指针left, 右半部分指针right, 当nums[left]<=nums[right]时, left右移 , 那么nums[left]> right左侧的部分,即为这一次排序过程这个数的逆序对; 所以cnt+=(right-mid-1);
这样时间复杂度为O(nlogn); 空间复杂度为O(n);
二进制
- [x] 面试题56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 a^a=0 a^0=0 由于a,b都只有一个, 所以异或和不为0;
那么肯定能找到一个二进制位, 这一位上a和b不同 那么 a=a^x1^x1^x2^x2.... 那么b=x1^x1^x2^x2....^b