vlambda博客
学习文章列表

输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

class Solution {public: int lengthOfLIS(vector<int>& nums) { int sz = nums.size(), ans = 0; vector<int> f(sz, 0); for(int i = 0; i < sz; i++) { int tmp = 1; for(int j = i-1; j >= 0; j--) { if(nums[i] > nums[j]) tmp = max(tmp, f[j]+1); }  f[i] = tmp; ans = max(ans, tmp); } return ans; }};

输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。

输入：text1 = "abc", text2 = "abc"输出：3解释：最长公共子序列是 "abc"，它的长度为 3。

输入：text1 = "abc", text2 = "def"输出：0解释：两个字符串没有公共子序列，返回 0。

class Solution {public: int longestCommonSubsequence(string text1, string text2) { int n = text1.length(), m = text2.length(); vector<vector<int> > f(n+1, vector<int>(m+1, 0)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { f[i][j] = max(f[i-1][j], f[i][j-1]); if(text1[i-1] == text2[j-1]) f[i][j] = max(f[i][j], f[i-1][j-1]+1); } } return f[n][m]; }};

[ [2], [3,4], [6,5,7], [4,1,8,3]]

class Solution {public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(), ans = 1e9; vector<vector<int> > f(n+1, vector<int>(n+1, 0)); for(int i = 0; i < n; i++) { for(int j = 0; j < triangle[i].size(); j++) { if(j == triangle[i].size()-1) f[i+1][j+1] = triangle[i][j] + f[i][j]; else if(j == 0) f[i+1][j+1] = triangle[i][j] + f[i][j+1]; else f[i+1][j+1] = triangle[i][j] + min(f[i][j+1], f[i][j]); if(i == n-1) ans = min(ans, f[i+1][j+1]); } } return ans; }};

for(int i = 0; i < n; i++) { for(int j = triangle[i].size()-1; j >= 0; j--) { f[j] = triangle[i][j] + min(f[j-1], f[j]); }}

class Solution {public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(), ans = 1e9; vector<int> f(n+1, 0); for(int i = 0; i < n; i++) { for(int j = triangle[i].size()-1; j >= 0; j--) { if(j == triangle[i].size()-1) f[j+1] = triangle[i][j] + f[j]; else if(j == 0) f[j+1] = triangle[i][j] + f[j+1]; else f[j+1] = triangle[i][j] + min(f[j+1], f[j]); if(i == n-1) ans = min(ans, f[j+1]); } } return ans; }};

输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。  偷窃到的最高金额 = 1 + 3 = 4 。

输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。  偷窃到的最高金额 = 2 + 9 + 1 = 12 。

class Solution {public: int rob(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> f(n, 0); for(int i = 0; i < n; i++) { f[i] = nums[i]; if(i >= 2) f[i] = max(f[i], f[i-2]+nums[i]); if(i >= 1) f[i] = max(f[i], f[i-1]); } return f[n-1]; }};

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]输出: 3 解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

class Solution {public: int maxEnvelopes(vector<vector<int>>& envelopes) { sort(envelopes.begin(), envelopes.end()); int n = envelopes.size(), ans = 0; vector<int> f(n, 0); for(int i = 0; i < n; i++) { int tmp = 0; for(int j = 0; j < i; j++) { if(envelopes[j][1] < envelopes[i][1] && envelopes[j][0] < envelopes[i][0]) tmp = max(tmp, f[j]); } f[i] = tmp + 1; ans = max(f[i], ans); } return ans; }};

输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')

class Solution {public: int minDistance(string word1, string word2) { int n = word1.length(), m = word2.length(); vector<vector<int> > f(n+1, vector<int>(m+1, 0)); for(int i = 1; i <= n; i++) f[i][0] = i; for(int j = 1; j <= m; j++) f[0][j] = j; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(word1[i-1] == word2[j-1]) f[i][j] = f[i-1][j-1]; else f[i][j] = min(f[i-1][j-1]+1, min(f[i][j-1]+1, f[i-1][j]+1)); } } return f[n][m]; }};