文章目录

• • LeetCode
  • • 1、两数之和*
    • 2、两数相加
    • 3、无重复字符的最长子串**
    • 4、寻找两个正序数组的中位数**
    • 5、最长回文子串**
    • • 动态规划思维导图
    • 6、Z 字形变换
    • 7、整数反转
    • 8、字符串转换整数 (atoi)
    • 9、回文数
    • 10、正则表达式匹配*
    • 11、盛最多水的容器*
    • 12、整数转罗马数字
    • 13、 罗马数字转整数*
    • 14、最长公共前缀*
    • 15、三数之和
    • 16、最接近的三数之和
    • 17、电话号码的字母组合*
    • 18、四数之和
    • 19、删除链表的倒数第N个节点
    • 20、有效的括号
    • 21、合并两个有序链表
    • 22、括号生成**
    • 23、合并K个排序链表
    • 24、两两交换链表中的节点
    • 25、K 个一组翻转链表
    • 26、删除排序数组中的重复项
    • 27、移除元素
    • 28、实现 strStr()*
    • 29、两数相除
    • 30、串联所有单词的子串**
    • 31、下一个排列
    • 32、最长有效括号*
    • 33、搜索旋转排序数组**
    • 34、在排序数组中查找元素的第一个和最后一个位置
    • 35、搜索插入位置
    • 36、有效的数独
    • 37、解数独**
    • 38、外观数列
    • 39、组合总和*
    • 40、组合总和 II
    • 41、缺失的第一个正数**
    • 42、接雨水
    • 43、字符串相乘
    • 44、通配符匹配*
    • 45、跳跃游戏 II
    • 46、全排列
    • 47、全排列 II
    • 48、旋转图像
    • 49、字母异位词分组*
    • 50、Pow(x, n)
    • 51、N皇后
    • 52、N皇后 II
    • 53、最大子序和*
    • 54、螺旋矩阵
    • 55、跳跃游戏
    • 56、合并区间
    • 57、插入区间
    • 58、最后一个单词的长度
    • 59、螺旋矩阵 II
    • 60、第k个排列
    • 61、旋转链表
    • 62、不同路径
    • 63、不同路径 II
    • 64、最小路径和
    • 65、有效数字*
    • 66、加一
    • 67、二进制求和
    • 68、文本左右对齐
    • 69、x 的平方根
    • 70、爬楼梯*
    • 71、简化路径
    • 72、编辑距离
    • 73、矩阵置零*
    • 74、搜索二维矩阵
    • 模板

LeetCode

1、两数之和*

题目链接

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。不能使用重复元素
方法一：分治
用首尾递进查找做的，需要一次排序，时间复杂度是 O(nlogn)
方法二：字典*
把原先的数组转化成字典，通过字典去查询速度就会快很多，遍历数组，对于元素num1，若target-1存在于字典中直接返回，若不存在，则将其放入字典。时间复杂度是 O(n)

#方法一
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:start,end=0,len(nums)-1if end<1:return Falsenums.sort()sums=nums[start]+nums[end]while (sums!=target):if start==end:return Falseif sums<target:start+=1elif sums>target:end-=1sums=nums[start]+nums[end]return [start,end]
#方法二
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:d={}for index,num1 in enumerate(nums):num2=target-num1if num2 in d:return [d[num2],index]d[num1]=indexreturn None

2、两数相加

题目链接

题目： 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序的方式存储的，并且它们的每个节点只能存储 一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以0 开头。465:(5 -> 6 -> 4)
方法：链表

• 这题比较直观，就是循环创建新的节点储存新的计算结果，同时使用变量carry储存进位信息，直到两个代表加数的链表都走到尽头

注意：

• 在循环中不能将计算结果保存在现有节点中，再创建新节点，应该直接将结果保留在新节点中，否则尾节点会有一个多余的0

