发表更新算法 / LeetCode4 分钟读完 (大约561个字)

第 363 场力扣周赛

计算 K 置位下标对应元素的和

模拟。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            if (Integer.bitCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }
}

让所有学生保持开心的分组方法数

比赛时又写复杂了，当时是想到所有相同的数都必须同时选，所以加了一层循环来跳过相同的数。但是相同的数天然的不满足判断条件，所以不需要这样写。这题唯一需要注意的就是特判全都不选的情况，以及全都选的情况必定满足，可以直接加到答案里（以减少判断代码）。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int countWays(List<Integer> nums) {
        Collections.sort(nums);
        int n = nums.size(), ans = 1;
        if (nums.get(0) > 0) ans++;
        for (int i = 0; i < n - 1; i++) {
            if (i + 1 > nums.get(i) && i + 1 < nums.get(i + 1)) {
                ans++;
            }
        }
        return ans;
    }
}

最大合金数

比赛时又又写复杂了，当时是把所有的库存都清除了再二分的，其实可以直接二分！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int ans = 0;
        for (var cur : composition) {
            int lo = 0, hi = (int) 2e8;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                long cnt = 0L;
                for (int i = 0; i < n; i++) {
                    cnt += Math.max((long) cur.get(i) * mid - stock.get(i), 0L) * cost.get(i);
                }
                if (cnt <= budget) lo = mid + 1;
                else hi = mid - 1;
            }
            ans = Math.max(ans, hi);
        }
        return ans;
    }
}

完全子集的最大元素和

注意题目的描述是每对元素的乘积都是完全平方数。朴素的想法就是对下标进行质因数分解，将所有出现次数为奇数质因数相乘，其结果作为桶的下标，把所有同类的数放在同一个桶里面，然后对每个桶求和取最大值，这样的时间复杂度是 \(O(n\sqrt{n})\)。但是有 \(O(n)\) 的解法，如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public long maximumSum(List<Integer> nums) {
        long ans = 0L;
        int n = nums.size();
        for (int i = 1; i <= n; i++) {
            long sum = 0L;
            for (int j = 1; i * j * j <= n; j++) {
                sum += nums.get(i * j * j - 1);
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
发表更新算法 / LeetCode5 分钟读完 (大约705个字)

第 113 场力扣夜喵双周赛

使数组成为递增数组的最少右移次数

直接从最小值开始判断数组是否递增，或者可以找到第一个递减的位置，然后再判断数组是否递增（因为如果数组满足条件，则其最多只有一个递减段）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size(), idx = -1, min = 101;
        for (int i = 0; i < n; i++) {
            if (nums.get(i) < min) {
                min = nums.get(i);
                idx = i;
            }
        }
        for (int i = 0; i < n - 1; i++) {
            int x = (idx + i) % n, y = (x + 1) % n;
            if (nums.get(x) > nums.get(y)) return -1;
        }
        return (n - idx) % n;
    }
}

删除数对后的最小数组长度

贪心，比赛时我是用双指针做的，前半部分和后半部分进行匹配（当时边界想了很久，真笨！）。其他做法，参考题解：【小羊肖恩】数学 + 贪心：解决较长数组脑筋急转弯问题的关键。（因为 HashMap 很慢，所以用双指针会更快。）

方法一：贪心

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size(), i = 0;
        for (int j = (n + 1) / 2; j < n; j++) {
            if (nums.get(i) < nums.get(j)) {
                i++;
            }
        }
        return n - i * 2;
    }
}

方法二：贪心 + 数学

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size(), max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            max = Math.max(max, map.merge(x, 1, Integer::sum));
        }
        return 2 * max <= n ? n % 2 : n - (n - max) * 2;
    }
}

统计距离为 k 的点对

枚举 \(x_{1}\oplus x_{2}\) 的值为 \(p\)，可以得到 \(y_{1}\oplus y_{2}\) 的值为 \(k-p\)。可以使用 HashMap 对前缀中的值计数来求解，需要注意循环的顺序，如果调换顺序会使代码变复杂，会花费更多的时间计算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        int ans = 0;
        Map<List<Integer>, Integer> map = new HashMap<>();
        for (var c : coordinates) {
            int x = c.get(0), y = c.get(1);
            for (int i = 0; i <= k; i++) {
                ans += map.getOrDefault(List.of(x ^ i, y ^ (k - i)), 0);
            }
            map.merge(c, 1, Integer::sum);
        }
        return ans;
    }
}

可以到达每一个节点的最少边反转次数

