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

疯狂的馒头


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