旺崽的博客

要么天赋异禀，要么天道酬勤

0%

发表于 分类于 Valine：

LeetCode 1208 尽可能使字符串相等

题目链接


给你两个长度相同的字符串，s 和 t。


将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。


用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。


如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。


如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1：

1
2
3
输入：s = "abcd", t = "bcdf", cost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

示例 2：

1
2
3
输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3：

1
2
3
输入：s = "abcd", t = "acde", cost = 0
输出：1
解释：你无法作出任何改动，所以最大长度为 1。

前缀和+二分~
先预处理所有位置差的绝对值的前缀和，然后对每一个位置，二分不超过 cost 的最大位置，不断更新答案即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        vector<int> dif;
        for (int i = 0; i < s.size(); i++) {
            if (dif.empty()) dif.push_back(abs(s[i] - t[i]));
            else dif.push_back(abs(s[i] - t[i]) + dif.back());
        }
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            if (abs(s[i] - t[i]) > maxCost) continue;
            else {
                int pos = upper_bound(dif.begin(), dif.end(), dif[i] + maxCost - abs(s[i] - t[i])) - dif.begin();
                ans = max(ans, pos - i);
            }
        }
        return ans;
    }
};

发表于 分类于 Valine：

LeetCode 424 替换后的最长重复字符

题目链接

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 1e4。

示例 1：

1
2
3
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

1
2
3
4
5
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

双指针，用 $l,r$ 两个指针寻找最大长度，先移动 $r$ 指针，并记录此时 $[l,r]$ 区间内某一字符出现最多的次数 $mx$，显然 $k$ 次替换最大的区间长度就是 $l+mx+k-1$，也即 $r<l+mx+k-1$，一旦 $r$ 指针超过此范围，将 $l$ 指针向右移动即可，整个思路就是先移动右指针，再移动左指针，寻找最大区间长度即可，AC代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> num(26);
        int mx = 0, l = 0, r = 0, n = s.size();
        while (r < n) {
            num[s[r] - 'A']++;
            mx = max(mx, num[s[r] - 'A']);
            if (r - l + 1 - mx > k) {
                num[s[l] - 'A']--;
                l++;
            }
            r++;
        }
        return r - l;
    }
};

发表于 分类于 Valine：

LeetCode 839 相似字符串组

题目链接

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，”tars” 和 “rats” 是相似的 (交换 0 与 2 的位置)； “rats” 和 “arts” 也是相似的，但是 “star” 不与 “tars”，”rats”，或 “arts” 相似。

总之，它们通过相似性形成了两个关联组：{“tars”, “rats”, “arts”} 和 {“star”}。注意，”tars” 和 “arts” 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

示例 1：

1
2
输入：strs = ["tars","rats","arts","star"]
输出：2

示例 2：

1
2
输入：strs = ["omv","ovm"]
输出：1

并查集~
双重循环遍历字符串组，把相似的字符串合并到同一个并查集里，最后找一下并查集里连通块的个数即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> f;

    int findFather(int x) {
        return x == f[x] ? x : f[x] = findFather(f[x]);
    }

    bool check(string &a, string &b, int len) {
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if (a[i] != b[i]) {
                cnt++;
                if (cnt > 2) return 0;
            }
        }
        return 1;
    }

    int numSimilarGroups(vector<string> &strs) {
        int n = strs.size();
        if (n == 0) return 0;
        f.resize(n);
        for (int i = 0; i < n; i++) f[i] = i;
        int len = strs[0].size(), ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int fi = findFather(i), fj = findFather(j);
                if (fi == fj) continue;
                if (check(strs[i], strs[j], len)) {
                    f[fi] = fj;
                }
            }
        }
        for (int i = 0; i < n; i++) if (f[i] == i) ans++;
        return ans;
    }
};

发表于 分类于 Valine：

LeetCode 778 水位上升的泳池中游泳

题目链接

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1，N-1)？

示例 1:

1
2
3
4
5
6
7
输入: [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。

等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例 2:

1
2
3
4
输入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
输出: 16
解释:
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

二分+BFS~
这题跟 LeetCode 1631 最小体力消耗路径 几乎一模一样，就是二分最少时间，然后从左上角到右下角 BFS 即可，不同的时 BFS 里面的判别条件稍微改了一下而已，即当前水位高度必须大于等于平台高度，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
private:
    int m, n, dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
public:
    bool check(int x, vector<vector<int>> &grid) {
        queue<pair<int, int>> q;
        vector<int> vis(m * n);
        pair<int, int> a, b;
        q.push({0, 0});
        vis[0] = 1;
        while (!q.empty()) {
            a = q.front();
            q.pop();
            if (a.first == m - 1 && a.second == n - 1) {
                return 1;
            }
            for (int i = 0; i < 4; i++) {
                b.first = a.first + dir[i][0];
                b.second = a.second + dir[i][1];
                if (b.first >= 0 && b.first < m && b.second >= 0 && b.second < n && !vis[b.first * n + b.second] &&
                    grid[b.first][b.second] <= x) {
                    vis[b.first * n + b.second] = 1;
                    q.push(b);
                }
            }
        }
        return 0;
    }

    int swimInWater(vector<vector<int>> &grid) {
        m = grid.size(), n = grid[0].size();
        int l = grid[0][0], r = 2500;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid, grid)) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
};

