974 https://leetcode.com/problems/subarray-sums-divisible-by-k/
subarray의 합이 k로 나눠지는 subarray를 구해야하는데 인덱스와 상관없이 구하는게 아니라 근처의 값들로만 구성해야 해서 백트래킹같은게 아니다. 앞에서부터 prefix sum을 계산해주며 prefix sum이 k로 나눠지면 그 값이 존재하는만큼 더해준다. 그리고 뒤에서도 사용하기 위해 그 값이 나온만큼 증가시켜준다.
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
ret = 0
d = {0: 1}
prefix_sum = 0
for i in range(len(nums)):
prefix_sum += nums[i]
key = prefix_sum % k
if key not in d:
d[key] = 1
else:
ret += d[key]
d[key] += 1
return ret
1375 https://leetcode.com/problems/number-of-times-binary-string-is-prefix-aligned/
별생각없이 비트 연산자로 하나하나 구현을 했고 답은 나왔는데 좀 느렸다. 그래서 뭐가 잘못된거지 하고 다른사람들의 답을 봤는데.. 대박 좀 읽어보면 원 지문은 현재 지문과 좀 달랐던것 같다. 그래도 유추해서 요지는 이해할수 있다.
1-indexed기준으로 i번째의 비트를 1로 전환했을때 그 i번째가 가장 오른쪽에 있는 경우와 같으면 그게 prefix-aligned이다.
그러니까.. 예로 5개를 채웠는데 가장 오른쪽의 비트가 5라고 하면 5개가 전부 왼쪽에 전부 들어갔을것이므로 자동으로 prefix-aligned가 된다. 5개를 채웠는데 가장 오른쪽의 비트가 7이다? 그러면 중간 어디가 비어있다는 뜻이므로 아니다.
결국 n개를 채웠는데 가장 오른쪽의 비트가 n이다? 그럼 prefix-aligned이다. 와 진짜 알고리즘 문제 보고 구현할 생각만 했지 이렇게 방법을 떠올릴 생각은 못했네
class Solution:
def numTimesAllBlue(self, flips: List[int]) -> int:
rst = 0
cur_max = 0
for i, l in enumerate(flips):
cur_max = max(cur_max, l)
# everytime meet max, increase rst
if i + 1 == cur_max:
rst += 1
return rst
93 https://leetcode.com/problems/restore-ip-addresses/
s의 길이가 20 이하이니 dp가 아니라 백트래킹으로 구현만 해도 된다. 재귀적으로 구현한다.
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
ret = []
def get_ip(s, made_ip):
if len(made_ip) > 4: # ip주소가 4자리 이상이면 무시
return
if s == '': # 더 만들만한 거리가 없는데
if len(made_ip) == 4: # 4자리이면 .으로 조인
ret.append('.'.join(made_ip))
return
if s[0] == '0': # 0으로 시작하면 무조건 앞자리는 0임.
get_ip(s[1:], made_ip + ['0'])
else:
if len(s) >= 3 and int(s[:3]) < 256: # 3자리 이상이고 앞 3자리가 256보다 작아야함.
get_ip(s[3:], made_ip + [s[:3]]) # 3자리 끊어탐색
if len(s) >= 2: # 남은 길이가 2이상이면 2자리 탐색
get_ip(s[2:], made_ip + [s[:2]])
get_ip(s[1:], made_ip + [s[0]]) # 1자리 탐색.
get_ip(s, [])
return ret
616 https://leetcode.com/problems/add-bold-tag-in-string/
하나하나 다 검사하면 당연히 시간초과가 나니까 미리 가지치지로 갯수를 줄여놔야 한다.
1. 단어 리스트중 실제로 존재하는 단어들을 검색해봐서 위치값을 저장해놓는다.
2. 존재하는 단어들의 위치값 리스트를 머지해준다. https://leetcode.com/problems/merge-intervals/ 를 참고하자.
3. 머지된 단어 리스트로 일일히 <b>태그를 붙여준다.
class Solution:
def addBoldTag(self, s: str, words: List[str]) -> str:
word_range = []
words = set(words)
for w in words:
len_w = len(w)
for i in range(len(s)-len_w+1):
if s[i:i+len_w] == w:
word_range.append([i, i+len_w])
word_range.sort()
new_word_range = []
for i in range(len(word_range)):
if not new_word_range:
new_word_range.append(word_range[i])
elif new_word_range[-1][1] >= word_range[i][0]:
new_word_range[-1][1] = max(new_word_range[-1][1], word_range[i][1])
else:
new_word_range.append(word_range[i])
for new_word in new_word_range[::-1]:
s = s[:new_word[0]] + '' + s[new_word[0]:new_word[1]] + '' + s[new_word[1]:]
return s