2022-01-0733阅读🍒LeetCode剑指 Offer 14- I. 剪绳子（DP）题目思路：DP定义dp[n]表示长度为n的绳子最大乘积。一段长度为n的绳子，切第一刀共有n-1种情况，即第一刀绳子的长度为1, 2, 3....n-1。然后再在这些绳子中继续切寻找最大值，切出来...
2022-01-0527阅读🍒LeetCode剑指 Offer 11. 旋转数组的最小数字题目思路可以遍历直接求。也可以采用二分法，定义两个指针，一个指向开头，一个指向末尾。如果中间值处于前面的递增子数组，那么中间值应该大于等于最左边的值，那么最小值应该在中间值的右边。如果中间值处于...
2022-01-0437阅读🍒LeetCode剑指 Offer 03. 数组中重复的数字题目思路1.sort后遍历找到一样的返回。时间复杂O(nlogn)。2.用哈希表遍历如果这个数字为key的value为0则+1，不为0直接return。时间复杂度O(n)，空间复杂度O(n)。3...
2022-01-0128阅读🍒LeetCodeLC *516. 最长回文子序列（DP）题目思路二维DP首先确定dp[i][j]含义：字符串s[i...j]的最长回文子序列。转移方程：如果知道dp[i+i][j-1]能不能知道dp[i][j]。图中dp[i+1][j-1] = 1，...
2021-12-3027阅读🍒LeetCodeLC *322. 零钱兑换（DP）题目思路经典DP。dp[i]：兑换i最少需要多少个硬币。确定基本状态：dp[0] = 0状态转移：想要得到amount需要的最少硬币，如果知道了dp[amount-1]的数量，那dp[amoun...
2021-12-2929阅读🍒LeetCodeLC 1995. 统计特殊四元组（哈希表）题目思路数据只有50，可以直接四层循环暴力过也可以使用哈希表，逆序遍历c，把每个d可能的数都存入哈希表中，然后判断a + b + c是否能在哈希表中找到对应的值。可以用数组代替哈希表func c...
2021-12-2846阅读🍒LeetCodeLC 39. 组合总和（回溯）题目思路这题可以直接用DFS暴力搜也可以过。可以采用回溯 + 剪枝缩短一下时间对于[2, 3, 6 ,7]可以让target减去每个数，然后依次减下去得到0这条路径就是一个答案。但是这样会产生四...
2021-12-2741阅读🍒LeetCodeKMP算法KMP为字符串匹配算法，在朴素匹配算法基础中，每当匹配失败匹配串就要回到开始匹配的地方，这样字符串大的话就会很慢，特别是"abcabcabcd" "abcd"这种。KMP利用前面匹配失败的串，比...
2021-09-19285阅读🍒LeetCodeLC* 650. 只有两个键的键盘（搜索）（动态规划）题目思路因为每次只有两个操作：复制或粘贴。可以用深搜把所有情况遍历。采用一个memo数组记忆化搜索class Solution { public: int INM = INT_MAX -...
2021-09-12216阅读🍒LeetCodeLC* 678. 有效的括号字符串（栈）题目思路创建两个栈left, star，分别存放')'和'*'的下标，当遇到')'时，先看left是否空，不空则pop，空则看star，star空直接返回false，不空pop。然后右括号匹配完...
