class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 计算最大收益 * @param prices int整型vector 股票每一天的价格 * @return int整型 */ int maxProfit(vector<int>& prices) { // write code here // 升序段两端为买卖点 int len = prices.size(); int start = 0; int ans = 0; for(int i=1; i<len; ++i) { if(...

#include <climits> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型vector * @return int整型 */ int maxProfit(vector<int>& prices) { // write code here // 方法一：双重遍历 // 方法二：直接遍历，min_num为[0,i]之间的最小值，max_num保存i能获得的最大利润； in...

class Solution { public: int rob(vector<int>& nums) { //dp[i]表示长度为i+1的数组，最多能偷取多少钱 vector<int> dp(nums.size(), 0); //选择偷了第一家 dp[0] = nums[0]; //最后一家不能偷 for(int i = 1; i < nums.size(); i++) { if(i==1) dp[i] = max(dp[i - 1], nums[i]); else //对于每家可以选择偷或者不偷 dp[i] = max(dp[i - 1], nums[...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int rob(vector<int>& nums) { // write code here int n = nums.size(); if(n==0) return 0; vector<int> dp(n,0); dp[0] = nums[0]; for(int i=1; i&lt...

class Solution { public: int longestValidParentheses(string s) { int res = 0; //长度为0的串，返回0 if(s.length() == 0) return res; //dp[i]表示以下标为i的字符为结束点的最长合法括号长度 vector<int> dp(s.length(), 0); //第一位不管是左括号还是右括号都是0，因此不用管 for(int i = 1; i < s.length(); i++){ //取到左括号记为0，有右括号才合法 if(s[i] == ')'){ //情况一：如...

#include <string> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串vector */ vector<string> restoreIpAddresses(string s) { // write code here vector<string> ans; int len = s.size(); if(len>12)...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A string字符串 * @return int整型 */ bool huiwen(string t_A) { int l=0, r=t_A.size()-1; while(l<r) { if(t_A[l]!=t_A[r]) return false; ++l; --r; } return true; } int getLongestPalindrome(string A) { ...

#include <algorithm> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型 */ int FindGreatestSumOfSubArray(vector<int>& array) { // write code here // 有点像股票买卖，不对，不一样 if(array.empty()) return 0; int ...

class Solution { public: int LIS(vector<int>& arr) { if(arr.empty()) return 0; //设置数组长度大小的动态规划辅助数组 vector<int> dp(arr.size(), 1); int res = 1; for(int i = 1; i < arr.size(); i++){ for(int j = 0; j < i; j++){ //可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1 if(arr[i] > arr[j] &&am...

// 动态规划 #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 解码 * @param nums string字符串 数字串 * @return int整型 */ int solve(string nums) { // write code here int len = nums.size(); vector<int> dp(len,0); for(int i=0; i<len; ++i) { if(i==0) { if(nums[i...

方法一：递归回溯 // 超时 用例通过率：50.00% #include <algorithm> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ int dfs(vector<vector<int> >& matrix, int m, int n) {...

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param m int整型 * @param n int整型 * @return int整型 */ int uniquePaths(int m, int n) { // write code here // 动态规划 vector<vector<int>> dp(m,vector<int>(n,1)); for(int i=1; i<m; ++i) { fo...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ string LCS(string str1, string str2) { // write code here int n=str1.size(); int m=str2.size(); string str=&qu...

class Solution {public:int minCostClimbingStairs(vector<int>& cost) {//dp[i]表示爬到第i阶楼梯需要的最小花费vector<int> dp(cost.size() + 1, 0);for(int i = 2; i <= cost.size(); i++)//每次选取最小的方案dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);return dp[cost.size()];}};