DAY45
1两数之和
[https://www.bilibili.com/video/BV1pt421u7qG/?spm_id_from=333.880.my_history.page.click&vd_source=baa5f3043be10f96febc0c68c5983df5]
出自B站热血编程系列,主要是复习双指针sum写法、重载比较运算符
- class Solution {
- public:
- vector<int> twoSum(vector<int>& nums, int target) {
- unordered_map<int,int> map;
- for(int i=0;i<nums.size();i++){
- if(map.find(target-nums[i])!=map.end()) return {map[target-nums[i]],i};
- map[nums[i]]=i;
- }
- return {};
- }
- };
- class Solution {
- public:
- vector<int> twoSum(vector<int>& nums, int target) {
- vector<int> index(nums.size());
- for(int i=0;i<nums.size();i++) index[i]=i;
- sort(index.begin(),index.end(),[&](int a,int b){
- return nums[a]<nums[b];
- });
- int l=0,r=nums.size()-1;
- while(l<r){
- int sum=nums[index[l]]+nums[index[r]];
- if(sum==target){
- return {index[l],index[r]};
- }
- if(sum<target) l++;
- else r--;
- }
- return{};
- }
- };
朴素法:
- class Solution {
- public:
- vector<int> twoSum(vector<int>& nums, int target) {
- for(int i=0;i<nums.size();i++){
- for(int j=i+1;j<nums.size();j++){
- int sum=nums[i]+nums[j];
- if(sum==target) return {i,j};
- }
- }
- return {};
- }
- };
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/ ]
,他归纳了同类型的题,当然得先思考再看题解。
分成尽可能相等重量的两个石头堆。
- class Solution {
- public:
- int lastStoneWeightII(vector<int>& stones) {
- int sum=0;
- for(auto n:stones) sum+=n;
- int target=sum/2;
- vector<int> dp(1505,0);
- for(int i=0;i<stones.size();i++){
- for(int j=target;j>=stones[i];j--)
- dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
- }
- return sum-dp[target]-dp[target];
- }
- };
494目标和
正数堆、负数堆。然后就不会了。
- 回溯:
- class Solution {
- public:
- int count=0;
- void backtracking(vector<int>&nums,int target,int index,int cursum){
- if(index==nums.size()){
- if(cursum==target) count++;
- }
- //要加else 否则不终止且越界.
- else{
- backtracking(nums,target,index+1,cursum+nums[index]);
- backtracking(nums,target,index+1,cursum-nums[index]);
- }
- }
- int findTargetSumWays(vector<int>& nums, int target) {
- backtracking(nums,target,0,0);
- return count;
- }
- };
- 动态规划:
Left+right=sum;(无符号,仅集合)
Left-right=target;(手动给他上符号)
得出right=sum-left
进一步:left-sum+left=target;
所以:left=(target+sum)/2;
2*left=sum+target;“所以sum+target是偶数”是有解的保证。
之前的01背包:求的指定容量下的最大装载价值。这里不一样,他要求的是满足给定价值的选集合法有多少种?(装满容器有多少方法)
- class Solution {
- public:
- int findTargetSumWays(vector<int>& nums, int target) {
- int s=0;
- for(auto n:nums) s+=n;
- int left=(s+target)/2;
- if((s+target)%2==1) return 0;
- if(abs(target)>s) return 0;
- vector<int> dp(left+1,0);
- dp[0]=1;
- for(int i=0;i<nums.size();i++){
- for(int j=left;j>=nums[i];j--)
- dp[j]+=dp[j-nums[i]];
- }
- return dp[left];
- }
- };
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;
- class Solution {
- public:
- int findMaxForm(vector<string>& strs, int m, int n) {
- vector<vector<int>>dp(m+1,vector<int>(n+1,0));
- for(auto str:strs){
- int x=0,y=0;
- for(auto s:str){
- if(s=='0') x++;
- else y++;
- }
- for(int i=m;i>=x;i--){
- for(int j=n;j>=y;j--)
- dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
- }
- }
- return dp[m][n];
- }
- };