有个状态转移想不懂。唉今天状态好差。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 * @param pattern string字符串 * @return bool布尔型 */ bool match(string str, string pattern) { int len1 = str.size(), len2 = pattern.size...

这一个dp理解一开始有点问题，搞乱了。应该理解成相应长度比较好！ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ int editDistance(string str1, string str2) { int len1 = str1.size(), len2 = ...

隔了几天没写，唉思路速度都跟不上。果然这东西就是不能停 class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ vector<string> restoreIpAddresses(string s) { std::vector<std::string> res; // 找出三个点可能的位置三重循环暴力查找 int length = s.size(); ...

这道题我不理解，也不了解manacher算法。先这样吧，回头再看不浪费时间了。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A string字符串 * @return int整型 */ int getLongestPalindrome(string A) { int length = A.size(); // 源字符串全部变为偶数个字符，加上头两位。最后有指向回文串最右...

群里网友在讨论，自己也简单思考了一下，确实容易混乱

渐渐对动态规划有感觉了 class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { // dp[i] 表示结尾元素为i下标的子数组的和的最大值 // 最后一个不一定就是和最大值，因为子数组不一定取到最后一个元素 // 每次取子数组时，记录下最大值 int res = -200; std::vector<int> dp(array.size(), 0); // 假设每个元素都为子数...

不是很理解这个，再看看 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { if (arr.empty()) { return 0; } // dp[...

类似背包但又不是背包，涨知识了 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 最少货币数 * @param arr int整型vector the array * @param aim int整型 the target * @return int整型 */ int minMoney(vector<int>& arr, int aim) { // 为0，无需货币 if ...

考虑边界条件（鲁棒性） class Solution { public: /** * 解码 * @param nums string字符串 数字串 * @return int整型 */ int solve(string nums) { // dp[i] 表示长度为 i 的字符串有 多少种可能译码结果 if (nums.empty() || nums[0] == '0') { return 0; } int size = nums.size(); ...

开始慢慢习惯这种题目 class Solution { public: /** * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ int minPathSum(vector<vector<int> >& matrix) { int row = matrix.size(), col = matrix[0].size(); // dp[i][j] 代表i*j大小矩阵的最大...

数学解法不是很理解，能够画出来式子，但是转化为代码计算不是很理解 class Solution { public: /** * * @param m int整型 * @param n int整型 * @return int整型 */ // 到达最后一个结点有两种方式，一个向下一个向右这两种 // 使用递归从后面往前推容易理解 // 使用动态规划 // 运用数学 --> 最优解 int uniquePaths(int m, int n) { // 递归思路 if (m == 1 |...

字串和子序列不同，一旦中间一个不等，其当前长度最长公共字串就要变为0. 同时记录下公共字串的最大值以及对应的字符串末尾下标。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ // 字串...

这道题对我有点难度哈。 dp状态转移方程怎么确认？怎么根据dp状态转移进行字符串还原？ 这道题的难点 class Solution { public: /** * longest common subsequence * @param s1 string字符串 the string * @param s2 string字符串 the string * @return string字符串 */ // 找出最长公共子序列长度，同时记录该路径（下标） // 两个难点，一个状态转移，一个字符串组装 string LCS(st...

跳台阶的变种，加入了代价，需要计算最优 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cost int整型vector * @return int整型 */ int minCostClimbingStairs(vector<int>& cost) { // dp[i] 表示在该台阶之前的最小花费 std::vector<int> dp(cost...