第55场双周赛

删除一个元素使数组严格递增

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        boolean flag = true;
        int n = nums.length;
        for (int i = 0; i < n - 1; ++ i) {
            if (nums[i] >= nums[i + 1]) {
                if (flag) {
                    if (i - 1 < 0 || nums[i - 1] < nums[i + 1]) flag = false;
                    else if (i + 2 >= n || nums[i] < nums[i + 2]) flag = false;
                    else return false;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

删除一个字符串中所有出现的给定子字符串

class Solution {
    public String removeOccurrences(String s, String part) {
        StringBuilder sb = new StringBuilder(s);
        int len = part.length();
        for (int i = 0; i < sb.length() - len + 1; ++ i) {
            if (sb.substring(i, i + len).equals(part)) {
                sb.delete(i, i + len);
                i = Math.max(-1, i - len);
            }
        }
        return sb.toString();
    }
}

最大子序列交替和

动态规划

class Solution {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;
        long[][] f = new long[n + 1][2];
        f[0][0] = 0;
        for (int i = 1; i <= n; ++ i) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] - nums[i - 1]);
            f[i][1] = Math.max(f[i - 1][1], Math.max(0, f[i - 1][0]) + nums[i - 1]);
        }
        return Math.max(f[n][1], f[n][0]);
    }
}

LeetCode Weekly 246

查询差绝对值的最小值

前缀和⭐

class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        int M = 100;
        int n = nums.length, m = queries.length;
        int[][] s = new int[n + 1][M + 1];

        // 处理前缀和
        // s[i][j] 表示 nums数组中[0, i - 1]元素中是否有数字 j
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= M; ++ j) {
                int t = 0;
                if (nums[i - 1] == j) t = 1;
                s[i][j] = s[i - 1][j] + t;
            }
        }

        int[] res = new int[m];
        int idx = 0;
        // 枚举所有询问
        for (int[] q : queries) {
            int l = q[0] + 1, r = q[1] + 1; // 前缀和数组下标从1开始
            int t = M, last = -1;
            for (int j = 1; j <= M; ++ j) {
                if (s[r][j] > s[l - 1][j]) {
                    if (last != -1) t = Math.min(t, j - last);
                    last = j;
                }
            }
            if (t == M) t = -1; 
            res[idx ++] = t;
        }
        return res;
    }
}

LeetCode Weekly 245

可移除字符的最大数目

二分

class Solution {
    public int maximumRemovals(String s, String p, int[] removable) {
        int n = removable.length;
        int l = -1, r = n - 1;
        while (l < r) {
            int mid = (r + l + 1) / 2;
            char[] c = s.toCharArray();
            for (int i = 0; i <= mid; ++ i) c[removable[i]] = '0';
            if (judge(c, p)) l = mid;
            else r = mid - 1;
        }
        return l + 1;
    }

    public boolean judge (char[] c, String p) {
        int n = c.length, m = p.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m;++ i) {
            if (c[i] == '0') continue;
            if (c[i] == p.charAt(j)) ++ j;
        }
        if (j == m) return true;
        else return false;
    }
}

第 54 场双周赛

最大的幻方

前缀和

