Open Bryce1010 opened 4 years ago
[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优化
两个状态: 前i个数 和 当前和为j; 最终状态为n个数和为sum/2的状态
状态转移为 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]
[ ] (困难)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]
归并排序
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 先访问右儿子, 保存每层访问的第一个节点,就是题目要求的节点
填充 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则next 指针设置为 NULL。 层次序遍历
求数组逆序对
左半部分指针left, 右半部分指针right, 当nums[left]<=nums[right]时, left右移 , 那么nums[left]> right左侧的部分,即为这一次排序过程这个数的逆序对; 所以cnt+=(right-mid-1);
这样时间复杂度为O(nlogn); 空间复杂度为O(n);
快慢指针找循环节
一个整型数组 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
第 178 场周赛
bfs+dfs
bfs+dfs
最短路
0-1BFS
[题解]结论,复习树上搜索和图论
第 177场周赛
第 176 场周赛