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];
    }
}

第52场双周赛

将句子排序

class Solution {
    public String sortSentence(String s) {
        String[] strs = s.split(" ");
        Arrays.sort(strs, (a, b) -> a.charAt(a.length() - 1) - b.charAt(b.length() - 1));
        StringBuilder ans = new StringBuilder();
        for (String str : strs) {
            ans.append(str.substring(0, str.length() - 1) + " ");
        }
        ans.deleteCharAt(ans.length() - 1);
        return ans.toString();
    }
}

增长的内存泄露

class Solution {
    public int[] memLeak(int memory1, int memory2) {
        int crashTime = 1;
        while(true) {
            if (memory1 >= memory2) {
                if (crashTime > memory1) return new int[]{crashTime, memory1, memory2};
                memory1 -= crashTime;
            } else {
                if (crashTime > memory2) return new int[]{crashTime, memory1, memory2};
                memory2 -= crashTime;
            }
            ++ crashTime;
        }
    }
}

旋转盒子

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        for (char[] c : box) {
            int i = n - 1, j = n - 1;
            while (i >= 0) {
                if (c[i] == '#') {
                    c[i] = '.';
                    c[j] = '#';
                    -- j;
                } else if (c[i] == '*') {
                    j = i - 1;
                }
                --i;
            }
        }
        char[][] ans = new char[n][m];
        for (int i = 0; i < n; ++ i){
            for (int j = 0; j < m; ++j) {
                ans[i][j] = box[m - 1 - j][i];
            }
        }
        return ans;
    }
}

向下取整数对和

class Solution {
    public int sumOfFlooredPairs(int[] nums) {
        int mod = (int)(1e9 + 7);
        int N = 100010;
        int[] count = new int[N];
        for (int i = 0; i < nums.length; ++ i) {
            count[nums[i]] ++;
        }
        for (int i = N - 2; i >= 1; -- i) {
            count[i] += count[i + 1];
        }
        int ans = 0;
        for (int i = 0; i < nums.length; ++ i) {
            for (int j = 1; j*nums[i] < N; ++ j) {
                ans = (ans + count[j * nums[i]]) % mod;
            }
        }
        return ans;
    }
}

LeetCode Weekly 240

人口最多的年份

class Solution {
    public int maximumPopulation(int[][] logs) {
        int ansYear = 0, max = 0;
        Arrays.sort(logs, (x, y) -> x[0] - y[0]);
        for (int year = 1950; year <= 2050; ++year) {
            int num = 0;
            for (int i = 0; i < logs.length; ++i) {
                if (year >= logs[i][0] && year < logs[i][1]) ++num;
                else if (year < logs[i][0]) break;
            }
            if (num > max) {
                max = num;
                ansYear = year;
            }
        }
        return ansYear;
    }
}

下标对中的最大距离

二分

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int ans = 0;
        for (int i = 0; i < len1; i ++) {
            int low = 0, high = len2 - 1;
            while (low < high) {
                int mid = (low + high + 1) / 2;  
                if (nums2[mid] >= nums1[i]) {
                    low = mid;
                } else {
                    high = mid - 1;
                }
            }
            if (nums2[low] >= nums1[i] && low >= i)
                ans = Math.max(ans, low - i);
        }
        return ans;
    }
}

双指针

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int ans = 0;
        for (int i = nums1.length - 1, j = nums2.length - 1; j >= 0; j --) {
            while (i > 0 && nums1[i - 1] <= nums2[j]) i --;
            if (nums1[i] <= nums2[j]) ans = Math.max(ans, j - i);
        }
        return ans;
    }
}

子数组最小乘积的最大值

单调栈 & 前缀和

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[n];
        int[] right = new int[n];
        // 设置哨兵去除边界情况的判断
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        // 单调栈求 i 位置左右两边小于 nums[i] 的最小数
        for (int i = n - 1; i >= 0; -- i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                left[stack.pop()] = i;
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = 0; i < n; ++ i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                right[stack.pop()] = i;
            }
            stack.push(i);
        }
        // 求前缀和 这里设置long防止爆int
        long[] pre = new long[n + 1];
        for (int i = 1; i <= n; ++ i) {
            pre[i] = pre[i -1] + nums[i - 1];
        }
        // 求乘积的最大值
        long ans = 0;
        for (int i = 0; i < n; ++ i) {
            ans = Math.max(ans, (pre[right[i]] - pre[left[i] + 1]) * nums[i]);
        }
        return (int) (ans % 1000000007);
    }
}

有向图中最大颜色值

拓扑排序 & 动态规划

