代码随想录算法训练营第36期DAY45

DAY45

1两数之和

[https://www.bilibili.com/video/BV1pt421u7qG/?spm_id_from=333.880.my_history.page.click&vd_source=baa5f3043be10f96febc0c68c5983df5]

出自B站热血编程系列，主要是复习双指针sum写法、重载比较运算符

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.         unordered_map<int,int> map;
5.         for(int i=0;i<nums.size();i++){
6.             if(map.find(target-nums[i])!=map.end()) return {map[target-nums[i]],i};
7.             map[nums[i]]=i;
8.         }
9.         return {};
10.     }
11. };

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.         vector<int> index(nums.size());
5.         for(int i=0;i<nums.size();i++) index[i]=i;
6.         sort(index.begin(),index.end(),[&](int a,int b){
7.             return nums[a]<nums[b];
8.         });
9.         int l=0,r=nums.size()-1;
10.         while(l<r){
11.             int sum=nums[index[l]]+nums[index[r]];
12.             if(sum==target){
13.                 return {index[l],index[r]};
14.             }
15.             if(sum<target) l++;
16.             else r--;
17.         }
18.         return{};
19.     }
20. };

朴素法：

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.         for(int i=0;i<nums.size();i++){
5.             for(int j=i+1;j<nums.size();j++){
6.                 int sum=nums[i]+nums[j];
7.                 if(sum==target) return {i,j};
8.             }
9.         }
10.         return {};
11.     }
12. };

1049最后一块石头的重量ii

据说和416分割等和子集很像，思考一下：分成了size()/2+size()%2个集合，集合内部的差要尽可能地小。之后就不会了，晕眩。

如果要吃透这题，看这篇题解

[ https://leetcode.cn/problems/last-stone-weight-ii/solutions/805162/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-5lfv/ ]

，他归纳了同类型的题，当然得先思考再看题解。

分成尽可能相等重量的两个石头堆。

1. class Solution {
2. public:
3.     int lastStoneWeightII(vector<int>& stones) {
4.         int sum=0;
5.         for(auto n:stones) sum+=n;
6.         int target=sum/2;
7.         vector<int> dp(1505,0);
8.         for(int i=0;i<stones.size();i++){
9.             for(int j=target;j>=stones[i];j--)
10.             dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
11.         }
12.         return sum-dp[target]-dp[target];
13.     }
14. };

494目标和

正数堆、负数堆。然后就不会了。

1. 回溯：

1. class Solution {
2. public:
3.     int count=0;
4.     void backtracking(vector<int>&nums,int target,int index,int cursum){
5.         if(index==nums.size()){
6.             if(cursum==target) count++;
7.         }
8.         //要加else 否则不终止且越界.
9.         else{
10.         backtracking(nums,target,index+1,cursum+nums[index]);
11.         backtracking(nums,target,index+1,cursum-nums[index]);
12.         }
13.     }
14.     int findTargetSumWays(vector<int>& nums, int target) {
15.         backtracking(nums,target,0,0);
16.         return count;
17.     }
18. };

1. 动态规划：

Left+right=sum;（无符号，仅集合）

Left-right=target;（手动给他上符号）

得出right=sum-left

进一步：left-sum+left=target;

所以：left=(target+sum)/2;

2*left=sum+target;“所以sum+target是偶数”是有解的保证。

之前的01背包：求的指定容量下的最大装载价值。这里不一样，他要求的是满足给定价值的选集合法有多少种？（装满容器有多少方法）

1. class Solution {
2. public:
3.     int findTargetSumWays(vector<int>& nums, int target) {
4.         int s=0;
5.         for(auto n:nums) s+=n;
6.         int left=(s+target)/2;
7.         if((s+target)%2==1) return 0;
8.         if(abs(target)>s) return 0;
9.         vector<int> dp(left+1,0);
10.         dp[0]=1;
11.         for(int i=0;i<nums.size();i++){
12.             for(int j=left;j>=nums[i];j--)
13.             dp[j]+=dp[j-nums[i]];
14.         }
15.         return dp[left];
16.     }
17. };

474一和零

满足两个维度的背包。三变量（物品个数[也就是子集的长度]、m个0，n个1）

Dp数组的含义：dp[i][j] 装满i个0，j个1，最多（max）装了多少个物品(dp[i][j])。

Res: dp[m][n]

放入当前物品，有x个0，y个1；dp[i-x][j-y]+1；

1. class Solution {
2. public:
3.     int findMaxForm(vector<string>& strs, int m, int n) {
4.         vector<vector<int>>dp(m+1,vector<int>(n+1,0));
5.         for(auto str:strs){
6.             int x=0,y=0;
7.             for(auto s:str){
8.                 if(s=='0') x++;
9.                 else y++;
10.             }
11.             for(int i=m;i>=x;i--){
12.                 for(int j=n;j>=y;j--)
13.                 dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
14.             }
15.         }
16.         return dp[m][n];
17.     }
18. };