1. 两数之和
1.暴力搜索
1
2
3
4
5
6
7
8
9
10
11
|
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
return i,j
|
2.哈希表
理论基础 （摘自https://www.programmercarl.com/）
首先什么是 哈希表，哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。
1
2
3
4
5
6
7
8
|
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
|
2. 两数相加
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
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
new_node = ListNode(0)
new_node_bak = new_node
carr = 0
tmp_val1 ,tmp_val2 = 0,0
while(l1 or l2):
tmp_val1 = l1.val if l1 else 0
tmp_val2 = l2.val if l2 else 0
tmp_val = tmp_val1 + tmp_val2 + carr
new_node.val = tmp_val % 10
carr = tmp_val // 10
l1 = l1.next if l1 else 0
l2 = l2.next if l2 else 0
if carr:
new_node.next = ListNode(carr)
# 如果没有进位 判断next是否有值如果有值就创建节点 ,没有就什么也不干
elif l1 or l2:
new_node.next = ListNode(0)
new_node = new_node.next
return new_node_bak
|
递归解法
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
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 如果l1不存在返回l2,如果l2不存在返回l1
if not l1:
return l2
if not l2:
return l1
# 将l2 和l1相加
l1.val += l2.val
# 判断和是否大于等于10
if l1.val >= 10:
# 如果大于等于10 则将进位和v1.next进行相加，然后正常进行相加
l1.next = self.addTwoNumbers(ListNode(l1.val // 10),l1.next)
# 将当前位置的值改为个位
l1.val = l1.val % 10
# 如果不大于十则进行正常的相加
l1.next = self.addTwoNumbers(l1.next,l2.next)
return l1
|
3. 无重复字符
建立一个哈希表 然后采用双指针的方法来去除重复字符，最后得到最大长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 建立一个集合
s1 = set()
# 记录当前长度
now_len = 0
# 记录最大长度
max_len = 0
# 记录左指针index
j = 0
for i in range(len(s)):
now_len += 1
# 如果碰到了相同的字符 则移除左指针指向的内容知道没有相同的字符
while s[i] in s1:
s1.remove(s[j])
j += 1
now_len -= 1
if now_len > max_len: max_len = now_len
s1.add(s[i])
return max_len
|
704 二分查找
注意为了防止溢出 middle需要写为left + (right - left) // 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def search(self, nums: List[int], target: int) -> int:
right = len(nums) - 1
left = 0
middle = 0
while(left <= right):
middle = left + (right - left) // 2 # (right + left) // 2
if(nums[middle] > target):
right = middle - 1
elif(nums[middle] < target):
left = middle + 1
else:
return middle
return -1
|
35. 搜索插入位置
当没有target的时候，二分法的right < target的index
例如[1,3,5]找4，最终right == 1 left == 3所以插入位置即1 + 1 == 2 即3的后面
例如[1,4,5]找2，最终right == 0 left == 1所以插入位置即 0 + 1 ==1 即1的后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
middle = 0
#找到了返回
while(left <= right):
middle = left + (right - left) // 2
if(nums[middle] > target):
right = middle - 1
elif(nums[middle] < target):
left = middle + 1
else:
return middle
# 说明没有找到
return right + 1
|
34.在排序数组中查找元素的第一个和最后一个位置
数是连续的
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
|
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def get_middle():
left = 0
right = len(nums) - 1
middle = 0
while(left <= right):
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
else:
return middle
return -1
idx = get_middle()
print(idx)
if idx == -1: return [-1,-1]
else:
left,right = idx,idx
while( left - 1 >= 0 and nums[left - 1] == target ):
left -= 1
while( right + 1 < len(nums) and nums[right + 1] == target):
right += 1
return [left,right]
|
69. x 的平方根
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
|
class Solution:
def mySqrt(self, x: int) -> int:
# nums = [m for m in range(x + 1)]
# left = 0
# right = len(nums) - 1
# middle = 0
# while(left <= right):
# middle = left + (right - left) // 2
# # print(middle)
# if nums[middle] * nums[middle] == x:
# return nums[middle]
# elif nums[middle] * nums[middle] < x:
# left = middle + 1
# else:
# right = middle - 1
# return nums[right]
left,right,middle = 0,x,0
while(left <= right):
middle = left + (right - left) // 2
if middle * middle < x:
left = middle + 1
elif middle * middle > x:
right = middle - 1
else:
return middle
return right
|
367.有效的完全平方数
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def isPerfectSquare(self, num: int) -> bool:
right,left,middle = num,0,0
while(left <= right):
middle = left + (right - left) // 2
if(middle * middle == num):
return True
elif middle * middle < num:
left = middle + 1
elif middle * middle > num:
right = middle -1
return False
|
633. 平方数之和
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def judgeSquareSum(self, c: int) -> bool:
l,r = 0,int(c ** 0.5)
add_sum = 0
while(l <= r):
add_sum = l*l + r*r
if(add_sum == c):
return True
elif (add_sum > c):
r -= 1
else:
l += 1
return False
|
27. 移除元素
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
fast_index,slow_index = 0,0
for fast_index in range(len(nums)):
if(nums[fast_index] != val):
nums[slow_index] = nums[fast_index]
slow_index += 1
return slow_index
|
26. 删除有序数组中的重复项
1
2
3
4
5
6
7
8
9
|
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
fastIndex,slowIndex = 0,0
for fastIndex in range(len(nums)):
if(nums[fastIndex] != nums[slowIndex]):
slowIndex += 1
nums[slowIndex] = nums[fastIndex]
return slowIndex + 1
# print(nums[0:slowIndex + 1])
|
283. 移动零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
fastIndex,slowIndex = 0,0
for fastIndex in range(len(nums)):
if nums[fastIndex] != 0:
nums[slowIndex] = nums[fastIndex]
slowIndex += 1
# for i in range(len())
# print(slowIndex)
for x in range(len(nums) - slowIndex):
nums[slowIndex] = 0
slowIndex += 1
|
844. 比较含退格的字符串
双指针法 （快慢指针）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def get_list(s1:str) -> list:
fastIndex,slowIndex = 0,0
s1 = list(s1)
for fastIndex in range(len(s1)):
if s1[fastIndex] == '#' and slowIndex >= 0:
s1[slowIndex] = '\x00'
if slowIndex == 0:
slowIndex = 0
else:
slowIndex -= 1
else:
s1[slowIndex] = s1[fastIndex]
slowIndex += 1
print(slowIndex)
return s1[0:slowIndex]
s = get_list(s)
t = get_list(t)
if s == t:
return True
else:
return False
|
有序数组的平方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l,r = 0,len(nums) - 1
nums2 = [x for x in range(len(nums))]
size = len(nums) - 1
while(size >= 0):
if nums[l]*nums[l] > nums[r]*nums[r]:
nums2[size] = nums[l] * nums[l]
l += 1
else:
nums2[size] = nums[r] * nums[r]
r -= 1
size -= 1
# print(nums2)
return nums2
|
排序算法
冒泡排序
1
2
3
4
5
6
7
8
9
|
def bubbleSort(s:list):
n = len(s)
for i in range(n):
for j in range(0,n - i - 1):
if s[j] > s[j + 1]:
tmp = s[j + 1]
s[j + 1] = s[j]
s[j] = tmp
|
209. 长度最小的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
#使用滑动窗口来做
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
add_sum = 0
sub_length = float("inf") #定义一个无限大的数
j = 0
for i in range(len(nums)):
add_sum += nums[i]
while add_sum >= target:
sub_length = min(i - j + 1,sub_length) #符合条件 每次取最小值
add_sum -= nums[j]
j += 1
return 0 if sub_length == float("inf") else sub_length
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
#使用滑动窗口来做
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
add_sum = 0
sub_length = float("inf") #定义一个无限大的数
j = 0
for i in range(len(nums)):
add_sum += nums[i]
while add_sum - nums[j] >= target:
add_sum -= nums[j]
j += 1
if j > 0:
sub_length = min(i - j + 1,sub_length) #每次取最小值
elif add_sum >= target:
sub_length = min(i - j + 1,sub_length)
elif j == 0 and sub_length == float("inf"):
sub_length = float("inf")
print(i,j,sub_length)
if sub_length == float("inf"):
return 0
else:
return sub_length
# print(sub_length)
|
904. 水果成篮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
# 定义一个Counter
j = 0
m = 0
c = Counter()
for i in range(len(fruits)):
c[fruits[i]] += 1
while(len(c) > 2): #不符合条件
c[fruits[j]] -= 1
if c[fruits[j]] == 0:
c.pop(fruits[j])
j += 1
m = max(m,i - j + 1) #符合条件之后取最大值
return m
|
3. 无重复字符的最长子串
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
s1 = set() #建立一个集合 哈希表函数有Counter: 用来计数的 还有dict
s = list(s)
j = 0
max_length = 0
for i in range(len(s)):
while s[i] in s1:
s1.remove(s[j])
j += 1
s1.add(s[i])
max_length = max(max_length,i - j + 1)
return max_length
|
203. 移除链表元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(next = head)
cur = dummy
while(cur.next):
if(cur.next.val == val):
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
|
4. 寻找两个正序数组的中位数
/x返回小数，//x返回整数
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
|
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
size1 = len(nums1)
size2 = len(nums2)
size = size1 + size2
nums = [x for x in range(size)]
for i in range(size1):
nums[i] = nums1[i]
for i in range(len(nums1),size):
nums[i] = nums2[i - size1]
# print(nums)
# 冒泡排序
tmp_num = 0
for i in range(size):
for j in range(size - i - 1):
if nums[j] > nums[j + 1]:
tmp_num = nums[j + 1]
nums[j + 1] = nums[j]
nums[j] = tmp_num
# print(nums,size)
if size % 2 != 0:
return float(nums[(size - 1) // 2])
else:
# num:float = (float(nums[size // 2]) + float(nums[size // 2 - 1]))
# print(num / 2)
return (float(nums[size // 2]) + float(nums[size // 2 - 1])) / 2
|
206. 反转链表
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while(cur != None):
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
|
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(cur: Optional[ListNode],pre: Optional[ListNode]):
# 结束标志
if(cur == None):
return pre
# 实际调用的方法
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
# 递归
return reverse(cur,pre)
return reverse(head,None)
|
递归2
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
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
i = 0
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(cur: Optional[ListNode]):
if not cur:
return None
next_note = reverse(cur.next)
# 如果是尾节点
if next_note == None:
self.i = cur
return cur
# 如果是初节点，则将初节点的值赋值为None
if head == cur:
cur.next = None
next_note.next = cur
return self.i
# 如果是中间节点
else:
next_note.next = cur
return cur
return reverse(head)
|
707. 设计链表
单向链表
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
class Node(object):
def __init__(self,x):
self.val = x
self.next = None
class MyLinkedList:
def __init__(self):
self.head = Node(0)
self.size = 0
def get(self, index: int) -> int:
head = self.head
if index <= self.size - 1:
while(index):
head = head.next
index -= 1
return head.val
else:
return -1
def addAtHead(self, val: int) -> None:
dummy = Node(val)
dummy.next = self.head
self.head = dummy
self.size += 1
def addAtTail(self, val: int) -> None:
head = self.head
size = self.size
# pre = head
if size:
while(size):
pre = head
head = head.next
size -= 1
pre.next = Node(val)
self.size += 1
else:
self.addAtHead(val)
def addAtIndex(self, index: int, val: int) -> None:
if index <= 0:
self.addAtHead(val)
elif index == self.size:
self.addAtTail(val)
elif index < self.size:
head = self.head
while(index):
pre = head
head = head.next
index -= 1
pre.next = Node(val)
pre.next.next = head
self.size += 1
else:
return 0
def deleteAtIndex(self, index: int) -> None:
if index > 0 and index <= self.size - 1:
head = self.head
while(index):
pre = head
head = head.next
index -= 1
pre.next = head.next
self.size -= 1
elif index == 0:
head = self.head
self.head = head.next
self.size -= 1
else:
return -1
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
|
19. 删除链表的倒数第 N 个结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
size = 0
dummy = head
while head:
head = head.next
size += 1
head = dummy
if size - n < 0:
return None
elif size == n:
head = head.next
return head
else:
for i in range(size - n - 1):
head = head.next
# print(head.val)
head.next = head.next.next
return dummy
|
快慢指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
fast = head
slow = head
# dummy = ListNode(next = head)
for i in range(n):
fast = fast.next
if fast:
while(fast.next):
fast = fast.next
slow = slow.next
slow.next = slow.next.next
else:
head = head.next
return head
|
242. 有效的字母异位词
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
x = Counter()
for i in s:
x[i] += 1
for i in t:
x[i] -= 1
for j in x:
if x[j] != 0:
return False
return True
|
349. 两个数组的交集
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
s = Counter()
m = []
for x in nums1:
s[x] = 1
for j in nums2:
if j in s and s[j] == 1:
m.append(j)
s[j] = 0
print(m)
return m
|
1. 两数之和
1
2
3
4
5
6
7
8
9
|
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
c = Counter()
for i in range(len(nums)):
if target - nums[i] in c:
return [c[target - nums[i]],i]
else:
c[nums[i]] = i
print("Not Found")
|
454. 四数相加 II
加法结合律，转化为两数相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
c = Counter()
# 四数相加转化为两数下相加
for n1 in nums1:
for n2 in nums2:
if n1 + n2 in c:
c[n1 + n2] += 1
else:
c[n1 + n2] = 1
counter = 0
for n3 in nums3:
for n4 in nums4:
if -(n3 + n4) in c:
counter += c[-n3 - n4]
print(counter)
return counter
|
383. 赎金信
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# 定义一个哈希表
c = Counter()
# 初始化
for n1 in magazine:
c[n1] += 1
#判断哈希表内是否存在，如果存在并且index大于等于1则进行减一，如果不存在则说明字符串里面不包含不满足条件
for n2 in ransomNote:
if n2 in c and c[n2] >= 1:
c[n2] -= 1
else:
return False
print(c)
return True
|
15. 三数之和
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
|
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums,reverse = False) #升序
dummy = []
size = len(nums)
for i in range(len(nums)):
if nums[i] > 0: #如果该数大于0 则表明后续没有没有任何两个数和当前数和为0
break
if i >= 1: #判断是否和上个数字重复，如果重复则继续
if nums[i] == nums[i - 1]:
continue
#三指针
l = i + 1
r = size - 1
while(l < r):
add_sum = nums[i] + nums[l] + nums[r]
if(add_sum == 0):
dummy.append([nums[i],nums[l],nums[r]])
while l < r and nums[l] == nums[l + 1]: #去重
l += 1
while l < r and nums[r] == nums[r - 1]: #去重
r -= 1
l += 1
r -= 1
#指针移动
elif(add_sum < 0):
l += 1
elif(add_sum > 0):
r -= 1
print(dummy)
return dummy
|
344. 反转字符串
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
l = 0
r = len(s) - 1
while(l <= r):
s[l],s[r] = s[r],s[l]
l += 1
r -= 1
print(s)
|
18. 四数之和
和三数之和类似，加一个for循环
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
|
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
size = len(nums)
nums = sorted(nums)#升序排序
# print(nums)
ans = []
for i in range(size):
if i > 0 and nums[i] == nums[i - 1]: continue # 去重
# if nums[i] > target: return ans
for m in range(i + 1,size):
if m > i + 1 and nums[m] == nums[m - 1]: continue #如果当前字符和上一个字符相同则继续,即去重
l = m + 1
r = size - 1
while(l < r): #双指针
sum = nums[l] + nums[r] + nums[i] + nums[m]
if(sum == target):
ans.append([nums[i],nums[m],nums[l],nums[r]])
while(l < r) and nums[l] == nums[l + 1]: l += 1
while(l < r) and nums[r] == nums[r - 1]: r -= 1
l += 1
r -= 1
elif sum < target:
l += 1
elif sum > target:
r -= 1
print(ans)
return ans
|
剑指 Offer 05. 替换空格
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
|
class Solution:
def replaceSpace(self, s: str) -> str:
s = list(s)
n = len(s)
# counter = 0
# for i in s:
# if i == ' ':
# counter += 1
#计算空格数
counter = s.count(' ')
#扩展
s.extend([' '] * counter * 2)
m = len(s)
# 双指针 一个指向原来的字符串的末尾,一个指向扩展后的字符串的末尾
l = n - 1
r = m - 1
while(l >= 0):
if (s[l] != ' '):
s[r] = s[l]
r -= 1
l -= 1
else:
s[r - 2 : r + 1] = "%20"
r -= 3
l -= 1
return ''.join(s) #转换为字符串的形式
|
151. 反转字符串中的单词
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
|
class Solution:
def reverseWords(self, s: str) -> str:
# 去除多余空格
flags = 0
s = list(s)
ans = []
l,r = 0,len(s) - 1
# 使用双指针法,移除开头空格
while(s[l] == ' '): l += 1
## 移除末尾空格
while(s[r] == ' '): r -= 1
## 移除中间空格
while(l <= r):
if(s[l] != ' '):
ans.append(s[l])
l += 1
elif(s[l] == ' ' and s[l - 1] != ' '):
ans.append(s[l])
l += 1
else:
l += 1
print(ans)
# 翻转整个字符串
l = 0
r = len(ans) - 1
while(l < r):
ans[l],ans[r] = ans[r],ans[l]
l += 1
r -= 1
print(ans)
# 在末尾扩展一个空格
ans.extend([' '])
# 单词反转
l = 0
n = len(ans)
for tmp_r in range(n):
if(ans[tmp_r] == ' '):
r = tmp_r - 1
# print(r)
while(l < r):
ans[l],ans[r] = ans[r],ans[l]
l += 1
r -= 1
l = tmp_r + 1
ans = ans[:-1]
# print(ans)
return ''.join(ans)
|
28. 找出字符串中第一个匹配项的下标
常规解法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
size_haystack = len(haystack)
size = len(needle)
# x = []
if haystack == needle:
# 如果两个字符串是相同的则直接返回0
return 0
for i in range(size_haystack):
# 匹配
if(haystack[i:i + size] == needle):
return i
return -1
|
KMP解法
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
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
haystack_len = len(haystack)
needle_len = len(needle)
k = -1
# 初始化prefix数组
prefix = [-1 for x in range(needle_len)]
# 生成next数组
for i in range(1,needle_len):
while k > -1 and needle[k + 1] != needle[i]:
k = prefix[k]
prefix[i] = k
if needle[k + 1] == needle[i]:
k += 1
prefix[i] = k
k = -1
for i in range(haystack_len):
# 遇到不符合的字符串进行回退操作
while(k > -1 and needle[k + 1] != haystack[i]):
k = prefix[k]
if needle[k + 1] == haystack[i]:
k += 1
# print(i,k)
if k == needle_len - 1:
# print(k,needle_len)
return i - k
return -1
|
459. 重复的子字符串
KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
s = list(s)
# 初始化prefix数组
prefix = [-1 for x in range(len(s))]
# print(prefix)
k = -1
# 生成prefix数组
for i in range(1,len(s)):
while k > -1 and s[k + 1] != s[i]:
k = prefix[k]
print(i,k)
prefix[i] = k
if s[k + 1] == s[i]:
k += 1
prefix[i] = k
print(prefix)
# 如果prefix[-1]不等于说明存在相同的前后缀并且字符串长度可以被（字符串长度 - 最长相等前后缀长度）整除则说明是重复字符组成
#数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环
if prefix[-1] != -1 and len(s) % (len(s) - (prefix[-1] + 1)) == 0:
return True
return False
# print(prefix)
|
232. 用栈实现队列
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
|
class MyQueue:
def __init__(self):
self.array = []
def push(self, x: int) -> None:
self.array.append(x)
return self.array
def pop(self) -> int:
x = self.array[0]
self.array.pop(0)
return x
def peek(self) -> int:
return self.array[0]
def empty(self) -> bool:
if self.array:
return False
else:
return True
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
|
225. 用队列实现栈
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
|
class MyStack:
def __init__(self):
self.array = []
def push(self, x: int) -> None:
self.array.append(x)
return self.array
def pop(self) -> int:
x = self.array[-1]
self.array.pop(-1)
return x
def top(self) -> int:
return self.array[-1]
def empty(self) -> bool:
if self.array:
return False
else:
return True
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
|
1047. 删除字符串中的所有相邻重复项
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def removeDuplicates(self, s: str) -> str:
# 消消乐
# s = list(s)
ans = []
for i in range(len(s)):
if ans and s[i] == ans[-1]:
ans.pop(-1)
else:
ans.append(s[i])
# print(ans)
return ''.join(ans)
|
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def removeDuplicates(self, s: str) -> str:
# 双指针
s = list(s)
fast = slow = 0
while(fast < len(s)):
# 相同则后退
if slow > 0 and s[slow] == s[slow - 1]:
slow -= 1
fast += 1
s[slow] = s[fast]
# 不同直接赋值
else:
s[slow] = s[fast]
slow += 1
fast += 1
return ''.join(s[0:slow])
|
150. 逆波兰表达式求值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
ans = []
for i in tokens:
if i == '+' or i == '-' or i == '*' or i == '/' and len(ans) >= 2:
x1 = ans.pop(-2)
x2 = ans.pop(-1)
x3 = eval(f'{x1} {i} {x2}')
ans.append(int(x3))
# print(ans)
else:
ans.append(i)
# print(ans)
return int(ans[0])
|
239. 滑动窗口最大值
单调栈，栈里面的值都是单调递增或者递减
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
size = len(nums)
d = deque()
ans = []
for i in range(k):
while d and nums[i] >= nums[d[-1]]:
d.pop()
d.append(i)
ans.append(nums[d[0]])
for i in range(k,size):
while d and nums[i] >= nums[d[-1]]:
d.pop()
d.append(i)
while d and d[0] <= i - k:
d.popleft()
ans.append(nums[d[0]])
# print(ans)
return ans
|
347. 前 K 个高频元素
小顶堆的初利用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
s = {}
for i in range(len(nums)):
s[nums[i]] = s.get(nums[i],0) + 1
d = []
for num,value in s.items():
heappush(d,(value,num))
if len(d) > k:
heappop(d) # pop出来的是最小的也就是顶部的值
result = [0] * k
# pop的时候是从小到大pop，因此需要倒序一下，即从大大小输出
for i in range(-1,k - 1,1):
result[i] = heappop(d)[1]
return result
|
77. 组合
回溯算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
# 回溯算法
path = []
res = []
def dfs(n,k,startIdx):
# 结束标志
if len(path) == k:
res.append(path[:])# 添加path副本
return
for i in range(startIdx,n + 1):
path.append(i)
dfs(n,k,i + 1)
path.pop() #回溯
dfs(n,k,1)
return res
|
剪枝优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
# 回溯算法
path = []
res = []
def dfs(n,k,startIdx):
# 结束标志
if len(path) == k:
res.append(path[:])# 添加path副本
return
lastIdx = n - (k - len(path)) + 2
for i in range(startIdx,lastIdx):
path.append(i)
dfs(n,k,i + 1)
# print(path)
path.pop()
dfs(n,k,1)
# print(res)
return res
|
组合总和 III
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution:
def __init__(self):
self.res = []
self.path = []
self.sum = 0
def dfs(self,k,n,startIdx):
if self.sum > n: #剪枝
return
if len(self.path) == k:
if self.sum == n:
self.res.append(self.path[:])
return
for i in range(startIdx,10):
self.sum += i
self.path.append(i)
self.dfs(k,n,i + 1)
self.path.pop()
self.sum -= i
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.dfs(k,n,1)
print(self.res)
return self.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
|
class Solution:
def __init__(self):
self.phoneNumMaps = {
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz'
}
self.ans = []
self.answer = []
def letterCombinations(self, digits: str) -> List[str]:
if len(digits) == 0:
return []
self.dfs(digits,0)
return self.ans
def dfs(self,digits,idx):
if idx == len(digits):
self.ans.append(''.join(self.answer[:]))
return
m = self.phoneNumMaps[digits[idx]]
for x in m:
self.answer.append(x)
self.dfs(digits,idx + 1)
self.answer.pop()
|
组合总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def __init__(self):
self.ans = []
self.sum = 0
self.answer = []
def dfs(self,candidates: List[int], target: int):
if self.sum > target:
return
if self.sum == target:
answer = sorted(self.answer)
if answer not in self.ans:
self.ans.append(answer)
return
for i in candidates:
self.sum += i
self.answer.append(i)
self.dfs(candidates,target)
self.answer.pop()
self.sum -= i
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.dfs(candidates,target)
return self.ans
|
组合总和 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution:
def __init__(self):
self.sum = 0
self.ans = []
self.answer = []
def dfs(self,candidates: List[int], target: int,startIdx):
if self.sum > target:
return
if self.sum == target and self.answer not in self.ans:
print(self.answer)
self.ans.append(self.answer[:])
return
for i in range(startIdx,len(candidates)):
if i > startIdx and candidates[i] == candidates[i - 1]: #对同一层去重，如果startIdx > 0的话就是对所有行去重
continue
self.sum += candidates[i]
self.answer.append(candidates[i])
self.dfs(candidates,target,i + 1)
self.answer.pop()
self.sum -= candidates[i]
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates = sorted(candidates)
self.dfs(candidates,target,0)
return self.ans
|
复原 IP 地址
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
|
class Solution:
def __init__(self):
self.ans = []
def dfs(self,s: str,startIdx: int,pointNum: int):
if pointNum == 3:
if self.is_valid(s,startIdx,len(s) - 1):
self.ans.append(s[:])
return
for i in range(startIdx,len(s)):
if self.is_valid(s,startIdx,i):
s = s[:i + 1] + '.' + s[i + 1:]
self.dfs(s,i + 2,pointNum + 1)
s = s[:i + 1] + s[i + 2:]
else:
break
def is_valid(self,s: str,startIdx,endIdx):
if startIdx > endIdx : return False
if s[startIdx] == '0' and startIdx != endIdx:
# print(f"startIdx: {startIdx} endIdx: {endIdx} ")
return False
if 0 <= int(s[startIdx:endIdx + 1]) <= 255:
return True
else:
return False
def restoreIpAddresses(self, s: str) -> List[str]:
try:
self.dfs(s,0,0)
print(self.ans)
return self.ans
except Exception as e:
print(e)
return self.ans
|
子集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def __init__(self):
self.ans = []
self.result = []
def dfs(self,nums,start):
self.result.append(self.ans[:])
if start == len(nums):
return
for i in range(start,len(nums)):
self.ans.append(nums[i])
self.dfs(nums,i + 1)
self.ans.pop()
def subsets(self, nums: List[int]) -> List[List[int]]:
self.dfs(nums,0)
return self.result
|
子集 II
排列一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def __init__(self):
self.ans = []
self.result = []
def dfs(self,nums,start):
# if self.ans not in self.result:
# self.result.append(self.ans[:])
ans = sorted(self.ans[:])
if ans not in self.result:
self.result.append(ans)
# print(start)
if start == len(nums): return
for i in range(start,len(nums)):
self.ans.append(nums[i])
self.dfs(nums,i + 1)
self.ans.pop()
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
self.dfs(nums,0)
print(self.result)
return self.result
|
去重版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def __init__(self):
self.ans = []
self.result = []
def dfs(self,nums,start):
if self.ans not in self.result:
self.result.append(self.ans[:])
if start == len(nums): return
for i in range(start,len(nums)):
if i > start and nums[i] == nums[i - 1]: #去重
continue
self.ans.append(nums[i])
self.dfs(nums,i + 1)
self.ans.pop()
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
self.dfs(nums,0)
print(self.result)
return self.result
|
递增子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def __init__(self):
self.ans = []
self.result = []
def dfs(self,nums,start):
ans = sorted(self.ans)
if ans != self.ans:
pass
elif ans == self.ans and ans not in self.result and len(ans) > 1:
self.result.append(ans)
if start == len(nums):
return
for i in range(start,len(nums)):
if i > start and nums[i] == nums[i - 1]: continue
self.ans.append(nums[i])
self.dfs(nums,i + 1)
self.ans.pop()
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
self.dfs(nums,0)
print(self.result)
return self.result
|
全排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def __init__(self):
self.ans = []
self.result = []
self.tmp = 0
def dfs(self,nums,flags):
if flags == len(nums):
if self.ans not in self.result:
self.result.append(self.ans[:])
return
for i in range(len(nums)):
if nums[i] in self.ans:
continue
self.tmp = nums[i]
self.ans.append(nums[i])
self.dfs(nums,flags + 1)
self.ans.pop()
def permute(self, nums: List[int]) -> List[List[int]]:
self.dfs(nums,0)
print(self.result)
return self.result
|
全排列 II
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
|
class Solution:
def __init__(self):
self.ans = []
self.result = []
self.used = 0
def dfs(self,nums,flags):
if len(self.ans) == len(nums) and self.ans not in self.result:
self.result.append(self.ans[:])
if flags == len(nums):
return
for i in range(len(nums)):
if not self.used[i]: #保证在不同层里面不出现相同的数字
if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]: #在同一层里面进行去重
print(self.used[i - 1])
continue #剪枝
self.used[i] = 1
self.ans.append(nums[i])
self.dfs(nums,flags + 1)
self.ans.pop()
self.used[i] = 0
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.used = [0] * len(nums)
self.dfs(nums,0)
# print(self.s)
return self.result
|
贪心算法初尝试 - 分发饼干
局部最优到整体最优
1
2
3
4
5
6
7
8
9
|
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g = sorted(g)
s = sorted(s)
res = 0
for i in range(len(s)):
if res < len(g) and s[i] >= g[res]:
res += 1
return res
|
贪心算法二 - 最大子数组和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def getSum(self,nums,start,end):
add_sum = 0
for i in range(start,end):
add_sum += nums[i]
return add_sum
def maxSubArray(self, nums: List[int]) -> int:
ans = 0
result = -float("inf") #定义一个最小值
for i in range(len(nums)):
ans += nums[i]
if ans > result:
result = ans
elif ans <= 0:
ans = 0
print(result)
return result
|
摆动序列
1
2
3
4
5
6
7
8
9
|
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
prev,cur,res = 0,0,1
for i in range(len(nums) - 1):
cur = nums[i + 1] - nums[i]
if cur * prev <= 0 and cur != 0: #如果两个差值小于等于0，则说明是摆动，如果cur等于0则说明是平的
res += 1
prev = cur
return res
|
买卖股票的最佳时机 II
贪心算法，只收集正利润
1
2
3
4
5
6
7
|
class Solution:
def maxProfit(self, prices: List[int]) -> int:
result = 0
for i in range(len(prices) - 1):
tmp_value = max(prices[i + 1] - prices[i],0)
result += tmp_value
return result
|
跳跃游戏
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def canJump(self, nums: List[int]) -> bool:
size = len(nums)
if len(nums) == 1: return True
ans = 0
for i in range(len(nums) - 1):
if i <= ans:#下一步可以跳到
ans = max(ans,i + nums[i])
if ans >= len(nums) - 1:
return True
return False
|
跳跃游戏Ⅱ
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def jump(self, nums: List[int]) -> int:
ans = 0
max_num = 0
end = 0
for i in range(len(nums) - 1):#最后一个位置没有意义
max_num = max(i + nums[i],max_num) # 每次取跳跃的最大值
if i == end: #如果达到最大值，则进行下一次跳跃，跳跃的终点为下一次的最大值
end = max_num
ans += 1
return ans
|
