2022-05-0880阅读🍒LeetCodeLC 442. 数组中重复的数据题目思路可以在输入数组中用数字的正负来表示该位置所对应数字是否已经出现过。遍历输入数组,给对应位置的数字取相反数,如果已经是负数,说明前面已经出现过,直接放入输出数组。class Solutio...
2022-01-07320阅读🍒LeetCode剑指 Offer 14- I. 剪绳子(DP)题目思路:DP定义dp[n]表示长度为n的绳子最大乘积。一段长度为n的绳子,切第一刀共有n-1种情况,即第一刀绳子的长度为1, 2, 3....n-1。然后再在这些绳子中继续切寻找最大值,切出来...
2022-01-05305阅读🍒LeetCode剑指 Offer 11. 旋转数组的最小数字题目思路可以遍历直接求。也可以采用二分法,定义两个指针,一个指向开头,一个指向末尾。如果中间值处于前面的递增子数组,那么中间值应该大于等于最左边的值,那么最小值应该在中间值的右边。如果中间值处于...
2022-01-04260阅读🍒LeetCode剑指 Offer 03. 数组中重复的数字题目思路1.sort后遍历找到一样的返回。时间复杂O(nlogn)。2.用哈希表遍历如果这个数字为key的value为0则+1,不为0直接return。时间复杂度O(n),空间复杂度O(n)。3...
2022-01-01276阅读🍒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-30294阅读🍒LeetCodeLC *322. 零钱兑换(DP)题目思路经典DP。dp[i]:兑换i最少需要多少个硬币。确定基本状态:dp[0] = 0状态转移:想要得到amount需要的最少硬币,如果知道了dp[amount-1]的数量,那dp[amoun...
2021-12-29253阅读🍒LeetCodeLC 1995. 统计特殊四元组(哈希表)题目思路数据只有50,可以直接四层循环暴力过也可以使用哈希表,逆序遍历c,把每个d可能的数都存入哈希表中,然后判断a + b + c是否能在哈希表中找到对应的值。可以用数组代替哈希表func c...
2021-12-28230阅读🍒LeetCodeLC 39. 组合总和(回溯)题目思路这题可以直接用DFS暴力搜也可以过。可以采用回溯 + 剪枝缩短一下时间对于[2, 3, 6 ,7]可以让target减去每个数,然后依次减下去得到0这条路径就是一个答案。但是这样会产生四...
2021-12-27231阅读🍒LeetCodeKMP算法KMP为字符串匹配算法,在朴素匹配算法基础中,每当匹配失败匹配串就要回到开始匹配的地方,这样字符串大的话就会很慢,特别是"abcabcabcd" "abcd"这种。KMP利用前面匹配失败的串,比...
2021-09-19579阅读🍒LeetCodeLC* 650. 只有两个键的键盘(搜索)(动态规划)题目思路因为每次只有两个操作:复制或粘贴。可以用深搜把所有情况遍历。采用一个memo数组记忆化搜索class Solution { public: int INM = INT_MAX -...