week7

2021-09-06

如题目＞▽＜

零钱兑换（lc）

链接：

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array//

思路：

dp, 当前i面额能拼出的最小值为之前i-所有面值+1中最小的那个，0元可以0次拼出f[0]=0，其余全初始化为正无穷，意义为拼不出来

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

游戏中弱角色的数量（lc）

链接：

https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game/

思路：

由于我们需要计算弱角色的数量，所以应当先把其中一个属性降序排下序，以供防御力的比较。由于我们想要顺序遍历，记录防御力最大值，所以遍历的时候前面的防御力不应当大于后面的，因此防御力需要升序排序

int numberOfWeakCharacters(vector<vector<int>>& A) {
        sort(A.begin(),A.end(),[](vector<int>&a,vector<int>&b){
            if(a[0]==b[0])return a[1]<b[1];
            else return a[0]>b[0];
        });
        int mx=-1;
        int res=0;
        for(int i=0;i<A.size();i++){
            if(A[i][1]<mx){
                res++;
            }
            if(A[i][1]>mx){
                mx=A[i][1];
            }
        }
        return res;
    }

不同路径（lc）

链接：

https://leetcode-cn.com/problems/unique-paths/

思路：

最后一步取决于左边和上边的值的和，左边界和上边界全为1，

int uniquePaths(int m, int n) {
        long long mp[m+1][n+1];
        for(int i=0;i<=m;i++){
            mp[i][0]=1;
        }
        for(int i=0;i<=n;i++){
            mp[0][i]=1;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                mp[i][j]=mp[i-1][j]+mp[i][j-1];
            }
        }
        return mp[m-1][n-1];
    }

跳跃游戏（lc）

链接：

https://leetcode-cn.com/problems/unique-paths/

思路：

最后一步取决于之前能否跳过来，如果之前本身能跳过来，并且之前的位置加上对应的大小能跳过来就标记为ture

bool canJump(vector<int>& nums) {
        int res=0,n=nums.size();
        for(int i=0;i<n;i++){
            if(i<=res)
            res=max(res,nums[i]+i);
        }
        return res>=n-1;
    }

分割平衡字符串（lc）

链接：

https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/

思路：

贪心，平衡就记录

int balancedStringSplit(string s) {
        int l=0,r=0;
        int cnt=0;
        for(int i=0;i<s.size();i++){
            
            if(s[i]=='L'){
                l++;
            }
            else{
                r++;
            }
            if(l==r&&l!=0){
                cnt++;
                l=0;r=0;
            }
        }
        return cnt;
    }

解码方法（lc）

链接：

https://leetcode-cn.com/problems/decode-ways/

思路：

动态规划，前i个字符串的解码方法为前i-1个字符串的解码方法（第i-1个字符满足1~~9）加上前i-2个字符串的解码方法（第i-1,i-2个字符组成的数字在10~~26之间）

int balancedStringSplit(string s) {
        int l=0,r=0;
        int cnt=0;
        for(int i=0;i<s.size();i++){
            
            if(s[i]=='L'){
                l++;
            }
            else{
                r++;
            }
            if(l==r&&l!=0){
                cnt++;
                l=0;r=0;
            }
        }
        return cnt;
    }

最长上升连续子序列（lc）

链接：

https://www.lintcode.com/problem/397/

思路：

动态规划，每相邻两个数递增就让dp[i]=dp[i-1]+1，如果不递增，则设为1，由于题意实际是连续递增或递减中的最长连续子序列，所以需要将数组在倒过来一下。
因为我们的dp数组操作只有i和i-1，所以我们可以用一个长度为2的滚动数组来优化空间

int find(vector<int> &A ,int n){
        int res = 1;
        int f[2];
        int old = 0, now = 0;
        for(int i = 0 ;i < n ; i++){
            old = now;
            now = 1 - now;
            f[now]=1;
            if(i>0&&A[i] > A[i-1]){
                f[now] = f[old] + 1;
            }
            if(f[now] > res){
                res = f[now];
            }
        }
        return res;
    }
    int longestIncreasingContinuousSubsequence(vector<int> &A) {
        // write your code here
        int n = A.size();
        if (n == 0)
        return 0;
        int mx = find(A,n);

        int l = 0, r = n-1;
        while(l < r){
            int t = A[l];
            A[l] = A[r];
            A[r] = t;
            l++;
            r--;
        }
        mx = max(mx,find(A,n));
        return mx;
    }

最小路径和（lc）

链接：

https://leetcode-cn.com/problems/minimum-path-sum/

思路：

动态规划，上面和左面的路径一定是笔直走过来的，所以一直累加，f[i][j]的最短路径是左面或者上面其中某一个的最短路径和加上当前位置的长度，因为只涉及两行的动态规划，所以可以设计成两行的滚动数组

int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int dp[2][n];
        int old=1,now=0,t1,t2;
        for(int i=0;i<m;i++){
                old=now;
                now=1-now;
            for(int j=0;j<n;j++){
                if(i==0&&j==0){
                    dp[now][j]=grid[i][j];
                    continue;
                }
                if(i>0){
                    t1=dp[old][j];
                }
                else{
                    t1=INT_MAX-1;
                }
                if(j>0){
                    t2=dp[now][j-1];
                }
                else{
                    t2=INT_MAX-1;
                }
                if(t1<t2){
                    dp[now][j]=t1+grid[i][j];
                }
                else{
                    dp[now][j]=t2+grid[i][j];
                }
            }
        }
        return dp[now][n-1];
    }

滑动窗口最大值（lc）

链接：

https://leetcode-cn.com/problems/sliding-window-maximum/

思路：

单调队列，将队列长度维护在k以内，保证队列的头部是当前区间内最大的值，要插入新值，需要与队列后端的元素进行比较，如果后端元素较小则需要弹出，保证
队列是单调递减的

vector<int> maxSlidingWindow(vector<int>& A, int k) {
        int n = A.size();
        deque<int> dq;
        vector<int> res;
        for (int i = 0 ;i < n; i++){
            if(!dq.empty()&&i-dq.front()>=k){
                dq.pop_front();
            }
            while(!dq.empty()&&A[dq.back()]<A[i]){
                dq.pop_back();
            }
            dq.push_back(i);
            if(i>=k-1)
            res.push_back(A[dq.front()]);
        }
        return res;
    }