Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

第一章力扣热题100道(1-5)

作者：Gausst松鼠会 | 2024-02-26 18:56:19

踩

力扣热题100

1. 两数之和

① 题目

给定一个整数数组nums和一个整数目标值target,请你在该数组中抓出和为目标值target的那两个整数,并返回他们的数组下标.
你可以假设每种输入只会对应一个答案.但是,数组中同一个元素在答案里不能重复出现.你可以按照任意的顺序返回答案.

② 示例

输入: nums = [2,7,11,15],target = 9
输出: [0,1]

输入: nums = [3,2,4],target = 6
输出: [1,2]

输入: nums = [3,3],target = 6
输出: [0,1]
1
2
3
4
5
6
7
8

③ 答案

解法1: 暴力遍历解法

遍历数组,根据条件,如果满足条件就记录下编号.

首先是写一个统计时间的装饰器,这个装饰器会在后面的算法评估测试中一直使用:

def cout_time(func):
    def inner(*args, **kwargs):
        timeBefore = time.time()
        ret = func(*args, **kwargs)
        print("函数:{}() 执行耗时: {} ms".format(func.__name__, (time.time() - timeBefore) * 1000))
        return ret

    return inner
1
2
3
4
5
6
7
8

暴力解法的算法:

# 暴力解题法
@cout_time
def two_sum_01(nums, target):
    for index1, x in enumerate(nums):
        for index2, y in enumerate(nums):
            if x + y == target and index1 != index2:
                return [index1, index2]
    return []
1
2
3
4
5
6
7
8

测试:

if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
1
2
3
4
5

测试结果:

解法2: 解法1的优化版本,也就是说遍历的时候,不需要全部都遍历,第一个列表可以从头开始遍历,第二列表,只需要遍历第一个列表后面的元素即可,因为之前的已经遍历过了,肯定是不满足要求的.改进版本:

# 暴力解法改进版
@cout_time
def two_sum_02(nums,target):
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i] + nums[j] == target:
                return [i,j]
    return []


if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums,target)
    print("res: {}".format(resIndex))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

结果:

可以看出来,速度有所提升.

解法3: 使用list的相关函数求解

解题的思路是 num2 = target - num1,只需要判断num2是否也在nums中:主要使用下面两个方法:

num2 in nums, 返回True代表存在
nums.index(num2), 查找num2的索引

@cout_time
def two_sum_03(nums, target):
    j = -1
    for i in range(len(nums)):
        num1 = nums[i]
        num2 = target - num1
        if num2 in nums:
            if ((nums.count(num2) == 1) & (num2 == num1)):
                continue
            else:
                j = nums.index(num2, i + 1)
                break

    if j > 0:
        return [i, j]
    else:
        return []
if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))
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
28

结果:

时间又缩短了哦

方法4: 方法3的改进版本,num2的查找并不需要每次从nums查找一遍,只需要从num1位置之前或者之后查找即可.为了方便index,这里选择从num1位置之前查找.

@cout_time
def two_sum_04(nums, target):
    index1 = -1
    index2 = -1
    for i in range(1, len(nums)):
        index1 = i
        num1 = nums[i]
        num2 = target - num1
        tempNums = nums[:i]
        if num2 in tempNums:
            index2 = tempNums.index(num2)
            break
    if index2 >= 0:
        return [index2, index1]


if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_04(nums, target)
    print("res: {}".format(resIndex))
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
28
29
30

结果:

时间上又缩短了

解法5: 字典模拟哈希求解.通过字典来模拟哈希查询的过程.将数据根据索引和值存放到一个字典当中

这里要注意一点,把nums的值作为字典的键,nums的索引作为值.这里有个问题,就是相同值是怎么处理的呢! 看一个例子先:

相同的值会被覆盖掉,也就是说好保存最后一个重复元素的索引,所以这里即使有重复元素,遍历的时候获取到的也是最后一个重复元素的索引,而遍历的时候是从前往后遍历的,所以这样如果要找到的目标元素是两个相同的元素,也是可以很好的找到目标解的.

