头像

脆脆鲨


访客:18688

离线:1个月前



脆脆鲨
9个月前
class Solution {
    public boolean isMatch(String s, String p) {
        int lens=s.length(),lenp=p.length();
        boolean[][] dp=new boolean[lens+1][lenp+1];
        dp[0][0]=true;
        //初始化p为""的状态,全是false直接跳过
        //初始化s为""的状态
        for(int i=1;i<=lenp;i++){
            if(p.charAt(i-1)=='*' && dp[0][i-2])//当前是*并且再前两个是匹配的状态
                dp[0][i]=true;
        }
        for(int i=1;i<=lens;i++){
            char sc=s.charAt(i-1);
            for(int j=1;j<=lenp;j++){
                char pc=p.charAt(j-1);
                if(pc=='*'){
                    char pcpre=p.charAt(j-2);
                    if(pcpre==sc || pcpre=='.'){
                        dp[i][j]=dp[i-1][j] || dp[i][j-2] || dp[i-1][j-2];
                    }else{
                        dp[i][j]=dp[i][j-2];
                    }
                }else if(pc=='.'){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    if(pc==sc)
                        dp[i][j]=dp[i-1][j-1];
                    else
                        dp[i][j]=false;
                }
            }
        }

        return dp[lens][lenp];
    }
}


活动打卡代码 AcWing 518. Coin Change 2

脆脆鲨
9个月前
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;
        for(int i=0;i<coins.length;i++){
            //枚举硬币的金额
            int v=coins[i];
            //在之前的基础上,加了一个新的金额,要重新访问不同的总金额
            for(int j=v;j<=amount;j++){
                dp[j]+=dp[j-v];
            }
        }
        //当硬币只有1元时,[1,amount]的方案数是xxx,当加了一个金额为2的硬币时,[2,amount]的方案数是yyy
        return dp[amount];
    }
}


活动打卡代码 AcWing 72. Edit Distance

脆脆鲨
9个月前
class Solution {
    public int minDistance(String word1, String word2) {
        int len1=word1.length(),len2=word2.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            dp[i][0]=dp[i-1][0]+1;
        }
        for(int i=1;i<=len2;i++){
            dp[0][i]=dp[0][i-1]+1;
        }
        for(int i=1;i<=len1;i++){
            char c1=word1.charAt(i-1);
            for(int j=1;j<=len2;j++){
                char c2=word2.charAt(j-1);
                if(c1==c2){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[len1][len2];
    }
}



脆脆鲨
9个月前
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        if(len<=1) return len;
        int[] dp=new int[len];
        int max=1;
        dp[0]=1;
        for(int i=1;i<len;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i])
                    dp[i]=Math.max(dp[i],dp[j]+1);
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}


活动打卡代码 AcWing 198. House Robber

脆脆鲨
9个月前
class Solution {
    public int rob(int[] nums) {
        int len=nums.length;
        int[] f=new int[len+1];//f[i]表示第i个不偷
        int[] g=new int[len+1];//g[i]表示第i个要偷
        for(int i=1;i<=len;i++){
            int v=nums[i-1];
            f[i]=Math.max(f[i-1],g[i-1]);
            g[i]=v+f[i-1];
        }
        return Math.max(f[len],g[len]);
    }
}


活动打卡代码 AcWing 91. Decode Ways

脆脆鲨
9个月前
class Solution {
    public int numDecodings(String s) {
        int len=s.length();
        //if(len<=1) return 1;
        int[] dp=new int[len+1];
        dp[0]=1;
        dp[1]=s.charAt(0)=='0'?0:1;
        for(int i=2;i<=len;i++){
            char prec=s.charAt(i-2);
            char curc=s.charAt(i-1);
            //先看一位的
            if(curc!='0') dp[i]+=dp[i-1];//就是前面一位的情况,为'0'的话是不可能单独一位的
            int tmp=(prec-'0')*10+(curc-'0');
            //System.out.println(dp[i]);
            if(tmp>=10 && tmp<=26) dp[i]+=dp[i-2];
        }
        return dp[len];
    }

}


活动打卡代码 AcWing 63. Unique Paths II

脆脆鲨
9个月前
class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        int rows=grid.length,cols=grid[0].length;
        int[][] dp=new int[rows][cols];
        dp[0][0]=1-grid[0][0];
        for(int i=1;i<rows;i++){
            if(grid[i][0]==1) break;
            dp[i][0]=dp[i-1][0];
        }
        for(int i=1;i<cols;i++){
            if(grid[0][i]==1) break;
            dp[0][i]=dp[0][i-1];
        }
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                if(grid[i][j]==0){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[rows-1][cols-1];
    }
}


活动打卡代码 AcWing 120. Triangle

脆脆鲨
9个月前
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int r=triangle.size()-2;r>=0;r--){
            List<Integer> curLine=triangle.get(r);
            List<Integer> nextLine=triangle.get(r+1);
            for(int c=0;c<curLine.size();c++){
                int nextmin=Math.min(nextLine.get(c),nextLine.get(c+1));
                //if(c-1>=0)
                    //nextmin=Math.min(nextmin,nextLine.get(c-1));
                curLine.set(c,curLine.get(c)+nextmin);
            }
        }
        return triangle.get(0).get(0);
    }
}


活动打卡代码 AcWing 53. Maximum Subarray

脆脆鲨
9个月前
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        int preMax=nums[0];
        int ans=preMax;
        for(int i=1;i<nums.length;i++){
            int curMax=Math.max(preMax+nums[i],nums[i]);
            ans=Math.max(ans,curMax);
            preMax=curMax;
        }
        return ans;
    }
}



脆脆鲨
9个月前
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int[] ans=new int[2];
        int N=edges.length;
        int[] father=new int[N+1];
        for(int i=1;i<=N;i++){
            father[i]=i;
        }
        for(int[] edge:edges){
            int a=edge[0],b=edge[1];
            int fa=find(father,a),fb=find(father,b);
            if(fa==fb){
                //属于同一个根,更新答案
                ans[0]=a;
                ans[1]=b;
            }
            //合并合并
            father[fa]=fb;
        }
        return ans;
    }

    private int find(int[] father,int x){
        while(father[x]!=x){
            father[x]=father[father[x]];
            x=father[x];
        }
        return x;
    }
}