讨论/题目交流/🏆 第 188 场力扣周赛/
🏆 第 188 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 用栈操作构建数组
4 分 - 形成两个异或相等数组的三元组数目
5 分 - 收集树上所有苹果的最少时间
7 分 - 切披萨的方案数

展开讨论
力扣 (LeetCode)发起于 2020-05-10
最近编辑于 2020-05-10

第一次AK,纪念下😂
1.

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> ans = new ArrayList<>();
        if(target.length == 0)
            return ans;
        int last = 0;
        for(int curr:target) {
            for(int j=1;j<curr - last;j++) {
                ans.add("Push");
                ans.add("Pop");
            }
            ans.add("Push");
            last = curr;
        }
        return ans;
    }
}
class Solution {
    public int countTriplets(int[] arr) {
        int[][] dp = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            int prev = arr[i];
            dp[i][i] = prev;
            for (int j = i + 1; j < arr.length; j++) {
                dp[i][j] = prev ^ arr[j];
                prev = dp[i][j];
            }
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j; k < arr.length; k++) {
                    if (dp[i][j - 1] == dp[j][k])
                        count++;
                }
            }
        }
        return count;
    }
}
class Solution {
    private List<Boolean> hasApple;
    private Map<Integer, List<Integer>> g;

    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        g = new HashMap<>();
        this.hasApple = hasApple;
        for (int[] e : edges) {
            List<Integer> ch = g.get(e[0]);
            if (ch == null)
                g.put(e[0], ch = new ArrayList<>());
            ch.add(e[1]);
        }
        return Math.max(0, dfs(0))*2;
    }

    private int dfs(int root) {
        List<Integer> ch = g.getOrDefault(root, Collections.emptyList());
        if (ch.isEmpty()) {
            return hasApple.get(root) ? 0 : -1;
        }
        int ans = 0;
        for (int next : ch) {
            int nextPath = dfs(next);
            if (nextPath >= 0)
                ans += nextPath + 1;
        }
        return ans == 0 ? (hasApple.get(root) ? 0 : -1) : ans;
    }
}
class Solution {
    boolean[][] grid;
    Integer[][][] memo;
    private int kMod = (int) (1e9 + 7);

    public int ways(String[] pizza, int k) {
        int m = pizza.length;
        int n = pizza[0].length();
        grid = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pizza[i].charAt(j) == 'A')
                    grid[i][j] = true;
            }
        }
        memo = new Integer[m][n][k + 1];
        return dp(0, 0, k);
    }

    private boolean hasAppleCurr(int left, int right, int top, int bottom) {
        for (int i = left; i < right; i++)
            for (int j = top; j < bottom; j++)
                if (grid[j][i])
                    return true;
        return false;
    }

    private int dp(int left, int top, int k) {
        if (left >= grid[0].length || top >= grid.length)
            return 0;
        if (memo[top][left][k] != null)
            return memo[top][left][k];
        if (k == 1) {
            return hasAppleCurr(left, grid[0].length, top, grid.length) ? 1 : 0;
        }
        long ans = 0;
        // 横切
        for (int i = top + 1; i < grid.length; i++) {
            if (hasAppleCurr(left, grid[0].length, top, i))
                ans = (ans + dp(left, i, k - 1)) % kMod;
        }
        for (int i = left + 1; i < grid[0].length; i++) {
            if (hasAppleCurr(left, i, top, grid.length))
                ans = (ans + dp(i, top, k - 1)) % kMod;
        }
        return memo[top][left][k] = (int) ans;
    }
}
2
展开全部 12 讨论