2024 https://leetcode.com/problems/maximize-the-confusion-of-an-exam/
바로 앞글의 1004번 문제랑 똑같다. 근데 이번엔 T나 F의 최대값으로 만들어야 한다. 그러면 간단하게는 T일경우의 최댓값과 F일경우의 최댓값을 구해서 그중에 최댓값을 리턴하면 된다.
class Solution:
def maxConsecutiveAnswers(self, ans: str, k: int) -> int:
#ans = 'TFFT'
#k = 1
l,r = 0,0
d = {'T':0, 'F':0}
ret = 0
while r < len(ans):
#print(l,r)
d[ans[r]] += 1
while d['T'] > k and d['F'] > k: # l과 r사이, 즉 윈도우 내의 T나 F가 변환하능한 k개 이하를 유지해주기 위함
d[ans[l]] -= 1
l += 1
ret = max(ret, r-l+1)
r += 1
return ret
424 https://leetcode.com/problems/longest-repeating-character-replacement/
1. 슬라이딩 윈도우를 만든다.
2. 슬라이딩 윈도우 내의 (모든 문자 갯수) - (가장 많은 수의 문자)를 뺀 나머지 문자를 k개로 바꿔야 하므로 이게 k보다 작을 때만 유지한다.
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
#s='ABCDE'
#k=1
l,r = 0,0
ret = 0
d = {}
while r < len(s):
if s[r] not in d:
d[s[r]] = 0
d[s[r]] += 1
while True:
dd = sorted(d.items(), key=lambda x: -x[1])
if sum(d[1] for d in dd) - dd[0][1] <= k:
break
d[s[l]] -= 1
l += 1
ret = max(ret, r-l+1)
r += 1
return ret
근데 이 코드는 매번 정렬이 일어나서 느리다. 모든 문자의 합과 가장 많은 문자의 갯수를 변수처리하면 훨씬 빨라진다.
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
#s='ABCDE'
#k=1
l,r = 0,0
ret = 0
max_v, sum_v = 0,0
d = {}
while r < len(s):
if s[r] not in d:
d[s[r]] = 0
d[s[r]] += 1
max_v = max(max_v, d[s[r]])
sum_v += 1
while sum_v - max_v > k:
d[s[l]] -= 1
sum_v -= 1
l += 1
ret = max(ret, r-l+1)
r += 1
return ret
498 https://leetcode.com/problems/diagonal-traverse/
https://qkqhxla1.tistory.com/1171요글의 leetcode 1329번에서 대각 행렬에 대해 다뤘었다. 약간 변경한다.
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
diagonal_dict = {}
for i in range(len(mat)):
for j in range(len(mat[0])):
if i+j not in diagonal_dict:
diagonal_dict[i+j] = []
diagonal_dict[i+j].append(mat[i][j])
ret = []
for k,v in diagonal_dict.items():
if k % 2 == 1:
ret += v
else:
ret += v[::-1]
return ret
99 https://leetcode.com/problems/recover-binary-search-tree/
이진 트리에서 잘못된 부분을 찾은후 그 두부분을 바꿔줘야 한다.
1. 제대로 만들어진 이진 트리의 경우 중위 순회(inorder)를 하게 되면 값이 정렬되어 나오는게 정상이다.
2. 중위순회한 결과값이[1,2,8,4,7,3,10] 이라고 가정하면 항상 값이 증가하게 나와야 하므로[1,2,3,4,7,8,10]이 나와야 한다.
빨간색인 3,8이 잘못된 노드이며, 이건 (왼쪽에서 오른쪽으로 가면서 증가하지 않는 값의 왼쪽 값), (오른쪽에서 왼쪽으로 가면서 감소하지 않는 값의 오른쪽 값)을 찾은후 그 두개를 서로 바꿔주면 된다.
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
tree = []
def inorder(node):
if not node:
return
inorder(node.left)
tree.append(node)
inorder(node.right)
inorder(root)
for i in range(len(tree)-1):
if tree[i].val > tree[i+1].val:
a = tree[i]
break
for i in range(len(tree)-1, 0, -1):
if tree[i].val < tree[i-1].val:
b = tree[i]
break
a.val, b.val = b.val, a.val