Day 5. 02/15/20

[tech-cow]

No description provided.

[tech-cow]

247. Strobogrammatic Number II

通过字典里面的分叉，然后用Two Pointer向内夹紧的方法进行DFS

class Solution(object):
    def findStrobogrammatic(self, n):
        res = []
        dic = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}
        self.helper(res, [None] * n, 0, n - 1, dic)
        return res

    def helper(self, res, temp, left, right, dic):
        if left > right:
            res.append(''.join(temp))
            return

        for key in dic:
            if left == right and key in ('6','9'):
                continue

            if left != right and left == 0 and key == '0':
                continue

            temp[left], temp[right] = key, dic[key]
            self.helper(res, temp, left + 1, right - 1, dic)

[tech-cow]

200 Number of Islands

class Solution(object):
    def numIslands(self, grid):
        if not grid: return 0
        visited = {}
        m, n = len(grid), len(grid[0])
        res = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and (i, j) not in visited:
                    res += 1
                    self.dfs(grid, i, j, visited)
        return res
        
        
    def dfs(self, grid, i, j, visited):
        m, n = len(grid), len(grid[0])
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0' or (i, j) in visited:
            return
        
        visited[(i, j)] = True
        self.dfs(grid, i + 1, j, visited)
        self.dfs(grid, i - 1, j, visited)
        self.dfs(grid, i, j + 1, visited)
        self.dfs(grid, i, j - 1, visited)

[tech-cow]

53. Maximum Subarray

class Solution(object):
    # Space O(N)
    def maxSubArray(self, nums):
        f = [-float('inf')] * len(nums)
        globalMax = -float('inf')
        
        for i, num in enumerate(nums):
            if f[i - 1] < 0:
                f[i] = num
            else:
                f[i] = num + f[i - 1]
            globalMax = max(globalMax, f[i])
        return globalMax