class Solution {
    public int largestMagicSquare(int[][] grid) {
        int n = grid.length, m = grid[0].length;

        // 横向前缀和
        int[][] sx = new int[n][m + 1];
        for (int i = 0; i < n; ++ i) {
            for (int j = 1; j <= m; ++ j)
                sx[i][j] = sx[i][j - 1] + grid[i][j - 1];
        }
        // 纵向前缀和
        int[][] sy = new int[m][n + 1];
        for (int i = 0; i < m; ++ i) {
            for (int j = 1; j <= n; ++ j)
                sy[i][j] = sy[i][j - 1] + grid[j - 1][i];
        }

        // 从大到小遍历所有的边长
        for (int edge = Math.min(n, m); edge >= 2; -- edge) {
            for (int i = 0; i + edge <= n; ++ i) {
                for (int j = 0; j + edge <= m; ++ j) {
                    int stdSum = sx[i][j + edge] - sx[i][j];
                    boolean flag = true;

                    // 行和列
                    for (int k = 0; k < edge; ++ k) {
                        int sum1 = sx[i + k][j + edge] - sx[i + k][j];
                        int sum2 = sy[j + k][i + edge] - sy[j + k][i];
                        if (sum1 != stdSum || sum2 != stdSum){
                            flag = false;
                            break;
                        }
                    }
                    if (!flag) continue;

                    // 对角线
                    int d1 = 0, d2 = 0;
                    for (int k = 0; k < edge; ++ k) {
                        d1 += grid[i + k][j + k];
                        d2 += grid[i + edge - 1 - k][j + k];
                    }
                    if (d1 == stdSum && d2 == stdSum) {
                        return edge;
                    }
                }
            }
        }
        return 1;
    }
}

LeetCode Weekly 244

使二进制字符串字符交替的最少反转次数⭐⭐

滑动窗口

class Solution {
    public int minFlips(String s) {
        String tar = "01";
        int len = s.length();
        int cnt = 0;
        for (int i = 0; i < len; ++ i) {
            if (s.charAt(i) != tar.charAt(i % 2)) ++ cnt;
        }

        // len - cnt 便是 tar = "10" 时操作2的计数值
        int ans = Math.min(cnt, len - cnt);
        s += s; // 双倍字符串 即可使用滑动窗口丝滑拼接
        for (int i = 0; i < len; ++ i) {
            if (s.charAt(i) != tar.charAt(i % 2)) -- cnt;
            if (s.charAt(i + len) != tar.charAt((i + len) % 2)) ++ cnt;
            ans = Math.min(ans, Math.min(cnt, len - cnt));
        }
        return ans;
    }
}

装包裹的最小浪费空间⭐⭐

二分

class Solution {
    static int mod = (int)(1e9 + 7);
    public int minWastedSpace(int[] packages, int[][] boxes) {
        // 用供应商去枚举箱子 用小数组去二分大数组
        int n = packages.length;
        Arrays.sort(packages);
        long sum = 0;
        for (int p : packages) sum += p;
        long ans = Long.MAX_VALUE;
        for (int[] box : boxes) {
            Arrays.sort(box);
            int m = box.length;
            if (packages[n - 1] > box[m - 1]) continue;
            long space = -sum;
            int last = -1;
            for (int b : box) {
                int l = last, r = n - 1;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (packages[mid] <= b) l = mid;
                    else r = mid - 1;
                }
                if (l == last) continue;
                space += (long)b * (r - last); // 这里右边都是int计算结果会越界需要long转型
                last = l;
            }
            ans = Math.min(ans, space);
        }
        return ans == Long.MAX_VALUE ? -1 : (int)(ans % mod);
    }
}

LeetCode Weekly 243

使用服务器处理任务

双堆

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        int n = tasks.length, m = servers.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {
            if (x[0] != y[0]) return x[0] - y[0]; // 权重
            return x[2] - y[2]; // 下标
        });
        for (int i = 0; i < m; ++ i) {
            pq.offer(new int[]{servers[i], 0, i});
        }
        PriorityQueue<int[]> pqBusy = new PriorityQueue<>((x, y) -> {
            if (x[1] != y[1]) return x[1] - y[1]; // 变成空闲的时间
            return x[0] - y[0]; // 权重
        });

        int[] ans = new int[n];
        for (int i = 0; i < n; ++ i) {
            while (!pqBusy.isEmpty() && pqBusy.peek()[1] <= i)
                pq.offer(pqBusy.poll());

            int[] server;
            if (pq.isEmpty()) {
                server = pqBusy.poll();
                server[1] += tasks[i];
            } else {
                server = pq.poll();
                server[1] = i + tasks[i];
            }
            ans[i] = server[2];
            pqBusy.offer(server);
        }
        return ans;
    }
}

