Ligh0x74's Blog

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

tcdr

模拟。

Java

public static void solve() {
    String s = io.next();
    var sb = new StringBuilder();
    Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
    for (char c : s.toCharArray()) {
        if (!set.contains(c)) sb.append(c);
    }
    io.println(sb.toString());
}

C++

void solve() {
    string s;
    cin >> s;
    s.erase(remove_if(s.begin(), s.end(), [&](char c) {
        return set{'a', 'e', 'i', 'o', 'u'}.count(c);
    }), s.end());
    cout << s << "\n";
}

The Middle Day

模拟。

Java

public static void solve() {
    int m = io.nextInt();
    int[] d = new int[m];
    int tot = 0;
    for (int i = 0; i < m; i++) {
        d[i] = io.nextInt();
        tot += d[i];
    }
    int mid = (tot + 1) / 2;
    for (int i = 0; i < m; i++) {
        if (mid <= d[i]) {
            io.println(i + 1 + " " + mid);
            return;
        }
        mid -= d[i];
    }
}

C++

void solve() {
    int m;
    cin >> m;
    int tot = 0;
    vector<int> d(m);
    for (int i = 0; i < m; i++) {
        cin >> d[i];
        tot += d[i];
    }
    int mid = (tot + 1) / 2;
    for (int i = 0; i < m; i++) {
        if (mid <= d[i]) {
            cout << i + 1 << " " << mid << "\n";
            return;
        }
        mid -= d[i];
    }
}

Flavors

模拟。

Java

public static void solve() {
    int n = io.nextInt();
    List<Integer>[] buckets = new List[n + 1];
    Arrays.setAll(buckets, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        int f = io.nextInt(), s = io.nextInt();
        buckets[f].add(s);
    }
    int ans = 0, max1 = 0, max2 = 0;
    for (var bucket : buckets) {
        if (bucket.isEmpty()) continue;
        Collections.sort(bucket, (a, b) -> b - a);
        int a = bucket.get(0);
        if (a > max1) {
            max2 = max1;
            max1 = a;
        } else if (a > max2) {
            max2 = a;
        }
        if (bucket.size() < 2) continue;
        int b = bucket.get(1);
        ans = Math.max(ans, a + b / 2);
    }
    ans = Math.max(ans, max1 + max2);
    io.println(ans);
}

C++

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> buckets(n + 1);
    for (int i = 0; i < n; i++) {
        int f, s;
        cin >> f >> s;
        buckets[f].push_back(s);
    }
    int ans = 0, max1 = 0, max2 = 0;
    for (auto &bucket : buckets) {
        if (bucket.empty()) continue;
        nth_element(bucket.begin(), bucket.begin() + 1, bucket.end(), greater());
        if (bucket[0] > max1) {
            max2 = max1;
            max1 = bucket[0];
        } else if (bucket[0] > max2) {
            max2 = bucket[0];
        }
        if (bucket.size() < 2) continue;
        ans = max(ans, bucket[0] + bucket[1] / 2);
    }
    ans = max(ans, max1 + max2);
    cout << ans << "\n";
}

算是暴力吧。首先最多执行 \(m+n\) 次操作，然后每次操作将所有行和列遍历，判断是否可以标记。如果不优化，那么遍历的复杂度是 \(O(mn)\)，总时间复杂度就是 \(O(mn(m+n))\)，会超时。可以维护剩余的行数 \(r\) 和剩余的列数 \(c\)，那么如果某行的某颜色的数量等于列数，那么就说明可以标记该行，列同理。这样我们就可以只维护行列中的每个颜色有多少饼干，而不需要维护位置关系，从而将遍历的时间复杂度降为 \(O(26(m+n))\)。

Java