换根 DP，关键是要想到建立反向边，并为边添加相应的边权。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[] minEdgeReversals(int n, int[][] edges) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(new int[]{v, 0});
            g[v].add(new int[]{u, 1});
        }
        int[] ans = new int[n];
        ans[0] = dfs(0, -1, g);
        dfs2(0, -1, g, ans);
        return ans;
    }
    
    private int dfs(int x, int fa, List<int[]>[] g) {
        int res = 0;
        for (int t[] : g[x]) {
            int y = t[0], w = t[1];
            if (y == fa) continue;
            res += dfs(y, x, g) + w;
        }
        return res;
    }
    
    private void dfs2(int x, int fa, List<int[]>[] g, int[] ans) {
        for (int t[] : g[x]) {
            int y = t[0], w = t[1];
            if (y == fa) continue;
            ans[y] = ans[x] + (w == 0 ? 1 : -1);
            dfs2(y, x, g, ans);
        }
    }
}
发表更新算法 / AtCoder4 分钟读完 (大约589个字)

AtCoder Beginner Contest 320

Leyland Number

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    int a = io.nextInt(), b = io.nextInt();
    int x = 1;
    for (int i = 0; i < b; i++) {
        x *= a;
    }
    int y = 1;
    for (int i = 0; i < a; i++) {
        y *= b;
    }
    io.println(x + y);
}

Longest Palindrome

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    String s = io.next();
    int n = s.length();
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            String a = s.substring(i, j + 1);
            String b = new StringBuilder(a).reverse().toString();
            if (a.equals(b)) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    io.println(ans);
}

Slot Strategy 2 (Easy)

暴力枚举每个转盘的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void solve() {
    int n = 3, m = io.nextInt();
    int ans = Integer.MAX_VALUE;
    String[] s = new String[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.next();
    }
    for (int i = 0; i < n * m; i++) {
        char a = s[0].charAt(i % m);
        for (int j = 0; j < n * m; j++) {
            if (i == j) continue;
            char b = s[1].charAt(j % m);
            for (int k = 0; k < n * m; k++) {
                if (i == k || j == k) continue;
                char c = s[2].charAt(k % m);
                if (a == b && b == c) {
                    ans = Math.min(ans, Math.max(i, Math.max(j, k)));
                }
            }
        }
    }
    io.println(ans == Integer.MAX_VALUE ? -1 : ans);
}

Relative Position

DFS 模拟，需要注意给的不是一棵树，所以在 DFS 时要使用访问数组，而不能用父结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int a = io.nextInt() - 1, b = io.nextInt() - 1, x = io.nextInt(), y = io.nextInt();
        g[a].add(new int[]{b, x, y});
        g[b].add(new int[]{a, -x, -y});
    }
    long[] X = new long[n];
    long[] Y = new long[n];
    Arrays.fill(X, Long.MAX_VALUE);
    Arrays.fill(Y, Long.MAX_VALUE);
    boolean[] vis = new boolean[n];
    dfs(0, vis, g, 0, 0, X, Y);
    for (int i = 0; i < n; i++) {
        if (X[i] != Long.MAX_VALUE && Y[i] != Long.MAX_VALUE) {
            io.println(X[i] + " " + Y[i]);
        } else {
            io.println("undecidable");
        }
    }
}

private static void dfs(int i, boolean[] vis, List<int[]>[] g, long x, long y, long[] X, long[] Y) {
    X[i] = x;
    Y[i] = y;
    vis[i] = true;
    for (int[] t : g[i]) {
        int j = t[0];
        if (vis[j]) continue;
        long nx = t[1] + x, ny = t[2] + y;
        dfs(j, vis, g, nx, ny, X, Y);
    }
}

Somen Nagashi

还是模拟，可以一边输入一边处理，减少代码量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    long[] ans = new long[n], re = new long[n];
    PriorityQueue<Integer> q = new PriorityQueue<>();
    PriorityQueue<Integer> p = new PriorityQueue<>((a, b) -> Long.compare(re[a], re[b]));
    for (int i = 0; i < n; i++) {
        q.offer(i);
    }
    while (m-- != 0) {
        int t = io.nextInt(), w = io.nextInt(), s = io.nextInt();
        while (!p.isEmpty() && re[p.peek()] <= t) q.offer(p.poll());
        if (q.isEmpty()) continue;
        int x = q.peek();
        ans[x] += w;
        re[x] = t + s;
        p.offer(q.poll());
    }
    for (int i = 0; i < n; i++) {
        io.println(ans[i]);
    }
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×