Leecode 101刷题笔记之第三章:和你一起你轻松刷题(Python)

简介: 本文是关于LeetCode算法题的刷题笔记,主要介绍了使用双指针技术解决的一系列算法问题,包括Two Sum II、Merge Sorted Array、Linked List Cycle II等,并提供了详细的题解和Python代码实现。

167. Two Sum II - Input array is sorted (Easy)-Two Sum

题目描述
在一个增序的整数数组里找到两个数,使它们的和为给定值。已知有且只有一对解。
输入输出样例
输入是一个数组(numbers)和一个给定值(target)。输出是两个数的位置,从1 开始计数。

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

在这个样例中,第一个数字(2)和第二个数字(7)的和等于给定值(9)。
题解
因为数组已经排好序,我们可以采用方向相反的双指针来寻找这两个数字,一个初始指向最
小的元素,即数组最左边,向右遍历;一个初始指向最大的元素,即数组最右边,向左遍历。

如果两个指针指向元素的和等于给定值,那么它们就是我们要的结果。如果两个指针指向元
素的和小于给定值,我们把左边的指针右移一位,使得当前的和增加一点。如果两个指针指向元
素的和大于给定值,我们把右边的指针左移一位,使得当前的和减少一点。

可以证明,对于排好序且有解的数组,双指针一定能遍历到最优解。证明方法如下:假设最
优解的两个数的位置分别是l 和r。我们假设在左指针在l 左边的时候,右指针已经移动到了r;
此时两个指针指向值的和小于给定值,因此左指针会一直右移直到到达l。同理,如果我们假设
在右指针在r 右边的时候,左指针已经移动到了l;此时两个指针指向值的和大于给定值,因此
右指针会一直左移直到到达r。所以双指针在任何时候都不可能处于¹l; rº 之间,又因为不满足条
件时指针必须移动一个,所以最终一定会收敛在l 和r。
具体代码

# leetcode submit region begin(Prohibit modification and deletion)
"""
执行耗时:20 ms,击败了75.58% 的Python用户
内存消耗:13.1 MB,击败了89.31% 的Python用户
"""
class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        if numbers:
            start = 0
            end = len(numbers) - 1
            while start < end:
                if numbers[start] + numbers[end] == target:
                    return [start + 1, end + 1]
                elif numbers[start] + numbers[end] > target:
                    end -= 1
                else:
                    start += 1
# leetcode submit region end(Prohibit modification and deletion)

88. Merge Sorted Array (Easy)–归并有序数组

题目描述
给定两个有序数组,把两个数组合并为一个。
输入输出样例
输入是两个数组和它们分别的长度m 和n。其中第一个数组的长度被延长至m + n,多出的
n 位被0 填补。题目要求把第二个数组归并到第一个数组上,不需要开辟额外空间。

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: nums1 = [1,2,2,3,5,6]

题解
因为这两个数组已经排好序,我们可以把两个指针分别放在两个数组的末尾,即nums1 的
m 􀀀 1 位和nums2 的n 􀀀 1 位。每次将较大的那个数字复制到nums1 的后边,然后向前移动一位。
因为我们也要定位nums1 的末尾,所以我们还需要第三个指针,以便复制。

在以下的代码里,我们直接利用m 和n 当作两个数组的指针,再额外创立一个pos 指针,起
始位置为m+n􀀀1。每次向前移动m 或n 的时候,也要向前移动pos。这里需要注意,如果nums1
的数字已经复制完,不要忘记把nums2 的数字继续复制;如果nums2 的数字已经复制完,剩余
nums1 的数字不需要改变,因为它们已经被排好序。
具体代码

"""
执行用时:8 ms, 在所有 Python 提交中击败了99.61%的用户
内存消耗:12.7 MB, 在所有 Python 提交中击败了99.49%的用户
"""
def merge(nums1, m, nums2, n):
    # l为nums1的m开始索引, r为nums2的n开始索引,index为修改nums1的开始索引,然后从nums1末尾开始往前遍历
    l=m-1
    r=n-1
    index=len(nums1)-1
    # 按从大到小,从后往前修改nums1的值,每次都赋值为nums1和nums2的当前索引的较大值,然后移动索引
    while l>=0 and r>=0:
        # 通过nums2的值慢慢赋值给nums1
        if nums1[l]>nums2[r]:
            nums1[index]=nums1[l]
            l-=1
        else:
            nums1[index]=nums2[r]
            r-=1
        index-=1
    # 如果nums2还没遍历完
    while r>=0:
        nums1[index]=nums2[r]
        r-=1
        index-=1
    return nums1

142. Linked List Cycle II (Medium)-快慢指针

题目描述
给定一个链表,如果有环路,找出环路的开始点。
输入输出样例

