头像

cznczai


访客:2746

离线:4个月前



cznczai
8个月前

图片说明
图片说明

class Solution {
    public int strangePrinter(String s) {
            if(s.length()==0)return 0;
            int n = s.length();
            int dp[][] = new int [n][n];
            // for(int i = 0 ; i < n ; i++ ) {  //当然这一步可以放在下面for循环里面
            //  dp[i][i] = 1 ;  //每一步都是打印一次 也就是染一次 最坏情况
            // }
            for(int j =0 ; j < n; j++ ) { //开始到结尾的截断字符串长度   //上面没有注释 则 j = 1
                for(int i = 0 ; i + j < n ; i++) { //从第一位开始dp
                    dp[i][i+j] = 1 + j;      //最坏情况 i + f(i,j):(j - i + 1 )
                    for(int k = i ; k < i + j ; k++) {
                        int sum = dp[i][k] + dp[k+1][i+j] ;
                        if(s.charAt(k)==s.charAt(i+j)) {  //直接被覆盖 例如 abaa  所以 后面两个aa可以一起覆盖
                            sum--;
                        }
                        dp[i][j+i] = Math.min(dp[i][i+j], sum);
                    }
                }
            }
            return dp[0][n-1];
        }
}



cznczai
8个月前

leetcode 劝退题 花了7个小时 还算是基本能解出来 一些边界条件还是很模糊
尾扫描

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int k1 = (m+n)/2;
        int k2 = (m+n)/2+1;
        double value1 = find_num(k2, nums1 , nums2);
        if((m+n)%2 != 0) {
            return value1;
        }
        double value2 = find_num(k1, nums1 , nums2);
        return (value1+value2)/2;

    }
    public static double find_num(int k , int [] nums1 , int[] nums2) {
        double ans = 0;
        int m = nums1.length-1;
        int n = nums2.length-1;
        while(k>0&&m>=0&&n>=0) {
            k--;
            int temp1 = nums1[m];
            int temp2 = nums2[n];
            if(temp1>temp2) {
                ans = temp1;
                m--;
            }
            else {
                ans = temp2;
                n--;
            }
        }
        while(k>0&&m>=0) {
            ans = nums1[m];
            m--;
            k--;
        }
        while(k>0&&n>=0) {
            ans = nums2[n];
            n--;
            k--;
        }
        return ans ;
    }
}

二分

图片说明
第一步 思路有点问题 修改为 第k/2必定在矩阵里面
图片说明

图片说明

图片说明

图片说明

图片说明

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if(total%2==0) {
            int value1 = findKth(nums1 ,0 ,nums2 ,0 ,total/2+1);
            int value2 = findKth(nums1 ,0 ,nums2 ,0 ,total/2 );
            return (value1+value2)/2.0;

        }
        else 
            return findKth(nums1 ,0 ,nums2 ,0 ,total/2+1);
    }
    public static int findKth(int nums1[] , int i ,int []nums2 , int j ,int k) {
        if(nums1.length- i > nums2.length - j )return findKth(nums2, j, nums1, i, k);
        if(nums1.length == i)return nums2[j + k - 1];
        if(k==1)return Math.min(nums1[i],nums2[j]);
        int si = Math.min(i + k / 2,nums1.length);
        int sj = j + k /2 ;
        if(nums1[si-1]>nums2[sj-1]) {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else return findKth(nums1, si, nums2, j, k - (si - i));
        }
}



cznczai
8个月前

f[i,j] = f[i-1,j]+f[i-1,j-c]+f[i-1,j-2c]+f[i-1,j-3c]+f[i-1,j-4c]…
f[i-1,j-c] = f[i-1,j-c]+f[i-1,j-2c]+f[i-1,j-3c]+f[i-1,j-4c]…
f[i,j] = f[i - i , j ] + f[i-1 , j -c ]
j-c 的意义是除掉k个自己,所对应的值有多少种解法

