2020-3-1 刷题记录

前言:每天写这个的目的就是能够每天回忆一遍今天做过的题,如果哪里需要总结的单独拿出来

0X00 leetcode 做了 5 道

• leetcode 323. Number of Connected Components in an Undirected Graph

• leetcode 300. Longest Increasing Subsequence

• leetcode 261. Graph Valid Tree

• leetcode 200. Number of Islands

• leetcode 305. Number of Islands II

0X01 每道题的小小总结

动态规划是道难啃的题目,我感觉每天都要做一做

323. Number of Connected Components in an Undirected Graph

并查集模板题目

class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.count = n

    def find(self, x):
        if self.father[x] != x:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx != fy:
            self.count -= 1
            self.father[fy] = fx

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)

        for x, y in edges:
            uf.union(x, y)
        
        return uf.count

261. Graph Valid Tree

也是动态规划的模板题,

坑的地方在: 不能有离散的点

class UnionFind:
    def __init__(self, n):
        self.fathers = [i for i in range(n)]
        self.count = n
    
    def find(self, x):
        if self.fathers[x] != x:
            self.fathers[x] = self.find(self.fathers[x])
        return self.fathers[x]
    
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False
        self.fathers[fy] = fx
        self.count -= 1
        return True

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        uf = UnionFind(n)

        for x, y in edges:
            if not uf.union(x, y):
                return False
        
        return uf.count == 1

305. Number of Islands II

关键在于「集合合并」, 所以是并查集的题目,

不过是一个二维并查集

class UnionFind:
    def __init__(self, m, n):
        l = m * n
        self.m = m
        self.n = n
        self.fathers = [i for i in range(l)]
    
    def pos2idx(self, p):
        x, y = p
        return x * self.n + y
    
    def find(self, idx):
        if self.fathers[idx] != idx:
            self.fathers[idx] = self.find(self.fathers[idx])
        return self.fathers[idx]
    
    def union(self, p1, p2):
        idx1, idx2 = self.pos2idx(p1), self.pos2idx(p2)
        f1, f2 = self.find(idx1), self.find(idx2)
        if f1 == f2:
            return False
        self.fathers[f1] = self.fathers[f2]
        return True  
    
class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        if len(positions) == 0: return [0]
        
        lands = set()
        res = []
        uf = UnionFind(m, n)
        count = 0

        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for p in positions:
            count += 1
            idx = uf.pos2idx(p)
            if idx in lands: 
                count -= 1
                res.append(count)
                continue
            lands.add(idx)
            x, y = p
            for dx, dy in dirs:
                x1, y1 = x + dx, y + dy
                if x1 < 0 or y1 < 0 or x1 >= m or y1 >= n: continue
                if uf.pos2idx((x1, y1)) not in lands: continue
                # print("x1, y1 ", x1, y1)
                if uf.union(p, (x1, y1)): count -= 1
            # print("---------------")
            
            res.append(count)

        return res

关于并查集的一些小总结我都写到这里:

2020-3-1 并查集小总结

200. Number of Islands

标准网格型 dfs 题目,知道那个模板直接秒

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        if len(grid) == 0: return 0

        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        count = 0

        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n: return
            if grid[x][y] == "0" or visited[x][y]: return
            visited[x][y] = True
            dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
            for dx, dy in dirs:
                dfs(x + dx, y + dy)

        for x in range(m):
            for y in range(n):
                if grid[x][y] == "1" and not visited[x][y]:
                    dfs(x, y)
                    count += 1

        return c

300. Longest Increasing Subsequence

动态规划...每天来一道...

首先一个 O() 的做法

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 一维坐标型动态规划
        # dp[x] 代表 包含 x 的最长子序列
        # dp[x] = 从 0 ~ x -1 寻找一个比 nums[x] 小的,而且 dp 最大的 
        # 答案取最大值
        if len(nums) == 0: return 0
        m = len(nums)
        dp = [1] * m
        ans = 1
        for i in range(1, m):
            for j in range(i-1, -1, -1):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1) 
            
            ans = max(ans, dp[i])
        
        return ans

第二种解法,直接从这个序列里面找到最长上升子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        # 维护一个最长子序列
        m = len(nums)
        record = [0] * m
        # init 
        record[0] = nums[0]
        ans = 1

        for i in range(1, m):
            left, right = 0, ans - 1
            while left <= right:
                mid = left + (right - left) // 2
                if record[mid] == nums[i]: 
                    left = mid
                    break
                if record[mid] < nums[i]:
                    left = mid + 1
                else:
                    right = mid - 1
            
            record[left] = nums[i]
            if left == ans:
                ans += 1
        
        return ans

record[i] 记录了 i+1 长度 的最小的那个值, 时间复杂度 O(nlogn)

这里还用到了二分查找的模板,我在这里复习一下

left, right = 0, len(nums) - 1
while left <= right:
    mid = left + (right - left)
    if nums[mid] == target:
        left = mid
        break
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
        
# 最后 left 是插入的位置