200. 岛屿数量

中等

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路：

1，建立一个visited的矩阵用于遍历。遍历过的地方就标记成true

2，定义一个dfs的寻找岛的算法，给定一个起点，通过dfs的方式搜索周围4个方向的陆地，搜索时要判断是否越界。

3，构造循环遍历整个二维矩阵的循环，遇到没有遍历并且是岛的地方就启动深度搜索，并将count+1

class Solution:
    def numIslands(self, grid):
        row = len(grid)
        col = len(grid[0])

        visited = [[False] * col for _ in range(row)]

        def dfs(i, j):
            visited[i][j] = True
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

            for dx, dy in directions:
                nx = i + dx
                ny = j + dy
                if 0 <= nx < row and 0 <= ny < col:
                    if not visited[nx][ny] and grid[nx][ny] == "1":
                        dfs(nx, ny)

        count = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1" and not visited[i][j]:
                    count += 1
                    dfs(i, j)

        return count

122 买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。

返回 你能获得的 最大 利润 。

思路：

使用贪心算法，只要今天比昨天的高，就买

profit = 0
for i in range(1, len(prices)):
    if prices[i] > prices[i-1]:
        profit += prices[i] - prices[i-1]
return profit

1004 最大连续1的个数III

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

题目要求：在数组中允许把最多 k 个零翻成一，求最长连续一的长度。

这是典型滑动窗口问题：

• 用两个指针 left 和 right 表示一个窗口

• 窗口里最多允许 k 个零

• 当窗口里零的数量超过 k 时，移动 left 直到满足条件

窗口的大小就是当前连续一的长度（因为零被视为翻成了一）。

思路：

1，遍历数组，用left来记录左侧窗口边界

2，每次查看是否是0，如果是1，直接右移，并比较大小

3，如果是0，则减小左侧窗口大小，移动left，直到窗口大小又为k

可以使用max(a,b)函数来快速比较大小

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        count_0 = 0
        max_len = 0

        for i in range(len(nums)):
            if nums[i] == 0:
                count_0 += 1

            # 缩小窗口直到 0 的数量 <= k
            while count_0 > k:
                if nums[left] == 0:
                    count_0 -= 1
                left += 1

            # 更新最大长度
            max_len = max(max_len, i - left + 1)

        return max_len

93，复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

思路：

1，首先定义一个简单的valid函数，用于判断一个分块是否符合IP地址的限制，非零数字之前不能有0，数字的范围在0～256

2，设计回溯函数，输入为起点和当前字符串信息

3，递归调用这个函数，递归的出口是长度为4，如果此时刚好用完所有字符，则加入到答案。不然的话直接退出。

如果没有达到4，那么就在未来的三个字符长度内递归调用搜索。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        def valid(seg):
            # 合法条件
            # 1. 字符串长度为 1，或不以 0 开头
            # 2. 数值在 0 到 255
            return (seg == "0" or not seg.startswith("0")) and 0 <= int(seg) <= 255  

        def backtrack(start, path):
            # 成功退出的逻辑
            # 已经切出 4 段并且用完所有字符
            if len(path) == 4:
                if start == len(s):
                    res.append(".".join(path))
                return

            # 每段最多 3 位
            for end in range(start + 1, min(start + 4, len(s) + 1)):
                seg = s[start:end]
                if valid(seg):
                    backtrack(end, path + [seg])

        backtrack(0, [])
        return res

452，用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

思路：利用贪心算法。根据所有气球的右侧点从小到大排列并遍历

sort函数的使用方法：

sort 默认是升序排列

.sort是直接修改原列表

代码实现：

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
            
        # 按 xend 排序
        points.sort(key=lambda x: x[1])

        arrows = 1
        arrow_pos = points[0][1]

        for xstart, xend in points:
            # 如果当前气球的起点 > 上一支箭的位置
            # 就必须再射一支新的箭
            if xstart > arrow_pos:
                arrows += 1
                arrow_pos = xend  # 更新新的箭位置

        return arrows

684，冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定一个图，该图从一棵 n 个节点 (节点值 1～n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

思路：并查集

1,首先构造一个parent list用于存每个节点的parent

2，构造find函数，使用while x ！= parent（x）的方式来不断往上查找，直到找到根结点。这个根节点来表了所有属于同一个连接的类别

3，构造union函数，根据每条边edge查找两个端点，如果发现两个端点的parent root相同，则说明这两个点都在一条可以连通的线上，再次加上这个边就会形成环，因此返回这个边

代码：

class Solution:
    def findRedundantConnection(self, edges):
        # 构造一个parent list，其中的每个index代表当前节点，parent[idx]代表其parent
        # 初始时所有点都视为parent
        parent = list(range(len(edges) + 1)) 

        def find(x):
            # 一直沿着树往上查找，直到
            while x != parent[x]:
                parent[x] = parent[parent[x]]
                x = parent[x]
            # 退出终点：x == parent[x]，即已经访问到parent节点
            return x

        def union(a, b):
            pa, pb = find(a), find(b)
            if pa == pb: # 通过查找parent节点是否是同一个节点来判断ab是否在同一个集合
                return False
            # 如果不在同一个集合，则将ab所在的两个数合并
            parent[pb] = pa
            return True

        for a, b in edges:
            if not union(a, b): # 一旦发现ab属于同一个集合，即构成一个环，则算法退出
                return [a, b]

208，实现Trie前缀树

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

思路：

node的结构：

trie树的子节点用字典表示。一个词的结束用is_end来表述

代码：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)