class Solution {
    public int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        // 邻接表
        List<List<Integer>> g = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) {
            g.add(new ArrayList<>());
        }
        // 统计节点入度
        int[] indeg = new int[n];
        for (int[] edge : edges) {
            ++ indeg[edge[1]];
            g.get(edge[0]).add(edge[1]);
        }
        // 记录拓扑排序中遇到节点个数
        int found = 0;
        int[][] f = new int[n][26];
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; ++ i) {
            if (indeg[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            ++ found;
            int u = q.poll();
            // 将节点对应颜色加1
            ++ f[u][colors.charAt(u) - 'a'];
            // 枚举 u 后所有结点 v 
            for (int v : g.get(u)) {
                -- indeg[v];
                // 将 f(v,c) 更新为其与 f(u,c) 的较大值
                for (int c = 0; c < 26; ++c) {
                    f[v][c] = Math.max(f[v][c], f[u][c]);
                }
                if (indeg[v] == 0) q.offer(v);
            }
        }

        if (found != n) return -1;

        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            ans = Math.max(ans, Arrays.stream(f[i]).max().getAsInt());
        }
        return ans;
    }
}

LeetCode Weekly 239

到目标元素的最小距离

class Solution {
    public int getMinDistance(int[] nums, int target, int start) {
        int n = nums.length;
        int abs = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == target && Math.abs(i - start) < abs) {
                abs = Math.abs(i - start);
            }
        }
        return abs;
    }
}

将字符串拆分为递减的连续值

暴力枚举法

class Solution {
    //由于题中数据范围为 1 <= s.length <= 20
    //暴力枚举法
    public boolean splitString(String s) {
        int n = s.length();
        //暴力枚举所有分法
        for (int i = 1; i < 1 << n - 1; ++i) {
            boolean flag = true;
            long last = -1, x = s.charAt(0) - '0';
            for (int j = 0; j < n - 1; ++j) {
                if ((i >> j & 1) == 1) { //是边界
                    if (last != -1 && x != last - 1) {
                        flag = false;
                        break;
                    }
                    last = x;
                    x = s.charAt(j + 1) - '0';
                } else { //不是边界,累计计算此区间数的大小
                    x = x * 10 + s.charAt(j + 1) - '0';
                }
            }
            if (x != last - 1) flag = false;
            else return true;
        }
        return false;
    }
}

邻位交换的最小次数⭐⭐

下个排列 & 逆序和

