763 leetcode.com/problems/partition-labels/
글자들이 한묶음씩 묶여있다. 이걸 최대한 나눠줘야 한다. 모든 단어의 가장 오른쪽 인덱스를 저장해놓고, 하나씩 반복하면서 '여태까지 나온 글자중에 가장 오른쪽에 있는 글자' 가 현재 위치이면 이 인덱스가 하나의 파티션의 끝이 되므로, 이것과 현재 인덱스가 같으면 인덱스를 계산해서 넣어준다.
class Solution(object):
def partitionLabels(self, S):
ret = [0]
index_dict = {c:i for i,c in enumerate(S)}
max_last_index = 0
for i, c in enumerate(S):
max_last_index = max(max_last_index, index_dict[c])
if i == max_last_index:
ret.append(i - sum(ret) + 1)
return ret[1:]
1551 leetcode.com/problems/minimum-operations-to-make-array-equal/
왠지 앞의 상태를 사용하는 dp문제인것 같았는데 그냥 규칙 찾는 문제였다. 홀수인 경우에는 0, 2, 2+4, 2+4+6 이렇게 값이 증가하고, 짝수인 경우에는 1, 1+3, 1+3+5+7 이렇게 증가한다.
왜냐면... 홀수 n=3일 경우를 보자. 중간 3을 놔두고 1과 5가 2씩 증감한다. -> 2
홀수 5는 중간 5를 놔두고 3과 7이 2씩 증감, 양끝의 1과 9가 4씩 증감하면 된다. -> 2 + 4
짝수도 마찬가지다. 그러니 홀수와 짝수를 나뉘어서 값을 계산하면 된다.
class Solution(object):
def minOperations(self, n):
# n = 1 -> [1] -> 0
# n = 3 -> [1,3,5] -> 234 -> 333 -> 2
# n = 5 -> [1,3,5,7,9] -> 23578,33577,34567,44566,45556,55555 -> 2 + 4
# n = 7 -> 2 + 4 + 6
# n = 2 -> [1,3] -> 22 -> 1
# n = 4 -> [1,3,5,7] -> 2356,3355,3445,4444-> 1 + 3
# n = 6 -> [1,3,5,7,9,11] -> 2357910 -> 335799 -> 345789 -> 445788 -> 455778 -> 555777 -> 556677 -> 566667 -> 666666 -> 1 + 3 + 5
# n = 8 -> 1 + 3 + 5 + 7
if n % 2 == 1:
return sum(range(2, n, 2))
else:
return sum(range(1, n, 2))
1305 leetcode.com/problems/all-elements-in-two-binary-search-trees/
솔직히 가장 간단하고 쉬운 방법은 트리를 순서상관없이 자식있으면 모두 순회해서 값을 가져온다음 sort해서 리턴하면 된다. 근데 그게 문제의 의도가 아닌것같아서.. inorder로 두 트리를 순회하면 정렬이 된 상태로 값을 가져올수 있다. 그리고 두 트리에서 값을 하나씩 빼가면서 작은 값을 먼저 넣어주면 정렬순서가 유지된다.
class Solution(object):
def getAllElements(self, r1, r2):
r1_list, r2_list = [], []
def inorder(node, _list):
if not node:
return
inorder(node.left, _list)
_list.append(node.val)
inorder(node.right, _list)
inorder(r1, r1_list)
inorder(r2, r2_list)
ret = []
while r1_list and r2_list:
ret.append(r1_list.pop(0) if r1_list[0] < r2_list[0] else r2_list.pop(0))
return ret + r1_list + r2_list
1305 leetcode.com/problems/uncrossed-lines/
dp이자 lcs(longest common subsequence) 문제이다. dp 테이블을 만들고 인덱스 i, j의 문자가 같으면 현재 위치에서 가질수 있는 subsequence의 가장 긴 길이는 dp[i-1][j-1] + 1이다. 다르면 이전 길이 두개중 큰거 하나를 골라준다.
class Solution(object):
def maxUncrossedLines(self, A, B):
len_a, len_b = len(A), len(B)
dp = [[0]*(len_b+1) for i in xrange(len_a+1)]
for i in xrange(1, len_a + 1):
for j in xrange(1, len_b + 1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]