2024-10-24

92.反转链表||

标签

链表

给你单链表的头指针head和两个整数left和right，其中left<=right。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

输入：head = [5], left = 1, right = 1
输出：[5]

方法

局部反转链表，思路为在一次遍历中将当前节点的下一个放在局部链表的最前面，需要将pre和cur先遍历到left-1和left，借助最开始局部链表首节点cur的前一个节点pre，同时注意链表换位置的操作在代码中上一行的尾部是这一行的头部。
反转链表||
需要三个指针变量，pre，cur，tmp
pre：永远指向待反转区域的第一个节点left的前一个节点，pre不会改变
cur：指向待反转区域的第一个节点left
tmp：永远指向cur的下一个节点，循环过程中cur变化后tmp会变化
步骤如下：

  • 记录cur的下一个节点为tmp
  • 将cur的下一个节点指向tmp的下一个节点
  • 将tmp的下一个节点指向pre的下一个节点
  • 将pre的下一个节点指向tmp

这样就将当前节点的下一个节点放在待排序区域[left,right]的首位置left了
图中的例子应为725436->752436->745236->734526

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next=head
        pre = dummy
        # left-1表示当循环结束时cur为需要反转的第一个节点left，pre为上一个节点
        for _ in range(left-1):
            pre = pre.next
        cur = pre.next
        for _ in range(left,right):
            # 是在需要反转的链表内进行将cur.next插在最前面，需要用到pre.next，12345变成13245，再变成14325
            tmp = cur.next
            cur.next = tmp.next
            tmp.next = pre.next
            pre.next = tmp

        return dummy.next

1535.找出数组游戏的赢家同3175. 找到连续赢 K 场比赛的第一位玩家

标签

数组 模拟

给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。

每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。

返回赢得比赛的整数。

输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：一起看一下本场游戏每回合的情况：

过程

因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜。

输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9

思路

由于较小的元素会移至数组的末尾，在重新遇到被移至数组末尾的元素之前，arr 的每个元素都会被访问到。

考察游戏执行的流程，本质上是在从左到右遍历 arr，求数组最大值（打擂台）。我们要找首个连续 k 回合都是最大值的数。

如果遍历完 arr 也没找到这样的数，那么答案就是 arr 的最大值 mx，因为此时比 mx 小的数都会移到 mx 的右边，所以后面比大小都是 mx 胜利。

具体算法

  1. 初始化 mx=arr[0], win=0，从 arr[1] 开始遍历数组。其中 win 用来统计 mx 连续多少个回合是最大值（获胜）。
  2. 如果 arr[i]>mx，更新 mx=arr[i] 以及 win=0。
  3. 把 win 加一，如果 win=k 就退出循环。
  4. 遍历结束（或者中途退出循环），返回 mx。

代码

1
2
3
4
5
6
7
8
9
10
11
def getWinner(self, arr: List[int], k: int) -> int:
    mx = arr[0]
    win = -1  # 对于 arr[0] 来说，需要连续 k+1 个回合都是最大值
    for x in arr:
        if x > mx:  # 新的最大值
            mx = x
            win = 0
        win += 1  # 获胜回合 +1
        if win == k:
            break
    return mx

2024-10-27

684.冗余连接

标签

深度优先搜索、广度优先搜索、并查集

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

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

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

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

方法:并查集

树中边的数量=点的数量-1，这道题中的图在树的基础上多了一条边，所以节点数量=边的数量=n。

树是一个连通且无环的无向图，在树中多了一条附加的边之后就会出现环，因此附加的边是导致环出现的边。

可以通过并查集寻找附加的边。初始时，每个节点都属于不同的连通分量。遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量。
· 如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致出现环，合并这两个顶点的连通分量。
· 如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边会导致出现环，是附加的边，返回当前的边作为结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        # 定义节点的父节点，parent表示每个节点的parent是自己
        parent = list(range(n+1))
        # 找到当前节点的根节点，使用递归的写法，路经压缩，将index到根节点路径上的所有点的父节点都设为根节点
        # def find(index):
        #     if parent[index]!=index:
        #         parent[index] = find(parent[index])
        #     return parent[index]
        # 使用循环的写法，当没有找到根节点时，该节点变成自己的父节点
        def find(index):
            while index != parent[index]:
                index = parent[index]
            return index
        # 合并两个节点
        def union(index1,index2):
            if find(index1)!=find(index2):
                parent[find(index1)] = find(index2)

        for node1,node2 in edges:
            # 如果两个节点有边，则合并这两个节点，根节点一样
            if find(node1)!=find(node2):
                union(node1,node2)
            else:
                return [node1,node2]
        return []

2024-10-29

17.电话号码的字母组合

标签

哈希表、字符串、回溯

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入：digits = ""
输出：[]

输入：digits = "2"
输出：["a","b","c"]

方法:回溯

使用mapping数组模拟哈希表对数字和电话号码进行映射，回溯中判断添加到结果数组res中，用法是res.append("".join(arr))，join函数的执行逻辑为将列表arr中的每个元素间隔""拼接起来，在进行添加字符和删除的过程中，参数arr不是字符串（字符串不能进行append和pop操作），而是list列表，所以要使用dfs([])来调用函数，如果要使用参数arr为字符串的话，for循环中的操作应该为arr += x,dfs(arr),arr = arr[:-1]，调用函数应该为dfs("")

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def letterCombinations(self, digits: str) -> List[str]:
    res=[]
    mapping=["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
    # 回溯
    def dfs(arr):
        if digits =="":
            return []
        if len(arr)==len(digits):
            res.append("".join(arr))
        else:
            for x in mapping[int(digits[len(arr)])]:
                arr.append(x)
                dfs(arr)
                arr.pop()
    dfs([])
    return res

3259. 超级饮料的最大强化能量

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        n = len(energyDrinkA)
        dpA=[0]*(n+1)
        dpB=[0]*(n+1)
        for i in range(1,n+1):
            # 第一种情况
            dpA[i] = dpA[i-1] + energyDrinkA[i-1]
            dpB[i] = dpB[i-1] + energyDrinkB[i-1]
            if i>=2:
                # 第二种情况
                dpA[i]=max(dpA[i],dpB[i-2]+energyDrinkA[i-1])
                dpB[i]=max(dpB[i],dpA[i-2]+energyDrinkB[i-1])
        return max(dpA[n],dpB[n])
# dpA表示在第i步选择A饮料能获得的最大能量，所以第一种情况为上一步选择的也是A，即dpA[i-1] + energyDrinkA[i-1]，第二种情况为前两步选择的是B，即dpB[i-2]+energyDrinkA[i-1]