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

第 357 场力扣周赛

故障键盘

方法一：暴力模拟

比赛直接暴力模拟。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String finalString(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != 'i') sb.append(c);
            else sb.reverse();
        }
        return sb.toString();
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2})\)。
  • 空间复杂度：\(O(n)\)。

方法二：双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String finalString(String s) {
        int n = s.length();
        boolean reverse = false;
        Deque<Character> q = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == 'i') reverse = !reverse;
            else if (reverse) q.offerFirst(c);
            else q.offerLast(c);
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            if (reverse) sb.append(q.pollLast());
            else sb.append(q.pollFirst());
        }
        return sb.toString();
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(n)\)。

判断是否能拆分数组

方法一：正难则反

题目要求将数组拆分为单个元素，因为从拆分角度不太好模拟，所以可以考虑怎么将单个元素合并为整个数组。如果数组长度小于等于 \(2\)，则必定满足要求。如果数组长度大于 \(2\)，要想将所有元素合并成完整的数组，则必须有一个大于等于 \(m\) 的合并。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; i++) {
            if (nums.get(i) + nums.get(i - 1) >= m) {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(1)\)。

找出最安全路径

纯暴力做法是使用 \(O(n^{2})\) 的时间判断当前点的的安全系数是否大于等于指定的安全系数，总时间复杂度是 \(O(n^{4}\log n)\)。而我在比赛时预处理了一下小偷的位置，最坏情况其实也是 \(O(n^{4}\log n)\)，结果通过了，我想大概是因为如果小偷的数量很多，那么 BFS 的限制就多，如果小偷的数量很少，那么 BFS 的限制就少，所以复杂度也不会真的到达最坏情况吧。比较好的做法是多源 BFS + 二分，以每个小偷为起点进行多源 BFS，标记每个位置的最小安全系数，然后在二分的 BFS 时就可以花 \(O(1)\) 的时间判断当前点是否合法。

方法一：多源 BFS + 二分

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    int n;
    int[][] dis;
    int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();
        // 以每个小偷为起点进行多源 BFS
        dis = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dis[i], -1);
        }
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    dis[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int x = p[0], y = p[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || dis[nx][ny] >= 0) continue;
                dis[nx][ny] = dis[x][y] + 1;
                q.offer(new int[]{nx, ny});
            }
        }
        // 二分答案
        int lo = 0, hi = Math.min(dis[0][0], dis[n - 1][n - 1]);
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (check(mid)) lo = mid + 1;
            else hi = mid - 1;
        }
        return hi;
    }

    private boolean check(int mid) {
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        vis[0][0] = true;
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int x = p[0], y = p[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] || dis[nx][ny] < mid) continue;
                vis[nx][ny] = true;
                q.offer(new int[]{nx, ny});
            }
        }
        return vis[n - 1][n - 1];
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2}\log n)\)。
  • 空间复杂度：\(O(n^{2})\)。

子序列最大优雅度

方法一：贪心

刚看见题目不知道怎么做，想了想动态规划好像不太行，一个是时间复杂度不行，一个是找不到递推关系（感觉）。然后就想这个数据量，可以排序试一下，然后不知怎么就想到正确答案了。首先贪心取利润最大的 \(k\) 个元素，然后每当遇到一个未选过的类别，则用其替换之前的重复类别中的利润最小的元素，每次计算都更新答案。具体分析如下：

  • 如果第 \(k+1\) 个元素的类别是重复的，那么使用其替换之前的元素不会使优雅度变大，因为 distinct_categories 不变，并且数组元素按照利润降序排列，所以 total_profit 可能会变小或者不变。
  • 反之，我们可以尝试使用当前元素替换之前的元素：① 如果替换之前不重复的元素，那么显然不会优雅度不会变大；② 如果替换之前重复的元素，那么肯定优先选择利润最小的重复元素，distinct_categories 变大，total_profit 变小，优雅度有变大的可能。

