1081 https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
문제를 이해하는데 시간이 좀 걸렸다. 문제를 쉽게 풀어쓰자면 중간에 중복된 단어를 지워서 결과값으로 단어가 1개씩만 나오도록 만드는데 결과값이 사전 순서상으로 가장 낮은 값이 나와야 한다.
cdadabcc의 답이 abcd가 아니라 adbc가 나온 이유는 cdadabcc에서 a다음에 b가 먼저 오게 되면 b이후에는 cc밖에 없기때문에 d를 출력할수 없기 때문이다. 난 기본적으로 요 링크의 방법으로 풀었다.
class Solution(object):
def smallestSubsequence(self, text):
order_dict = {}
for i, t in enumerate(text):
order_dict[t] = order_dict.get(t, []) + [i]
order_dict = sorted(order_dict.iteritems(), key=lambda x: x[0])
ret = ''
i = 0
cur_index = -1
while i < len(order_dict):
c = order_dict[i][0]
index = -1
for j in order_dict[i][1]:
if cur_index < j:
index = j
break
if index == -1:
i += 1
continue
flag = True
for j in xrange(i+1, len(order_dict)):
if index > order_dict[j][1][-1]:
flag = False
break
if flag:
cur_index = index
ret += c
order_dict.pop(i)
i = 0
else:
i += 1
return ret
1130 https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
어떻게 풀까 고민하다가 답을 봤는데 주어지는게 leaf 노드이므로 아래에서부터 greedy하게 가장 작은 값들로 트리를 구성해주면서 값을 더해준다. 똑똑하다..
class Solution(object):
def mctFromLeafValues(self, arr):
ret = 0
while len(arr) > 1:
min_index = arr.index(min(arr))
if 0 < min_index < len(arr) - 1: # 가장 작은 값의 인덱스가 1~len(arr)-2 사이이면 왼쪽, 오른쪽 값 중에서 작은것하고 곱해서 값을 넣어준다.
ret += min(arr[min_index-1], arr[min_index+1]) * arr[min_index]
else: # 가장 작은 값의 인덱스가 0, len(arr)-1즉 엣지이면 0인경우에는 1과 곱하고 끝이면 끝-1인덱스와 곱한다.
if min_index == 0:
ret += arr[min_index] * arr[min_index+1]
else:
ret += arr[min_index] * arr[min_index-1]
arr.pop(min_index) # 트리를 만들었으니 pop
return ret
150 https://leetcode.com/problems/evaluate-reverse-polish-notation/
후위표기법으로 된 식을 계산하는 문제이다. 부호가 나오면 스택의 끝, 끝에서 다음 차례로 두개를 뺀다음 연산한다.
from collections import deque
class Solution(object):
def evalRPN(self, tokens):
stack = deque()
sign = set(['+', '-', '*', '/'])
for t in tokens:
if t in sign:
r, l = stack.pop(), stack.pop()
if t == '+':
stack.append(l+r)
elif t == "-":
stack.append(l-r)
elif t == "*":
stack.append(l*r)
else:
stack.append(int(float(l)/r))
else:
stack.append(int(t))
return stack[-1]
419 https://leetcode.com/problems/battleships-in-a-board/
생각을 좀 많이 해봐야 했다. 배들은 항상 떨어져있고, 수평이나 수직으로 1자이다. 판에서 배가 몇개인지 찾는건데 문제는 한번만 돌면서, 공간복잡도 O(1)안에 풀라고 한다.
수평이나 수직으로는 1자로 X가 나와야 하므로 어떤점 x,y일 경우에(x-1, y), (x, y-1)의 좌표 둘다에서 배가 아닌 .이 나오면 배라고 생각하고 카운트를 증가시켜준다. (x-1, y), (x, y-1)에서 배의 상징인 X가 나오면 이미 이전에 카운트했다고 가정하고 지나가자.
class Solution(object):
def countBattleships(self, board):
if not board:
return 0
ship_num = 0
for i in xrange(len(board)):
for j in xrange(len(board[0])):
if board[i][j] == 'X' and \
(i == 0 or board[i-1][j] == '.') and \
(j == 0 or board[i][j-1] == '.'):
ship_num += 1
return ship_num