LeetCode 刷题笔记（十）

这次主要是DP以及一些之前剩下的难题

ID: 70

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路历程:

做过，主要是为了复习一下DP思路

最主要的办法就是找规律

找出当前状态和前几个状态之间的联系

ID:198

也做过，思路和之前一样，主要是要判断当前这家要不要抢，以此迭代状态

ID:279

题目：

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路历程：

一开始就想到用DP，但是想不到该怎么遍历，后来看了眼题解，想通了

初始化的时候全部都赋成极大值，然后在DP过程中进行修改，每次状态转移时，都需要一个新的下标j来把关，实现减去一个个平方数

状态转移方程为: dp[i]=min(dp[i],dp[i-j*j]+1)

想通这个就没啥问题了，因为j不断变大，dp[i]会越来越小

answer:

class Solution {
public:
    int numSquares(int n) {
        vector<int>dp(10001,INT_MAX);
        dp[0]=0;
        for(int i=1;i<=100;i++){
            int p2=i*i;
            dp[p2]=1;
        }
        if(n==1)return 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j*j<i;j++){
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};

ID: 322

思路历程:

和上一道差不多，区别在于一个是用平方数，一个是给定数组

answer:

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

ID: 139

思路历程:

一开始只能想到简单的将字符串视为队列，然后每次找到相应下标就出队，但是没考虑到出队不一定符合答案要求...如["cars"]-----['car','ca','rs']

我看到都懵了一下

后来在想怎么用DP，一时半会儿想不出来，看了题解

将S整个看成了一个数组，DP则表示能否实现的状态

answer:

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

ID: 152

思路历程:

本来确实很简单，和 ID：53一样，状态转移方程：dp[i]=max(dp[i-1]*nums[i-1],nums[i-1])

但是出现了问题，就像 [-3,2,-3] 这样应该返回18，而上述的转移方程则会返回2，

因此我们需要考虑正负，同时记载最小值和最大值：

在遇到负数时，交换两者，
正数则正常

正常状态转移方程:

max_num=max(max_num*nums[i],nums[i]);
min_num=min(min_num*nums[i],nums[i]);

answer:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n =nums.size();
        if(n==1)return nums[0];
        int max_num=nums[0];
        int min_num=nums[0];
        int ans=nums[0];
        for(int i=1;i<n;i++){
            if(nums[i]<0)swap(max_num,min_num);
            max_num=max(max_num*nums[i],nums[i]);
            min_num=min(min_num*nums[i],nums[i]);
            ans=max(ans,max_num);
        }
        return ans;
    }
};

ID: 416

思路历程：

DP一开始真的很难想，甚至想不到怎么进行状态转移

后来想到提前拿到总和，状态转移就知道了

因为和上面的字符串一样，就是下标能不能到达的问题

但是问题又出现了，就是如果我正向往后一次次遍历的话

会出现重复使用的问题，比如我[1,5,11,5]

如果正向遍历，重复使用1那所有值都能走到了

这样就要考虑回溯，很麻烦

优质解答是反向遍历，这样可以保证在检查DP时，当前num没有被使用过

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i=0;i<nums.size();i++)sum+=nums[i];
        if(sum%2==1)return false;
        int mid=sum/2;
        vector<bool>dp(mid+1,0);
        dp[0]=1;
        for(int num:nums){
            for(int i = mid;i>=num;i--){
                if(dp[mid])return true;
                dp[i]=dp[i]||dp[i-num];// 从后往前就不需要回溯了
                // 从前往后需要进行回溯，不然反复使用 1 所有值都能到达
                /* 
                * 1 dp[1]=ture 
                * 5 dp[5] dp[6]
                * 11 dp[11]
                */
            }
        }

        return dp[mid];
    }
};

ID: 32

思路历程：

一开始想到了DP，但是忘记了嵌套括号也有效如(()())

后来想到判断的时候，可以加一种情况（之前只有判断()）

可以再加一种 ))

这样可以实现嵌套的判断，状态转移方程为

dp[i]=dp[i-1]+2+(i-dp[i-1] >=2?dp[i-dp[i-1]-2]:0);

answer:

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int>dp(30001,0);
        int ans=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==')'){
                if(i-1<0)continue;
                if(s[i-1]=='('){ // '()'
                    dp[i]=i>=2?dp[i-2]+2:2;
                }else if(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='('){ // '))'
                    dp[i]=dp[i-1]+2+(i-dp[i-1] >=2?dp[i-dp[i-1]-2]:0);
                }
                ans=max(ans,dp[i]);
            }
        }
        return ans;
    }
};

ID: 207

思路历程:

一开始就想到了判断环的存在，来实现是否能完成

环的判断一开始想着用set，每次一条路径走完就清空，如果有重复有返回false

全部路径走完就返回true

后来想用拓扑排序实现：队列和入度

本来就是图论章节，拓扑排序和DFS也很像，用队列来实现，用入度来判断是否入队

answer:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int>num_map(numCourses,0);//入度
        unordered_map<int,vector<int>> order;
        for(auto c:prerequisites){
            num_map[c[0]]++;
            order[c[1]].push_back(c[0]);   
        }
        int count =0;
        queue<int>que_num;
        for(int i=0;i<numCourses;i++){
            if(num_map[i]==0){
                que_num.push(i);
                count++;
            }
        }
        while(!que_num.empty()){
            int tmp = que_num.front();que_num.pop();//取出入度为0的数
            for(auto c:order[tmp]){
                num_map[c]--;//入度减少
                if(num_map[c]==0){
                    que_num.push(c);
                    count++;
                }
            }
        }
        return count==numCourses;
    }
};

DP小结

所有数据都看成状态数组

状态初始化
状态转移方程

简单来说就是找规律 :-D

下午OC辣！！！

offer快来！！！

题下次再接着刷，学Go去了！