class Solution {
    public int getMinSwaps(String num, int k) {
        char[] nums = num.toCharArray();
        int n = nums.length;
        // char[] numsk = nums; //浅复制:仅复制对象的引用
        char[] numsk = new char[n];
        for (int i = 0; i < n; ++i) {
            numsk[i] = nums[i];
        }
        while (k-- > 0) nextPermutation(numsk);

        int[] c = new int[n]; // 存nums里元素在numsk里的下标是多少
        int[] cnt = new int[10]; // 存每个数出现的次数
        Arrays.fill(cnt, 0);
        for (int i = 0; i < n; ++i) {
            int x = nums[i] - '0';
            cnt[x]++;
            int y = cnt[x];
            for (int j = 0; j < n; ++j) {
                if (numsk[j] - '0' == x && --y == 0) { //表示找到了此x
                    c[i] = j;
                    break;
                }
            }
        }

        //求c的逆序对
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (c[i] > c[j]) ++ans;
            }
        }
        return ans;
    }

    // 下一个排列
    public void nextPermutation(char[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i >= 0) {
            int j = n - 1;
            while (j > i && nums[j] <= nums[i]) {
                --j;
            }
            char tmp = nums[j];
            nums[j] = nums[i];
            nums[i] = tmp;
        }
        for (int left = i + 1, right = n - 1; left < right; ++left,--right) {
            char tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
}

下一个排列
数组中的逆序对
下个排列 & 贪心

class Solution {
    public int getMinSwaps(String num, int k) {
        int n = num.length();
        char[] nums = num.toCharArray();
        char[] numsk = new char[n];
        for (int i = 0; i < n; ++i) {
            numsk[i] = nums[i];
        }
        while (--k >= 0) nextPermutation(numsk);

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] != numsk[i]) {
                for (int j = i + 1; j < n; ++j) {
                    if (nums[j] == numsk[i]) {
                        for (int t = j - 1; t >= i; --t) {
                            ++ans;
                            char tmp = nums[t];
                            nums[t] = nums[t + 1];
                            nums[t + 1] = tmp;
                        }
                        break;
                    }
                }
            }
        }
        return ans;
    }

    public void nextPermutation(char[] nums) {
        int n = nums.length;
        int i = n - 2;
        // 从尾部开始找连续递增序列的边界的下个位置 i
        while (i >= 0 && nums[i] >= nums[i + 1]) -- i;
        // 在递增序列中找到第一个大于 nums[i] 的值
        if (i >= 0) {
            int j = n - 1;
            while (j > i && nums[j] <= nums[i]) -- j;
            char tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        // 反转递增序列
        for (int left = i + 1, right = n - 1; left < right; ++left, --right) {
            char tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
}

包含每个查询的最小区间🌟

并查集

class Solution {
   HashSet<Integer> set = new HashSet<>(); //用来去掉数据离散化操作中重复的数
    int[] nums = new int[1000000];
    int[] union; //并查集
    int[] w; //每个点的颜色
    int count = 0; //不同的数的个数
    public int[] minInterval(int[][] intervals, int[] queries) {
        //数据离散化
        for (int i = 0; i < intervals.length; i++) {
            int a = intervals[i][0];
            int b = intervals[i][1];
            if (!set.contains(a)){
                set.add(a);
                nums[count++] = a;
            }
            if (!set.contains(b)){
                set.add(b);
                nums[count++] = b;
            }
        }
        for (int i = 0; i < queries.length; i++) {
            if (!set.contains(queries[i])){
                set.add(queries[i]);
                nums[count++] = queries[i];
            }
        }
        Arrays.sort(nums, 0, count);
        // 最后一个元素"删掉"后会指向下个元素,因此最后一个元素的下一个元素也会被用到,故初始化需多加一个元素
        union = new int[count + 1];
        w = new int[count + 1];
        Arrays.fill(w, -1);
        for (int i = 0; i <= count; i++) union[i] = i;
        // 按区间大小排序
        Arrays.sort(intervals, (o1, o2) -> (o1[1] - o1[0]) - (o2[1] - o2[0]));
        for (int i = 0; i < intervals.length; i++) {
            int l = get(intervals[i][0]);
            int r = get(intervals[i][1]);
            int len = intervals[i][1] - intervals[i][0] + 1;
            while (find(l) <= r) { //l右边第一个没有被染色的点没有超过r的话
                l = find(l); // 找到l右边第一个没有被染色的点
                w[l] = len; // 将其染色为 len
                union[l] = l + 1; // 指向下一个点
            }
        }

        // 枚举所有的询问 找到答案数组
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int ma = get(queries[i]);
            res[i] = w[ma];
        }
        return res;
    }

    //并查集find函数
    public int find(int x){
        if (union[x] != x) union[x] = find(union[x]);
        return union[x];
    }

    //二分查找
    private int get(int tar) {
        int l = 0;
        int r = count - 1;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (nums[mid] == tar){
                return mid;
            }else if (nums[mid] < tar){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return 0;
    }
}

疯狂的馒头

第51场双周赛 (AK)

将所有数字用字符替换

class Solution {
    public String replaceDigits(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();
        for (int i = 1; i < len; i += 2) {
            chars[i] = shift(chars[i - 1], chars[i]);
        }
        return String.valueOf(chars);
    }

    private static char shift (char c, int n) {
        if (c + n - '0' > 'z') return 'z';
        return (char) (c + n - '0');
    }
}

座位预约管理系统

//去元素时间复杂度O(n)
class SeatManager {
    boolean[] seats;
    int empty;
    public SeatManager(int n) {
        seats = new boolean[n];
        empty = n;
    }

    public int reserve() {
        for (int i = 0; i < seats.length; ++i) {
            if (!seats[i]){
                seats[i] = true;
                return i + 1;
            }
        }
        return -1;
    }

    public void unreserve(int seatNumber) {
        seats[seatNumber - 1] = false;
    }
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.reserve();
 * obj.unreserve(seatNumber);
 */

优先队列

class SeatManager {
    //以O(1)取出队列中权值最小的元素,再以O(logn)维护队列
    PriorityQueue<Integer> seats = new PriorityQueue<>();
    public SeatManager(int n) {
        for (int i = 1; i <= n; ++i) {
            seats.add(i);
        }
    }

    public int reserve() {
        return seats.poll();
    }

    public void unreserve(int seatNumber) {
        seats.add(seatNumber);
    }
}

减小和重新排列数组后的最大元素

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        arr[0] = 1;
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] != arr[i - 1]) {
                arr[i] = arr[i - 1] + 1;
            }
        }
        return arr[arr.length - 1];
    }
}
class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int last = 0;
        for (int i = 0; i < arr.length; ++i) {
            last = Math.min(last + 1, arr[i]);
        }
        return last;
    }
}