class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:output=ListNode(0)l3=outputcarry=0while l1 or l2:num1=l1.val if l1 else 0num2=l2.val if l2 else 0l1=l1.next if l1 else Nonel2=l2.next if l2 else None#注意：计算中carry应该放在括号里面l3.next=ListNode((num1+num2+carry)%10)carry=(num1+num2+carry)//10l3=l3.nextif carry==1:l3.next=ListNode(1)return output.next

3、无重复字符的最长子串**

题目链接

题目： 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
方法一：移动指针 + set**

• 使用滑动窗口，在每一步的操作中，将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后右指针不断地向右移动，直到两个指针对应的子串中出现重复的字符，我们记录下这个子串的长度
• 在上一步操作中，我们需要使用一种数据结构来判断是否有重复的字符，常用的数据结构为哈希集合——set
• 时间复杂度：O(N)

方法二：移动指针+字典（1+）

• 以字符为键，以字符所在的索引值为value（List），这样每次找到相同的字符时就能准确地知道左指针所需要移至的位置（方法一需要一步一步移动）。空间换时间。要注意左指针之前的字符也会保留在字典里，所以每次判断重复时要比较value[-1]和left的大小。

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:d = set()#第一次right的初始值设置成了1，导致第一个值没有存入d报错。。。right=1maxstr,lenth=0,len(s)for left in range(lenth):if left!=0:d.remove(s[left-1])while right<lenth and s[right] not in d:d.add(s[right])right+=1maxstr=max(maxstr,right-left)return maxstr

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

题目链接

题目： 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。nums1 和 nums2 不会同时为空。

方法：二分法 + 递归**

• 实现在两个有序数组中找到第K个元素：首先使用两个变量i和j分别来标记数组nums1和nums2的起始位置，然后我们分别在nums1和nums2中查找第K/2个元素，若某个数组没有第K/2个数字，就赋值上一个整型最大值，这样在后面运用二分法时就会淘汰另一个数组的前K/2个元素
• 可以使用反证法证明第K个元素必不在较小的前K/2个元素里
• 最后使用二分法：比较这两个数组的第K/2小的数字midVal1和midVal2的大小，如果第一个数组的第K/2个数字小的话，那么说明我们要找的数字肯定不在nums1中的前K/2个数字，所以我们可以将其淘汰，将nums1的起始位置向后移动K/2个，并且此时的K也自减去K/2，调用递归。反之亦然
• 边界情况：
  • 当某一个数组的起始位置>=其数组长度时，就等效于直接在另一个数组中找中位数
  • 如果K=1的话，比较nums1和nums2的起始位置i和j上的数字就可以了。

注意：

• 找中位数的小技巧：分别找第 (m+n+1) // 2 个，和 (m+n+2) // 2 个，然后求其平均值即可，这对奇偶数均适用。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:len1,len2=len(nums1),len(nums2)def find(i,j,k):'''实现在两个有序数组中找到第K个元素'''if i>=len1: return nums2[j+k-1] #nums1走到尽头if j>=len2: return nums1[i+k-1] #nums2走到尽头if k==1:    return min(nums1[i],nums2[j])#分别在nums1和nums2中查找第K/2个元素mid1=nums1[i+k//2-1] if (i+k//2-1)<len1 else float('inf')mid2=nums2[j+k//2-1] if (j+k//2-1)<len2 else float('inf')return find(i+k//2,j,k-k//2) if mid1<mid2 else find(i,j+k//2,k-k//2)left,right=(len1+len2+1)//2,(len1+len2+2)//2return (find(0,0,left) + find(0,0,right)) / 2

5、最长回文子串**

题目链接

题目： 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。“bab” 和 “aba” 都是 “babad” 回文字符串，返回一个即可
方法一： DP

• 用 P(i,j)表示字符串 s 的第 i 到 j个字母组成的串是否为回文串，其状态转移方程：
  
• 动态规划的边界条件：
  
• 时间复杂度：O(n^2)，空间复杂度 ：O(n^2)
• 官方参考代码