反复执行上述操作，就一定可以遍历到最优的情况。比赛时代码很乱，赛后参考了灵神的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public long findMaximumElegance(int[][] items, int k) {
        int n = items.length;
        long ans = 0, sum = 0;
        Arrays.sort(items, (a, b) -> b[0] - a[0]);
        HashSet<Integer> set = new HashSet<>();
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int profit = items[i][0], category = items[i][1];
            if (i < k) {
                sum += profit;
                if (!set.add(category)) q.push(profit);
            } else if (!q.isEmpty() && set.add(category)) {
                sum += profit - q.pop();
            }
            ans = Math.max(ans, sum + (long) set.size() * set.size());
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n\log n)\)。
  • 空间复杂度：\(O(n)\)。
发表更新算法 / LeetCode6 分钟读完 (大约832个字)

第 110 场力扣夜喵双周赛

取整购买后的账户余额

方法一：模拟

比赛时没看明白，写复杂了一点。

1
2
3
4
5
class Solution {
    public int accountBalanceAfterPurchase(int purchaseAmount) {
        return 100 - (purchaseAmount + 5) / 10 * 10;
    }
}

复杂度分析

  • 时间复杂度：\(O(1)\)。
  • 空间复杂度：\(O(1)\)。

在链表中插入最大公约数

方法一：模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode cur = head;
        while (cur.next != null) {
            cur.next = new ListNode(gcd(cur.val, cur.next.val), cur.next);
            cur = cur.next.next;
        }
        return head;
    }
    
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

复杂度分析

  • 时间复杂度：\(O(n\log m)\)，其中 \(m\) 表示节点的最大值。
  • 空间复杂度：\(O(1)\)。

使循环数组所有元素相等的最少秒数

方法一：枚举

假设最后数组中的元素是 \(x\)，那么需要的最少秒数就是所有值为 \(x\) 的元素之间的最大间距的一半向上取整。由于数组是循环数组，我们可以在遍历时添加两次，或者在处理哈希表中的列表时特殊处理最后一个元素与第一个元素的间距。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minimumSeconds(List<Integer> nums) {
        int n = nums.size();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < 2 * n; i++) {
            map.computeIfAbsent(nums.get(i % n), k -> new ArrayList<>()).add(i);
        }
        int ans = Integer.MAX_VALUE;
        for (var list : map.values()) {
            int m = list.size(), max = 0;
            for (int i = 0; i < m - 1; i++) {
                max = Math.max(max, list.get(i + 1) - list.get(i) - 1);
            }
            ans = Math.min(ans, (max + 1) / 2);
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(n)\)。

使数组和小于等于 x 的最少时间

方法一：动态规划

比赛时其实很多点都想到了，当时遇到的问题就是不知道如何对 \(nums1[i]+nums2[i]\times t\) 排序，没想到要用动态规划，而且动态规划的建模方式有点技巧性，利用了排序来确定选择的第 \(j\) 个数就是在时间 \(j\) 操作的数。

状态定义：\(dp[i][j]\) 表示从前 \(i\) 个数中选择 \(j\) 个数进行操作，可以使元素和减少的最大值（相对于不进行任何操作）。因为我们将 \(aux\) 按照 \(nums_{2}\) 从小到大排序，所以如果 \(i\) 是选择的第 \(j\) 个数，那么就表示在时间 \(j\) 操作 \(i\)，因此减少的时间为 \(nums_{1}[aux[i]]+nums_{2}[aux[i]]\times j\)。

状态转移方程：\(dp[i+1][j]=\max(dp[i][j],dp[i][j-1]+nums_{1}[aux[i]]+nums_{2}[aux[i]]\times j)\)。

可以将空间复杂度优化为 \(O(n)\)，此处略过。

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
class Solution {
    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        int n = nums1.size(), sum1 =0, sum2 = 0;
        Integer[] aux = new Integer[n];
        for (int i = 0; i < n; i++) {
            aux[i] = i;
            sum1 += nums1.get(i);
            sum2 += nums2.get(i);
        }
        Arrays.sort(aux, (a, b) -> nums2.get(a) - nums2.get(b));
        // 动态规划
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = n; j > 0; j--) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - 1] + nums1.get(aux[i]) + nums2.get(aux[i]) * j);
            }
        }
        // 枚举答案
        for (int i = 0; i <= n; i++) {
            if (sum1 + sum2 * i - dp[n][i] <= x) {
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2})\)。
  • 空间复杂度：\(O(n^{2})\)。