最近的房间

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        //先排序
        Arrays.sort(rooms, (o1, o2) -> o2[1] - o1[1]);
        int n = queries.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int absId = Integer.MAX_VALUE;
            int minId = -1;
            for (int j = 0; j < rooms.length; ++j) {
                if (rooms[j][1] < queries[i][1]) {
                    break;
                }
                int tmp = Math.abs(rooms[j][0] - queries[i][0]);
                if (absId == tmp) {
                    if (minId > rooms[j][0]) minId = rooms[j][0];
                } else if (absId > tmp){
                    absId = tmp;
                    minId = rooms[j][0];
                }
            }
            ans[i] = minId;
        }
        return ans;
    }
}

离线算法 & TreeSet

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int[][] q = new int[queries.length][3];
        for(int i = 0; i < q.length; ++i){
            q[i][0] = queries[i][0];
            q[i][1] = queries[i][1];
            q[i][2] = i; // 记录在queries中的原位置
        }
        // 排序
        Arrays.sort(q, (x, y) -> y[1] - x[1]);
        Arrays.sort(rooms, (x, y) -> y[1] - x[1]);

        TreeSet<Integer> set = new TreeSet<>();
        int idx = 0;
        int[] ans = new int[q.length];
        Arrays.fill(ans, -1);
        for (int i = 0; i < q.length; ++i) {
            while (idx < rooms.length && rooms[idx][1] >= q[i][1]) {
                set.add(rooms[idx][0]);
                idx += 1;
            }
            Integer a = set.floor(q[i][0]); // 返回此set中小于或等于给定元素的最大元素
            Integer b = set.ceiling(q[i][0]); // 返回此set中大于或等于给定元素的最小元素
            if (a == null && b == null){
                ans[q[i][2]] = -1;
            } else if (b == null || a == null){
                ans[q[i][2]] = (a == null) ? b : a;
            } else {
                ans[q[i][2]] = ((q[i][0]-a) <= (b-q[i][0])) ? a : b;
            }
        }
        return ans;
    }
}

TreeSet常用方法

LeetCode Weekly 238

K进制表示下的各位数字总和

class Solution {
    public int sumBase(int n, int k) {
        int ans = 0;
        while(n != 0){
            ans += n % k;
            n /= k;
        }
        return ans;
    }
}

— 以下两题为双指针法的两种题型: 前者两个指针一起移动,后者固定一个指针移动另一个指针。 —

最高频元素的频数

二分

能使用二分的依据:j往左走需要的次数严格单调递增。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int l = 1, r = i;
            while (l < r) {
                int mid = l + r >> 1;
                if ((i - mid + 1) * nums[i - 1] - (sums[i] - sums[mid - 1]) <= k) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            ans = Math.max(ans, i - r + 1);
        }
        return ans;
    }
}

双指针

能使用双指针的依据: i往后走,i对应的j一定单调往后走。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        int ans = 0;
        for (int i = 1, j = 1; i <= n; ++i) {
            while ((i - j + 1) * nums[i - 1] - (sums[i] - sums[j - 1]) > k) {
                ++j;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

所有元音按顺序排布的最长子字符串

动态规划 + 哈希表

class Solution {
    public int longestBeautifulSubstring(String word) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();

        int n = word.length();
        int[] dp = new int[n];
        dp[0] = 1;
        int ans = 0;
        map.put(word.charAt(0), 1);
        for (int i = 1; i < n; ++i) {
            char tmp = word.charAt(i);
            if (tmp >= word.charAt(i - 1)) {
                dp[i] = dp[i - 1] + 1;
                map.put(tmp, 1);
                if (map.getOrDefault('a', 0) == 1 && map.getOrDefault('e', 0) == 1 && map.getOrDefault('i', 0) == 1 && map.getOrDefault('o',0) == 1 && map.getOrDefault('u',0) == 1){
                    ans = Math.max(ans, dp[i]);
                }
            }
            else {
                dp[i] = 1;
                map.clear();
                map.put(tmp, 1);
            }
        }
        return ans;
    }
}

注:执行时间较高

双指针

class Solution {
    public int longestBeautifulSubstring(String word) {
        int n = word.length();
        int ans = 0;
        String p = "aeiou";

        for (int i = 0; i < n; ++i) {
            if (word.charAt(i) != 'a') continue;
            int j = i, k = 0;
            while (j < n) {
                if (word.charAt(j) == p.charAt(k)) ++j;
                else {
                    if (k == 4) break;
                    if (word.charAt(j) == p.charAt(k + 1)) {
                        ++j; ++k;
                    } else break;
                }
                if (k == 4) ans = Math.max(ans, j - i); 
            }
            i = j - 1;
        }
        return ans;
    }
}

最高建筑高度🌟

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        auto&& r = restrictions;
        r.push_back({1,0}); //增加约束
        sort(r.begin(), r.end()); //排序
        if (r.back()[0] != n) {
            r.push_back({n, n - 1}); //增加约束
        }
        int m = r.size();

        //从左向右传递约束
        for (int i = 1; i < m; ++i) {
            r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0]);
        }
        //从右向左传递约束
        for (int i = m - 2; i >= 0; --i) {
            r[i][1] = min(r[i][1], r[i + 1][1] + (r[i + 1][0] - r[i][0]));
        }

        int ans = 0;
        for (int i = 1; i < m; ++i) {
            //计算 r[i - 1][0] 和 r[i][0] 之间建筑的最大高度
            int best = (r[i - 1][1] + r[i][1] + r[i][0] - r[i - 1][0]) / 2;
            ans = max(ans, best);
        }
        return ans;
    }
};