方法二：中心扩展算法

• 我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。
• 时间复杂度：O(n^2)，空间复杂度：O(1)。

方法三：Manacher 算法

• pass
• 时间复杂度：O(n)，空间复杂度 ：O(n)

#方法二，参考官方代码的改进部分已在备注中说明
class Solution:def longestPalindrome(self, s: str) -> str:start, end = 0, 0 #此处不直接记录当前最长回文子串，而是记录首尾索引值，能节省内存和简化代码lenth =len(s)def expand(i,j):    '''以i，j为回文中心向两边扩展回文子串'''            while (i>-1 and j<lenth and s[i]==s[j]):i-=1j+=1return i+1,j-1for i in range(lenth-1): #i是回文子串的中间'''DRY原则，需要分类讨论的构造函数进行统一'''left1,right1 = expand(i,i) #子串为奇数left2,right2 = expand(i,i+1) #子串为偶数if right1 - left1 > end - start:start, end = left1, right1if right2 - left2 > end - start:start, end = left2, right2return s[start:end+1]

动态规划思维导图

转自LeetCode评论区：评论地址

• KMP算法是一种改进的字符串匹配算法
• Manacher 算法专门用于解决“最长回文子串”问题，它是基于“中心扩散法”，采用和 kmp 算法类似的思想，依然是“以空间换时间”。

6、Z 字形变换

题目链接

题目： 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。之后，你的输出需要从左往右逐行读取，产生出一个新的字符串。示例：

方法一：找规律按行访问

• 首尾行字符间距为2*(numRows-1)，中间行字符间距为2*(numRows-i)，2*(i-1)
• 时间复杂度：O(n)，空间复杂度：O(n)

方法二：多维数组存储

#方法一
class Solution:def convert(self, s: str, numRows: int) -> str:lenth=len(s)out=''if numRows==1 or lenth<numRows: return sif numRows==2: return s[::2]+s[1::2]for i in range(1,1+numRows): #i表示当前记录的排数index=i-1 #i排第一列字符的位置while (index<lenth):out += s[index]index+=2*(numRows-i)#首尾行不执行此步骤out += s[index] if index<lenth and i!=1 and i!=numRows else ''index+=2*(i-1)return out

7、整数反转

题目链接

题目： 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

方法一：数字转字符串

• 时间复杂度：O(lg(n))44 ms，空间复杂度：O(lg(n))13.6 MB

方法二：通过求余模拟栈

• 时间复杂度：O(lg(n))40 ms，空间复杂度：O(1)13.7 M，可能数字太短看不出差异

#方法一
class Solution:def reverse(self, x: int) -> int:out=0 if x==0 else int(str(x)[::-1].strip('0')) if x>0 else -int(str(x)[-1:0:-1].strip('0'))return out if -2**31<=out<=2**31-1 else 0
#方法二
class Solution:def reverse(self, x: int) -> int:out=0sign=1 if x>=0 else -1x=abs(x)while (x!=0):out=out*10+x%10x=x//10return sign*out if -2147483648<=out<=2147483647 else 0

8、字符串转换整数 (atoi)

题目链接

题目：


方法一： 正则表达式

• 执行用时 :32 ms；内存消耗 :13.4 MB

方法一： 一行正则表达式

• 技巧一：int(*list)可以将长度为1的列表转化为整数，列表为空返回0（绝了！）
• 技巧二：findall 配合起始符号 ^ 找到第一个目标字符
• 技巧三：使用max，min函数来起到限幅的作用
• 执行用时 :40 ms；内存消耗 :13.7 MB

#方法一
from re import *
class Solution:def myAtoi(self, str: str) -> int:m=match(r'([\+\-]?[0-9]+)',str.strip(' '))if not m:return 0num=int(m.group(1))return num if -2147483648<=num<=2147483647 else -2147483648 if num<0 else 2147483647
#方法二
from re import *
class Solution:def myAtoi(self, str: str) -> int:return max(min(int(*re.findall('^[\+\-]?\d+', str.lstrip())), 2**31 - 1), -2**31)

