2025-07-19:计算字符串的镜像分数。用go语言,给定一个字符串 s
2025-07-19:计算字符串的镜像分数。用go语言,给定一个字符串 s,定义每个英文字母的“镜像”为字母表反转后对应的位置字母,例如:'a' 的镜像是 'z','b' 的镜像是 'y',依此类推。
初始时,字符串中所有字符都未被标记,且总分为 0。按照以下规则处理字符串:
1. 从左到右遍历每个字符,假设当前索引为 i。
2. 对于当前字符 s[i],在其左边(索引小于 i 且未标记的字符中)寻找一个距离最近的字符 s[j],该字符是 s[i] 的镜像。
3. 如果找到了这样的字符 s[j],则将 s[i] 和 s[j] 标记为已处理,且总分增加 i - j。
4. 如果未找到符合条件的字符,跳过当前字符,继续处理下一个字符。
最终,返回所有匹配操作累积的总分。
1 <= s.length <= 100000。
s 仅由小写英文字母组成。
输入: s = "aczzx"。
输出: 5。
解释:
i = 0。没有符合条件的下标 j,跳过。
i = 1。没有符合条件的下标 j,跳过。
i = 2。距离最近的符合条件的下标是 j = 0,因此标记下标 0 和 2,然后将总分加上 2 - 0 = 2 。
i = 3。没有符合条件的下标 j,跳过。
i = 4。距离最近的符合条件的下标是 j = 1,因此标记下标 1 和 4,然后将总分加上 4 - 1 = 3 。
题目来自力扣3412。
分步骤描述过程:
1. 初始化:
o 创建一个长度为26的切片 arr,每个元素是一个空的整数切片(栈),用于存储每个字母(a-z)在字符串中出现的未匹配索引。
o 初始化结果 res 为0,用于累计总分。
o 获取字符串长度 n。
2. 遍历字符串:
o 从字符串的第一个字符开始,依次处理每个字符 s[i](索引 i 从0到 n-1)。
3. 处理当前字符:
o 计算当前字符 s[i] 对应的字母索引 v = int(s[i] - 'a')(例如,'a' 对应0,'b' 对应1,...,'z' 对应25)。
o 计算当前字符的镜像字母索引 rev = 25 - v(例如,'a' 的镜像 'z' 对应25,'b' 的镜像 'y' 对应24,依此类推)。
4. 查找镜像字符:
o 检查 arr[rev] 是否非空(即是否有未匹配的镜像字符):
o 如果 arr[rev] 非空,弹出栈顶元素 j(即最近的未匹配镜像字符的索引),计算 i - j 并加到 res 中。
o 如果 arr[rev] 为空,将当前字符的索引 i 压入 arr[v] 的栈中(表示当前字符未被匹配,等待后续可能的匹配)。
5. 具体示例 s = "aczzx" 的处理过程:
o i = 0:s[0] = 'a',v = 0,rev = 25('z')。arr[25] 为空,将 0 压入 arr[0]。arr[0] = [0]。
o i = 1:s[1] = 'c',v = 2,rev = 23('x')。arr[23] 为空,将 1 压入 arr[2]。arr[2] = [1]。
o i = 2:s[2] = 'z',v = 25,rev = 0('a')。arr[0] 非空([0]),弹出 j = 0,计算 2 - 0 = 2,res = 2。arr[0] 变为空。
o i = 3:s[3] = 'z',v = 25,rev = 0('a')。arr[0] 为空,将 3 压入 arr[25]。arr[25] = [3]。
o i = 4:s[4] = 'x',v = 23,rev = 2('c')。arr[2] 非空([1]),弹出 j = 1,计算 4 - 1 = 3,res = 5。arr[2] 变为空。
6. 最终结果:
o 遍历结束后,res = 5,与题目描述一致。
时间复杂度和空间复杂度:
o 时间复杂度:O(n),其中 n 是字符串长度。每个字符仅被处理一次,且栈操作(压入和弹出)均为 O(1)。
o 额外空间复杂度:O(n),最坏情况下所有字符都未被匹配,此时 arr 中的栈总大小为 n。
Go完整代码如下:
.
package main
import (
"fmt"
)
func calculateScore(s string)int64 {
// 创建一个切片,元素为 int 类型的栈,表示每个字母的索引栈
arr := make([][]int, 26)
for i := range arr {
arr[i] = []int{}
}
res := int64(0)
n := len(s)
for i := 0; i < n; i++ {
v := int(s[i] - 'a')
rev := 25 - v // 镜像字母对应的索引
iflen(arr[rev]) > 0 {
// 弹出最近的镜像字符索引
j := arr[rev][len(arr[rev])-1]
arr[rev] = arr[rev][:len(arr[rev])-1]
res += int64(i - j)
} else {
// 没有找到镜像字符,当前字符入栈
arr[v] = append(arr[v], i)
}
}
return res
}
func main() {
s := "aczzx"
result := calculateScore(s)
fmt.Println(result)
}
Python完整代码如下:
.
# -*-coding:utf-8-*-
def calculateScore(s: str) -> int:
# 创建一个列表,元素为栈(列表),表示每个字母的位置索引栈
arr = [[] for _ in range(26)]
res = 0
n = len(s)
for i, ch in enumerate(s):
v = ord(ch) - ord('a')
rev = 25 - v # 镜像字母对应的索引
if arr[rev]:
# 弹出最近的镜像字符索引
j = arr[rev].pop()
res += i - j
else:
# 没有找到镜像字符,当前字符入栈
arr[v].append(i)
return res
if __name__ == "__main__":
s = "aczzx"
result = calculateScore(s)
print(result)
·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”,并致力于分享全面的编程知识。在这里,您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大规模架构师每日一题”,让 Go 语言和算法助力您的职业发展
·
相关文章
- LeetCode 力扣官方题解 | 516.最长回文子序列
- iPhone必崩溃bug曝光!这个WiFi水太深谁也把握不住
- JS 写正则表达式,判断是否为手机号
- 算法 - 最长回文子序列(最长回文子串动态规划图解)
- 2023-04-28:将一个给定字符串 s 根据给定的行数 numRows以从上往下
- 2025-07-15:子字符串匹配模式。用go语言,给定一个字符串 s 和一
- 前端 JavaScript 字符串中提取数字
- C语言字符串操作总结大全(超详细)
- webpack的几个常见loader源码浅析,动手实现一个md2html-loader
- 推荐一个检测 JS 内存泄漏的神器(js内存泄漏的原因和场景)