LeetCode冲刺：Day2

发布于 2022-11-09  35 次阅读

今日总结

动态规划的学习今天算结束了，后续每天做一两道保持手感应该就行了。明天开始看看贪心or回溯吧。

不知道老师出题范围是多大，感觉什么类型的算法都得看点，两周还是有点紧。

下周是市场机制设计pre+交作业，信安考试。周末也要抽时间弄弄。

1. 不同的二叉搜索树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

先提交两次，观察在4和5时对应的种数。

发现每次插入新节点，无非是将原有的i-1个节点排列组合，于是得出状态转移方程。

代码

#include <vector>

using std::vector;

class Solution {
public:
    int numTrees(int n) {
        if (n<=2) return n;
        vector<int> dp(n+1,0);
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for (int i=3;i<=n;++i) {
            for (int j=0;j<i;++j) {
                dp[i]+=dp[j]*dp[i-1-j];
            }
        }
        return dp[n];
    }
};

时间0ms，空间超过73.25%。

代码随想录在文档里写的：

这道题⽬虽然在⼒扣上标记是中等难度，但可以算是困难了！

那看来写了半小时也是情有可原哈哈。

2. 分割等和子集

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

转化为01背包问题。

实际上可以再抽象一点：

给定一个上限capacity，一个元素集合items，要从items中选取元素使其满足，不超过capacity且某种属性和最大。

这类问题都可以用背包问题的思想解决。

代码

#include <vector>
#include <algorithm>

using std::max;
using std::vector;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int> dp(10001,0);
        int sum=0;
        for (int num:nums) sum+=num;
        if (sum%2==1) return false;
        int target=sum/2;
        for (int i=0;i<nums.size();++i) {
            for (int j=target;j>=nums[i];--j) {
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
};

3. 最后一块石头的重量 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

虽然这里是要求最小剩余重量，但也可以转化为上一题中的分割子集使得差距最小。

代码

#include <vector>
#include <algorithm>

using std::vector;
using std::max;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        if (stones.size()==1) return stones[0];
        vector<int> dp(15001,0);
        int sum=0;
        for (int stone:stones) sum+=stone;
        int target=sum/2;
        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-2*dp[target];
    }
};

4. 目标和

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

依然转换为背包，但状态转换方程的逻辑变了。不要生搬硬套公式，要先理解设定。

代码

#include <vector>
#include <algorithm>

using std::vector;
using std::max;

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if (nums.size()==1&&(nums[0]+target!=0&&nums[0]!=target)) return 0;
        vector<int> dp(1001,0);
        int sum=0;
        dp[0]=1;
        for (int num:nums) sum+=num;
        if ((sum+target)%2==1) return 0;
        int x = (sum+target)/2;
        for (int i=0;i<nums.size();++i) {
            for (int j=x;j>=nums[i];--j) {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[x];
    }
};

5. 一和零

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

01背包的扩展——二维01背包。这个二维是物品重量二维，因此在遍历物品时需要两层循环。

代码

#include <vector>
#include <string>
#include <algorithm>

using std::vector;
using std::string;
using std::max;

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for (string str:strs) {
            int zeroNum=0,oneNum=0;
            for (char c:str) {
                if (c=='0') ++zeroNum;
                else ++oneNum;
            }
            for (int i=m;i>=zeroNum;--i) {
                for (int j=n;j>=oneNum;--j) {
                    dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }

        }
        return dp[m][n];
    }
};

6. 零钱兑换 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

物品个数无限，求固定重量的组合数，典型的完全背包问题。

代码

#include <vector>