9、回文数

题目链接

题目： 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。如：121TRUE，-121False，10False。
方法一：数字转字符串

• 将整个数字翻转后与原数字比较，76ms，13.7MB

方法二：数字转字符串

• 将后半段数字翻转后与前半段字比较，76ms，13.5MB（若不用字符，直接求余内存消耗会小些）

#方法一
class Solution:def isPalindrome(self, x: int) -> bool:return False if x<0 or (x%10 == 0 and x != 0) else x==int(str(x)[::-1])
#方法一
class Solution:def isPalindrome(self, x: int) -> bool:s=str(x)lenth=len(s)if x<0 or (x%10 == 0 and x != 0):return Falseelif lenth==1:return Trueelse :return s[:lenth//2:1]==s[:(lenth-1)//2:-1]

10、正则表达式匹配*

题目链接

题目： 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。’.’ 匹配任意单个字符，’*’ 匹配零个或多个前面的那一个元素。
方法： DP（准确来说应该是记忆化的递归）*

• 注释应该够看懂了

注：

• 此题不能用递归，否则时间复杂度会将是指数级的。可以选择加装饰器记忆体化，但是在leetcode上不太方便（对，就是是懒得试）。
• 方法是按照官方改写的，官方解答分类情况比我原版代码要少很多，整体更简洁易懂。原版代码中首先按照第一个字符是否匹配分类；然后每个分类中再分别讨论了后一个字符是否为*，这就产生了四种分类。而且我在讨论边界情况时讨论了s、p的长度不同时大于1的各种情况，在递归中可以一定程度上简化时间，但在有数据存储的dp中就大可不必了。

class Solution:def isMatch(self, s: str, p: str) -> bool:memo={}len1,len2=len(s),len(p)def dp(i,j):'''判断s[i:]和p[j:]的匹配情况，以下注释用s、p代替它们'''if (i,j) not in memo:#p为空：s为空时True，s不为空时Falseif j==len2 :memo[i,j]=(i==len1)#p不为空else:first=i<len1 and (p[j]==s[i] or p[j]=='.')#下一个字符为*if j+1<len2 and p[j+1]=='*':#‘*’一个都不匹配or暂时匹配一个（即匹配数量>=1）memo[i,j]=dp(i,j+2) or (first and dp(i+1,j))#下一个字符不为*else:#一个正则字符匹配一个普通字符memo[i,j]=first and dp(i+1,j+1)return memo[i,j]return dp(0,0)

11、盛最多水的容器*

题目链接

题目： 给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。

方法：双指针法*

• 指针初始位置位于两端，每次选较木板短对应的指针向内移动一格，直到左右指针相等。在过程中一直更新最大值。
• 向内收缩短板的证明：在状态 S(i, j)下向内移动短板至 S(i + 1, j)（假设 h[i] < h[j]），则相当于消去了 {S(i, j - 1), S(i, j - 2), … , S(i, i + 1)}S(i,j−1),S(i,j−2),…,S(i,i+1) 状态集合，而所有消去状态的面积一定 <= S(i, j)。因此我们每次向内移动短板，所有的消去状态都不会导致丢失面积最大值 。

class Solution:def maxArea(self, height: List[int]) -> int:Vmax,i,j=0,0,len(height)-1while i<j:minblock=min(height[i],height[j])Vmax=max(Vmax,minblock*(j-i))# 哪边短移动哪边，等长则都移动一格i+=1 if minblock==height[i] else 0j-=1 if minblock==height[j] else 0return Vmax

12、整数转罗马数字

题目链接

题目： 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

方法：贪心+DRP原则

• 使用两个数组将分别将阿拉伯数组和罗马数字一一对应着倒序储存，莫要憨憨地手动列举所有情况。
• 

class Solution:def intToRoman(self, num: int) -> str:# 使用数组存储阿拉伯数字与罗马数字，且两表均为倒序（符合贪心算法）nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]Rnums = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]index = 0res = ''while index < 13:if num >= nums[index]:res += Rnums[index]*(num//nums[index])num  = num % nums[index]index += 1return res

13、 罗马数字转整数*

题目链接

题目： 同12，只是输入输出反转
方法一：正则

• 按照题12中的对应表反推。132ms，忒慢了

方法二：哈希*

• 从左到右检测，如果当前字符代表的值不小于其右边，就加上该值；否则就减去该值。44ms

# 方法一
from re import *
class Solution:def romanToInt(self, s: str) -> int:# 使用数组存储阿拉伯数字与罗马数字，且两表均为倒序（符合贪心算法）nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]Rnums = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]index = 0res = 0while index < 13 and s != '':find = findall(r'^%s+'%Rnums[index], s)match =find[0] if find!=[] else ''lenth = len(match) / len(Rnums[index])res   += nums[index] * lenths     = s[len(match):]index += 1return int(res)
# 方法二
class Solution:def romanToInt(self, s):a = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}        ans=0        for i in range(len(s)):            if i<len(s)-1 and a[s[i]]<a[s[i+1]]:                ans-=a[s[i]]else:ans+=a[s[i]]return ans

