leetcode 283(구현), 108(array to bst), 109, 49(anagram), 438, 567(sliding window)

283 https://leetcode.com/problems/move-zeroes/

 

모든 0을 리스트의 끝부분으로 보내는 문제이다. easy인데 기발한 답이 많았다. 생각해보다 0이면 해당 원소를 pop하고.. 0을 끝에 넣는식으로 짰다. 근데 아래에는 기발한 답 리스트이다.

 

1. 0의 위치를 기록해두고, 0이 아닌 원소들이 나오면 0과 자리를 바꿔줌.

https://leetcode.com/problems/move-zeroes/discuss/72012/Python-short-in-place-solution-with-comments.

# in-place
def moveZeroes(self, nums):
    zero = 0  # records the position of "0"
    for i in xrange(len(nums)):
        if nums[i] != 0:
            nums[i], nums[zero] = nums[zero], nums[i]
            zero += 1

2. 정렬을 하는데.... 정렬 함수를 0이 아닌것들을 우선순위로 만듦으로서 0이 자동적으로 끝의 위치로 가게끔 함.(천재인듯..) 더군다나 sorted는 새 리스트의 복사본을 만듦과는 달리, 리스트.sort()는 복사본을 만들지 않고 원래의 리스트를 변경함으로써 문제에 있는 in place조건도 만족함.

https://leetcode.com/problems/move-zeroes/discuss/72074/Share-my-one-line-python-solution

nums.sort(key= lambda x: 1 if x == 0 else 0) 

108. https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

 

유명한 문제중 하나이다. 중앙값을 잡아준 후, 중앙을 기준으로 좌,우로 나눈후 좌,우에서 다시 새로운 트리를 만든다.

class Solution(object):
    def sortedArrayToBST(self, num):
        if not num:
            return
        mid = len(num)//2
        root = TreeNode(num[mid])
        root.left = self.sortedArrayToBST(num[:mid])
        root.right = self.sortedArrayToBST(num[mid+1:])
        return root

109. https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

 

108번이랑 똑같은데 이번엔 인자가 리스트로 들어오는게 아니라 첫번째 head 포인터가 들어온다. head를 순환해서 리스트로 변환해준다음 위와 동일한 알고리즘을 돌려준다.

class Solution(object):
    def sortedListToBST(self, head):
        if not head:
            return None
        
        linked_list = []
        while head:
            linked_list.append(head)
            head = head.next
        return self.sortedListToBST2(linked_list)
    
    def sortedListToBST2(self, linked_list):
        if not linked_list:
            return None
            
        if len(linked_list)%2 == 1:
            mid = len(linked_list)//2
        else:
            mid = len(linked_list)//2-1

        root = TreeNode(linked_list[mid].val)
        root.left = self.sortedListToBST2(linked_list[:mid])
        root.right = self.sortedListToBST2(linked_list[mid+1:])
        return root

49. https://leetcode.com/problems/group-anagrams/

 

anagram은 문자들의 배치를 바꿔서다른 문자열을 서로 만들수 있는지 여부를 판별한다.

 

sort(a) == sort(b)로 anagram 여부를 판별할수 있다.

class Solution(object):
    def groupAnagrams(self, strs):
        ana_group = {}
        for s in strs:
            sorted_s = ''.join(sorted(s))
            ana_group[sorted_s] = ana_group.get(sorted_s, []) + [s]
        return ana_group.values()

438 https://leetcode.com/problems/find-all-anagrams-in-a-string/

 

큰 string안에 작은 string이 anagram으로써 들어가는지 판별하는 문제이다. sliding window로 풀 수 있다.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        d = {}
        t = {}
        for pp in p:
            t[pp] = t.get(pp, 0) + 1
        l,r = 0,0
        ret = []
        while r < len(s):
            d[s[r]] = d.get(s[r], 0) + 1
            if r - l + 1 > sum(t.values()):  # 슬라이딩 윈도우의 길이가 t의 길이만큼을 유지하도록 한다.
                d[s[l]] -= 1
                if d[s[l]] == 0:
                    del d[s[l]]
                l += 1
            if d == t:
                ret.append(l)
            r += 1
        return ret

567 https://leetcode.com/problems/permutation-in-string/

 

긴 스트링 안에 작은 스트링의 permutation이 포함되는지를 판별하는 문제이다. 근데 바로 위 438번인 긴 스트링 안에 작은 스트링의 아나그램으로서 들어가느냐 문제와 똑같다.

긴 스트링 안에 작은 스트링의 아나그램이 들어가는가? -> 딕셔너리로 sub의 단어의 갯수가 같으면 아나그램이라고 판단.

긴 스트링 안에 작은 스트링의 permutation이 들어가는가? -> 딕셔너리로 sub의 단어의 갯수가 같으면 permutation이라고 판단.