数据结构与算法解题-20240422

---

一、2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

迭代的思路是，初始化答案为一个「空链表」，每次循环，向该链表末尾添加一个节点（保存一个数位）。

循环即遍历链表 l1和l2， 每次把两个节点的值l1.val和l2.val与进位值carry相加，除以10的余数即为当前节点需要保存的数位，除以10的商即为新的进位值。

需要注意的是，在第一次循环时，我们无法往一个空节点的末尾添加节点。这里的技巧是，创建一个哨兵节点（dummy node），当成初始的「空链表」。循环结束后，哨兵节点的下一个节点就是最终要返回的链表头节点。

class S2:
    def func(self, l1, l2):
        cur = dummy = ListNode()  # 哑节点
        carry = 0  # 进位标记
        while l1 or l2 or carry:  # 如果有一个不是空节点，或者还有进位，就继续遍历
            L1 = l1.val if l1 else 0
            L2 = l2.val if l2 else 0
            sumL = L1 + L2 + carry
            cur.next = ListNode(sumL % 2)  # 每个节点保存一个数位
            sumL //= 10  # 新的进位
            cur = cur.next  # 下一个节点
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        return dummy.next  # 哑节点的下一个节点就是头节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、67. 二进制求和

简单
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：
输入:a = “11”, b = “1”
输出：“100”

示例 2：
输入：a = “1010”, b = “1011”
输出：“10101”

提示：
1 <= a.length, b.length <= 104
a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成
字符串如果不是 “0” ，就不含前导零

思路：
二进制字符串形式，不可以转化为int类型，因为可能溢出；
两个加数的字符串长度可能不同；
在最后，如果进位carry不为0，那么最后需要计算进位；
向结果字符串res拼接的顺序是向后凭借，返回时需要把res反转

class S67:
    def func(self, a, b):
        res = ''
        i = len(a) - 1
        j = len(b) - 1
        carry = 0
        while i >= 0 or j >= 0 or carry != 0:
            digitA = int(a[i]) if i >= 0 else 0
            digitB = int(b[j]) if j >= 0 else 0
            sumAB = digitA + digitB + carry
            if sumAB >= 2:
                carry = 1
                sumAB -= 2
            else:
                carry = 0
            i -= 1
            j -= 1
            res += str(sumAB)
        return res[::-1]


r = S67()
a = "11"
b = "1"
print(r.func(a, b))
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

三、415. 字符串相加

简单
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：
输入：num1 = “11”, num2 = “123”
输出：“134”

示例 2：
输入：num1 = “456”, num2 = “77”
输出：“533”

示例 3：
输入：num1 = “0”, num2 = “0”
输出：“0”

class S415:
    def func(self,a,b):
        i=len(a)-1
        j=len(b)-1
        carry=0
        res=''
        while i>=0 or j>=0 or carry!=0:
            A=int(a[i]) if i>=0 else 0
            B=int(b[j]) if j>=0 else 0
            sumAB=A+B+carry
            if sumAB>=10:
                sumAB=sumAB%10
                carry+=1
            else:
                carry=0
            i-=1
            j-=1
            res += str(sumAB)
        return res[::-1]

r=S415()
a = "11"
b = "123"
print(r.func(a, b))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四、LCS 01. 下载插件

简单
小扣打算给自己的 VS code 安装使用插件，初始状态下带宽每分钟可以完成 1 个插件的下载。假定每分钟选择以下两种策略之一:
使用当前带宽下载插件
将带宽加倍（下载插件数量随之加倍）
请返回小扣完成下载 n 个插件最少需要多少分钟。

注意：实际的下载的插件数量可以超过 n 个
示例 1：
输入：n = 2
输出：2
解释： 以下两个方案，都能实现 2 分钟内下载 2 个插件
方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件
方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件

示例 2：
输入：n = 4
输出：3
解释： 最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案: 第一分钟带宽加倍，带宽可每分钟下载 2 个插件; 第二分钟下载 2 个插件; 第三分钟下载 2 个插件。

class S01:
    def func(self, n):
        count = 0
        width = 1
        while width < n:
            width = width * 2
            count = count + 1
        count = count + 1
        return count


r = S01()
n = 4
print(r.func(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

五、71. 简化路径

中等
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，‘//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，‘…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的 规范路径 。

示例 1：
输入：path = “/home/”
输出：“/home”
解释：注意，最后一个目录名后面没有斜杠。

示例 2：
输入：path = “/…/”
输出：“/”
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：
输入：path = “/home//foo/”
输出：“/home/foo”
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：
输入：path = “/a/./b/…/…/c/”
输出：“/c”

思路：将字符串按照/进行分割
分为4种情况
空字符串，
一个点 .
两个点 …
只包含英文字母、数字或者_的目录。
1、对于空【字符串】以及【一个点】，我们实际上无需对他们进行处理，因为【空字符串】没有任何含义，
2、而【一个点】表示当前目录本身，我们无需切换目录
3、对于【两个点】或者【目录名】，我们则可以用栈来维护路径中的每一个目录。
4、当遇到【两个点】时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的顶目。
当我们遇到【目录名】时，就把它放入栈

class S71:
    def func(self, path):
        names = path.split('/')
        stack = []
        for name in names:
            if name == '..':
                if stack:
                    stack.pop()
            elif name == '.':
                pass
            elif name == ' ':
                pass
            elif name:
                stack.append(name)
        return '/' + '/'.join(stack)


r = S71()
path = "/home//foo/"
print(r.func(path))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20