头像

zhaoxiaoyun

长安大学




离线:6天前


活动打卡代码 LeetCode 633. 平方数之和

class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }
}



import java.util.*;

public class Main {
    static int N = 110;
    static int[] l = new int[N];
    static int[] r = new int[N];
    static int[] v = new int[N];
    static int[] q = new int[N];
    static int n, k;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            scanner.nextLine();
            l[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
        }
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            q[i] = scanner.nextInt();
        }
        Arrays.sort(q, 0, n);
        k = 0;
        dfs(0);
        bfs();
    }

    public static void dfs (int t) {
        if (t == -1) return;
        dfs(l[t]);
        v[t] = q[k ++];
        dfs(r[t]);
    }

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int t = queue.poll();
            System.out.print(v[t] + " ");
            if (l[t] != -1)
                queue.offer(l[t]);
            if (r[t] != -1)
                queue.offer(r[t]);
        }
    }
}




class Solution {
    static int low, high, res;

    public int rangeSumBST(TreeNode root, int low, int high) {
        Solution.low = low;
        Solution.high = high;
        res = 0;
        dfs(root);
        return res;
    }

    public static void dfs (TreeNode root) {
        if (root.val <= high && root.val >= low)
            res += root.val;
        if (root.left != null)
            dfs(root.left);
        if (root.right != null)
            dfs(root.right);
    }
}


活动打卡代码 AcWing 680. 剪绳子

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[] w = new int[N];
    static int n;
    static int m;

    static boolean check(double mid) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += w[i] / mid;
        }
        return cnt >= m;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }
        double l = 0, r = 1e9;
        while (r - l > 1e-4) {
            double mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        System.out.println(String.format("%.2f", r));
    }
}




class Solution {
    public int shipWithinDays(int[] weights, int D) {
        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = (left + right) / 2;
            int need = 1, cur = 0;
            for (int weight : weights) {
                if (cur + weight > mid) {
                    ++need;
                    cur = 0;
                }
                cur += weight;
            }
            if (need <= D) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}



class Solution {
    static List<List<Integer>> res;
    static List<Integer> temp;

    public List<List<Integer>> findPath(TreeNode root, int sum) {
        res = new LinkedList<>();
        temp = new LinkedList<>();
        if (root == null)
            return res;
        dfs(root, sum);
        return res;
    }

    public static void dfs (TreeNode root, int sum) {
        if (root == null)
            return;
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                LinkedList<Integer> t = new LinkedList<>(temp);
                t.add(root.val);
                res.add(t);
            }
            return;
        }
        temp.add(root.val);
        dfs(root.left, sum - root.val);
        dfs(root.right, sum - root.val);
        temp.remove(temp.size() - 1);
    }
}



class Solution {
    static TreeNode dummy;
    static TreeNode cur;
    public TreeNode increasingBST(TreeNode root) {
        dummy = new TreeNode();
        cur = dummy;
        dfs(root);
        return dummy.right;
    }

    public static void dfs (TreeNode root) {
        if (root == null)
            return;
        dfs(root.left);
        cur.right = root;
        cur = cur.right;
        cur.left = null;
        dfs(root.right);
    }
}


活动打卡代码 AcWing 3382. 整数拆分

import java.util.*;

public class Main {
    static int N = 1000010;
    static int[] f = new int[N];
    static int mod = (int) 1e9;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        f[0] = 1;
        for (int i = 1; i <= n; i *= 2)
            for (int j = 1; j <= n; j++)
                if (j >= i)
                    f[j] = (f[j] + f[j - i]) % mod;
        System.out.println(f[n]);
    }
}


活动打卡代码 LeetCode 377. 组合总和 Ⅳ

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < n; j++) {
                if (nums[j] <= i)
                    f[i] += f[i - nums[j]];
            }
        }
        return f[target];
    }
}



import java.util.*;

public class Main {
    static int N = 1010;
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[][] f = new int[N][N];
    static int n, m;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 1; i <= n; i ++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        for (int i = n; i >= 1; i --) {
            for (int j = 0; j <= m; j ++) {
                f[i][j] = f[i + 1][j];
                if (j >= v[i])
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - v[i]] + w[i]);
            }
        }
        int t = m;
        for (int i = 1; i <= n; i ++) {
            if (v[i] <= t && f[i][t] == f[i + 1][t - v[i]] + w[i]){
                System.out.print(i + " ");
                t -= v[i];
            }
        }
    }
}