准时抵达会议现场的最小跳过休息次数⭐⭐

动态规划 & 浮点数精度问题处理

class Solution {
    static final double EPS = 1e-8, INT = 1e8;
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int n = dist.length;
        // f[i][j] 经过了[0, i - 1] 共 i 段路用了 j 次操作的最小时间
        double[][] f = new double[n + 1][n + 1];
        for (int i = 1; i <= n; ++ i) {
            double t = (double) dist[i - 1] / speed;
            for (int j = 0; j <= i; ++ j) {
                f[i][j] = INT;
                if (j <= i - 1) f[i][j] = Math.min(f[i][j], Math.ceil(f[i - 1][j] + t - EPS));
                if (j > 0) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + t);
            }
        }
        for (int i = 0; i <= n; ++ i) {
            if (f[n][i] < hoursBefore + EPS) return i;
        }
        return -1;
    }
}

🍹y总 - 笔记🍹

第 53 场双周赛

矩阵中最大的三个菱形和

斜向前缀和

class Solution {
    static int N = 110;
    public int[] getBiggestThree(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] s1 = new int[N][N];
        int[][] s2 = new int[N][N];
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= m; ++ j) {
                s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];
                s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];
            }
        }
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= m; ++ j) {
                set.add(grid[i - 1][j - 1]);
                // 枚举所有半径
                for (int k = 1; i - k >= 1 && i + k <= n && j - k >= 1 && j + k <= m; ++ k) {
                    int a = s2[i][j - k] - s2[i - k][j];
                    int b = s1[i][j + k] - s1[i - k][j];
                    int c = s2[i + k][j] - s2[i][j + k];
                    int d = s1[i + k][j] - s1[i][j - k];
                    // 去掉少算的和多算的点
                    set.add(a + b + c + d - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]);
                }
                while (set.size() > 3) set.pollFirst();
            }
        }
        int len = set.size();
        int[] ans = new int[len];
        for (int i = 0; i < len; ++ i) ans[i] = set.pollLast();
        return ans;
    }
}

两个数组最小的异或值之和⭐⭐

状态压缩dp

class Solution {
    static int INT = (int)1e9;
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        // 当前用过的数的状态是 i, 最小的异或值之和
        int[] f = new int[1 << n];
        f[0] = 0;
        for (int i = 1; i < 1 << n; ++ i) {
            f[i] = INT;
            // 统计1的个数
            int cnt = 0;
            for (int j = 0; j < n; ++ j) {
                if (((i >> j) & 1) == 1) ++ cnt; 
            }
            for (int j = 0; j < n; ++ j) {
                if (((i >> j) & 1) == 1) {
                    f[i] = Math.min(f[i], f[i - (1 << j)] + (nums2[j] ^ nums1[cnt - 1]));
                }
            }
        }
        return f[(1 << n) - 1];
    }
}

🍹y总 - 笔记🍹

类似题型:AcWing算法基础课 - 最短Hamilton路径

LeetCode Weekly 242

时到达的列车最小时速

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int l = 1, r = (int)2e7;
        while (l < r) {
            int mid = l + (r - l) / 2;
            double need = isArrive(dist, mid);
            if (need > hour) l = mid + 1;
            else if (need <= hour) r = mid;
        }
        if (isArrive(dist, l) <= hour) return l;
        return -1;
    }
    private double isArrive (int[] dist, int speed) {
        int n = dist.length;
        double need = 0;
        for (int i = 0; i < n - 1; ++ i) {
            need += (dist[i] + speed - 1) / speed;
        }
        need += ((double)dist[n - 1] / (double)speed);
        return need;
    }
}

跳跃游戏VII