public static void solve() {
    int m = io.nextInt(), n = io.nextInt();
    String[] arr = new String[m];
    for (int i = 0; i < m; i++) {
        arr[i] = io.next();
    }
    int[][] row = new int[m][26];
    int[][] col = new int[n][26];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            row[i][arr[i].charAt(j) - 'a']++;
            col[j][arr[i].charAt(j) - 'a']++;
        }
    }
    int r = m, c = n;
    boolean[] vr = new boolean[m];
    boolean[] vc = new boolean[n];
    for (int k = 0; k < m + n; k++) {
        List<int[]> mr = new ArrayList<>();
        List<int[]> mc = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if (vr[i]) continue;
            for (int j = 0; j < 26; j++) {
                if (row[i][j] == c && c >= 2) {
                    mr.add(new int[]{i, j});
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (vc[i]) continue;
            for (int j = 0; j < 26; j++) {
                if (col[i][j] == r && r >= 2) {
                    mc.add(new int[]{i, j});
                }
            }
        }
        for (int[] p : mr) {
            r--;
            vr[p[0]] = true;
            for (int i = 0; i < n; i++) {
                col[i][p[1]]--;
            }
        }
        for (int[] p : mc) {
            c--;
            vc[p[0]] = true;
            for (int i = 0; i < m; i++) {
                row[i][p[1]]--;
            }
        }
    }
    io.println(r * c);
}

Prerequisites

首先找到第 \(1\) 本书的所有前置书，然后对所有书进行拓扑排序，将之前找到的前置书按拓扑排序的倒序打印即可。或者直接 DFS。。

Java

public static void solve() {
    int n = io.nextInt();
    int[] indegree = new int[n];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n; i++) {
        int c = io.nextInt();
        for (int j = 0; j < c; j++) {
            int q = io.nextInt() - 1;
            g[i].add(q);
            indegree[q]++;
        }
    }

    boolean[] mark = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    q.offer(0);
    while (!q.isEmpty()) {
        int x = q.poll();
        for (int y : g[x]) {
            if (mark[y]) continue;
            mark[y] = true;
            q.offer(y);
        }
    }

    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.offer(i);
        }
    }
    Deque<Integer> ans = new ArrayDeque<>();
    while (!q.isEmpty()) {
        int x = q.poll();
        if (mark[x]) ans.push(x);
        for (int y : g[x]) {
            if (--indegree[y] == 0) {
                q.offer(y);
            }
        }
    }
    while (!ans.isEmpty()) io.print(ans.pop() + 1 + " ");
    io.println();
}

C++

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            int q;
            cin >> q;
            q--;
            adj[i].push_back(q);
        }
    }

    vector<bool> mark(n);
    auto dfs = [&](auto self, int x) {
        if (mark[x]) {
            return;
        }
        for (auto y : adj[x]) {
            self(self, y);
        }
        mark[x] = true;
        if (x != 0) {
            std::cout << x + 1 << " ";
        }
    };
    dfs(dfs, 0);
    cout << "\n";
}

Shortcuts

动态规划，调试好久。。如果所有点都选，那么答案最多为 \(10^{9}\)，所以可以确定不选的点不会超过 \(30\)。然后定义状态 \(dp[i][j]\) 表示到达第 \(i\) 个点并且总共跳过 \(j\) 个点的最短距离。如何想到定义该状态呢，因为答案和具体选哪几个点无关，只和最短距离以及跳过多少个点有关，大概是这样吧。

Java

public static void solve() {
    int c = 30;
    int n = io.nextInt();
    int[] x = new int[n];
    int[] y = new int[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        y[i] = io.nextInt();
    }
    double[][] dp = new double[n][c];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    dp[0][0] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < c; j++) {
            for (int k = i + 1; k < n && k - i - 1 + j < c; k++) {
                int nj = j + k - i - 1;
                dp[k][nj] = Math.min(dp[k][nj], dp[i][j] + Math.sqrt((x[i] - x[k]) * (x[i] - x[k]) + (y[i] - y[k]) * (y[i] - y[k])));
            }
        }
    }
    double ans = Integer.MAX_VALUE;
    for (int i = 0; i < c; i++) {
        ans = Math.min(ans, dp[n - 1][i] + (i == 0 ? 0 : 1 << (i - 1)));
    }
    io.println(ans);
}

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

第 359 场力扣周赛

判别首字母缩略词

Java

