LeetCode 第417场周赛个人题解
目录
Q1. 找出第 K 个字符 I
原题链接
思路分析
签到题就直接模拟吧
AC代码
class Solution:
def kthCharacter(self, k: int) -> str:
s = [0]
for i in range(k):
ns = list((c + 1) % 26 for c in s)
s += ns
if len(s) > k: break
return str(chr(s[k - 1] + ord('a')))Q2. 元音辅音字符串计数 I
原题链接
思路分析
见T3
AC代码
class Solution:
def countOfSubstrings(self, s: str, k: int) -> int:
n = len(s)
st = set("aeiou")
acc = [[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
]
acc1 = [0] * (n + 1) + [n]
for i, c in enumerate(s):
acc[0][i + 1] = acc[0][i] + (1 if c == 'a' else 0)
acc[1][i + 1] = acc[1][i] + (1 if c == 'e' else 0)
acc[2][i + 1] = acc[2][i] + (1 if c == 'i' else 0)
acc[3][i + 1] = acc[3][i] + (1 if c == 'o' else 0)
acc[4][i + 1] = acc[4][i] + (1 if c == 'u' else 0)
acc1[i + 1] = acc1[i] + (0 if c in st else 1)
res = 0
for i in range(n):
l = bisect_left(acc1, k + acc1[i])
r = bisect_right(acc1, k + acc1[i]) - 1
if l > n:
break
b = max(bisect_right(acc[c], acc[c][i]) for c in range(5))
if b > n:
break
l = max(i, b, l)
if r >= l:
res += r - l + 1
return resQ3. 元音辅音字符串计数 II
原题链接
思路分析
前缀和+二分
滑窗可以写，但是写红温了，还是写了沟槽的二分
开5个元音前缀和数组，一个辅音前缀和数组
枚举 i ，二分合法右端点，累计贡献
时间复杂度：O(nlogn)
AC代码
class Solution:
def countOfSubstrings(self, s: str, k: int) -> int:
n = len(s)
st = set("aeiou")
acc = [[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
,[0] * (n + 1) + [n]
]
acc1 = [0] * (n + 1) + [n]
for i, c in enumerate(s):
acc[0][i + 1] = acc[0][i] + (1 if c == 'a' else 0)
acc[1][i + 1] = acc[1][i] + (1 if c == 'e' else 0)
acc[2][i + 1] = acc[2][i] + (1 if c == 'i' else 0)
acc[3][i + 1] = acc[3][i] + (1 if c == 'o' else 0)
acc[4][i + 1] = acc[4][i] + (1 if c == 'u' else 0)
acc1[i + 1] = acc1[i] + (0 if c in st else 1)
res = 0
for i in range(n):
l = bisect_left(acc1, k + acc1[i])
r = bisect_right(acc1, k + acc1[i]) - 1
if l > n:
break
b = max(bisect_right(acc[c], acc[c][i]) for c in range(5))
if b > n:
break
l = max(i, b, l)
if r >= l:
res += r - l + 1
return resQ4. 找出第 K 个字符 II
原题链接
思路分析
递归
如上图所示，最终的数组其实就是不断二倍得到的
我们可以建立简单的递推关系
给定k，我们可以算出k是第几次操作得到的（取log2即可）
那么根据操作类型可以推出和对称位置的颜色关系（+1还是相同）
直接递归即可
时间复杂度：O(log^2 k)
AC代码
import math
class Solution:
def kthCharacter(self, k: int, operations: list[int]) -> str:
def dfs(i: int) -> int:
if i <= 0: return 0
if i == 1:
return 0
b = math.ceil(math.log2(i)) - 1
return (dfs(i - pow(2, b)) + (1 if operations[b] == 1 else 0)) % 26
return chr(dfs(k) + ord('a'))
原文地址：https://blog.csdn.net/EQUINOX1/article/details/142632504
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！