TagDeepFirst

Number of Islands.png

# Number of Islands
# Given a 2d grid map of '1's (land) and '0's (water),
# count the number of islands. 
# An island is surrounded by water;
# formed by connecting adjacent lands horizontally or vertically. 
# assume all four edges of the grid are all surrounded by water.
class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0   # grid map=>1s&0s=>islands number=>adjacent lands                                                 
        count = 0
        for i in range(len(grid)):  # 遍历每行
            for j in range(len(grid[0])): # 每列
                if grid[i][j] == '1':  # Islands元素
                    self.dfs(grid, i, j)  # 穷尽Islands路径 并标记元素
                    count += 1 #路径加一
        return count  #Islands总数
    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return                       #边界或路径结束    
        grid[i][j] = '#'                 #遍历的标记
        self.dfs(grid, i+1, j)           
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

# 1192. Critical Connections in a Network
import collections
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        def makeGraph(connections):
            graph = collections.defaultdict(list)
            for conn in connections:
                graph[conn[0]].append(conn[1])
                graph[conn[1]].append(conn[0])
            return graph

        graph = makeGraph(connections)
        connections = set(map(tuple, (map(sorted, connections))))
        rank = [-2] * n

        def dfs(node, depth):
            if rank[node] >= 0:
                # visiting (0<=rank<n), or visited (rank=n)
                return rank[node]
            rank[node] = depth
            min_back_depth = n
            for neighbor in graph[node]:
                if rank[neighbor] == depth - 1:
                    continue  # don't immmediately go back to parent. 
                    # that's why i didn't choose -1 as the special value, in case depth==0.
                back_depth = dfs(neighbor, depth + 1)
                if back_depth <= depth:
                    connections.discard(tuple(sorted((node, neighbor))))
                min_back_depth = min(min_back_depth, back_depth)
            rank[node] = n  # this line is not necessary. see the "brain teaser" section below
            return min_back_depth
            
        dfs(0, 0)  # since this is a connected graph, we don't have to loop over all nodes.
        return list(connections)

# 394. Decode String
# s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
class Solution:
    def decodeString(self, s: str) -> str:
        stack = []; curNum = 0; curString = ''
        for c in s:
            if c == '[':
                stack.append(curString)
                stack.append(curNum)
                curString = ''
                curNum = 0
            elif c == ']':
                num = stack.pop()
                prevString = stack.pop()
                curString = prevString + num*curString
            elif c.isdigit():
                curNum = curNum*10 + int(c)
            else:
                curString += c
        return curString

# 301. Remove Invalid Parentheses
# Scan from left to right, make sure count["("]>=count[")"].
# Then scan from right to left, make sure count["("]<=count[")"].

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        removed = 0
        results = {s}
        count = {"(": 0, ")": 0}
        for i, c in enumerate(s):
            if c == ")" and count["("] == count[")"]:
                new_results = set()
                while results:
                    result = results.pop()
                    for j in range(i - removed + 1):
                        if result[j] == ")":
                            new_results.add(result[:j] + result[j + 1:])
                results = new_results
                removed += 1
            else:
                if c in count:
                    count[c] += 1
        count = {"(": 0, ")": 0}
        i = len(s)
        ll = len(s) - removed
        for ii in range(ll - 1, -1, -1):
            i-=1
            c = s[i]
            if c == "(" and count["("] == count[")"]:
                new_results = set()
                while results:
                    result = results.pop()
                    for j in range(ii, ll):
                        if result[j] == "(":
                            new_results.add(result[:j] + result[j + 1:])
                results = new_results
                ll -= 1
            else:
                if c in count:
                    count[c] += 1
        return list(results)

# 332. Reconstruct Itinerary
# list of airline tickets [from, to], 
# reconstruct the itinerary in order.
# departs from JFK. begin with JFK.

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        targets = collections.defaultdict(list)
        for a, b in sorted(tickets)[::-1]:
            targets[a] += b,
        route = []
        def visit(airport):
            while targets[airport]:
                visit(targets[airport].pop())
            route.append(airport)
        visit('JFK')
        return route[::-1]  

    
    # def findItinerary(self, tickets):
    #     targets = collections.defaultdict(list)
    #     for a, b in sorted(tickets)[::-1]:
    #         targets[a] += b,
    #     route, stack = [], ['JFK']
    #     while stack:
    #         while targets[stack[-1]]:
    #             stack += targets[stack[-1]].pop(),
    #         route += stack.pop(),
    #     return route[::-1]

# from collections import defaultdict
# words = ['hello', 'world', 'nice', 'world']
# #使用lambda来定义简单的函数
# counter = defaultdict(lambda: 0) 
# for kw in words:
#     counter[kw] += 1