Ligh0x74's Blog

2023-08-21发表2023-08-21更新算法 / LeetCode6 分钟读完 (大约831个字)

统计和小于目标的下标对数目

使用排序 + 双指针优化。如果 \(nums[lo]+nums[hi]<target\)，那么 \([lo+1,hi]\) 范围内的数都能与 \(nums[lo]\) 组成对，\(lo\) 加一；反之，\([lo,hi-1]\) 范围内的数都不能与 \(nums[hi]\) 组成对，\(hi\) 减一。

Java

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int lo = 0, hi = nums.size() - 1, ans = 0;
        while (lo < hi) {
            if (nums.get(lo) + nums.get(hi) < target) {
                ans += hi - lo;
                lo++;
            } else {
                hi--;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0;
        for (int i = 0, j = n - 1; i < j; ) {
            if (nums[i] + nums[j] < target) {
                ans += j - i;
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }
};

循环增长使字符串子序列等于另一个字符串

贪心取就行。

Java

class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int m = str1.length(), n = str2.length(), j = 0;
        for (int i = 0; i < m && j < n; i++) {
            if (str1.charAt(i) == str2.charAt(j) || (str1.charAt(i) + 1 - 'a') % 26 == str2.charAt(j) - 'a') {
                j++;
            }
        }
        return j == n;
    }
}

C++

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int m = str1.size(), n = str2.size(), j = 0;
        for (int i = 0; i < m && j < n; i++) {
            if (str1[i] == str2[j] || (str1[i] + 1 - 'a') % 26 == str2[j] - 'a') {
                j++;
            }
        }
        return j == n;
    }
};

将三个组排序

要将 \(nums\) 变为美丽数组，就要将 \(nums\) 变为非递减的形式，所以问题就变为求最长非递减子序列。

Java

动态规划：

class Solution {
    public int minimumOperations(List<Integer> nums) {
        int n = nums.size(), ans = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums.get(i) >= nums.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return n - ans;
    }
}

贪心 + 二分：

class Solution {
    public int minimumOperations(List<Integer> nums) {
        int n = nums.size(), maxLen = 0;
        int[] aux = new int[n];
        for (int x : nums) {
            int lo = 0, hi = maxLen - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (aux[mid] <= x) lo = mid + 1;
                else hi = mid - 1;
            }
            aux[lo] = x;
            if (lo == maxLen) maxLen++;
        }
        return n - maxLen;
    }
}

状态机 DP：

有点妙啊，\(dp[i][j]\) 表示将子数组 \([0,i]\) 变为以 \([1,j]\) 为结尾的美丽数组所需的最小修改次数，然后可以空间优化。

class Solution {
	public int minimumOperations(List<Integer> nums) {
		int[] dp = {Integer.MAX_VALUE, 0, 0, 0};
		for (int x : nums) {
			for (int i = 1; i <= 3; i++) {
				dp[i] = Math.min(dp[i - 1], dp[i] + (x == i ? 0 : 1));
			}
		}
		return dp[3];
	}
}

C++

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int dp[4] = {INT_MAX, 0, 0, 0};
        for (int x : nums) {
            for (int i = 1; i <= 3; i++) {
                dp[i] = min(dp[i - 1], dp[i] + (x != i));
            }
        }
        return dp[3];
    }
};

范围中美丽整数的数目

经典数位 DP 没什么好说的，主要是记忆化取模，边乘边取模。

Java

class Solution {
    public int numberOfBeautifulIntegers(int low, int high, int k) {
        return f(0, 10, 0, true, false, high + "", k, new Integer[10][20][k])
                - f(0, 10, 0, true, false, low - 1 + "", k, new Integer[10][20][k]);
    }
    
    private int f(int i, int diff, int mod, boolean isLimit, boolean isNum, String s, int k, Integer[][][] dp) {
        if (i == s.length()) {
            return isNum && diff == 10 && mod == 0 ? 1 : 0;
        }
        if (!isLimit && isNum && dp[i][diff][mod] != null) {
            return dp[i][diff][mod];
        }
        int res = 0;
        if (!isNum) res += f(i + 1, diff, mod, false, false, s, k, dp);
        int lo = isNum ? 0 : 1, hi = isLimit ? s.charAt(i) - '0' : 9;
        for (int d = lo; d <= hi; d++) {
            res += f(i + 1, diff + d % 2 * 2 - 1, (mod * 10 + d) % k, isLimit && d == hi, true, s, k, dp);
        }
        if (!isLimit && isNum) {
            dp[i][diff][mod] = res;
        }
        return res;
    }
}

C++

class Solution {
public:
    int numberOfBeautifulIntegers(int low, int high, int k) {
        string s;
        const int BASE = 10;
        int dp[10][20][k];
        
        auto f = [&](auto self, int i, int diff, int mod, bool isLimit, bool isNum) {
            if (i == s.size()) {
                return isNum && diff == 0 && mod == 0 ? 1 : 0;
            }
            if (!isLimit && isNum && dp[i][diff + BASE][mod] != -1) {
                return dp[i][diff + BASE][mod];
            }
            int res = 0;
            if (!isNum) res += self(self, i + 1, diff, mod, false, false);
            int lo = isNum ? 0 : 1, hi = isLimit ? s[i] - '0' : 9;
            for (int d = lo; d <= hi; d++) {
                res += self(self, i + 1, diff + d % 2 * 2 - 1, (mod * 10 + d) % k, isLimit && d == hi, true);
            }
            if (!isLimit && isNum) dp[i][diff + BASE][mod] = res;
            return res;
        };

        auto calc = [&](int x) {
            s = to_string(x);
            memset(dp, -1, sizeof(dp));
            return f(f, 0, 0, 0, true, false);
        };

        return calc(high) - calc(low - 1);
    }
};

