LeetCode
本文最后更新于：1 年前
算法学习
Python数据类型
Number（数字）
String（字符串）
List（列表）
Tuple（元组）
Set（集合）
Dictionary（字典）
不可变数据（3 个）：数字、字符串、元组
可变数据（3 个）：列表、字典、集合
可变--->数据变化，地址不变---a=b指向同一地址，改变a，b的值也发生变化
列表
列表是写在方括号 [] 之间、用逗号分隔开的元素列表
列表可以完成大多数集合类的数据结构实现。列表中元素的类型可以不相同，它支持数字，字符串甚至可以包含列表（所谓嵌套）
列表可执行切片操作
列表可以直接赋值=，改变原值
可用+连接两个列表
list.append('') 向列表添加元素
del list[0] 删除列表元素
list.count(obj) 统计某个元素在列表中出现的次数
list.index(obj) 从列表中找出某个值第一个匹配项的索引位置
list.insert(index, obj) 将对象插入列表
list.pop([index=-1]) 移除列表中的一个元素（默认最后一个元素），并且返回该元素的值
list.remove(obj) 移除列表中某个值的第一个匹配项
list.reverse() 反向列表中元素
list.sort(cmp=None, key=None, reverse=False) 对原列表进行排序
元组
元组写在小括号 () 里，元素之间用逗号隔开
1、与字符串一样，元组的元素不能修改
2、元组也可以被索引和切片，方法一样
3、注意构造包含 0 或 1 个元素的元组的特殊语法规则
4、元组也可以使用+操作符进行拼接
集合
可以使用大括号 { } 或者 set() 函数创建集合
注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典
输出集合，重复的元素被自动去掉
set可以进行集合运算
a = set('abracadabra')
b = set('alacazam')
print(a)
print(a - b) # a 和 b 的差集
print(a | b) # a 和 b 的并集
print(a & b) # a 和 b 的交集
print(a ^ b) # a 和 b 中不同时存在的元素
字典
字典是一种映射类型，字典用 { } 标识，它是一个无序的 键(key) : 值(value) 的集合
dict = {}
dict['one'] = "111111"
dict[2] = "222222"
或
dict = {'name': 'aaa','code':111, 'site': 'www'}
列表是有序的对象集合，字典是无序的对象集合
两者之间的区别在于：字典当中的元素是通过键来存取的，而不是通过偏移存取
在同一个字典中，键(key)必须是唯一的
构造函数 dict() 可以直接从键值对序列中构建字典
dict([('a', 1), ('b', 2), ('c', 3)])
Python使用数据类型
栈 stack
栈只能在一端进行插入和删除操作，它按照先进后出(FILO)的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶
Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈
push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容
pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改
peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈
isEmpty() 测试栈是否为空。不需要参数，并返回布尔值
size() 返回栈中的 item 数量。不需要参数，并返回一个整数
使用列表实现栈
list.append(obj)---在列表末尾添加新的对象
list.pop()---移除列表最后一个元素，并返回该元素的值
list[len(list)-1]---返回列表尾部元素
Python实用函数
zip()
将可迭代的对象组合在一起
将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的对象
a1=["aaa","bbb","ccc"]
a2=["1","2","3"]
for i in zip(a1,a2):
print(i)
===>
('aaa', '1')
('bbb', '2')
('ccc', '3')
zip(*)
返回一个元组的迭代器，其中的第 i 个元组包含来自每个参数序列或可迭代对象的第 i 个元素
当所输入可迭代对象中最短的一个被耗尽时，迭代器将停止迭代
当只有一个可迭代对象参数时，它将返回一个单元组的迭代器
不带参数时，它将返回一个空迭代器
a1=["aaa","bbb","ccc"]
for i in zip(*a1):
print(i)
===>
('a', 'b', 'c')
('a', 'b', 'c')
('a', 'b', 'c')
lambda
匿名函数
s=sorted(s,key=lambda x:x[1],reverse=True)
lambda x:x[1]
lambda的主体是一个表达式，而不是一个代码块
LeetCode
1.两数之和
给一个数组，再给一个数n
从数组中选出两个数a,b相加==n
返回两个数的下标
方法：穷举法
class Solution:
def twoSum(self, nums: List[int], target: int):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
print(j)
if nums[i]+nums[j] == target:
print("[{}, {}]".format(i, j))
return [i, j]
print(nums)
return nums
7.回文数
左->右和右->左一样的数字
方法一：
按位比较
从两头处理字符，先判断数值是否相等，后判断是否到中间位置，再加上特殊情况
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0: # <0 是非回文数
return False
a = len(str(x))-1
x1 = str(x)
# print("数值为0-{}".format(a))
for i in range(0, a):
print("下标{0}---{1}".format(i, a-i))
print("数值{0}-----{1}".format(x1[i], x1[a-i]))
if x1[i] == x1[a-i]: # 判断数值是否相等
if a-i-i > 1: # 判断是否到达中间值
continue
else:
print("{}是回文数".format(x1))
return True
elif x1[i] != x1[a-i]:
print("{}不是回文数".format(x1))
return False
print("{}是回文数".format(x1))
return True # return 0-9 ---for i in range(x) [0,x)
方法二：
整体比较
字符翻转，不进行单个字符的比较
Python切片-->反序
class SolutionModify:
def isPalindrome(self, x: int) -> bool:
if str(x)[::-1] == str(x):
return True
else:
return False
13.罗马数字转整数
方法一：
取出特殊值单独计算，然后其他数依次相加
class Solution:
def romanToInt(self, s: str) -> int:
s1 = s
d = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
d1 = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
sum = 0
for i in d:
if s1.find(i) == -1:
continue
else:
s1 = s1.replace(str(i), "", 1)
sum = sum + d[i]
for i in s1:
if s1.find(i) != -1:
s1 = s1.replace(i, '', 1)
sum = sum + d1[i]
else:
continue
# print(sum)
return sum
方法二：
从[0][1]开始，取两个数做比较，如果大数在前就做sum+[0]，小数在前就做sum-[0]
class SolutionModify:
def romanToInt(self, s: str) -> int:
map = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
sum = 0
mid = s[0]
for i in range(1,len(s)):
if map[mid] >= map[s[i]]:
sum = sum + map[mid]
elif map[mid] < map[s[i]]:
sum = sum - map[mid]
mid = s[i]
sum = sum +map[mid]
return sum
14.最长公共前缀
ps:我好像在用c的逻辑去写python…太蠢了
编写一个函数来查找字符串数组中的最长公共前缀
如果不存在公共前缀，返回空字符串 “”
方法一：
纵向扫描
取出每个字符串的每个头字符进行单个比较并删除，若相等则记录，再循环比较当前第一位（实际第二位）字符
因未知字符串长度，添加越界报错...
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
length = len(strs) - 1
ret = ""
while True:
if strs[0] == "":
return ret
mid = strs[0][0]
for i in range(length + 1):
# print("字符串NO.", i)
try:
if strs[i][0] == mid:
strs[i] = strs[i].replace(strs[i][0], "", 1)
continue
else:
# print(ret)
return ret
except:
# print("+++++++", ret)
return ret
ret = ret + mid
代码改进：
def longestCommonPrefix1(self, strs: List[str]) -> str:
if len(strs) == 0:
return ""
rows, cols = len(strs), len(strs[0])
for i in range(cols):
for j in range(rows):
if len(strs[j]) == i or strs[j][i] != strs[0][i]:
return strs[0][:i]
return strs[0]
方法二：
先找出列表中最短的字符串，然后反向比较---从n到0，对每个字符串进行切片比较
若不相等，则结果为[n-1:]
for i in range 去判断最后return位置
class SolutionModify:
def longestCommonPrefix(self, strs: List[str]) -> str:
ret = ""
if "" in strs:
return ret
smallest = strs[0]
minm = len(strs[0])
for s in strs:
if len(s) < minm:
smallest = s # 取出长度最短的字符串
lth = len(smallest) - 1
for n in range(lth + 1, -1, -1):
for i in range(len(strs)):
if len(strs) == 1:
return smallest
if strs[i][:n] == smallest[:n]:
ret = smallest[:n]
elif strs[i][:n] != smallest[:n]:
break
if i == len(strs) - 1:
# print(ret)
return ret
方法三：
利用python的特性
zip(*)遍历每个字符串同下标的字符，将其组成为集合，去重，
若该集合长度为1， 则遍历下一个字符，否则return 结果
class Solution:
def longestCommonPrefix(self, strs):
res = ""
print(str(zip(*strs)))
for tmp in zip(*strs):
print("tmp-----",tmp)
tmp_set = set(tmp)
print("tmp_set-----",tmp_set)
if len(tmp_set) == 1:
res += tmp[0]
else:
break
print(res)
return res
方法四：
正序
取一个单词 s，和后面单词比较，看 s 与每个单词相同的最长前缀是多少
遍历所有单词
class Solution:
def longestCommonPrefix(self, s: List[str]) -> str:
if not s:
return ""
res = s[0]
i = 1
while i < len(s):
while s[i].find(res) != 0:
res = res[0:len(res)-1] # 给res赋值为res[0:len(res)-1]--->res从尾部去除一个字符
i += 1
return res
20. 有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效
有效字符串需满足：
左括号必须用相同类型的右括号闭合
左括号必须以正确的顺序闭合
方法一：
栈的思想---用List实现栈
先将匹配到的左括号入栈，然后当匹配到右括号时，比较栈顶元素，是否为对应的左括号
若是，则栈顶元素出栈，否---return False
最后判断栈内的元素个数是否为0
class Solution:
def isValid(self, s: str) -> bool:
map1 = {')': '(', ']': '[', '}': '{'}
ss = []
for i in s:
if i in map1.values():
ss.append(i)
if i in map1.keys():
if len(ss) == 0:
return False
if ss[len(ss)-1] == map1[i]:
ss.pop()
continue
else:
return False
return len(ss) == 0
精简--->author:z1m
class Solution:
def isValid(self, s: str) -> bool:
dic = {')':'(',']':'[','}':'{'}
stack = []
for i in s:
if stack and i in dic:
if stack[-1] == dic[i]: stack.pop()
else: return False
else: stack.append(i)
return not stack
21.合并两个有序链表
在本地跑不了…
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
方法一：
递归
从头开始，判断val，给小数的next赋值，返回小数的节点
例：
l1=[0,2]
l2=[1]
l1<l2(0<1)
l1.next=merge(2,1)--->l2--->l1
merge(2,1)
l1>l2(2>1)
l2.next=merge(2,null)--->l1
return l2
merge(2,null)
l2 is None
return l1
l1--->l2--->l1
0,1,2
# Definition for singly-linked list.
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1: return list2
if not list2: return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
方法二：
迭代
设置一个prehead，维护一个prev指针，比较l1和l2，调整prev的next指针，
如果 l1 当前节点的值小于等于 l2 ，就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位
否则，对 l2 做同样的操作。不管将哪一个元素接在了后面，都需要把 prev 向后移一位
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 if l1 is not None else l2
return prehead.next
26. 删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果
将最终结果插入 nums 的前 k 个位置后返回 k
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
方法一：
穷举...比较前后两数的大小，del 元素
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
while i < len(nums) - 1:
if i + 1 == len(nums): break
if nums[i] == nums[i + 1]:
del nums[i + 1]
i = i - 1
i = i + 1
return len(nums)
方法二：
双指针解法
一个指针 i 进行数组遍历，另外一个指针 j 指向有效数组的最后一个位置
只有当 i 所指向的值和 j 不一致（不重复），才将 i 的值添加到 j 的下一位置
即覆盖掉nums前面比较过的元素
使nums的前部分为所需数组，后部分为原来数组
返回j+1，即所需数组的长度，达到解题效果
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
j = 0
for i in range(len(nums)):
if nums[i] != nums[j]:
j+=1
nums[j]=nums[i]
return j+1
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
方法一：
穷举法
找到，删除
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
while i < len(nums):
if nums[i] == val:
del nums[i]
if i == 0: continue
else: i -= 1
i += 1
return len(nums)
方法二：
双指针解法
当没匹配到val时，保持nums[j]=nums[i],
当匹配到val，j不变，i++，跳过val所在项
所以j的值为元素的个数，即nums的有效部分的长度
def removeElement2(self, nums: List[int], val: int) -> int:
j = 0
for i in range(len(nums)):
if nums[i] != val:
nums[j] = nums[i]
j += 1
return j
28. 实现 strStr()
实现 strStr() 函数
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1
方法一：
.........
def strStr(self, haystack: str, needle: str) -> int:
if needle == "":
return 0
elif needle in haystack:
return haystack.find(needle)
else:
return -1
方法二：
暴力破解
切片法
将 字符串 needle 与字符串 haystack 的所有长度为 len(needle) 的子串均匹配一次
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
else:
for i in range(len(haystack)):
if i+len(needle) > len(haystack):break
if haystack[i:i+len(needle)] == needle:
return i
return -1
方法三：
Knuth-Morris-Pratt 算法
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
from typing import List
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
i = 0
while i < len(nums):
if nums[i] < target:
i += 1
continue
if nums[i] >= target:
return i
return len(nums)
class Solution1:
def searchInsert(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] >= target:
return i
return len(nums)
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
子数组 是数组中的一个连续部分
方法一：
从头开始相加，结果<0，则sum=0，记录最大和
纯负数情况：仅获取最大的负数，设置一个flag遍历，若没有自然数，则return最大负数
from typing import List
import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
sum1, sumLarge, flag = [0, 0, 0]
sumTiny = -sys.maxsize - 1
for i in nums:
# 遍历连续子数组，获取最大值
if sumLarge < 0:
sumLarge = 0
sumLarge = sumLarge + i
if sumLarge > sum1:
sum1 = sumLarge
# 不存在自然数的情况
if i >= 0:
flag = 1
# 获取最大的负数
if i > sumTiny and i < 0:
sumTiny = i
if flag == 1:
return sum1
else:
return sumTiny
58. 最后一个单词的长度
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串
方法一：
分割，最后一项的长度
class Solution:
def lengthOfLastWord(self, s: str) -> int:
return len(s.split()[-1])
66. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字
你可以假设除了整数 0 之外，这个整数不会以零开头
反向遍历list，找出 第一个不为 9 的元素，将其+1
若都为 9 则返回新数组
from typing import List
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
if digits[-1] == 9:
for i in range(len(digits) - 1, -1, -1):
if i == 0 and digits[i] == 9:
a = [1, ]
for j in range(len(digits)):
a.append(0)
return a
if digits[i] == 9:
digits[i] = 0
continue
else:
digits[i] += 1
break
else:
digits[-1] += 1
return digits
a = Solution()
b = [8, 9, 9, 9]
a.plusOne(b)
简便写法：
反向遍历，判断当前值是否为 9 ，是则0，否+1 return
（这样就不用对 全为9 的情况再进行具体编码）
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits) - 1, -1, -1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
a = [0] * len(digits)
a.insert(0, 1)
return a
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！