题解
对于链表找环路的问题,有一个通用的解法——快慢指针(Floyd 判圈法)。给定两个指针,
分别命名为slow 和fast,起始位置在链表的开头。每次fast 前进两步,slow 前进一步。如果fast
可以走到尽头,那么说明没有环路;如果fast 可以无限走下去,那么说明一定有环路,且一定存
在一个时刻slow 和fast 相遇。当slow 和fast 第一次相遇时,我们将fast 重新移动到链表开头,并
让slow 和fast 每次都前进一步。当slow 和fast 第二次相遇时,相遇的节点即为环路的开始点。
具体代码

"""
执行用时:32 ms, 在所有 Python 提交中击败了84.83%的用户
内存消耗:18.9 MB, 在所有 Python 提交中击败了93.97%的用户
"""
def detectCycle(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head:return None
    slowp=fastp=head
    while fastp and fastp.next:
        slowp=slowp.next
        fastp=fastp.next.next
        if fastp and slowp==fastp:
            slowp=head
            while fastp!=slowp:
                slowp=slowp.next
                fastp=fastp.next
            return slowp
    return None

76. MinimumWindow Substring (Hard)-滑动窗口

题目描述
给定两个字符串S 和T,求S 中包含T 所有字符的最短连续子字符串的长度,同时要求时间
复杂度不得超过O(n).
输入输出样例
输入是两个字符串S 和T,输出是一个S 字符串的子串。

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

在这个样例中,S 中同时包含一个A、一个B、一个C 的最短子字符串是“BANC”。
题解
本题使用滑动窗口求解,即两个指针l 和r 都是从最左端向最右端移动,且l 的位置一定在
r 的左边或重合。注意本题虽然在for 循环里出现了一个while 循环,但是因为while 循环负责移
动l 指针,且l 只会从左到右移动一次,因此总时间复杂度仍然是O¹nº。本题使用了长度为128
的数组来映射字符,也可以用哈希表替代;其中chars 表示目前每个字符缺少的数量,flag 表示
每个字符是否在T 中存在。
具体代码

"""
执行用时:468 ms, 在所有 Python 提交中击败了5.62%的用户
内存消耗:16.1 MB, 在所有 Python 提交中击败了18.54%的用户
"""
from collections import Counter
def minWindow(s, t):
    def check(dic):
        return all(map(lambda x:x>=0,dic.values()))
    len_t,len_s=len(t),len(s)
    if len_t>len_s :return ''
    if s=='' and t=='': return ''

    a,b=Counter(),Counter(t)
    l,mans,mins=0,float('inf'),float('-inf')
    a.subtract(b)
    for r in range(len(s)):
        a[s[r]]+=1
        while check(a):
            # 说明找到更小的区间了
            if mans-mins>r-l:
                mins,mans=l,r
            a[s[l]]-=1
            l+=1
    return s[mins:mans+1] if mans!=float('inf') else ''

练习-基础难度

633. Sum of Square Numbers(Easy)

Two Sum 题目的变形题之一。
题目描述
给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c 。
输入输出样例
输入:c = 5
输出:true
解释:1 * 1 + 2 * 2 = 5
题解
双指针
i 从 0 开始
j 从可取的最大数 int(math.sqrt©) 开始
total = i * i + j * j
total > c: j = j - 1,将 total 值减小
total < c: i = i + 1,将 total 值增大
total == c:返回 True
具体代码

"""
执行用时:60 ms, 在所有 Python 提交中击败了91.84%的用户
内存消耗:13.1 MB, 在所有 Python 提交中击败了40.31%的用户
"""
def judgeSquareSum(c):
    """
    :type c: int
    :rtype: bool
    """
    import math
    l=0
    r=int(math.sqrt(c))
    while r>=l:
        sums=r * r + l * l
        if sums==c:
            return True
        elif sums>c:
            r-=1
        else:
            l+=1
    return False

680. Valid Palindrome II (Easy)

Two Sum 题目的变形题之二。
题目描述
给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
输入输出样例
输入: s = “aba”
输出: true
题解
遇到第一个不同的时候,就进行判断:删左边的或删右边的
两种可能都进行下判断
c++ 没有 [::-1] 的用法,自己实现一下
时间复杂度:O(n)
空间复杂度:O(1)
具体代码

"""
执行用时:72 ms, 在所有 Python 提交中击败了82.51%的用户
内存消耗:13.6 MB, 在所有 Python 提交中击败了43.44%的用户
"""
def validPalindrome(s):
    if s == s[::-1]:
        return True
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] == s[r]:
            l, r = l + 1, r - 1
        else:
            # 考虑到只能删除一个数 那么直接
            a=s[l+1:r+1]
            b=s[l:r]
            return a==a[::-1] or b==b[::-1]

524. LongestWord in Dictionary through Deleting (Medium)

归并两个有序数组的变形题。
题目描述
给你一个字符串 s 和一个字符串数组 dictionary ,找出并返回 dictionary 中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个,返回长度最长且字母序最小的字符串。如果答案不存在,则返回空字符串。
输入输出样例
输入:s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出:“apple”
题解
先根据长度和字符串进行排序,然后通过双指针处理字符串,如果字典里面的字符子串全部都在s中,则返回字符串本身,如果不存在则返回空字符串
具体代码