class Solution {
    public boolean isAcronym(List<String> words, String s) {
        int n = words.size(), m = s.length();
        if (n != m) return false;
        for (int i = 0; i < n; i++) {
            if (words.get(i).charAt(0) != s.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
        int m = words.size(), n = s.size();
        if (m != n) return false;
        for (int i = 0; i < n; i++) {
            if (words[i][0] != s[i]) {
                return false;
            }
        }
        return true;
    }
};

k-avoiding 数组的最小总和

贪心。

Java

class Solution {
    public int minimumSum(int n, int k) {
        int m = Math.min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
}

C++

class Solution {
public:
    int minimumSum(int n, int k) {
        int m = min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
};

销售利润最大化

不从动态规划的角度思考，我首先用的是对左端点排序。如果用动态规划，那么根据转移方程就会对右端点排序，处理方式也比对左端点排序简单一些。还可以不排序做，使用桶存储相同 \(end\) 的 \(offer\)，分别处理每个桶。

Java

class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Collections.sort(offers, (a, b) -> a.get(1) - b.get(1));
        offers.add(List.of(n - 1, n - 1, 0));
        int m = offers.size(), i = 0;
        int[] leftMax = new int[n + 1];
        for (var offer : offers) {
            int s = offer.get(0), e = offer.get(1), g = offer.get(2);
            for (; i <= e; i++) leftMax[i + 1] = leftMax[i];
            leftMax[e + 1] = Math.max(leftMax[e + 1], leftMax[s] + g);
        }
        return leftMax[n];
    }
}

C++

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        vector<vector<pair<int, int>>> groups(n);
        for (auto &offer : offers) {
            groups[offer[1]].emplace_back(offer[0], offer[2]);
        }
        vector<int> f(n + 1);
        for (int end = 0; end < n; end++) {
            f[end + 1] = f[end];
            for (auto &[start, gold] : groups[end]) {
                f[end + 1] = max(f[end + 1], f[start] + gold);
            }
        }
        return f[n];
    }
};

找出最长等值子数组

Java

滑动窗口：

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        Map<Integer, Integer> map = new HashMap<>();
        int lo = 0, hi = 0, ans = 0;
        while (hi < n) {
            map.merge(nums.get(hi++), 1, Integer::sum);
            if (hi - lo - map.get(nums.get(lo)) > k) {
                map.merge(nums.get(lo++), -1, Integer::sum);
            }
            ans = Math.max(ans, map.get(nums.get(lo)));
        }
        while (lo + 1 < n) {
            map.merge(nums.get(lo++), -1, Integer::sum);
            ans = Math.max(ans, map.get(nums.get(lo)));
        }
        return ans;
    }
}

滑动窗口（优化）：

优化一：观察到 \(1\leq nums[i]\leq nums.lenth\)，所以可以用数组模拟哈希表。
优化二：滑动窗口直接枚举右端点，这样可以枚举到所有情况。但是如何保证删除的元素数量小于等于 \(k\) 呢？当左端点的值 \(nums[i]\) 不能构成等值数组，则将左端点右移。为什么这样可以保证？当 \(nums[i]\neq nums[j]\) 时，移动左端点不影响答案；当 \(nums[i]=nums[j]\) 时，移动左端点可以保证删除的元素数量小于等于 \(k\)。

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

C++

分组 + 双指针：

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        vector<vector<int>> pos(n + 1);
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        for (auto &ps : pos) {
            int left = 0;
            for (int right = 0; right < ps.size(); right++) {
                while (ps[right] - ps[left] - right + left > k) {
                    left++;
                }
                ans = max(ans, right - left + 1);
            }
        }
        return ans;
    }
};

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

第 111 场力扣夜喵双周赛

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

使用排序 + 双指针优化。如果 \(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);
    }
};

tcdr

The Middle Day

Flavors

Magical Cookies

Prerequisites

Shortcuts

判别首字母缩略词

k-avoiding 数组的最小总和

销售利润最大化

找出最长等值子数组

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

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

将三个组排序

范围中美丽整数的数目

链接

分类

最新文章

归档

标签

链接