发表更新算法 / AtCoder5 分钟读完 (大约797个字)

AtCoder Beginner Contest 313

To Be Saikyo

简单模拟。

1
2
3
4
5
6
7
public static void solve() {
    int n = io.nextInt(), x = io.nextInt(), max = 0;
    for (int i = 1; i < n; i++) {
        max = Math.max(max, io.nextInt());
    }
    io.println(Math.max(max - x + 1, 0));
}

Who is Saikyo?

如果 \(A\) 比 \(B\) 强，则让 \(B\) 的入度加一，最后入度为零的程序员就是最强的，如果多于一个那么返回 \(-1\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] in = new int[n + 1];
    for (int i = 0; i < m; i++) {
        int u = io.nextInt(), v = io.nextInt();
        in[v]++;
    }
    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            ans = i;
            cnt++;
        }
    }
    io.println(cnt == 1 ? ans : -1);
}

Approximate Equalization 2

假设我们将数组 \(A\) 执行最少操作后得到数组 \(B\) ，那么 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 就是最小操作次数，因为必定有 \(\sum_{i=1}^{N}A_{i}=\sum_{i=1}^{N}B_{i}\) ，所以上述公式一定可以被二整除。题目要求 \(B\) 的最大值和最小值的差最多为一，那么 \(B\) 一定由 \(N-r\) 个 \(p\) ，以及 \(r\) 个 \(p+1\) 组成，其中 \(p=\frac{\sum_{i=1}^{N}B_{i}}{N},r=\sum_{i=1}^{N}B_{i}\bmod N\) 。然后问题就变为如何组织 \(A_{i}\) 和 \(B_{i}\) 的对应关系，使得 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 最小。显然对数组 \(A\) 进行升序排序，那么数组 \(B\) 的 \(N-r\) 个 \(p\) 对应 \(A\) 的前 \(N-r\) 个元素，数组 \(B\) 的 \(r\) 个 \(p+1\) 对应 \(A\) 的后 \(r\) 个元素，这样排列会使得操作次数最小。

PS：比赛时没什么思路，猜了个平均数，然后没有排序通过遍历比较大小来计算操作次数，结果和正解殊途同归了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = io.nextInt();
        sum += arr[i];
    }
    // 可以替换为快速选择
    Arrays.sort(arr);
    long ans = 0L, p = sum / n, r = sum % n;
    for (int i = 0; i < n; i++) {
        ans += Math.abs(arr[i] - (p + (i >= n - r ? 1 : 0)));
    }
    io.println(ans / 2);
}

Odd or Even

每次查询的返回值可以看作 \(A_{x_{1}}\oplus A_{x_{2}}\oplus \cdots \oplus A_{x_{k}}\) ，所以我们可以首先对前 \(k+1\) 个数进行 \(k+1\) 次查询，然后把所有查询结果异或，可以得到前 \(k+1\) 个数的异或值（因为在 \(k+1\) 次查询中，每个数出现 \(k\) 次，并且 \(k\) 是奇数），将该异或值分别与之前的查询结果异或，可以得到前 \(k+1\) 个数的值。之后的操作类似，就是查询然后异或，得到后面的所有值。

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
36
public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), xor = 0;
    List<Integer> aux;
    int[] ans = new int[n];
    for (int i = 0; i <= k; i++) {
        aux = new ArrayList<>();
        for (int j = 0; j <= k; j++) {
            if (i != j) aux.add(j);
        }
        ans[i] = query(aux);
        xor ^= ans[i];
    }
    for (int i = 0; i <= k; i++) ans[i] ^= xor;
    xor ^= ans[k] ^ ans[k - 1];
    aux = new ArrayList<>();
    for (int i = 0; i < k; i++) aux.add(i);
    for (int i = k + 1; i < n; i++) {
        aux.set(k - 1, i);
        ans[i] = query(aux) ^ xor;
    }
    io.print("! ");
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static int query(List<Integer> aux) {
    io.print("? ");
    for (int x : aux) {
        io.print(x + 1 + " ");
    }
    io.println();
    io.flush();
    return io.nextInt();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×