using std::vector;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0]=1;
        for (int i=0;i<coins.size();++i) {
            for (int j=coins[i];j<=amount;++j) {
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

居然从看到题开始五分钟就写完了，感动。希望老师也考这个难度吧hh。

7. 组合总和 Ⅳ

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

完全背包，但求的是排列书，所以外层遍历背包，内层遍历物品。

有一个小问题是测试用例里有相加超过int上限的数据，所以要加个限制。

除了这个小限制都是自己写的，这应该也算独立完成吧。

代码

#include <vector>

using std::vector;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,0);
        dp[0]=1;
        for (int j=0;j<=target;++j) {
            for (int i=0;i<nums.size();++i) {
                if (j>=nums[i] && dp[j]<__INT_MAX__-dp[j-nums[i]]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
};

8. 零钱兑换

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

稍微有点特殊，因为递推用的是最小值，所以初始化时候应该初始为最大值，这个地方卡住了。

代码

#include <vector>
#include <algorithm>
using std::vector;
using std::min;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for (int i=0;i<coins.size();++i) {
            for (int j=coins[i];j<=amount;++j) {
                if (dp[j-coins[i]]!=INT_MAX) dp[j] = min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==INT_MAX?-1:dp[amount];
    }
};

9. 完全平方数

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

类似上一题，也是递推用最小的。不知道怎么回事，运行用时略长。

答案的优化在两处：

  1. 将i的上限改为i的平方小于等于n。这里确实疏忽了，没必要把i设成最大的100。
  2. 去掉更新dp时的溢出判断。这里有点迷惑，上一题需要溢出判断，这题又不需要。下次评论问问。

代码

#include <vector>
#include <algorithm>
using std::vector;
using std::min;
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for (int i=0;i<=100;++i) {
            for (int j=i*i;j<=n;++j) {
                if (dp[j-i*i]!=INT_MAX) dp[j]=min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};

10. 单词拆分

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

比较绕。把字符串视作背包，单词视作物品。看能不能填满。dp数组存储布尔值。当当前位置是true，且从下一个位置起始的一段字符串在词典内，则到这个字符串的末尾也是true。

代码

#include <vector>
#include <string>
#include <unordered_set>
using std::vector;
using std::string;
using std::unordered_set;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1,false);
        unordered_set<string> us(wordDict.begin(),wordDict.end());
        dp[0]=true;
        for (int j=1;j<=s.size();++j) {
            for (int i=0;i<j;++i) {
                if (dp[i]&&(us.find(s.substr(i,j-i))!=us.end())) dp[j]=true;
            }
        }
        return dp[s.size()];
    }
};

11. 打家劫舍

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

脑子没转过来……

代码

#include <vector>
#include <algorithm>

using std::vector;
using std::max;

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size()==1) return nums[0];
        vector<int> dp(nums.size(),0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for (int i=2;i<nums.size();++i) {
            dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
};

12. 打家劫舍 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

爽到了哈哈。

前面n-1个值是没有变化的，问题在于最后一个值。如果偷第n家，那第一家就不能偷，如果不偷第n家，那么值就是第n-1家的值。

后者照常算。

前者可以通过删掉第一家，变成一个新数组，照原有方法重新算出一个终值，也就是偷第n家产生的收益。

前后两个数取最大，即为所求。

性能也没问题，时间0ms，空间超过50%。

代码

#include <vector>

using std::vector;
using std::max;

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size()==1) return nums[0];
        if (nums.size()==2) return max(nums[0],nums[1]);
        //删掉nums[0]计算一个终值
        vector<int> nums2(nums);
        nums2.erase(nums2.begin());
        vector<int> dp2(nums2.size());
        int fn;
        if (nums2.size()==2) fn = max(nums2[0],nums2[1]);
        else {
            dp2[0]=nums2[0];
            dp2[1]=max(nums2[0],nums2[1]);
            for (int i=2;i<nums2.size();++i) {
                dp2[i] = max(dp2[i-1],dp2[i-2]+nums2[i]);
            }
            fn=dp2[nums2.size()-1];
        }

        vector<int> dp(nums.size());
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for (int i=2;i<nums.size()-1;++i) {
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return max(fn,dp[nums.size()-2]);

    }
};