发表于 分类于 Valine：

2021牛客寒假算法基础集训营3 H.数字串

题目链接

题目描述

牛牛发现了一种方法可以将只包含小写字母的字符串按照以下方式使其转换成一个数字串：
取其中的每个字母，$\mathit a$ 转换为 $\text 1$，$\mathit b$ 转换为 $\text 2……\mathit z$ 转换为 $\text 26$，然后将这些数字拼接起来。
例如，$\mathit abcz$ 可以转换为 $\text 12326$。
现在给出一个只包含小写字母的字符串 $\mathit S$，你需要找到一个只包含小写字母的字符串 $\mathit T$，使得两个串不相同但是能转换成相同的数字串。

输入描述:

一行一个长度不超过 $10^{6}$ 的小写字母字符串 $\mathit S$。

输出描述:

一行一个长度不超过 $2×10^{6}$ 的小写字母字符串 $\mathit T$。
如果无解，请输出 $\text -1$。
如果答案有解且你输出的字符串包含了除了小写字母以外的字符或长度超过了 $2×10^{6}$，那么你会得到“答案错误”的返回结果。
否则如果答案有解且你的答案与输入的字符串可以转换为一样的数字串，那么你的答案会被认为是正确的。

示例1

输入

1
cwc

输出

1
cbcc

示例2

输入

1
ccc

输出

1
-1

打 ACM 的同仁们可以多了解一下 py，针对字符串类 py 提供了大量现成的函数，非常方便，拿这题举例，我们很容易发现替换其实就是以下几种情况：

  • $aa<->k$
  • $ab<->l$
  • $ac<->m$
  • $\cdots$
  • $bf<->z$

也就是说我们只需要把上述情况都试一遍，如果替换之后都和原串一样，直接输出 $-1$ 即可，如果替换之后和原串不一样就是正确答案，注意 $t$ 这个字符对应的 $20$ 无法转换成两个字符，特判掉即可，上述的替换在 py 里直接有一个 replace 函数，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys

s = input()
for i in range(11, 27):
    if i == 20:
        continue
    a = s.replace(chr(97 + i - 1), chr(97 + i // 10 - 1) + chr(97 + i % 10 - 1))
    if a != s:
        print(a)
        sys.exit(0)
    a = s.replace(chr(97 + i // 10 - 1) + chr(97 + i % 10 - 1), chr(97 + i - 1))
    if a != s:
        print(a)
        sys.exit(0)
print(-1)

发表于 分类于 Valine：

2021牛客寒假算法基础集训营3 G.糖果

题目链接

题目描述

在一个幼儿园里面有 $\mathit n$ 个小朋友，分别编号 $\text 1,2,…,n$。在这些小朋友中有一些小朋友互为朋友关系，总共有 $\mathit m$ 对朋友。
作为幼儿园老师，你想买一些糖果分给小朋友，你知道第 $\mathit i$ 个小朋友想要至少 $a_{i}$ 个糖果，否则他就会不开心。
同时，如果一个小朋友得到的糖果数小于他某个朋友得到的糖果数，他也会不开心。
请问你最少买多少糖果才能保证每个小朋友都不会不开心呢？

输入描述:

第一行以空格分隔的两个整数 $\mathit n,m$。
第二行以空格分隔的 $\mathit n$ 个正整数 $a{i}$。
接下来 $\mathit m$ 行每行以空格分隔的两个正整数 $\mathit u,v$u,v，代表 $\mathit u$ 是 $\mathit v$ 的朋友，$\mathit v$ 是 $\mathit u$ 的朋友。
$1\leq n\leq 10^{6}$
$0\leq m\leq 10^{6}$
$1\leq a{i} \leq 10^{9}$
$1\leq u,v \leq n,u≠v$

输出描述:

购买的最少糖果数以保证每个小朋友都不会不开心。

示例1

输入

1
2
3
3 1
1 2 3
1 2

输出

1
7

DFS~
显然我们可以根据朋友关系把图分成很多个连通块，在每一个连通块中，可以求出连通块中元素的数量 $cnt$ 和最大糖果数量 $a$，则最后的答案即为：

AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, m, u, v, vis[N];
vector<int> G[N];
ll ans, cnt, mx, a[N];

void dfs(int x) {
    vis[x] = 1;
    cnt++;
    mx = max(mx, a[x]);
    for (auto y:G[x]) {
        if (!vis[y]) dfs(y);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    while (m--) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt = mx = 0;
            dfs(i);
            ans += cnt * mx;
        }
    }
    printf("%lld", ans);
    return 0;
}

发表于 Valine：

ACM算法分类及完成情况

今天闲着无聊，就把ACM的算法分类记录了一下(若有遗漏，后续会补充)顺便记录一下自己的学习进度，嘻嘻(●’◡’●)，编程之路，道阻且长，继续加油！愿所有努力的人都能有所收获！