2023-08-14发表2023-08-15更新算法 / LeetCode7 分钟读完 (大约979个字)

第 358 场力扣周赛

数组中的最大数对和

赛时直接暴力做，赛后优化代码参考自灵神。就是维护每个最大数位对应的最大值，然后可以优化掉一个 \(n\)。

class Solution {
    public int maxSum(int[] nums) {
        int ans = -1;
        int[] maxVal = new int[10];
        Arrays.fill(maxVal, Integer.MIN_VALUE);
        for (int x : nums) {
            int maxD = 0;
            for (int y = x; y > 0; y /= 10) {
                maxD = Math.max(maxD, y % 10);
            }
            ans = Math.max(ans, x + maxVal[maxD]);
            maxVal[maxD] = Math.max(maxVal[maxD], x);
        }
        return ans;
    }
}

翻倍以链表形式表示的数字

做乘法惯性思维，就想着从最低位开始乘然后进位，结果可以从高位开始乘，因为乘二时低位最多就进一位。（如果从低位开始乘，就转数组或者反转链表吧）

class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head.val > 4) head = new ListNode(0, head);
        for (ListNode cur = head; cur != null; cur = cur.next) {
            cur.val = cur.val * 2 % 10;
            if (cur.next != null && cur.next.val > 4) {
                cur.val++;
            }
        }
        return head;
    }
}

限制条件下元素之间的最小绝对差

一开始没反应过来，以为找最大值和最小值就行。结果发现是让绝对值最小，要找最接近当前值的那个值，那就可以使用 TreeSet。但是我又搞复杂了，其实只要维护一个方向就可以，但是我维护了左右方向距离为 \(x\) 的值。

class Solution {
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        int n = nums.size(), ans = Integer.MAX_VALUE;
        TreeSet<Integer> set = new TreeSet<>();
        set.add(Integer.MAX_VALUE);
        set.add(Integer.MIN_VALUE / 2);
        for (int i = x; i < n; i++) {
            set.add(nums.get(i - x));
            int cur = nums.get(i);
            ans = Math.min(ans, Math.min(cur - set.floor(cur), set.ceiling(cur) - cur));
        }
        return ans;
    }
}

吐血吐血，赛后 Debug 发现分解质因数的代码打错一个变量，改了就能 AC。一开始也看错题目了，以为答案是乘质数分数，结果答案是乘数组中的值，那么优先选最大的数就是最优的。问题就变成给定某个数，选择它为目标值的数组有多少个。数组的个数等于左边质数分数小于当前值能到达的最远位置，乘右边质数分数大于等于当前值能到达的最远位置。所以我们可以先对质数分数降序排序，相同分数再对下标升序排序，按照这个顺序处理元素，使用 TreeSet 维护已处理的值，就可以比较方便的得到左右两边的边界，从而得到以当前值为目标值的数组个数。最后，按照值从大到小来做乘法。

计算每个位置有多少数组还可以使用单调栈（更快），详情见题解区。

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    private static final int N = (int) 1e5 + 1;
    private static int[] f = new int[N];

    // 素数筛
    static {
        for (int i = 2; i < N; i++) {
            if (f[i] == 0) {
                for (int j = i; j < N; j += i) {
                    f[j]++;
                }
            }
        }
    }

    public int maximumScore(List<Integer> nums, int k) {
        // 计算每个位置有多少个数组
        int n = nums.size();
        TreeSet<Integer> set = new TreeSet<>();
        set.add(-1); set.add(n);
        var aux = new Integer[n];
        for (int i = 0; i < n; i++) aux[i] = i;
        Arrays.sort(aux, (a, b) -> {
            int x = nums.get(a), y = nums.get(b);
            return f[x] != f[y] ? f[y] - f[x] : a - b;
        });
        long[] cnt = new long[n];
        for (int i : aux) {
            long l = i - set.ceiling(i);
            long r = set.floor(i) - i;
            cnt[i] = l * r;
            set.add(i);
        }
        // 从大到小枚举值，计算答案
        long ans = 1L;
        for (int i = 0; i < n; i++) aux[i] = i;
        Arrays.sort(aux, (a, b) -> nums.get(b) - nums.get(a));
        for (int i = 0; k > 0; i++) {
            int t = (int) Math.min(cnt[aux[i]], k);
            ans = (ans * power(nums.get(aux[i]), t)) % MOD;
            k -= t;
        }
        return (int) ans;
    }
    
    private long power(long x, int n) {
        long res = 1L;
        while (n != 0) {
            if (n % 2 == 1) res = res * x % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }
}

2023-08-07发表2023-08-15更新算法 / LeetCode9 分钟读完 (大约1366个字)

第 357 场力扣周赛

故障键盘

方法一：暴力模拟

比赛直接暴力模拟。

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)\)。

方法二：双端队列

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\) 的合并。

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 + 二分

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 变小，优雅度有变大的可能。

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

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)\)。

统计和小于目标的下标对数目

循环增长使字符串子序列等于另一个字符串

将三个组排序

范围中美丽整数的数目

数组中的最大数对和

翻倍以链表形式表示的数字

限制条件下元素之间的最小绝对差

操作使得分最大

故障键盘

判断是否能拆分数组

找出最安全路径

子序列最大优雅度

链接

分类

最新文章

归档

标签

链接