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

时间:2024-06-01 13:31:37

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<inttwoSum(vector<int>& nums, int target) {
  4.         unordered_map<int,intmap;
  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<inttwoSum(vector<int>& nums, int target) {
  4.         vector<intindex(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<inttwoSum(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<intdp(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==1return 0;
  8.         if(abs(target)>s) return 0;
  9.         vector<intdp(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. };