leetcode 338(dp), 11(two pointer), 36, 53(dp 카데인 알고리즘, 최대 부분합), 152(최대 부분곱)

338 https://leetcode.com/problems/counting-bits/

비트의 갯수를 리턴하는 dp문제이다. 처음에 문제가 이해 안갔는데 예제의 2 -> [0,1,1]의 경우 0<=i<=2 사이의 0,1,2에 대해 0의 이진수로 표현시 1의 갯수는 0개, 1은 1개, 2는 1개라는걸 차례로 적어놓은것이다.

어떻게 할까 하다가 규칙을 발견했다.

0 -> 000 -> 0

1 -> 001 -> 1

2 -> 010 -> 1

3 -> 011 -> 2

4 -> 100 -> 1

5 -> 101 -> 2

6 -> 110 -> 2

7 -> 111 -> 3

2의 거듭제곱갯수를 주기로 f(n) = f(n-1) + (f(n-1)의 각각의 원소+1)가 성립된다.

4,5,6,7의 1,2,2,3의 경우 이전 주기 2,3-> (1,2) + ((1,2)의 각각의원소 + 1 == (2,3))인 1,2,2,3이 성립된다. 이걸 이용한다.

class Solution(object):
    def countBits(self, num):
        ret = [0]
        while True:
            ret += map(lambda x: x+1, ret)
            if len(ret) > num:
                break
        return ret[:num+1]

11 https://leetcode.com/problems/container-with-most-water/

two pointer문제이다. 넓을수록 물을 많이 가둘 가능성이 높으므로 시작점을 첫점과 끝점으로 한후 중앙으로 좁혀나간다.

좁히는 방법은 높이가 높을수록 물을 많이 가둘 가능성이 높으므로 양 끝점중 높이가 낮은 쪽을 중앙으로 하나씩 밀어넣으면서 본다.

https://leetcode.com/problems/container-with-most-water/discuss/6100/Simple-and-clear-proofexplanation

class Solution(object):
    def maxArea(self, height):
        s, e = 0, len(height)-1
        water = 0
        while True:
            if s == e:
                break
            water = max(water, (e - s) * min(height[s], height[e]))
            if height[s] < height[e]:
                s += 1
            else:
                e -= 1
        return water

36 https://leetcode.com/problems/valid-sudoku/

노가다문제라 설명이 필요 없다...

class Solution(object):
    def isValidSudoku(self, board):
        for i in xrange(9):
            c = [0]*9
            cc = [0]*9
            for j in xrange(9):
                if board[i][j] != '.':
                    c[int(board[i][j])-1] += 1
                    if c[int(board[i][j])-1] > 1:
                        return False
                if board[j][i] != '.':
                    cc[int(board[j][i])-1] += 1
                    if cc[int(board[j][i])-1] > 1:
                        return False
        
        for i in xrange(0, 9, 3):
            for j in xrange(0, 9, 3):
                x,y = i+1,j+1  # 각각 스도쿠의 중심점
                c = [0]*9
                for _x,_y in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]:
                    if board[x + _x][y + _y] != '.':
                        c[int(board[x + _x][y + _y])-1] += 1
                        if c[int(board[x + _x][y + _y])-1] > 1:
                            return False
                        
        return True

53 https://leetcode.com/problems/maximum-subarray/

최대 부분합을 구하는 문제이다. dp리스트에 i의 값은 max(이전 i-1들의 값중의 최대값 + 현재값, 현재값)으로 구한다.

카데인 알고리즘(kadane) : https://m.blog.naver.com/PostView.nhn?blogId=dkdlelgksthf&logNo=221052887894&proxyReferer=https:%2F%2Fwww.google.com%2F

class Solution(object):
    def maxSubArray(self, nums):
        dp = [-999999999]*len(nums)
        dp[0] = nums[0]
        for i in xrange(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)

152 https://leetcode.com/problems/maximum-product-subarray/

최대 부분곱을 구하는 문제이다. 이걸 어떻게 하는지 몰랐는데...

https://leetcode.com/problems/maximum-product-subarray/discuss/490459/Unofficial-solution-intuitive-explanations-O(n)-two-different-approaches

읽어보자.

요약 : The key intuition here is that when we can come upon a negative number, our current max can suddenly becomes a min but is still a max by absolute value. Following the next negative number, our min can become a max again. Therefore keeping track of min is useful.

그러니까 현재 음수여서 최소값이어도 절대값이 가장 큰 경우 다음 수가 음수일 경우에 다시 최대값이 될 수가 있으니 왼쪽에서부터의 최대값, 오른쪽에서부터의 최대값을 각각 구해서 그중 큰 수를 리턴하면 그게 최대값이다.

def maxProduct(self, A):
        B = A[::-1]
        for i in range(1, len(A)):
            A[i] *= A[i - 1] or 1  # A[i - 1]이 0인 경우에는 이후에 다 0이 나오게 되므로 0이면 1로 놔둠.
            B[i] *= B[i - 1] or 1  # 위와 마찬가지
        return max(A + B)