LeetCode Weekly 237

判断句子是否为全字母句

class Solution {
    public boolean checkIfPangram(String sentence) {
        int ans = 0;
        for (int i = 0; i < sentence.length(); ++i) {
            ans |= (1 << (sentence.charAt(i) - 'a'));
        }
        return ans == (1 << 26) - 1;
    }
}

雪糕的最大数量

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int cnt = 0;
        Arrays.sort(costs);
        for (int cost : costs) {
            if (coins >= cost) {
                coins -= cost;
                ++cnt;
            }
            else break;
        }
        return cnt;
    }
}

单线程CPU🌟

排序 & 优先队列(小根堆)

class Solution {
    class Task {
        int id;
        int enqueueTime;
        int processingTime;

        public Task (int id, int enqueueTime, int processingTime) {
            this.id = id;
            this.enqueueTime = enqueueTime;
            this.processingTime = processingTime;
        }
    }
    public int[] getOrder(int[][] tasks) {
        int len = tasks.length;
        List<Task> taskList = new ArrayList<Task>();
        for (int i = 0; i < len; ++i) {
            taskList.add(new Task(i, tasks[i][0], tasks[i][1]));
        }
        //按入队时间排序
        Collections.sort(taskList, (t1, t2) -> t1.enqueueTime - t2.enqueueTime);
        //优先队列
        PriorityQueue<Task> minHeap = new PriorityQueue<Task>((t1, t2) -> {
            //短作业优先
            if (t1.processingTime != t2.processingTime) return t1.processingTime - t2.processingTime;
            //运行时间相等时按照id排序
            else return t1.id - t2.id;
        });

        long now = 0; //时间戳
        int[] ret = new int[len];
        int i = 0; //taskList坐标
        int j = 0; //ret坐标
        while (i < len) {
            //将所有开始时间小于等于当前时间戳的task放入优先队列中
            while (i < len && taskList.get(i).enqueueTime <= now) {
                minHeap.offer(taskList.get(i++));
            }
            //当堆中没有任务时,前移时间戳
            if (minHeap.isEmpty()) {
                now = (long) taskList.get(i).enqueueTime;
                //加入task进队列
                while (i < len && taskList.get(i).enqueueTime <= now) {
                    minHeap.offer(taskList.get(i++));
                }
            }
            //取出任务执行
            Task t = minHeap.poll();
            ret[j++] = t.id;
            now += (long) t.processingTime;
        }
        //此时所有taskList所有任务均已执行或加入队列中
        //清空队列剩余任务
        while (!minHeap.isEmpty()) {
            ret[j++] = minHeap.poll().id;
        }
        return ret;
    }
}

所有数对按位与结果的异或和

逐位确定结果

class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int ans = 0;
        //依次确定答案二进制表示中的每一位
        for (int k = 30; k >= 0; --k) {
            int cnt1 = 0;
            for (int num : arr1) {
                if ((num & (1 << k)) != 0) {
                    ++cnt1;
                }
            }
            int cnt2 = 0;
            for (int num : arr2) {
                if ((num & (1 << k)) != 0) {
                    ++cnt2;
                }
            }
            //当cnt1和cnt2均为奇数时,结果中k位为1
            //一个数与 0 进行异或运算,它的值不改变
            if ((cnt1 % 2 == 1) && (cnt2 % 2 == 1)) {
                ans |= (1 << k);
            }
        }
        return ans;
    }
}

利用与异或运算法则

class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int p1 = 0, p2 = 0;
        for (int i : arr1) {
            p1 ^= i;
        }
        for (int j : arr2) {
            p2 ^= j;
        }
        return p1 & p2;
    }
}

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