14、最长公共前缀*

题目链接

题目： 查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。输入: [“flower”,“flow”,“flight”]，输出: “fl”
方法一：垂直扫描法

• 依次判断所有字符串的每一列是否相同。

方法二：zip()+set()函数*

• 和方法一本质相同，但是使用封装函数后，代码更简洁。

#方法一
class Solution:def longestCommonPrefix(self, strs) -> str:res=''strlen=len(strs)if strlen==0:return ''i=0while (i<len(strs[0])): #i:字符索引a=strs[0][i]for j in range(1,strlen): #j:字符串索引值if i>=len(strs[j]) or strs[j][i]!=a:return resres+=ai+=1return res
#方法二
class Solution(object):def longestCommonPrefix(self, strs):ans = ''for i in zip(*strs):if len(set(i)) == 1:ans += i[0]else:breakreturn ans        

15、三数之和

题目链接

题目： 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
方法：排序+双指针法
注意：

• 避免重复三元组出现不能使用set，因为：TypeError: unhashable type: ‘list’；不能直接使用“in”检查，时间复杂度会过高；
• 直接在算法中跳过相同的数字可以起到剪枝和避免重复的作用。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res=[]nums.sort()for i in range(len(nums)-2): #从第一个数检查到倒数第三个数if nums[i]>0: break #最小数字大于0后停止检测if i>0 and nums[i]==nums[i-1]: continue #注意：这里不要直接i+=1，因为可能有多个连续重复数字left,right=i+1,len(nums)-1while (left<right):sums=nums[i]+nums[left]+nums[right]if sums==0:newlist=[nums[i],nums[left],nums[right]]res.append(newlist) '''下面两条查重和上面一次查重，用来避免出现重复的三元组'''while (left<right and nums[left]==nums[left+1]):left+=1while (left<right and nums[right]==nums[right-1]):right-=1left+=1right-=1elif sums>0:right-=1elif sums<0:left+=1return res

16、最接近的三数之和

题目链接

题目： 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
方法：排序+双指针法

• 注意：剪枝操作略有不同，不能直接判断 nums[i] > target，还要加上 nums[i] > 0等条件。

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:       res=float('inf')nums.sort()for i in range(len(nums)-2): #从第一个数检查到倒数第三个数if res!=float('inf') and nums[i]>0 and nums[i]>target: break #最小数字大于target后停止检测if i>0 and nums[i]==nums[i-1]: continue #注意：这里不要直接i+=1，因为可能有多个连续重复数字left,right=i+1,len(nums)-1while (left<right):sums=nums[i]