时间复杂度O(mn) 空间复杂度O(mn)。可以考虑使用滚动数组思想，将空间复杂度优化到O(n)「C++ 代码」 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A int整型vector * @param B int整型vector * @return int整型 */ int longestCommonSubarry(vector<int>& A, vector<int>& B) { int m = A.size(), n = B.size(); int...

时间复杂度O(NM|s|)，空间复杂度O(N)「C++ 代码」 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param dic string字符串vector * @return bool布尔型 */ bool wordDiv(string s, vector<string>& dic) { int n = s.length(); // dp[i]表示s前i个字符组成的字符串是否是给定字符串数组的子集 vector<bool&gt...

时间复杂度O(N), 空间复杂度O(1)。贪心思想：从左往右遍历，将所有的星号视作左括号，若此时左括号的数目仍然小于右括号，那么一定不成立。相似地再从右往左遍历一遍。最后若不为False, 则说明星号可以自适应转化得到True.[C++ 代码] class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ bool isValidString(string s) { int n = s.length(); int left = 0...

时间复杂度O(N), 空间复杂度O(N)。可以发现，状态转移方程中，dp[i]仅与dp[i-1]有关，所以我们可以利用滚动数组的思想进行简化达到O(1)的空间复杂度。「C++ 代码」 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> FindGreatestSumOfSubArray(vector<int>& array) { int n = arra...

判断字符串的子序列问题，一种做法是基于动态规划计算公共子序列，若公共子序列等于字符串S则说明S是T的子序列。这样做的解法时间复杂度是O(n2），但实际上不用这么麻烦，存在更简单容易理解的时间复杂度为O(N)的方法：【C++ 代码】 class Solution { public: /** * * * * @param S string字符串 * @param T string字符串 * @return bool布尔型 */ bool isSubsequence(string S, string T) { // 1. 记录字符串S和T的长度 int m = S.length(); int n =...

class Solution { vector<int> direction = {-1, 0, 1, 0, -1}; int dfs(vector<vector<int>>& matrix, int x, int y, vector<vector<int>>& dp){ // 如果不为零，说明在之前的递归中已经计算过以（x, y）为起点的最长路径，此时直接返回即可 if(dp[x][y]!=0) return dp[x][y]; // 1. 如果为零，首先赋值自身为1 dp[x][y] = 1; // 2. 分别从四个方向出发计算最...

最长回文子串（注：非子序列），考虑使用中心扩展法，时间复杂度O(n²)，空间复杂度O(1)。 int expand(string& A, int left, int right){ int n = A.length(); // 考虑边界处理 while(left>=0 && right<n && A[left]==A[right]){ --left; ++right; } return right-left-1; } int getLongestPalindrome(string A) { int res = 0; int n = A.length(); for(int i=0; ...