leetcode 206(linked list), 92, 238(product), 78(subset, dfs)

206번. https://leetcode.com/problems/reverse-linked-list/

노드, pre 노드 등을 따로 만들어서 처리하는게 더 복잡해서 이렇게 리스트에 넣고 리스트의 특성을 이용했다.

class Solution(object):
    def reverseList(self, head):
        if not head:
            return None
        if not head.next:
            return head
        
        linked_list = []
        while head:
            linked_list.append(head)
            head = head.next
        
        for i in xrange(len(linked_list)-1, 0, -1):
            linked_list[i].next = linked_list[i-1]
        linked_list[0].next = None
        return linked_list[-1]

92번. https://leetcode.com/problems/reverse-linked-list-ii/

바로 위 206번 문제보다 조금 더 나아간 문제이다. 

class Solution(object):
    def reverseBetween(self, head, m, n):
        if not head:
            return None
        if not head.next:
            return head
        
        linked_list = []
        while head:
            linked_list.append(head)
            head = head.next
        
        linked_list = linked_list[:m-1] + linked_list[m-1:n][::-1] + linked_list[n:]  # linked_list를 다시구성한다. 처음 + 중간부분(중간부분은 거꾸로) + 끝부분
        linked_list = linked_list[::-1]  # 그리고 다시 한번 더 거꾸로

        for i in xrange(len(linked_list)-1, 0, -1):
            linked_list[i].next = linked_list[i-1]
        linked_list[0].next = None
        return linked_list[-1]

238. https://leetcode.com/problems/product-of-array-except-self/

문제를 조건대로 O(n), constant space complexity로 고정해놓고 풀려그랬는데 못풀었다. discussion을 보고 해답을 이해했다. 

첫번째 for i in xrange(1, len(nums))~에서는 

res를 출력해보면 알겠지만res[i] = res[:i]까지의 곱한 값이 들어있다.

[2,3,4,5]이면 res 에는 [1, 2, 2*3, 2*3*4]

그리고 두번째 for문에서는 거꾸로 돌면서 이 과정을 한번 더 반복한다. 그러면...

[(1)*3*4*5, (2)*4*5, (2*3)*5, 2*3*4] 이런식으로 자연스럽게 본인을 뺀 나머지 값들의 곱이 만들어진다.

class Solution(object):
    def productExceptSelf(self, nums):
        #nums = [2,3,4,5]
        res = [1] * len(nums)
        t = 1
        for i in xrange(1, len(nums)): # from left to right 
            t *= nums[i-1]
            res[i] *= t
        #print res

        t = 1
        for i in range(len(nums)-2,-1,-1):
            t *= nums[i+1]
            res[i] *= t
        #print res
        return res

78. https://leetcode.com/problems/subsets/

모든 subset을 구하는 문제이다. dfs로 구한다.

class Solution(object):
    def subsets(self, nums):
        res = []
        stack = [[0, []]]  # [index, subset]
        while stack:
            index, subset = stack.pop()
            res.append(subset)
            for i in xrange(index, len(nums)): 
                stack.append([i+1, subset+[nums[i]]])  # 현재 subset + 추가 subset을 넣는다.
        return res

근데 풀고 다른사람들의 답을 보니 현타온다. 하..

https://leetcode.com/problems/subsets/discuss/27301/Python-easy-to-understand-solutions-(DFS-recursively-Bit-Manipulation-Iteratively). subarray, subset, 부분집합

# Iteratively
def subsets(self, nums):
    res = [[]]
    for num in sorted(nums):
        res += [item+[num] for item in res]
    return res