赞
踩
牛客链接:NC163 最长上升子序列(一)
定义长度为n的ans数组,用以保存以arr[i]结尾的最长严格上升子序列的长度。在每次获得最长序列的时候进行比较从而得到最终结果。结果满足复杂度要求。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { // write code here if(arr.size()==0) return 0; int res = 0; vector<int> ans(arr.size(),1); for(int i = 1; i < arr.size();++i){ for(int j =0; j<i; ++j){ if(arr[i]>arr[j]) { ans[i] = max(ans[i],ans[j]+1); } } res = max(ans[i] ,res); } return res; } };
牛客链接:NC164 最长上升子序列(二)
和上题目目的相同,只是更严格的要求了时间和空间复杂度。这里使用动态规划+二分的思路。
arr[i]用来存储尽可能小的值,因为小的值在后续中,更可能寻找到大的值从而使得长度增加。
遍历每个a[ i ],如果严格大于arr的最后一个数,则加入arr;
否则,找到找到大于等于他的最小的一个数,进行替换。
最终获得的arr的长度就是答案。
//实现1:手写二分 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& a) { // write code here int n=a.size(); if(n==0) return 0; vector<int> arr; arr.push_back(a[0]); for(int i =1;i<n;++i){ if(a[i]>arr.back()){ arr.push_back(a[i]); } else{ int l=0, r = arr.size()-1,mid; while(l<r){ //寻找>=的位置 也可以直接使用lower_bound() 替代 mid = (l+r)>>1; if(arr[mid]>=a[i]) r = mid; else l = mid+1; } arr[l] = a[i]; //更新长度为l的子序列的最小值 } } return arr.size(); } }; //实现2:调用函数 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& a) { // write code here vector<int> arr; for(int i : a){ vector<int>::iterator it = lower_bound(arr.begin(),arr.end(),i); if(it == arr.end()) arr.push_back(i); else *it = i; } return arr.size(); } };
牛客链接:NC165 最长公共子序列(一)
题解一:满足要求1
定义ans[][]二维数组,其中ans[i][j] 表示s1中第i个字符和s2中第j个字符为结尾的最长公共子序列。如果 s1[i-1]==s2[j-1],结果则为ans[i-1][j-1]+1,否则最大值在ans[i-1][j], ans[i][j-1]中产生。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * s1和s2最长公共子序列的长度 * @param s1 string字符串 * @param s2 string字符串 * @return int整型 */ int LCS(string s1, string s2) { // write code here vector<vector<int>> ans(s1.size()+1,vector<int>(s2.size()+1,0)); for(int i = 1;i<=s1.size();++i) for(int j = 1; j<=s2.size(); ++j) { if(s1[i-1] == s2[j-1]) ans[i][j] = ans[i-1][j-1] + 1; else ans[i][j] = max(ans[i-1][j], ans[i][j-1]); } return ans[s1.size()][s2.size()]; } };
解法2:进阶版
解法1中,建立的arr数组,其实每次都只是用了当前行和之前一行的数据,因此可以使用两个一维数组代替。
b数组用于保存上次的结果,a数组用于计算当前行的结果。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * s1和s2最长公共子序列的长度 * @param s1 string字符串 * @param s2 string字符串 * @return int整型 */ int LCS(string s1, string s2) { // write code here int n = min(s1.size(),s2.size()); vector<int> a(n+1,0); vector<int> b(n+1,0); if(s1.size()<s2.size()) swap(s1,s2); for(int i = 1; i<=s1.size();++i){ for(int j = 1; j<=s2.size(); ++j) { if(s1[i-1] == s2[j-1]) a[j] = b[j-1] + 1; else a[j] = max(a[j-1],b[j]); } swap(a, b); //交换a,b a = vector<int>(n+1,0); //初始化a为全0的数组 } return b[n]; } };
牛客链接:NC173 填充数组
对于数组中的每一段0,都可以是一个子问题:填充数为i,填充范围为j个数。
因此这里建立一个dp[i][j]二维数组,其中i表示待填充数的个数,j表示待填充位置的候选范围个数。
- 待填充个数为0时,dp[0][j] = 0;
- 候选范围为0时候,dp[i][0] = 0;
- 待填充个数为1时,dp[1][j] = j;
- 对于dp[i][j],可以拓展为与dp[i-1][j]和dp[i][j]的关系。 dp[i][j] = dp[i-1][j] + dp[i][j-1]:当前第i个数填充j个范围中最大数时,候选方案为 dp[i-1][j] ,当第i个数填充(0 - j-1)范围的时候,结果就是dp[i][j-1];
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param a int整型vector * @param k int整型 * @return int整型 */ const int MOD = 1e9+7; int FillArray(vector<int>& a, int k) { // write code here int n = a.size(); vector<vector<int>> dp(n+1,vector<int>(k+1,0)); for(int i = 0; i <= k; ++i){ dp[1][i] = i; } for(int i =2;i<=n; ++i){ for(int j = 1;j <=k; ++j){ dp[i][j] = (dp[i][j-1] + dp[i-1][j])%MOD; } } int i=0; long long res = 1; while(i<n){ //计算每一段的方案数,累乘 while(i<n&&a[i]!=0){ i++; } if(i==n) break; int left=i; //左区间 左端第一个为0的数 int low=i>0?a[i-1]:1; //候选的范围的低值 while(i<n&&a[i]==0){ i++; } int right=i; //右区间 右端最后一个为0的数 int high=i<n?a[i]:k; //候选的范围的高值 当为n的时候,表示最后一段到结尾的为0,就要考虑极限值。 res=(res*dp[right-left][high-low+1])%MOD; //累乘 } return res; } };
牛客链接:NC176 打家劫舍(一)
解法1
定义数组dp,其中dp[i]表示一共有i家能够偷到的最大值金额。其中dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]); 一共有i家能够偷到的最大金额需要考虑有i-1家和i-2家的情况。这两种情况有可能相同,但是i-2家的时候可以选择投第i家,i-1家不一定,有可能i-1家被偷了,那么第i家就不能偷了。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int rob(vector<int>& nums) { // write code here vector<int> dp(nums.size()+1,0); dp[1] = nums[0]; for(int i =2;i<=nums.size();++i){ dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]); } return dp[nums.size()]; } };
解法2
定义二维数组dp,其中dp[i][0]表示第i家不偷的情况能够获得的最大值,dp[i][1]表示偷第i家能够获得的最大值。其中dp[i][0] = max(dp[i-1][0],dp[i-1][1]),dp[i][1] = dp[i-1][0] + nums[i];
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int rob(vector<int>& nums) { // write code here vector<vector<int>> dp(nums.size(),vector<int>(2,0)); dp[0][0] = 0; dp[0][1] = nums[0]; for(int i =1;i<nums.size(); ++i){ dp[i][0] = max(dp[i-1][0],dp[i-1][1]); //不偷这家 dp[i][1] = dp[i-1][0] + nums[i]; //偷这家 } return max(dp[nums.size()-1][0],dp[nums.size()-1][1]); } };
优化:上述方法2每次考虑当前住户的时候其实只用到之前的一家的信息,所以可以使用两个变量来替代数组。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int rob(vector<int>& nums) { // write code here int last_notsteal = 0; int last_steal = nums[0]; int temp; for(int i =1;i<nums.size(); ++i){ temp = last_notsteal; last_notsteal = max(last_notsteal,last_steal); //不偷这家 last_steal = temp + nums[i]; //偷这家 } return max(last_notsteal,last_steal); } };
牛客链接:NC177 打家劫舍(二)
解法1
和(一)中一样,这里多了一个考虑环形的设计,导致我们需要考虑两种情况:
- 第一家偷,那就不能考虑最后一家,最后一家只能不偷,那么结果就是dp[n-1];
- 第一家不偷,那么初始化dp[1] = 0,最终结果为dp[n],取决于第n家偷不偷产生的最大值。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int rob(vector<int>& nums) { // write code here vector<int> dp(nums.size()+1,0); dp[1] = nums[0]; for(int i =2;i<nums.size();++i){ dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]); } int ans = dp[nums.size()-1]; dp[1] = 0; for(int i =2;i<=nums.size();++i){ dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]); } ans = max(ans,dp[nums.size()]); return ans; } };
解法2
同(一),使用两个变量来保存偷与不偷,考虑不同的初始化。只要第一家和最后一家不同时考虑。 考虑第一家到第n-1家和第2家到第n家两种情况最大值,必定不会出现头尾都偷的情况。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int rob(vector<int>& nums) { // write code here int last_notsteal = 0; int last_steal = nums[0]; int temp; for(int i =1;i<nums.size()-1; ++i){ temp = last_notsteal; last_notsteal = max(last_notsteal,last_steal); //不偷这家 last_steal = temp + nums[i]; //偷这家 } int res = max(last_notsteal,last_steal); last_notsteal = 0; last_steal = nums[1]; for(int i =2;i<nums.size(); ++i){ temp = last_notsteal; last_notsteal = max(last_notsteal,last_steal); //不偷这家 last_steal = temp + nums[i]; //偷这家 } res = max(res,max(last_notsteal,last_steal)); return res; } };
牛客链接:NC178 打家劫舍(三)
解法1:DFS
会超时。每次递归每个树的结点,考虑选择偷与不偷当前结点。最终取最大值就是结果,
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ int dfs(TreeNode* r,bool pick = true){ // 当前是否可选 if(r == NULL)return 0; // 当前不选 int ans = dfs(r->left) + dfs(r->right); // 选择当前 if(pick){ ans = max(ans, r->val + dfs(r->left,false) + dfs(r->right,false)); } return ans; } int rob(TreeNode* root) { return dfs(root); } };
解法2
利用深度遍历从最后一层到根判断是否偷该结点。
当偷该节点的时候,两个子节点都不偷。
当不偷该节点的时候,有四种可能:
- 两个根节点都不偷
- 两个根节点都偷
- 偷左节点,不偷右节点
- 偷右节点,不偷左节点
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ pair<int, int> dfs(TreeNode* root){ //其中first表示不偷,second表示偷 if(root == nullptr) return {0,0}; pair<int, int> left,right; left = dfs(root->left); right = dfs(root->right); //不偷的情况有四种 int no_steal = max(left.second+right.second,max(left.first+right.first,\ max(left.second+right.first,left.first+right.second))); int steal = left.first + right.first + root->val; return {no_steal,steal}; } int rob(TreeNode* root) { // write code here pair<int, int> ans = dfs(root); return max(ans.first, ans.second); } };
牛客链接:NC243 目标和
解法1:DFS
对于数组中每个元素都进行正负号的判断,最终数组到达尾部,且target为0时就是一个候选选项。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int dfs(vector<int>& nums, int target){ if(target == 0 && nums.size() == 0) return 1; if(nums.size() == 0) return 0; int ans = 0; vector<int> temp(nums.begin()+1,nums.end()); ans += dfs(temp, target+nums[0]); ans += dfs(temp, target-nums[0]); return ans; } int findTargetSumWays(vector<int>& nums, int target) { // write code here if(nums.size() == 0) return 0; int ans = 0; vector<int> temp(nums.begin()+1,nums.end()); ans += dfs(temp, target+nums[0]); ans += dfs(temp, target-nums[0]); return ans; } };
解法2:动态规划
我们定义整个数组分为两部分一部分为加上去的总值a,一部分为减去的总值b;其中a+b=sum,a-b = target; 所以2*a = sum+target(偶数);
题目就变成了从n个元素数组中选择n个数和为a的次数,这就形成了01完全背包问题。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int findTargetSumWays(vector<int>& nums, int target) { // write code here if(nums.size() == 0) return 0; int sum = 0; for(auto num: nums) sum+=num; if((sum+target)%2==1) return 0; int v = (sum+target)/2; vector<vector<int>> dp(nums.size()+1,vector<int>(v+1,0)); dp[0][0] = 1; for(int i =1; i<=nums.size(); ++i){ for(int j =0; j<=v; ++j){ dp[i][j] = dp[i-1][j]; if(j>=nums[i-1]) dp[i][j] += dp[i-1][j-nums[i-1]]; } } return dp[nums.size()][v]; } };
每行元素之和上一行有关,可使用滑动数组的方式去掉第一个维度
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int findTargetSumWays(vector<int>& nums, int target) { // write code here if(nums.size() == 0) return 0; int sum = 0; for(auto num: nums) sum+=num; if((sum+target)%2==1) return 0; int v = (sum+target)/2; vector<int> dp(v+1,0); dp[0]= 1; for(int i =0; i<nums.size(); ++i){ for(int j = v; j>=nums[i]; --j){ dp[j] += dp[j-nums[i]]; } } return dp[v]; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。