Skip to content

Latest commit

 

History

History
221 lines (140 loc) · 4.58 KB

0959._Regions_Cut_By_Slashes.md

File metadata and controls

221 lines (140 loc) · 4.58 KB

959. Regions Cut By Slashes

难度: Medium

刷题内容

原题连接

内容描述

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space.  These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

 

Example 1:

Input:
[
  " /",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:

Example 4:

Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:

Example 5:

Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:

 

Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

解题方案

思路 1 - 时间复杂度: O(row * col)- 空间复杂度: O(row * col)******

看成一个大图，每个格子有4个方位，上下左右，根据格子里的内容是'\', '/'还是' '来连接每个格子的不同方位

  • 格子里的内容是'\'， 那么当前格子的上和右肯定连接起来，下和左肯定连接起来
  • 格子里的内容是'/'， 那么当前格子的上和左肯定连接起来，下和右肯定连接起来
  • 格子里的内容是' '， 那么当前格子的上下左右全部连接起来
  • 每个格子的上和它上面那个格子（如果存在）的下肯定连接起来
  • 每个格子的下和它下面那个格子（如果存在）的上肯定连接起来
  • 每个格子的右和它右面那个格子（如果存在）的左肯定连接起来
  • 每个格子的左和它左边那个格子（如果存在）的右肯定连接起来

参考寒神

class UnionFind(object):
    def __init__(self):  
        self.uf = {}
        
    def find(self, x):
        self.uf.setdefault(x, x)
        if x != self.uf[x]:
            self.uf[x] = self.find(self.uf[x])
        return self.uf[x]
    
    def union(self, x, y):
        self.uf[self.find(x)] = self.find(y)


class Solution:
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        uf = UnionFind()
        
        # 0 top, 1 right, 2 bottom, 3 left
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i:
                    uf.union((i-1, j, 2), (i, j, 0))
                if j:
                    uf.union((i, j-1, 1), (i, j, 3))
                if grid[i][j] == "\\":
                    uf.union((i, j, 0), (i, j, 1))
                    uf.union((i, j, 2), (i, j, 3))
                elif grid[i][j] == "/":
                    uf.union((i, j, 3), (i, j, 0))
                    uf.union((i, j, 1), (i, j, 2))
                else:
                    uf.union((i, j, 0), (i, j, 1))
                    uf.union((i, j, 2), (i, j, 3))
                    uf.union((i, j, 3), (i, j, 0))
                    uf.union((i, j, 1), (i, j, 2))
        return len(set(map(uf.find, uf.uf)))

优化写法，

class UnionFind(object):
    def __init__(self):  
        self.uf = {}
        
    def find(self, x):
        self.uf.setdefault(x, x)
        if x != self.uf[x]:
            self.uf[x] = self.find(self.uf[x])
        return self.uf[x]
    
    def union(self, x, y):
        self.uf[self.find(x)] = self.find(y)


class Solution:
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        uf = UnionFind()
        
        # 0 top, 1 right, 2 bottom, 3 left
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i:
                    uf.union((i-1, j, 2), (i, j, 0))
                if j:
                    uf.union((i, j-1, 1), (i, j, 3))
                if grid[i][j] != "/":
                    uf.union((i, j, 0), (i, j, 1))
                    uf.union((i, j, 2), (i, j, 3))
                if grid[i][j] != "\\":
                    uf.union((i, j, 3), (i, j, 0))
                    uf.union((i, j, 1), (i, j, 2))
        return len(set(map(uf.find, uf.uf)))