"""
执行用时:440 ms, 在所有 Python 提交中击败了19.25%的用户
内存消耗:15.5 MB, 在所有 Python 提交中击败了87.70%的用户
"""
def findLongestWord(s, dictionary):
    """
    :type s: str
    :type dictionary: List[str]
    :rtype: str
    """
    def check(dict, s):
        # 双指针判断
        ld, ls = 0, 0
        while ld < len(dict) and ls < len(s):
            if dict[ld] == s[ls]:
                ld += 1  # 在里面就找目标里下一个数
            ls += 1  # 不在里面就继续遍历原字符串
            if ld == len(dict):
                return True
        return False

    # -len(x),表示字符串长度最长的排在前面,如果遇到了相同长度的字符串,则比较两个字符串的字典序
    dictionary.sort(key=lambda x: (-len(x), x))
    for dict in dictionary:
        if check(dict, s):
            return dict
    return ''

练习-进阶难度

340. Longest Substring with At Most K Distinct Characters (Hard)

由于要VIP无法进行练习。

目录
相关文章
|
2月前
|
搜索推荐 Python
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
23 3
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第四章:和你一起你轻松刷题(Python)
这篇博客是关于LeetCode上使用Python语言解决二分查找问题的刷题笔记,涵盖了从基础到进阶难度的多个题目及其解法。
18 0
|
2月前
|
算法 C++ 索引
Leecode 101刷题笔记之第二章:和你一起你轻松刷题(Python)
本文是关于LeetCode 101刷题笔记的第二章,主要介绍了使用Python解决贪心算法题目的方法和实例。
11 0
|
17天前
|
存储 数据挖掘 开发者
Python编程入门:从零到英雄
在这篇文章中,我们将一起踏上Python编程的奇幻之旅。无论你是编程新手,还是希望拓展技能的开发者,本教程都将为你提供一条清晰的道路,引导你从基础语法走向实际应用。通过精心设计的代码示例和练习,你将学会如何用Python解决实际问题,并准备好迎接更复杂的编程挑战。让我们一起探索这个强大的语言,开启你的编程生涯吧!
|
23天前
|
机器学习/深度学习 人工智能 TensorFlow
人工智能浪潮下的自我修养:从Python编程入门到深度学习实践
【10月更文挑战第39天】本文旨在为初学者提供一条清晰的道路,从Python基础语法的掌握到深度学习领域的探索。我们将通过简明扼要的语言和实际代码示例,引导读者逐步构建起对人工智能技术的理解和应用能力。文章不仅涵盖Python编程的基础,还将深入探讨深度学习的核心概念、工具和实战技巧,帮助读者在AI的浪潮中找到自己的位置。
|
23天前
|
机器学习/深度学习 数据挖掘 Python
Python编程入门——从零开始构建你的第一个程序
【10月更文挑战第39天】本文将带你走进Python的世界,通过简单易懂的语言和实际的代码示例,让你快速掌握Python的基础语法。无论你是编程新手还是想学习新语言的老手,这篇文章都能为你提供有价值的信息。我们将从变量、数据类型、控制结构等基本概念入手,逐步过渡到函数、模块等高级特性,最后通过一个综合示例来巩固所学知识。让我们一起开启Python编程之旅吧!
|
23天前
|
存储 Python
Python编程入门:打造你的第一个程序
【10月更文挑战第39天】在数字时代的浪潮中,掌握编程技能如同掌握了一门新时代的语言。本文将引导你步入Python编程的奇妙世界,从零基础出发,一步步构建你的第一个程序。我们将探索编程的基本概念,通过简单示例理解变量、数据类型和控制结构,最终实现一个简单的猜数字游戏。这不仅是一段代码的旅程,更是逻辑思维和问题解决能力的锻炼之旅。准备好了吗?让我们开始吧!
|
10天前
|
Python
Python编程入门:从零开始的代码旅程
本文是一篇针对Python编程初学者的入门指南,将介绍Python的基本语法、数据类型、控制结构以及函数等概念。文章旨在帮助读者快速掌握Python编程的基础知识,并能够编写简单的Python程序。通过本文的学习,读者将能够理解Python代码的基本结构和逻辑,为进一步深入学习打下坚实的基础。
|
14天前
|
数据采集 存储 数据处理
Python中的多线程编程及其在数据处理中的应用
本文深入探讨了Python中多线程编程的概念、原理和实现方法,并详细介绍了其在数据处理领域的应用。通过对比单线程与多线程的性能差异,展示了多线程编程在提升程序运行效率方面的显著优势。文章还提供了实际案例,帮助读者更好地理解和掌握多线程编程技术。
|
17天前
|
存储 人工智能 数据挖掘
Python编程入门:打造你的第一个程序
本文旨在为初学者提供Python编程的初步指导,通过介绍Python语言的基础概念、开发环境的搭建以及一个简单的代码示例,帮助读者快速入门。文章将引导你理解编程思维,学会如何编写、运行和调试Python代码,从而开启编程之旅。
36 2