417
Q1. Find the K-th Character in String Game I
def kthCharacter(self, k: int) -> str:
chars = ['a','b','c','d','e','f','g','h','i',
'j','k','l','m','n','o','p','q','r',
's','t','u','v','w','x','y','z']
res = [0] * k
cur = 0
iter = 1
for i in range(1, len(res)):
res[i] = res[i - pow(2, iter - 1)] + 1
if i == pow(2, iter) - 1:
iter += 1
return chars[res[k-1]]
使用python內建函式chr(), ord()
ord('a') # 97
ord('b') # 98
chr(97) # a
chr(98) # b
def kthCharacter(self, k: int) -> str:
s = 'a'
while len(s) < k:
s += ''.join(chr(((ord(c) - ord('a') + 1) % 26) + ord('a')) for c in s)
return s[k-1]
Q2. Count of Substrings Containing Every Vowel and K Consonants I
5 <= word.length <= 250
def countOfSubstrings(self, word: str, k: int) -> int:
counts = {}
consonants = 0
left = 0
ans = 0
for i in range(len(word)):
counts[word[i]] = counts.get(word[i], 0) + 1
if word[i] not in "aeiou":
consonants += 1
while counts.get('a', 0) > 0 \
and counts.get('e', 0) > 0 \
and counts.get('i', 0) > 0 \
and counts.get('o', 0) > 0 \
and counts.get('u', 0) > 0 \
and consonants >= k:
if consonants == k:
ans += 1
tmp = i + 1
while tmp < len(word) and word[tmp] in "aeiou": # check (valid + vowel) is valid
ans += 1
tmp += 1
counts[word[left]] -= 1
if word[left] not in "aeiou":
consonants -= 1
left += 1
return ans
Q3. Count of Substrings Containing Every Vowel and K Consonants II
5 <= word.length <= 2 * 10^5
vowel >= 5 and consonants >= k
- vowel >= 5 and consonants >= k + 1
-------------------------------------
vowel >= 5 and consonants == k
class Solution:
def solve(self, word, k):
cnt = Counter()
ans = left = cons = 0
vowel = "aeiou"
for c in word:
if c in vowel:
cnt[c] += 1
else:
cons += 1
while len(cnt) == 5 and cons >= k:
out = word[left]
if out in vowel:
cnt[out] -= 1
if cnt[out] == 0:
del cnt[out]
else:
cons -= 1
left += 1
ans += left
return ans
def countOfSubstrings(self, word: str, k: int) -> int:
return self.solve(word, k) - self.solve(word, k+1)
Q4. Find the K-th Character in String Game II
class Solution:
def kthCharacter(self, k: int, operations: List[int]) -> str:
def f(k, ops):
if k == 1:
return 'a'
m = len(ops)
op = ops.pop()
if k > pow(2, m - 1): # right half
ch = f(k - pow(2, m - 1), ops)
return chr(((ord(ch) - ord('a') + op) % 26) + ord('a'))
else: # left half
return f(k, ops)
return f(k, operations)
418
Q1. Maximum Possible Number by Binary Concatenation
def count(self, nums):
ans = nums[0]
for i in range(1, len(nums)):
N = (nums[i]).bit_length()
ans = ans << N
ans += nums[i]
return ans
def maxGoodNumber(self, nums: List[int]) -> int:
orders = [
[nums[0], nums[1], nums[2]],
[nums[0], nums[2], nums[1]],
[nums[1], nums[2], nums[0]],
[nums[1], nums[0], nums[2]],
[nums[2], nums[0], nums[1]],
[nums[2], nums[1], nums[0]],
]
return max([self.count(o) for o in orders])
def maxGoodNumber(self, nums: List[int]) -> int:
def cmp(a, b):
N1 = a.bit_length()
N2 = b.bit_length()
ab = a << N2 | b
ba = b << N1 | a
return ba - ab
nums.sort(key=cmp_to_key(cmp))
ans = 0
for n in nums:
ans = ans << n.bit_length() | n
return ans
Q2. Remove Methods From Project
def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
sus = set()
graph = defaultdict(list)
for [m1, m2] in invocations:
graph[m1].append(m2)
q = deque([k])
while q:
bad = q.popleft()
if bad not in sus:
sus.add(bad)
q.extend(graph[bad])
canRemove = True
for [m1, m2] in invocations:
if m1 not in sus and m2 in sus:
canRemove = False
if canRemove:
return [v for v in range(n) if v not in sus]
else:
return [v for v in range(n)]
419
Q1(3318). Find X-Sum of All K-Long Subarrays I
def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
ans = []
N = len(nums)
def cmp(a, b):
if a[1] != b[1]:
return b[1] - a[1]
else:
return b[0] - a[0]
for i in range(N - k + 1):
freq = Counter(nums[i:i+k])
common = freq.most_common()
common.sort(key=cmp_to_key(cmp))
cnt = 0
for (a, b) in common[:x]:
cnt += a * b
ans.append(cnt)
return ans
Q2(3319). K-th Largest Perfect Subtree Size in Binary Tree
class Solution:
def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:
hs = []
def f(node):
if not node:
return 0
l = f(node.left)
r = f(node.right)
if l == -1 or r == -1:
return -1
if abs(l - r) > 0:
return -1
if l == r:
hs.append(l + 1)
return l + 1
return -1
f(root)
hs.sort(reverse=True)
print(hs)
return (1 << hs[k - 1]) - 1 if len(hs) >= k else -1
the number of nodes in a perfect/full/complete binary tree is
h: the height of the tree
420
Q1(3324). Find the Sequence of Strings Appeared on the Screen
def stringSequence(self, target: str) -> List[str]:
ans = ["a"]
current = "a"
i = 0
while ans[-1] != target:
if current[i] != target[i]:
prefix = current[0: -1] if len(current) > 0 else ''
last = chr(ord(current[-1]) + 1)
current = prefix + last
else:
current += 'a'
i += 1
ans.append(current)
return ans
def stringSequence(self, target: str) -> List[str]:
ans = []
s = []
for c in target:
c = ord(c) - ord('a')
s.append('a')
for s[-1] in ascii_lowercase[:c+1]:
ans.append(''.join(s))
return ans
# ascii_lowercase[0: 5] -> "abcd"
Q2(3325). Count Substrings With K-Frequency Characters I
def numberOfSubstrings(self, s: str, k: int) -> int:
ans = 0
l = 0
cnt = Counter()
N = len(s)
for r in range(len(s)):
cnt[s[r]] += 1
if any(v >= k for _, v in cnt.items()):
ans += (N - r)
print(cnt, N - r, ans)
cnt[s[l]] -= 1
l += 1
while any(v >= k for _, v in cnt.items()):
cnt[s[l]] -= 1
l += 1
ans += N - r
return ans
def numberOfSubstrings(self, s: str, k: int) -> int:
ans = left = 0
cnt = defaultdict(int)
for c in s:
cnt[c] += 1
while cnt[c] >= k:
cnt[s[left]] -= 1
left += 1
ans += left
return ans
"""
cabacb, k = 2
1. add 'c' {c: 1}
2. add 'a' {a: 1, c: 1}
3. add 'b' {a: 1, b: 1, c: 1}
4. add 'a' {a: 2, b: 1, c: 1} <- legal
remove 'c' {a: 2, b: 1} left = 1
remove 'a' {a: 1, b: 1} left = 2
ans += 2 ("caba", "aba")
5. add 'c' {a: 1, b: 1, c: 1}
ans += 2 ("cabac", "abac") left = 2
6. add 'b' {a: 1, b: 2, c: 1} <- legal
remove 'b' {a: 1, b: 1, c: 1} left = 3
ans += 3 ("cabacb", "abacb", "bacb")
ans = 7
"""
421
Q2. Total Characters in String After Transformations I
def lengthAfterTransformations(self, s: str, t: int) -> int:
res = [0] * 26
for c in s:
res[ord(c) - ord('a')] += 1
for i in range(t):
n = res.pop()
if n > 0:
res = [n] + res
res[1] += n
else:
res = [0] + res
return sum(res) % (pow(10, 9) + 7)
422
Q1(3340). Check Balanced String
def isBalanced(self, num: str) -> bool:
odd = 0
even = 0
for i in range(len(num)):
if i % 2 == 0:
even += int(num[i])
else:
odd += int(num[i])
return odd == even
423
Q1(3349). Adjacent Increasing Subarrays Detection I
def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
n = len(nums)
def isIncrease(arr):
for i in range(len(arr) - 1):
if arr[i] >= arr[i + 1]:
return False
return True
for i in range(n):
s1 = nums[i: i + k]
s2 = nums[i + k: i + 2 * k]
if len(s1) < k or len(s2) < k:
break
if isIncrease(s1) and isIncrease(s2):
return True
return False
Q2(3350). Adjacent Increasing Subarrays Detection II
def maxIncreasingSubarrays(self, nums: List[int]) -> int:
n = len(nums)
c = 0
res = []
for i in range(n):
if i + 1 < n and nums[i] < nums[i + 1]:
c += 1
else:
res.append(len(nums[i - c : i + 1]))
c = 0
ans = 0
if len(res) == 1:
return res[0] // 2
for a, b in pairwise(res):
ans = max(ans, min(a, b), max(a, b) // 2)
return ans
424
Q1(3354). Make Array Elements Equal to Zero
def countValidSelections(self, nums: List[int]) -> int:
N = len(nums)
prefix = [0] * N
prefix[0] = nums[0]
for i in range(1, N):
prefix[i] = prefix[i - 1] + nums[i]
suffix = [0] * N
suffix[N - 1] = nums[N - 1]
for i in range(N - 2, -1, -1):
suffix[i] += suffix[i + 1] + nums[i]
ans = 0
for i in range(N):
if nums[i] == 0:
if (prefix[i] - suffix[i]) == 0:
ans += 2
elif abs(prefix[i] - suffix[i]) == 1:
ans += 1
return ans