先一个一个数字进行思考 通过循环来实现一个一个的数字进行考虑
第一个有几种
第二个有几种(需要减去第一个 当然减去的前提是能凑amount)
依次类推 每一个位置所对应的值都是能达到的该数的种数
虽然求的是amount 但是0~amount之间的数据值/位置都是有意义的 也就是 j++ 而不是 j+=coins[i]

 public int change(int m, int[] coins) {
        int len = coins.length;
        int f[] = new int [m+1];
        f[0] = 1;
        for(int i = 0 ; i < len;i++) {
            for(int j = coins[i] ; j <= m ; j++) {
                f[j] += f[j-coins[i]];  //连选多个的情况也有了
            }
        }
        return f[m];
    }



cznczai
8个月前

import java.util.Scanner;

//全局变量 -> 定义到堆里面  -> 都会被初始化为0
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int v[] = new int [n+1];
        int w[] = new int [n+1];
        for(int i = 1 ; i <= n ; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        System.out.println(zore_one_knapsack(v,w,n,m));
    }
    public static int zore_one_knapsack(int v[] , int w[] ,int n ,int m ) {
        int flag[][] = new int [n+1][m+1];
        for(int i = 1 ; i <= n ; i ++) {
            for(int j = 1 ; j <= m ; j ++) {
                if(j < w[i])
                    flag[i][j] = flag[i-1][j];    //有空间就选 因为是前i个有空间只能选
                else {                              // 没有空间就看不选第i件物品的价值,跟选了第i件物品的价值[得空出j-w[i]的空间]
                    int value1 = flag[i-1][j-w[i]] + v[i];
                    int value2 = flag[i-1][j];
                    flag[i][j] = Math.max(value1 , value2);
                }
            }
        }

        return flag[n][m];

    }

}



cznczai
9个月前

// 最简单通过的做法

class Solution {
    private boolean flag;

    public boolean makesquare(int[] nums) {
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            temp += nums[i];
        }
        if (nums.length == 0 || temp % 4 != 0)
            return false;
        int count[] = new int[4];
        Arrays.sort(nums);
        dfs(nums, count, nums.length-1,temp/4);
        return flag;
    }

    private void dfs(int[] nums, int[] count, int x,int avg) {
        if (x == -1) {
            for (int i = 0; i < 3; i++) {
                if (count[i] != count[i + 1])
                    return;
            }
            flag = true;
        } else {
            count[0] += nums[x];
            if(count[0]<=avg)dfs(nums, count, x - 1,avg);
            count[0] -= nums[x];
            count[1] += nums[x];
            if(count[1]<=avg)dfs(nums, count, x - 1,avg);
            count[1] -= nums[x];
            count[2] += nums[x];
            if(count[2]<=avg)dfs(nums, count, x - 1,avg);
            count[2] -= nums[x];
            count[3] += nums[x];
            if(count[3]<=avg)dfs(nums, count, x - 1,avg);
            count[3] -= nums[x];
        }
    }
}




cznczai
9个月前
class Solution {
    private List ls;
    private int n;
    private LinkedList path;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ls = new LinkedList<LinkedList<Integer>>();
        path = new LinkedList<Integer>();
        n = nums.length;
        Arrays.sort(nums);

        dfs(nums, 0);
        return ls;
    }

    private void dfs(int[] nums, int u) {
        if (u == n) {
            ls.add(path.clone());
            return;
        }
        int k = 0;
        while (u + k < n && nums[u + k] == nums[u])
            k++;

        for (int i = 0; i <= k; i++) {  //看看几个连续的数
            dfs(nums, u + k);
            path.add(nums[u]); //也就是连续加了多少次nums[u] 前后导致重复出现  递归变成nums[u]连续出现几次 也就是对象是一连串的数字而非一连串的数字中的一个一个
                                //而且是按顺序个数递增 所以不用考虑 2(1) 2(2) 和2(2) 2(1)元素位置上的变化
        }                       //只是求子集 所以每个数只考虑选不选 而不需考虑顺序
        for (int i = 0; i <= k; i++) //恢复现场 吐出来
            path.removeLast();
    }
}



