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

第 118 场力扣夜喵双周赛

查找包含给定字符的单词

模拟。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public List<Integer> findWordsContaining(String[] words, char x) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].contains(x + "")) {
                ans.add(i);
            }
        }
        return ans;
    }
}

最大化网格图中正方形空洞的面积

分别求出行和列的最长连续线段，然后最大正方形面积就是两者最小值加一的平方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        int maxH = 0, maxV = 0;
        for (int i = 0, j = 0; j < hBars.length; j++) {
            if (hBars[j] - hBars[i] == j - i) {
                maxH = Math.max(maxH, j - i + 1);
            } else {
                i = j;
            }
        }
        for (int i = 0, j = 0; j < vBars.length; j++) {
            if (vBars[j] - vBars[i] == j - i) {
                maxV = Math.max(maxV, j - i + 1);
            } else {
                i = j;
            }
        }
        int len = Math.min(maxH, maxV) + 1;
        return len * len;
    }
}

购买水果需要的最少金币数

动态规划，\(dp[i]\) 表示获取 \([i,n]\) 范围内所有水果所需的最少金币数，有 \(dp[i]=prices[i]+\min_{j=i+1}^{2i+1}{dp[j]}\)，时间复杂度 \(O(n^{2})\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        for (int i = (n + 1) / 2 - 1; i > 0; i--) {
            int min = Integer.MAX_VALUE;
            for (int j = i + 1; j <= 2 * i + 1; j++) {
                min = Math.min(min, prices[j - 1]);
            }
            prices[i - 1] += min;
        }
        return prices[0];
    }
}

单调队列优化，时间复杂度 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = n; i > 0; i--) {
            while (!q.isEmpty() && q.peekFirst() > 2 * i + 1) {
                q.pollFirst();
            }
            if (i <= (n + 1) / 2 - 1) {
                prices[i - 1] += prices[q.peekFirst() - 1];
            }
            while (!q.isEmpty() && prices[q.peekLast() - 1] >= prices[i - 1]) {
                q.pollLast();
            }
            q.offerLast(i);
        }
        return prices[q.peekLast() - 1];
    }
}

找到最大非递减数组的长度

单调队列优化 DP，随缘补题。

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

AtCoder Beginner Contest 330

Counting Passes

模拟。

1
2
3
4
5
6
7
8
9
10
public static void solve() {
    int n = io.nextInt(), l = io.nextInt();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (io.nextInt() >= l) {
            ans++;
        }
    }
    io.println(ans);
}

Minimize Abs 1

等价于求 \(y=|x-a_{i}|\) 在区间 \([L,R]\) 内的最小值对应的 \(x\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), l = io.nextInt(), r = io.nextInt();
    for (int i = 0; i < n; i++) {
        int a = io.nextInt();
        if (l <= a && a <= r) {
            io.print(a + " ");
        } else if (a < l) {
            io.print(l + " ");
        } else {
            io.print(r + " ");
        }
    }
    io.println();
}

Minimize Abs 2

对于每个固定的 \(x\)，可以在 \(O(1)\) 时间内求出 \(|y^{2}+(x^{2}-D)|\) 的最小值（也可以二分），我们枚举 \([0,\lceil\sqrt{D}\rceil]\) 范围内的所有 \(x\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    long d = io.nextLong();
    long ans = Long.MAX_VALUE;
    long up = (long) Math.sqrt(d) + 1;
    for (long x = 0; x <= up; x++) {
        long t = x * x - d;
        if (t >= 0) {
            ans = Math.min(ans, t);
        } else {
            long y = (long) Math.sqrt(-t);
            ans = Math.min(ans, Math.abs(y * y + x * x - d));
            ans = Math.min(ans, Math.abs((y + 1) * (y + 1) + x * x - d));
        }
    }
    io.println(ans);
}

Counting Ls

对行列计数，然后枚举交叉点。

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
public static void solve() {
    int n = io.nextInt();
    char[][] s = new char[n][];
    for (int i = 0; i < n; i++) {
        s[i] = io.next().toCharArray();
    }

    int[] row = new int[n];
    int[] col = new int[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == 'o') {
                row[i]++;
                col[j]++;
            }
        }
    }

    long ans = 0L;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == 'o' && col[j] > 1) {
                ans += (long) (col[j] - 1) * (row[i] - 1);
            }
        }
    }
    io.println(ans);
}

Mex and Update

因为只有 \(n\) 个数，所以只需要考虑 \([0,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
27
28
29
30
public static void solve() {
    int n = io.nextInt(), q = io.nextInt();
    int[] a = new int[n];
    int[] cnt = new int[n + 1];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        if (a[i] <= n) {
            cnt[a[i]]++;
        }
    }

    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i <= n; i++) {
        if (cnt[i] == 0) {
            set.add(i);
        }
    }

    while (q-- != 0) {
        int i = io.nextInt() - 1, x = io.nextInt();
        if (a[i] <= n && --cnt[a[i]] == 0) {
            set.add(a[i]);
        }
        a[i] = x;
        if (a[i] <= n && cnt[a[i]]++ == 0) {
            set.remove(a[i]);
        }
        io.println(set.first());
    }
}
发表更新算法 / LeetCode3 分钟读完 (大约429个字)

第 372 场力扣周赛

使三个字符串相等

等价于求字符串的最长公共前缀。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int n = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
        int i = 0;
        while (i < n && s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i)) {
            i++;
        }
        return i == 0 ? -1 : s1.length() + s2.length() + s3.length() - 3 * i;
    }
}

区分黑球与白球

将每个 \(1\) 右边 \(0\) 的个数累加就是需要交换的次数，或者累加每个 \(0\) 左边 \(1\) 的个数也行。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public long minimumSteps(String s) {
        long ans = 0L;
        int n = s.length(), cnt = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') cnt++;
            else ans += cnt;
        }
        return ans;
    }
}

最大异或乘积

要求 \(\max((a\oplus x)\times(b\oplus x))\)，可以得出异或只会在两者都为 \(0\) 的位上补 \(1\)，或者交换两者某位上的 \(0\) 和 \(1\)。此时 \((a\oplus x)+(b\oplus x)=c\)，\(c\) 为某个定值，从而问题可以转化为求函数 \(y=x(c-x)\) 的最大值，可以知道当 \(x=\frac{c}{2}\) 时取到最大值，即我们需要让 \((a\oplus x)\) 和 \((b\oplus x)\) 尽可能相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private static final int MOD = (int) 1e9 + 7;
    
    public int maximumXorProduct(long a, long b, int n) {
        long p = a >> n << n, q = b >> n << n;
        for (int i = n - 1; i >= 0; i--) {
            if ((a >> i & 1) == (b >> i & 1)) {
                p |= 1L << i;
                q |= 1L << i;
            } else if (p < q) {
                p |= 1L << i;
            } else {
                q |= 1L << i;
            }
        }
        return (int) (p % MOD * (q % MOD) % MOD);
    }
}

找到 Alice 和 Bob 可以相遇的建筑

离线查询，可以预处理查询序列，然后使用单调栈 + 二分，或者使用最小堆；在线查询，可以使用线段树（暂时不学）。

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×