@cout_time
def two_sum_05(nums, target):
    # 先保存到字典当中去
    hashDict = {}
    for index, num in enumerate(nums):
        hashDict[num] = index

    for i in range(len(nums)):
        index1 = i
        index2 = hashDict.get(target - nums[i])
        if index2 is not None and index1 != index2:
            return [index1,index2]


if __name__ == '__main__':
    nums = list(range(10000))
    target = 12222
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_04(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_05(nums,target)
    print("res: {}".format(resIndex))
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
28
29
30
31

结果:我们把数据加大一些,可以明显看到差异:

方法6: 上面的hashDict的优化版本

不需要num2在整个dict中去查找.可以在num1之前的dict中查找,因此就只需要一次循环可解决.

@cout_time
def two_sum_06(nums, target):
    hashDict = {}
    for index, num in enumerate(nums):
        if hashDict.get(target - num) is not None:
            return [hashDict.get(target - num),index]
        hashDict[num] = index



if __name__ == '__main__':
    nums = list(range(10000))
    target = 12222
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_04(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_05(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_06(nums,target)
    print("res: {}".format(resIndex))
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
28
29
30

结果: 和上面的方法,提升的效果不是很明显.

2. 两数相加

① 题目

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

② 示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
1
2
3

示例2:

输入：l1 = [0], l2 = [0]
输出：[0]
1
2

示例3:

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
1
2

④ 答案

解法1: 先理解题目,首先题目中的链表的头部到尾部的顺序,刚好是个位->到更高的位的顺序.所以得到的结果的当前位只需要考虑相加之后,然后再加上上一个节点的进位,对10取模就是最终结果,然后新的下一个节点的进位carry为当前节点的(val1+val2+carry) // 10

算法步骤:

先将l1和l2头节点的值加起来赋值给新链表的头节点
遍历两个链表,只要有一个链表没有遍历结束,就继续遍历,当有一个链表结束的时候,将其值赋值为0
每次遍历生成一个当前节点cur的下一个节点,其值为链表对应节点的和再加上当前节点cur产生的进位.
更新进位后的当前节点cur的值
循环结束后,因为最后一个节点也是可能产生进位的,因此如果最后的节点的值是两位数的话,要新增一个节点,赋值为carry
返回头节点

代码实现:

def add_two_numbers(l1, l2):
    head = ListNode(l1.val + l2.val)
    cur = head  # 头节点
    while l1.next or l2.next:
        l1 = l1.next if l1.next else ListNode(0)  # 下一个节点的值
        l2 = l2.next if l2.next else ListNode(0)  # 下一个节点的值
        cur.next = ListNode(l1.val + l2.val + cur.val // 10)
        cur.val = cur.val % 10
        cur = cur.next  # 当前节点指向下一个节点

    # 判断最后那个节点,如果是两位数,就再进一位
    if cur.val >= 10:
        cur.next = ListNode(cur.val // 10)
        cur.val = cur.val % 10
    return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解法2: 也是遍历链表,只是进位还有链表L1和L2,是分别做累加,存在就累加,不存在就继续.

def add_two_numbers_01(Ln1, Ln2):
    """
    两个数相加,链表
    :param Ln1:
    :param Ln2:
    :return:
    """
    # 首先创建一个虚拟节点,并创建一个current指针,指向这个节点
    current = dummy = ListNode()
    # 初始化carry和两个两个链表对应节点相加的值
    carry, value = 0, 0

    while carry or Ln1 or Ln2:
        value = carry
        if Ln1:
            Ln1, value = Ln1.next, Ln1.val + value

        if Ln2:
            Ln2, value = Ln2.next, Ln2.val + value

        carry, value = divmod(value, 10)
        current.next = ListNode(value)
        current = current.next

    return dummy.next
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

3. 无重复字符串的最长子串

① 题目

给定一个字符串 s,请你找出其中不含有重复字符的最长子串的长度.

② 示例

示例1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3

示例2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3

示例3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4

③ 答案

解法1: 最直观的感受是遍历,然后求出所有的子串,然后记录那个最大的子串.

解题步骤:

双层遍历,第一层遍历从第一位开始
第二层遍历,从第一层遍历的开始位置开始,然后求出是否有重复元素,如果有重复元素就退出遍历.
最后根据子串的长度,记录最大值.这里是根据子串切片来实现的,通过判断子串的切片是否具有重复元素来实现.

@cout_time
def length_of_longest_substring_01(s):
    """
    获取最长的无重复子串的长度
    :param s:
    :return:
    """
    sLen = len(s)
    if sLen == 1:
        return 1
    maxLen = 0
    for i in range(sLen):
        for j in range(i, sLen):
            subStr = s[i:j+1]
            # 如果是最后一位了,就返回
            if j == sLen - 1:
                if len(subStr) > maxLen:
                    maxLen = len(subStr)
                break
            if s[j+1] in subStr:
                if len(subStr) > maxLen:
                    maxLen = len(subStr)
                break  # 退出内层循环,并记录那个长度
    return maxLen


if __name__ == '__main__':
    s = "abcabcbbabcedfeasdf"*10000
    res = length_of_longest_substring_01(s)
    print("res: {}".format(res))

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
28
29
30
31

结果:

解法2: 滑动窗口.

解释下滑动窗口:

滑动窗口是基于双指针的一种思想,两个指针指向的元素之间形成一个窗口.

核心思想:

维持住一个窗口,可以理解为队列,一开始窗口的边界为left,right,此时它们是重合的,所以窗口的大小为0
先扩张右边界,直到出现了下一个元素在[left,right)区间内,就将窗口的元素从左边开始删除,直到出现无重复元素
然后再扩张右边界,出现重复元素,再删除左边界,直到最后结束

@cout_time
def length_of_longest_substring_02(s):
    if not s:
        return 0
    left = 0
    subStr = set()
    n = len(s)
    maxLen = 0
    curLen = 0
    for i in range(n):
        curLen += 1
        while s[i] in subStr:
            subStr.remove(s[left])
            left += 1
            curLen -= 1
        if curLen > maxLen:
            maxLen = curLen
        subStr.add(s[i])
    return maxLen

if __name__ == '__main__':
    s = "abcabcbbabcedfeasdf" * 50000
    res = length_of_longest_substring_01(s)
    print("res: {}".format(res))

    print("========================================")
    res = length_of_longest_substring_02(s)
    print("res: {}".format(res))
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
28

结果:

滑动窗口明显速度上提升很大!

4. 寻找两个正序数组的中位数

① 题目

给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2.请你找出并返回这两个正序数组的中位数.算法的时间复杂度应该为O(log(m+n))

② 示例

示例1:

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
1
2
3

示例2:

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
1
2
3

③ 答案

解法1: 暴力解法

将两个数组,合并
排序,取中位数即可.

应该是不满足要求的,但是学习嘛,我也是写了一下.这里使用到了list的一些性质,比如合并,比如排序;

@cout_time
def find_median_sorted_arrays_01(nums1, nums2):
    nums1.extend(nums2)
    nums1.sort()
    # 判断个数是奇数还是偶数
    if len(nums1) % 2 == 0:
        midIndex = int(len(nums1) / 2) - 1
        medianVal = (nums1[midIndex] + nums1[midIndex + 1]) / 2
    else:
        midIndex = int(len(nums1) / 2)
        medianVal = nums1[midIndex]
    return medianVal


if __name__ == '__main__':
    num1 = list(range(10000))
    num2 = list(range(10000,100000))

    res = find_median_sorted_arrays_01(num1, num2)
    print("res: {}".format(res))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法2: 循环遍历,但是不需要两个列表合并.

由于两个数组的长度已知,因此中位数的对应的两个数组的下标位置也是已知的.只是这里要区分是偶数还有就是奇数的问题.

如果是奇数,比如[1,2,3], [4,5], len = 5. 中位数的下标位置为 len / 2,所以要遍历len/2次.
如果是偶数,比如[1,2,3],[4,5,6], len = 6. 中位数的下标位置为 len / 2 ,len / 2 - 1,所以遍历的次数也是len/2次.

我们维护一个指针,然后按照一定的规则遍历 len / 2次,最后得到的那个结构就是中位数,只是要根据len来判断奇偶来最后求得中位数.

然后就是数组遍历的时候,限制条件.
用aStart和bStart分别表示当前指向A数组和B数组的位置.如果aStart还没有到最后并且此时A的位置的数字小于B位置的数组,那么久可以后移了.

如果B数组此刻已经没有数字了,继续取数字B[bStart]就会越界,所以判断下bStart是否大于数组长度了.

@cout_time
def find_median_sorted_arrays_02(nums1,nums2):
    m = len(nums1)
    n = len(nums2)
    lens = m +n
    aStart,bStart = 0,0
    left = right = -1,-1
    for i in range(int(lens / 2) + 1):
        left = right
        if aStart < m and (bStart >= n or nums1[aStart] < nums2[bStart]):
            right = nums1[aStart]
            aStart += 1
        else:
            right = nums2[bStart]
            bStart += 1

    if (lens & 1) == 0:
        return (left + right) / 2.0
    else:
        return right





if __name__ == '__main__':
    num1 = list(range(10000))
    num2 = list(range(10000,100000))

    res = find_median_sorted_arrays_01(num1, num2)
    print("res: {}".format(res))

    res = find_median_sorted_arrays_02(num1,num2)
    print("res: {}".format(res))
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
28
29
30
31
32
33
34

结果:

解法3: 二分查找法

思路:

看到O(log(m+n))和有序数列,不难想到使用 二分查找来解决此题.

第一步: 交换顺序

为了减少思考,我们先假定一个序列的长度总不大于第二个.
如果大了,就交换一下.我们假定 len(nums1) <= len(nums2)
如果一开始不交换nums1和nums2,mid2 = half_len - mid1 可能会是负数.

记录两个序列的长度

len1,len2 = len(nums1),len(nums2)
1

记录二分查找的信息

怎么二分查找呢?
假设两个序列按照顺序合并了,那么中间点的位置在 (len1 + len2 + 1) // 2
假定这个理想的中位数是x
考虑一般的情况下,第一个序列存在一个数,其左边都是小于x,右边都是大于x.
对第二个序列也是一样的
我们对这两个数在各自序列的位置分别称作mid1和mid2.
我们首先对第一个序列进行二分查找
记录左边界,右边界为第一个序列的左右边界
而查找的中间就是左右边界的中间点.
对于mid2, 便是(len1 + len2 + 1) // 2 减去 mid1

更新二分查找的条件:

不妨这样想,最理想的情况下,两个序列的mid1和mid2应该是一样的.
这时候mid1左侧和mid2左侧的数都应该比mid1和mid2右侧的数小.
所以可以肯定的是,如果mid2左侧的数比mid1右侧的数都大,那么第一个序列的mid1太靠近左边了.
可以这么想,如果mid2左侧的数比mid1右侧的都要大,那不如第二个序列数选小一点而第一个序列的数选大一点,这样两个数会而更加接近.
要把第一个序列的中间往右,即二分查找的更新left
反之更新right,记得mid1不要越过上限!

while left < right:
    if mid1 < len1 and nums2[mid2-1] > nums1[mid1]:
        left = mid1 + 1
    else:
        right = mid1
    mid1 = (left + right) // 2
    mid2 = half_len - mid1
1
2
3
4
5
6
7

返回情况判断:

完成了这样的二分查找,我们找到了第一个序列的中间数和第二个序列的中间数
我们要返回哪个呢?还是返回它们的一半?
如果两个序列的长度和是奇数的话,那么就有一个唯一的中间的数
如果是偶数的话,就是两个中间值平均数.
我们假想两个序列合并排序,那么就有这个中位数分成左右两块
我们需要一个左边的最大值和右边的一个最小值
如何找到左边的最大值呢?
通常情况下,我们已经找到二路mid1和mid2,对比这两个数
小的那个就是右边的最小值.
对比mid1和mid2左边的数,大的那个就是左边的最大值.
为什么是这个逻辑呢? 为什么左侧两个数是左边的最大值,而本身就是右边的最小值呢?为什么不是它们本身两者分高低呢?
这样因为我们从0到(m + n) // 2总共共有(m + n) // 2 + 1个数（因为下标0也是一个数），这是大于半数的。而减去这俩中位数后，剩下的就正好是一半的数量。这即左半部分。所以我们找的mid其本身应该划分到右边部分。这里可以多找几个测试样例测试几次。
对了，还有一些特殊情况没考虑，就是比如第一行特别小的情况下，那么左大就是二行的mid2偏左，而右小就是二行的mid2。
如果总数是奇数，那么输出左大，如果是偶数，输出左大和右小的平均数。

@cout_time
def find_median_sorted_arrays_03(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    len1, len2 = len(nums1), len(nums2)

    left, right, half_len = 0, len1, (len1 + len2 + 1) // 2
    mid1 = (left + right) // 2
    mid2 = half_len - mid1

    while left < right:
        if mid1 < len1 and nums2[mid2 - 1] > nums1[mid1]:
            left = mid1 + 1
        else:
            right = mid1
        mid1 = (left + right) // 2
        mid2 = half_len - mid1

    if mid1 == 0:
        max_of_left = nums2[mid2 - 1]
    elif mid2 == 0:
        max_of_left = nums1[mid1 - 1]
    else:
        max_of_left = max(nums1[mid1 - 1], nums2[mid2 - 1])

    if (len1 + len2) % 2 == 1:
        return max_of_left

    if mid1 == len1:
        min_of_right = nums2[mid2]
    elif mid2 == len2:
        min_of_right = nums1[mid1]
    else:
        min_of_right = min(nums1[mid1], nums2[mid2])

    return (max_of_left + min_of_right) / 2


if __name__ == '__main__':
    num1 = list(range(10000))
    num2 = list(range(10000, 100000))

    res = find_median_sorted_arrays_01(num1, num2)
    print("res: {}".format(res))

    res = find_median_sorted_arrays_02(num1, num2)
    print("res: {}".format(res))

    res = find_median_sorted_arrays_03(num1, num2)
    print("res: {}".format(res))

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

结果:

可以看到速度非常的快,简直就是秒杀前面的的算法.

5. 最长回文字符串

① 题目

给定你一个字符串s,找到s中最长的回文子串.

② 示例

示例1:

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
1
2
3

示例2:

输入：s = "cbbd"
输出："bb"
1
2

③ 答案

首先科普一下,什么是回文子串?

就是这个字符串左右是对称的,不管是从前往后看,还是从后往前看,它都是一样的.

解法1: 暴力解法,遍历所有的字符串,然后找到最长的回文子串.有点类似之前的那个找无重复字符串子串的解法:

首先是要明白回文子串,长度肯定要大于2,如果长度为1,肯定就不是回文子串了.
判断某个字符开始,到另外一个字符结束的位置是否是回文字符串,如果是,就记录下长度,以及对应的回文字符串.
重复遍历,然后更新.

@cout_time
def longest_palindrome_01(s):
    """
    最长回文数解法1
    :param s:
    :return:
    """
    if len(s) <= 1:
        return s
    maxLen = 0
    sRes = ""
    for i in range(len(s) - 1):
        for j in range(i + 1, len(s) + 1):
            subs = s[i:j]
            if subs == subs[::-1]:
                if len(subs) > maxLen:
                    sRes = subs
                    maxLen = len(subs)
    return sRes if sRes != "" else sRes[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这个算法很耗时,测试的时候没有通过.

解法2: 可以从最长的子串开始遍历,然后找到回文串就返回,这样不用遍历全部的子串:

@cout_time
def longest_palindrome_02(s):
    length = len(s)
    if length < 2:
        return s
    for i in range(length, 0, -1):
        for j in range(length - i + 1):
            subStr = s[j:j + i]
            if subStr == subStr[::-1]:
                return subStr
    return ""

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

解法3: 动态规划

思路和算法

对于一个子串而言,如果它是回文串,并且长度大于2,那么将它收尾的两个字母去除之后,它仍然是一个回文串.例如对于字符串 abcba,如果我们已经知道了bcb是一个回文字符串,两边的字符又相同,那么abcba一定也是回文字符串.

根据这个思路,我们就可以用动态规划的方法解决这个问题.我们用P(i,j)表示字符串s的第i到j个字母组成的串(下文表示成s[i:j])是否为回文串:

这里的其他的情况包含两种可能性:

s[i,j] 本身不是一个回文串.
i > j, 此时s[i,j]本身不合法.
那么我们可以写出动态规划的状态转移方程:

也就是说,只有 s[i+1,j-1]是回文串并且s的第i个元素和第j个元素相同的时候,s[i:j]才是回文串.

上文的所有的讨论是建立在子串长度大于2的前提之上的,我们还需要考虑动态规划中的边界条件,即子串的长度为1或者2.对于长度为1的子串,它显然是回文串; 对于长度为2的子串,只要它的两个字母相同,它就是一个回文串.因此我们可以写出动态规划的边界条件:

根据这个思路,我们就可以完成动态规划了,最终的答案即为所有P(i,j) = true中 j - i + 1(即子串长度)的最大值.注意: 在状态转移方程中,我们是从长度较短的字符串向长度较长的字符串进行转移的,因此一定要注意动态规划的循环顺序.

@cout_time
def longest_palindrome_03(s):
    length = len(s)
    if length < 2:
        return s
    maxLen = 1
    begin = 0
    # dp[i][j] 表示s[i..j]是否是回文串
    dp = [[False] * length for _ in range(length)]
    for i  in range(length):
        dp[i][i] = True

    # 递推开始
    # 先枚举子串长度
    for L in range(2,length+1):
        # 枚举左边界,左边界的上限可以设置的宽松一些
        for i in range(length):
            # 由L 和i 可以确定右边界,即 j - i + 1 = L
            j = L + i -1
            # 如果右边界越界,就可以退出当前循环
            if j >= length:
                break

            if s[i] != s[j]:
                dp[i][j] = False
            else:
                if j - i <3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]

            # 只要dp[i][L] == True成立,就表示子串s[i...L]是回文,此时记录回文长度和起始位置
            if dp[i][j] and j - i + 1 > maxLen:
                maxLen = j - i + 1
                begin = i
    return s[begin:begin+maxLen]
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
28
29
30
31
32
33
34
35
36

结果:

动态规划的时间更快一些:

解法4: 中心扩展算法

思路和算法:

我们仔细观察下动态规划的那个方法的状态转移方程:

找出其中的状态转移链:

可以发现,所有的状态在转移的时候的可能性都是唯一的.也就是说,我们可以从每一种边界情况开始[扩展],也可以得出所有的状态对应的答案.

边界情况即为子串长度为1或者2的情况.我们枚举每一种边界情况,并从对应的子串开始不断地向两边扩展.如果两边的字母相同,我们就可以继续扩展,例如从P(i+1,j-1)扩展到P(i,j);如果两边的字母不同,我们就可停止扩展,因为在这之后的子串都不能是回文串了.

所以,我们发现,边界情况对应的子串实际上就是我们扩展出的回文串的(回文中心).这个方法的本质即为: 我们枚举所有的回文中心并尝试扩展,直到无法扩展为止,此时的回文串长度即为此(回文中心)下的最长回文长度.我们对所有的长度求出最大值,即可得到最终的答案.

def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1, right - 1


@cout_time
def longest_palindrome_04(s):
    start, end = 0, 0
    for i in range(len(s)):
        left1, right1 = expand_around_center(s, i, i)
        left2, right2 = expand_around_center(s, i, i + 1)
        if right1 - left1 > end - start:
            start, end = left1, right1

        if right2 - left2 > end - start:
            start, end = left2, right2
    return s[start:end + 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

结果:

中心扩展法时间更短了

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/146081

第一章 力扣热题100道(1-5)

文章目录

1. 两数之和

① 题目

② 示例

③ 答案

2. 两数相加

① 题目

② 示例

④ 答案

3. 无重复字符串的最长子串

① 题目

② 示例

③ 答案

4. 寻找两个正序数组的中位数

① 题目

② 示例

③ 答案

5. 最长回文字符串

① 题目

② 示例

③ 答案

第一章力扣热题100道(1-5)