lcp335

递枕头

方法一：模拟

class Solution {
    public int passThePillow(int n, int time) {
        boolean reverse = false;
        int i = 1;
        while (time-- > 0) {
            if (i == n)
                reverse = true;
            if (i == 1)
                reverse = false;
            if (reverse) {
                i--;
            } else {
                i++;
            }
        }
        return i;
    }
}

二叉树中的第 K 大层和

方法一：BFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        List<Long> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            long sum = 0;
            for (int i = 0; i < size; ++i) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            res.add(sum);
        }
        if (k > res.size())
            return -1;
        Collections.sort(res);
        return res.get(res.size() - k);
    }
}

分割数组使乘积互质

方法一：

获得分数的方法数

方法一：记忆化搜索(分组背包)

class Solution {
    static final int MOD = (int) 1e9 + 7;
    int n ;
    int[][] types, dp;
    Map<String, Integer> map = new HashMap<>();

    public int waysToReachTarget(int target, int[][] types) {
        this.types = types;
        n = types.length;
        dp = new int[n][1002];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, target);
    }

    private int dfs(int index, int target) {
        if (index == n)
            return target == 0 ? 1 : 0;
        if (dp[index][target] != -1)
            return dp[index][target];
        int res = 0, count = types[index][0], marks = types[index][1];
        for (int i = 0; i <= Math.min(target / marks, count); ++i)
            res = (res + (dfs(index + 1, target - i * marks) % MOD)) % MOD;
        return dp[index][target] = res;
    }
}