💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🚂 01.LYA的回文项链

问题描述

LYA喜欢收藏各种漂亮的项链。这次，她从古董商那里淘到了一条由 颗珍珠组成的项链，每颗珍珠都刻有一个小写字母。LYA希望通过一些魔法，将这条项链变成回文项链，即正着读和反着读珍珠上的字母都一样。

LYA掌握了两种魔法，每种魔法都需要消耗一定的魔力值：

1. 第一种魔法可以将项链最左边的珍珠取下，并将其戴在项链的最右边。例如，对于项链 ，使用一次这种魔法后，项链会变成 。
2. 第二种魔法可以将项链上的任意一颗珍珠上的字母变成任意一个小写字母。

现在，LYA想知道，最少需要使用多少魔力值，才能将这条项链变成回文项链呢？

输入格式

第一行包含一个正整数 ，表示项链的珍珠数量。

第二行包含一个长度为 的字符串，由小写字母组成，表示项链上每颗珍珠的字母。

输出格式

输出一个整数，表示将项链变成回文项链所需的最少魔力值。

样例输入

5
kkhbc

样例输出

2

数据范围

题解

本题可以分别计算两种操作的最小次数，然后取两者之和即可。

对于第一种操作，我们可以枚举将项链旋转 次，然后计算旋转后的项链需要修改多少个字符才能成为回文串。这个可以通过双指针的方式，分别从头尾开始比较对应位置的字符，统计不同字符的个数。

对于第二种操作，我们可以直接计算项链前后对应位置的不同字符个数，然后除以 即可。

最后，我们取这两种操作次数之和的最小值，即为最终答案。

时间复杂度为 ，空间复杂度为 。

参考代码

• Cpp

#include <iostream>
#include <string>
using namespace std;

int n;
string s;

int check(string s) {
    int cnt = 0;
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        if (s[i] != s[j]) cnt++;
    }
    return cnt;
}

int main() {
    cin >> n >> s;
    int ans = n;
    for (int i = 0; i < n; i++) {
        ans = min(ans, i + check(s));
        s = s.substr(1) + s[0];
    }
    cout << ans << endl;
    return 0;
}

• Python

n = int(input())
s = input()

def check(s):
    cnt = 0
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            cnt += 1
    return cnt

ans = n
for i in range(n):
    ans = min(ans, i + check(s))
    s = s[1:] + s[0]

print(ans)

• Java

import java.util.Scanner;

public class Main {
    static int n;
    static String s;
    
    public static int check(String s) {
        int cnt = 0;
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) cnt++;
        }
        return cnt;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.next();
        
        int ans = n;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, i + check(s));
            s = s.substring(1) + s.charAt(0);
        }
        System.out.println(ans);
    }
}

✈️ 02.K小姐的字符串魔术

问题描述

K小姐有一个由小写字母组成的字符串。她想对这个字符串施展魔术,使其变成一个 的矩形网格。魔术的规则如下:

1. 将字符串从左到右、从上到下依次填入网格中。
2. 网格的大小必须满足 ,其中 为字符串的长度。
3. 如果两个相同的字母在网格中上下左右相邻,那么它们属于同一个连通块。

施展魔术后,K小姐想知道在所有可能的网格中,连通块数量的最小值是多少。

输入格式

第一行包含一个正整数 ,表示字符串的长度。

第二行包含一个长度为 的仅由小写字母组成的字符串。

输出格式

输出一个整数,表示连通块数量的最小值。

样例输入

8
abaababa

样例输出

3

数据范围

题解

本题可以枚举所有可能的网格尺寸,对于每个尺寸,判断网格中连通块的个数,然后取所有尺寸中连通块个数的最小值。

判断网格中连通块个数可以使用 DFS 算法。从网格的每个位置出发,如果该位置还没有被访问过,就进行一次 DFS,将所有与之相连的相同字符都标记为已访问,连通块的数量加 。

具体实现时,枚举行数 为 到 的每个整数,列数 为 。对于每个 和 ,创建一个 行 列的网格,将字符串从左到右从上到下依次填入网格中。

然后对网格进行 DFS 遍历,用一个 行 列的 数组记录每个位置是否被访问过,初始时都为 。从位置 开始 DFS 时,将 标记为 ,然后递归地搜索上下左右四个相邻位置,如果相邻位置的字符和当前位置的字符相同,且没有被访问过,就继续 DFS。

遍历完网格后,连通块的数量即为进行 DFS 的次数。更新答案为所有网格中连通块数量的最小值。

时间复杂度 ,空间复杂度 。其中 为字符串长度。

参考代码

• Python

def dfs(grid, vis, i, j, x, y):
    vis[i][j] = True
    for a, b in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
        if 0 <= a < x and 0 <= b < y and not vis[a][b] and grid[a][b] == grid[i][j]:
            dfs(grid, vis, a, b, x, y)

n = int(input())
s = input()

ans = n
for x in range(1, n + 1):
    if n % x != 0:
        continue
    y = n // x
    grid = [[''] * y for _ in range(x)]
    for i in range(n):
        grid[i//y][i%y] = s[i]