cznczai
9个月前
class Solution {
    private int n;
    private List ls;
    private boolean[] bool;
    private LinkedList path;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        n = nums.length;
        ls = new ArrayList<LinkedList>();
        path = new LinkedList<Integer>();
        bool = new boolean[n];
        dfs(nums, 0);
        return ls;
    }

    private void dfs(int[] nums, int u) {
        if (u == n) {
            ls.add(path.clone());
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!bool[i]) {
                if (i >= 1 && nums[i] == nums[i - 1] && bool[i - 1] == false)   
                // if bool[i-1] ==true 的话 选择i位置 即可以满足条件 1
                // i-1的位置比i快选择 
                //如果i-1 还没选 且 在选i的时候 就可以直接跳出 说明已经重复选择i位置了
                // 第n趟递归是要在第n个位置选择一个数放置
                // num[i-1]会比nums[i]早被考虑放到当前位置上
                // 若bool[i-1]=false说明这个数在上一个排列中已经在这个位置放置过了
                // 所以当前位置不应该再放置与nums[i-1]相等的nums[i] 
                    continue;
                path.add(nums[i]);
                bool[i] = true;
                dfs(nums, u + 1);
                bool[i] = false;
                path.removeLast();
            }
        }
    }
}



cznczai
9个月前
class Solution {
    private List ls; 
    private boolean []bool;
    private int n;
    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        ls = new LinkedList<LinkedList>();
        if(n==0)return ls;
        bool = new boolean [n];
        dfs(nums,0,bool);
        return ls;
    }
    public void dfs(int nums[],int u,boolean bool[]) {
        if(u==n) {
            LinkedList path = new LinkedList<LinkedList>();
            for(int i = 0 ; i< n ;i++) {
                if(bool[i]==false)
                    path.add(nums[i]);
            }
            ls.add(path);
        }
        else {
            bool[u]= true;
            dfs( nums,u+1,bool);
            bool[u] = false;
            dfs( nums,u+1,bool);
        }
    }

}

二进制

class Solution {
    private List ls;
    private boolean[] bool;
    private int n;

    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        ls = new LinkedList<LinkedList>();
        bool = new boolean[n];
        for (int i = 0; i < Math.pow(2, n); i++) {
            LinkedList path = new LinkedList<LinkedList>();
            String s = Integer.toBinaryString(i);
            while(s.length()!=n) s = '0'+s;
            for (int x = 0; x < n; x++)
                if (s.charAt(x) == '1')
                    path.add(nums[x]);
            ls.add(path);
        }
        return ls;
    }
}


活动打卡代码 AcWing 99. 激光炸弹

cznczai
11个月前

java 解法 暴力 + 前缀 + 动态规划

import java.util.Scanner;
class Main {                                    //前缀和
    static final int MAX = 5050;
    static Scanner sc = new Scanner(System.in);        //输入
    static int[][] arr = new int [MAX][MAX];                    //全局变量放在堆里面 而局部变量放在栈里面 如果把数组放在函数里面 会爆栈

    public static void main(String[] args) {
        int N = sc.nextInt();
        int R = sc.nextInt();
        System.out.println(the_max( N, R));
    }

    public static int the_max(int N, int R) {                   //N 是 个数  ,R 是边长

        int X = R;                                      //要大于等于R 避免后面的处理
        int Y = R;                                                                         //外面不一定是正方形
        int ans = 0 ;
        for(int i = 0 ; i < N ; i ++) {
            int p_x = sc.nextInt() + 1;                 
            int p_y = sc.nextInt() + 1;                 //加一为了消除0的边界问题 因为后面有[i-1] 0-1 => error
            arr[p_x][p_y] = sc.nextInt();
            X = Math.max(p_x, X);                       //记录边界
            Y = Math.max(p_y, Y);
        }
        for(int i = 1 ; i <= X ; i++) {
            for(int j = 1 ; j <= Y ; j++) {
                arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];    //动态规划
            }
        }
        for(int i = R ; i <= X ; i++) {                                                //用于在R之间的范围内筛选 
            for(int j = R ; j <= Y ; j++) {
                ans = Math.max(ans,arr[i][j]-arr[i-R][j]-arr[i][j-R]+arr[i-R][j-R]);
            }
        }
        return ans ;
    }
}