动态规划

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        int[] dp = new int[n + 1];
        int[] pre = new int[n + 1];
        dp[1] = pre[1] = 1;
        for (int i = 2; i <= n; ++ i) {
            if (s.charAt(i - 1) == '0' && i - minJump >= 1) {
                int l = Math.max(1, i - maxJump), r = i - minJump;
                if (pre[r] - pre[l - 1] > 0) dp[i] = 1;
            }
            pre[i] = pre[i - 1] + dp[i];
        }
        return dp[n] == 1;
    }
}

石子游戏VIII⭐⭐

动态规划 - 经典题型

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] pre = new int[n];
        // 求前缀和
        pre[0] = stones[0];
        for (int i = 1; i < n; ++ i) pre[i] = pre[i - 1] + stones[i];
        // dp[i] 表示 Alice [i, n) 内选择下标所能得到的 Alice 与 Bob 分数的最大差值。
        int[] dp = new int[n];
        dp[n - 1] = pre[n - 1]; // 边界条件
        for (int i = n - 2; i > 0; -- i) {
            dp[i] = Math.max(dp[i + 1], pre[i] - dp[i + 1]); // 状态转移方程
        }
        return dp[1];
    }
}

LeetCode Weekly 241

找出所有子集的异或总和再求和

爆搜

class Solution {
    int ans;
    public int subsetXORSum(int[] nums) {
        ans = 0;
        dfs(nums, 0, 0);
        return ans;

    }
    private void dfs (int[] nums, int idx, int xor) {
        if (idx >= nums.length) return;
        ans += xor ^ nums[idx];
        dfs (nums, idx + 1, xor ^ nums[idx]);
        dfs (nums, idx + 1, xor);
    }
}

位枚举

class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < 1 << n; ++ i) {
            int xor = 0;
            for (int j = 0; j < n; ++ j) {
                if ((i >> j & 1) == 1) xor ^= nums[j];
            }
            ans += xor;
        }
        return ans;
    }
}

构成交替字符串需要的最小交换次数

class Solution {
    public int minSwaps(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int a = 0, b = 0;
        for (int i = 0; i < n; ++ i) {
            if (c[i] == '0') ++ a;
            else ++ b;
        }
        if(Math.abs(a - b) > 1) return -1;

        int count = 0;
        if (a == b + 1 || a == b) {
            for (int i = 0; i < n; i += 2) {
                if (c[i] != '0') ++ count;
            }
        }
        if (b == a + 1 || a == b) {
            int tmpCount = 0;
            for (int i = 0; i < n; i += 2) {
                if (c[i] != '1') ++ tmpCount;
            }
            if (a == b) count = Math.min(count, tmpCount);
            else count = tmpCount;
        }
        return count;
    }
}

找出和为指定值的下标对

class FindSumPairs {
    int[] nums1, nums2;
    HashMap<Integer, Integer> map;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        map = new HashMap<>();
        for (int num : nums2) {
            map.put (num, map.getOrDefault(num, 0) + 1);
        }
    }

    public void add(int index, int val) {
        map.put(nums2[index], map.get(nums2[index]) - 1);
        nums2[index] += val;
        map.put(nums2[index], map.getOrDefault(nums2[index], 0) + 1);
    }

    public int count(int tot) {
        int ans = 0;
        for (int num : nums1) {
            ans += map.getOrDefault((tot - num), 0) ;
        }
        return ans;
    }
}

恰有K根木棍可以看到的排列数目⭐⭐

动规 经典问题-第一类斯特林数

class Solution {
    public int rearrangeSticks(int n, int k) {
        int mod = (int)(1e9 + 7);
        // f[i][j] 表示将i个数划分成j个不同原排列的方案数
        int[][] f = new int[n + 1][k + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= k; ++ j) {
                f[i][j] = (int)(f[i - 1][j - 1] + (long)(i - 1) * f[i - 1][j] % mod) % mod;
            }
        }
        return f[n][k];
    }
}

Try and fail, but don't fail to try.