Leetcode刷题笔记

前言

代码能力是计算机专业学生的基础能力,求职技术方向的同学,无论是测试、开发或算法,互联网公司在这一块的考察都是重中之重。一般而言,大厂在每一轮的技术面中,至少会出一道编程题,多的会直接上三道编程题,难度主要集中在easy和medium,少数丧心病狂(褒义词)的面试官会出hard题。而考察范围已是圈内公开的秘密,就在《剑指offer》和Leetcode上,因此刷题成为了大家求职路上必须要迈过的一道坎,这个坎没有人可以帮到你,只有靠你自己。

本笔记记录自己在刷题过程中的总结

剑指Offer

[206] 反转链表

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路:
需要背诵级别的题目

代码:

1
2
3
4
5
6
7
8
9
10
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
p = head
while p:
p_next = p.next
p.next = pre
pre = p
p = p_next
return pre

[38]字符串的排列

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

1
2
输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

思路:
回溯法

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def permutation(self, s: str) -> List[str]:
result = []
visits = [False for i in range(len(s))]

def backtrace(trace):
if len(trace) == len(s):
result.append("".join(trace))

tmp_set = set()
for i in range(len(s)):
if not visits[i] and s[i] not in tmp_set:
trace.append(s[i])
visits[i] = True
tmp_set.add(s[i])
backtrace(trace)
trace.pop()
visits[i] = False
backtrace([])
return result

[42]连续子数组的最大和

输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

1
2
3
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

思想:
动态规划的问题,以num为最后一个数字的子数组

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return -1

result = nums[0]
temp_result = nums[0]

for num in nums[1:]:
# 以num为最后一个数字的子数组的最大值
if temp_result < 0:
temp_result = num
else:
temp_result += num
if temp_result > result:
result = temp_result

return result

[42]重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
1
2
3
4
5
  3
/ \
9 20
/ \
15 7

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

思路:
递归的进行调用,主要是细心

代码:

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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None

if len(preorder) == 1:
return TreeNode(preorder[0])

root_val = preorder[0]

index = inorder.index(root_val)

left_tree = self.buildTree(
preorder[1:1+index],
inorder[:index]
)

right_tree = self.buildTree(
preorder[1+index:],
inorder[index+1:]
)

root = TreeNode(root_val)
root.left = left_tree
root.right = right_tree

return root

[48]最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

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

思考:
滑动窗口的题目,直接用双端队列进行操作

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0

result = 1
q = collections.deque()
q.append(s[0])

for c in s[1:]:
while q and c in q:
q.popleft()
q.append(c)
result = max(result,len(q))

return result

[20]表述数值的字符串

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值,但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof

思考:
如果出现的字符是.,那么需要还没有.e
如果出现的字符是e/E,那么需要已经出现了数字并且没有e
如果出现的字符是+/-,那么需要位于第一位,或者之前是`e/E

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def isNumber(self, s: str) -> bool:
nums = set("0123456789")
num_flag = False
dot_flag = False
e_flag = False
s = s.strip()
for index, c in enumerate(s):
if c in nums:
num_flag = True
elif c == '.' and (not dot_flag) and (not e_flag):
dot_flag = True
elif c in 'eE' and (not e_flag) and num_flag:
e_flag = True
num_flag = False
elif c in '+-' and (index==0 or s[index-1] in 'eE'):
pass
else:
return False
return num_flag

[29]顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

思路:
确定好边界和跳出条件,这段代码需要背诵.边界收缩,增加以后,超过了什么;减少以后,更小了什么

代码:

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 spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
left,right,top,bottom = 0, len(matrix[0])-1, 0, len(matrix)-1
ret = []

while True:
# ->
for i in range(left,right+1):
ret.append(matrix[top][i])
top += 1
if top > bottom: break

# |
for i in range(top,bottom+1):
ret.append(matrix[i][right])
right -= 1
if right < left: break

# <-
for i in range(right,left-1,-1):
ret.append(matrix[bottom][i])
bottom -= 1
if bottom < top: break

# |
for i in range(bottom,top-1,-1):
ret.append(matrix[i][left])
left += 1
if left > right: break

return ret

[40]最小的k个数

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

1
2
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

思路:
排序是一个必要的操作,通过快排序可以更快的进行

代码:

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 getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if not arr or k==0:
return []
return self.quicksort(arr,0,len(arr)-1,k)

def quicksort(self,arr,l,r,k):
j = self.partition(arr,l,r)

if k == j or k == j+1:
return arr[:k]

if k < j:
return self.quicksort(arr,l,j-1,k)

if k > j:
return self.quicksort(arr,j+1,r,k)

def partition(self,arr,l,r):
pivot = arr[l]
index = l+1
for i in range(l+1,r+1):
if arr[i] < pivot:
arr[i],arr[index] = arr[index],arr[i]
index += 1
arr[l],arr[index-1] = arr[index-1],arr[l]
return index-1

[53]0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof

思想:
因为是0-n的有序序列,所以可以保证nums[i] = i, 从而可以通过二分查找快速定位。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def missingNumber(self, nums: List[int]) -> int:
i,j = 0,len(nums)-1

while i <= j:
k = (i+j) // 2
if nums[k] == k:
i+=1
else:
j-=1

return i

[60]从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

思想:
因为是反转,所以可以通过栈来实现

代码:

1
2
3
4
5
6
7
8
9
10
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if not head:
return []
stack = []
p = head
while p:
stack.append(p.val)
p = p.next
return stack[::-1]

[52]两个链表的第一个公共节点

输入两个链表,找出它们的第一个公共节点。

https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

思想:
a + c + b = b + c + a,即使没有公共节点也是满足的

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
p = headA
q = headB

while p != q:
if p:
p = p.next
else:
p = headB
if q:
q = q.next
else:
q = headA

return p

[56]数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

思路:
两个相同的数字的“异或”结果为0,所以一个数组中如果只有一个不重复的数字,那么对整个数组执行异或操作就能找到该数字。

现在有两个不同的数字,所以问题的关键是对数组进行分组操作,划分成两组,每组都只有一个不重复的数字,然后对两组分别执行整体“异或”操作。

如何划分?假设数组中不重复的两个数字为x,y,对整个数组进行异或操作的结果为ret, 即x^y=ret, 假设ret二进制表示中一定有至少1为为1,假设第i位的结果位1,那么说明xy在第i位的结果不同。那么就可以根据第i位是否为1对整个数组进行划分: xy一定分到不同的两个队列中,而剩余数字中相同的两个数字也一定划分到一个相同的队列中。

具体在操作上可以先找出ret最左侧的第一个为1的那一位,通过&操作和<<操作可以实现,再根据那一位对整个数组进行&操作进行划分。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from functools import reduce

class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret = reduce(lambda x,y:x^y, nums)
div = 1
while div & ret == 0:
div <<= 1
# 0与任何数的异或结果为这个数本身
a,b = 0,0
for num in nums:
if num & div == 0:
a ^= num
else:
# 此时 num & div = div
b ^= num
return [a,b]

[26]树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如: 给定的树 A:

1
2
3
4
5
     3
    / \
   4   5
  / \
 1   2

给定的树 B:

1
2
3
   4 
  /
 1

返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

思路:
B是A的子结构的三种情况:
(1)节点A为根节点的子树包含B
(2)B是A的左子树的子结构
(3)B是A的右子树的子结构

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not B:
return False
if not A:
return False
return self.recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

def recur(self, A: TreeNode, B: TreeNode) -> bool:
# 注意一定是先判断B的情况
if not B:
return True
if not A:
return False
if A.val != B.val:
return False
return self.recur(A.left,B.left) and self.recur(A.right,B.right)

[62]圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。

例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

思路:
这是典型的约瑟夫环问题,有几种做题的方法
(1) 模拟:构建一个list,模拟整个操作
(2) 递归:第一个去除的元素是m%n-1,那么剩下n-1个元素,假设最后剩下的元素为k,那么对于原始的n个元素最后剩下的就是(m%n + k) % k,也就是从m%n开始数k个。
(3) 迭代:对于递归进行优化,也就是正过来计算

代码:
模拟

1
2
3
4
5
6
7
8
9
10
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
circle = list(range(n))
current_index = 0
while True:
remove_index = (current_index + m - 1) % len(circle)
circle.pop(remove_index)
current_index = remove_index
if len(circle) == 1:
return circle[0]

递归

1
2
3
4
5
6
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
if n == 1:
return 0
last_remain = self.lastRemaining(n-1,m)
return (m%n + last_remain) % n

迭代

1
2
3
4
5
6
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
last_remain = 0
for i in range(2,n+1):
last_remain = (m%i + last_remain ) %i
return last_remain

[59]滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

1
2
3
4
5
6
7
8
  滑动窗口的位置                最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

思路:
窗口对应的数据结构为双端队列,本题需要使用一个单调的队列:

  1. 队列中的元素均来自窗口,所以窗口滑动,需要将队列中对应的元素一起移除
  2. 队列保持单调,非严格递减,所以窗口滑动新增元素的时候,需要将比新增元素小的元素一并删除

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k == 0: return []
q = collections.deque()
for i in range(k):
while q and q[-1] < nums[i]:
q.pop()
q.append(nums[i])
ret = [q[0]]
for i in range(k,len(nums)):
if q[0] == nums[i-k]:
q.popleft()
while q and q[-1] < nums[i]:
q.pop()
q.append(nums[i])
ret.append(q[0])
return ret

[14]剪绳子

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/submissions/

思路:
动态规划,dp[n]为长度为n绳子的最好结果,那么对于长度为m的绳子,先剪开一刀j,那么就是对比max( (m-j) * j ,dp[m-j] * j )的大小,也就是剩下的部分要不要继续再切分了

代码:

1
2
3
4
5
6
7
8
class Solution:
def cuttingRope(self, n: int) -> int:
dp = [0] * (n+1)
dp[2] = 1
for i in range(3,n+1):
for j in range(1, (i+1)//2 + 1):
dp[i] = max(dp[i], max(j * (i-j),dp[i-j] * j))
return dp[n]

[32]从上到下打印二叉树

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回:

1
[3,9,20,15,7]

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof

思路:
本质是对树的BFS,所以基于队列实现

代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
ret,q = [],collections.deque()
q.append(root)
while q:
node = q.popleft()
ret.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return ret

[68] 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof

思路:
先通过DFS遍历整个树,记录一下每个节点的父节点

代码:

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) -> None:
self.parent_map = {}

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
self.dfs(root)
self.parent_map[root] = None
self.p_path = set()
while p:
self.p_path.add(p)
p = self.parent_map[p]
while q:
if q in self.p_path:
return q
q = self.parent_map[q]
return None


def dfs(self,root):
if root.left:
self.parent_map[root.left] = root
self.dfs(root.left)
if root.right:
self.parent_map[root.right] = root
self.dfs(root.right)

[49]丑数

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
示例:

1
2
3
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

链接:https://leetcode-cn.com/problems/chou-shu-lcof

思路:
动态规划,dp[n] = min(dp[a]*2,dp[b]*3,dp[c]*5),

同时:
dp[a-1]*2 <= dp[n-1] < dp[a]*2;
dp[b-1]*3 <= dp[n-1] < dp[b]*3;
dp[c-1]*5 <= dp[n-1] < dp[c]*5;

代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def nthUglyNumber(self, n: int) -> int:
# dp[n] = min(dp[a]*2,dp[b]*3,dp[c]*5)
dp,a,b,c = [1]*n,0,0,0
for i in range(1,n):
n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5
print(n2,n3,n5)
dp[i] = min(n2,n3,n5)
if dp[i] == n2: a += 1
if dp[i] == n3: b += 1
if dp[i] == n5: c += 1
return dp[-1]

[54]二叉搜索树的第k大节点

给定一棵二叉搜索树,请找出其中第k大的节点。

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

思路:
遍历二叉数:右子树 -> 根节点 -> 左子树
注意减枝

代码:

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) -> None:
self.result = []

def kthLargest(self, root: TreeNode, k: int) -> int:
self.k = k
self.dfs(root)
return self.result[k-1]


def dfs(self,root):
if not root:
return
self.dfs(root.right)
if len(self.result) >= self.k:
return
self.result.append(root.val)
if len(self.result) >= self.k:
return
self.dfs(root.left)

[35]复杂链表的复制

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

思路:
通过一个字典来保存老节点与新节点的映射关系

代码:

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 copyRandomList(self, head: 'Node') -> 'Node':
d = {}

def getClonedNode(node):
if not node:
return None
if node not in d:
d[node] = Node(node.val)
return d[node]

oldNode = head
newNode = getClonedNode(head)
ret = newNode

while oldNode:
newNode.next = getClonedNode(oldNode.next)
newNode.random = getClonedNode(oldNode.random)
oldNode = oldNode.next
newNode = newNode.next

return ret

[34]二叉树中和为某一值的路径

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树,以及目标和 target = 22,

1
2
3
4
5
6
7
      5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

返回:

1
2
3
4
[
[5,4,11,2],
[5,8,4,5]
]

https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

思路:
典型的DFS的遍历,当然也可以BFS

代码:
DFS

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 pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
def recur(node,tar):
if node.left == None and node.right == None and tar == 0:
ret.append(path[:])
if node.left:
# 尝试向左走一步
path.append(node.left.val)
recur(node.left,tar-node.left.val)
path.pop()
if node.right:
# 尝试向右走一步
path.append(node.right.val)
recur(node.right,tar-node.right.val)
path.pop()

if not root:
return []

ret = []
path = [root.val]
recur(root,target-root.val)

return ret

BFS

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

def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
ret = []
q = collections.deque()
if not root:
return ret
q.append((root, [root.val]))
while q:
node, current_path = q.popleft()
if node.left is None and node.right is None and sum(current_path) == target:
ret.append(current_path[:])
if node.left:
path = current_path[:]
path.append(node.left.val)
q.append((node.left, path))
if node.right:
path = current_path[:]
path.append(node.right.val)
q.append((node.right, path))
return ret

[47]礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

1
2
3
4
5
6
7
8
输入: 
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof

思路:
通过动态规划求解,否则会超时

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
if not grid:
return 0
m = len(grid)
n = len(grid[0])
dp = [[0] * n]*m
for i in range(m):
for j in range(n):
if i-1<0:
upper = 0
else:
upper = dp[i-1][j]
if j-1<0:
left = 0
else:
left = dp[i][j-1]
dp[i][j] = grid[i][j] + max(left,upper)
return dp[m-1][n-1]

[59] 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空,pop_front 和 max_value 需要返回 -1

https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof

思路:
额外维护一个双端队列,保持单调不递增;类比第59题

代码:

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
import queue

class MaxQueue:


def __init__(self):
self.max_value_queue = collections.deque()
self.normal_queue = queue.Queue()


def max_value(self) -> int:
if not self.max_value_queue:
return -1
return self.max_value_queue[0]

def push_back(self, value: int) -> None:
while self.max_value_queue and self.max_value_queue[-1] < value:
self.max_value_queue.pop()

self.normal_queue.put(value)
self.max_value_queue.append(value)


def pop_front(self) -> int:
if not self.max_value_queue:
return -1
fron_value = self.normal_queue.get()
if fron_value == self.max_value_queue[0]:
self.max_value_queue.popleft()
return fron_value

[66]构建乘积数组

给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

1
2
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof

思路:
构建上下三角形的举证,通过两轮循环来实现

代码:

1
2
3
4
5
6
7
8
9
10
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
B = [1] * len(a)
for i in range(1,len(a)):
B[i] = B[i-1] * a[i-1]
temp = 1
for i in list(range(len(a)-1))[::-1]:
temp = temp * a[i+1]
B[i] = B[i] * temp
return B

[30] 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

思路:
对比59题,这里将数据结构替换成栈,相比队列,栈的结构如果不符合条件,直接不入栈即可。

代码:

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 MinStack:

def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_stack = []


def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or self.min_stack[-1] >= x:
self.min_stack.append(x)


def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()


def top(self) -> int:
return self.stack[-1]


def min(self) -> int:
return self.min_stack[-1]

[68]二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

思路:
因为是一个二叉搜索数,所以可以快速得到一个节点的路径;再进行路径的对比,找到分叉的节点即可。

代码:

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 __init__(self) -> None:
self.parent_map = {}

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

def get_path(target):
path = []
node = root
while node:
path.append(node)
if node.val > target.val:
node = node.left
elif node.val < target.val:
node = node.right
else:
break
return path

p_path = get_path(p)
q_path = get_path(q)
result = None
for p_path_node,q_path_node in zip(p_path,q_path):
if p_path_node == q_path_node:
result = p_path_node
break
return result

[21]合并两个有序的链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思考:
先确定一个最终返回的链表,然后把后面的链表链接上去即可

代码:

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 mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1

# 确保l1 < l2
if l2.val < l1.val:
l1,l2 = l2,l1

head = l1

# 将l2合并到l1上即可,也就是q合并到p上
p,q = l1,l2
while p.next and q:
if p.val <= q.val <= p.next.val:
p_next = p.next
q_next = q.next
p.next = q
p.next.next = p_next
p = p.next
q = q_next
else:
p = p.next
if q:
p.next = q

return head

[11]旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。  

1
2
输入:[3,4,5,1,2]
输出:1

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

思路:
二分查找,主要要跟右侧的数进行对比

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def minArray(self, numbers: List[int]) -> int:
start = 0
end = len(numbers) - 1
# 确保让最小的数字在[start,end]的区间
while start < end:
mid = (start+end) // 2
if numbers[mid] > numbers[end]:
start = mid + 1
elif numbers[mid] < numbers[end]:
end = mid
else:
end = end - 1
return numbers[mid]

[12]矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

1
2
3
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof

思考:
典型的DFS问题

代码:

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 exist(self, board: List[List[str]], word: str) -> bool:

def dfs(x,y,step):
if x < 0 or x >= len(board):
return False
if y < 0 or y >= len(board[0]):
return False
if board[x][y] != word[step]:
return False
if step == len(word) - 1:
return True

board[x][y] = ''
ret = dfs(x+1,y,step+1) or dfs(x-1,y,step+1) or dfs(x,y+1,step+1) or dfs(x,y-1,step+1)
board[x][y] = word[step]

return ret


if not board:
return False
if not word:
return False

for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i,j,0): return True

return False

[36]二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

思考:
确定最小的节点和最大的节点,通过递归来实现

代码:

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 treeToDoublyList(self, root: 'Node') -> 'Node':
if not root:
return None

left_min = root
right_max = root

if root.left:
left_min = self.treeToDoublyList(root.left)
left_max = left_min.left
left_max.right = root
root.left = left_max
if root.right:
right_min = self.treeToDoublyList(root.right)
right_max = right_min.left
right_min.left = root
root.right = right_min

left_min.left = right_max
right_max.right = left_min

return left_min

[46]把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

1
2
3
输入: 12258
输出: 5
解释: 122585种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi""mzi"

https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

思考:
两种场景,分开思考

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def translateNum(self, num: int) -> int:
return self.helper(str(num))

def helper(self,num_str):
if len(num_str) <= 1:
return 1

ret = self.helper(num_str[1:])

if 10 <= int(num_str[:2]) <= 25:
ret += self.helper(num_str[2:])

return ret

回溯算法

答题框架

1
2
3
4
5
6
7
8
9
10
result = []

def backtrack(路径,选择列表):
if 满足条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

其中:
路径:也就是已经做出的选择;选择列表:也就是你当前可以做的选择;结束条件:也就是到达决策树底层,无法再做选择的条件。

[78]子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

https://leetcode-cn.com/problems/subsets/
https://leetcode-cn.com/problems/subsets-ii/

思想:
回溯法,注意减枝的操作即可

代码:
无重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []

def backtrace(trace,index):
# 从index开始
result.append(trace[:])

if index >= len(nums):
return

for i in range(index,len(nums)):
trace.append(nums[i])
backtrace(trace,i+1)
trace.pop()

backtrace([],0)
return 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 subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
result = []

def backtrace(trace,index):
result.append(trace[:])

if index >= len(nums):
return

s = set()
for i in range(index,len(nums)):
if nums[i] in s:
continue
trace.append(nums[i])
s.add(nums[i])
backtrace(trace,i+1)
trace.pop()

nums.sort()
backtrace([],0)
return result

[93]复原 IP 地址

给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。

链接:https://leetcode-cn.com/problems/restore-ip-addresses

思想:
回溯法,同时进行减枝的操作

代码:

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
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []

def is_valid(ip_str):
if len(ip_str) == 1:
return True
if ip_str[0] == '0':
return False
if 0 < int(ip_str) <= 255:
return True
else:
return False

def backtrace(trace,index):
# trace 当前已经添加的ip地址
# index 从index开始遍历s
if len(trace) == 4 or index == len(s):
if len(trace) == 4 and index == len(s):
result.append(".".join(trace))
return

# 继续剪枝
if not ( 4-len(trace) <= len(s) - index <= 3*(4-len(trace)) ):
return

# 选择
for i in range(1,4):
if index + i <= len(s):
sub_str = s[index:index+i]
if is_valid(sub_str):
trace.append(sub_str)
backtrace(trace,index+i)
trace.pop()

backtrace([],0)
return result

动态规划

[42]接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

1
2
3
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

https://leetcode-cn.com/problems/trapping-rain-water

思考:
动态规划,当前位置能接到的雨水,等于两侧最大值中的较小的一个减去当前的数量

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
left_max = [0 for i in range(len(height))]
left_max[0] = height[0]
for i in range(1,len(height)):
left_max[i] = max(left_max[i-1],height[i])
right_max = [0 for i in range(len(height))]
right_max[-1] = height[-1]
for i in range(len(height)-2, -1, -1):
right_max[i] = max(right_max[i+1],height[i])
ans = 0
for i in range(len(height)):
ans = ans + (min(left_max[i],right_max[i]) - height[i])
return ans

通过优先队列,缩小范围来实现

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
from queue import PriorityQueue

class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
visited = set()
q = PriorityQueue()
q.put((height[0],0))
q.put((height[-1],len(height)-1))
visited.add(0)
visited.add(len(height)-1)
ret = 0
while not q.empty():
h,index = q.get()

steps = [1,-1]
for step in steps:
new_index = index + step
if 0 < new_index < len(height) and new_index not in visited:
if height[new_index] < h:
ret += (h - height[new_index])
height[new_index] = h
q.put((height[new_index],new_index))
visited.add(new_index)
return ret

[407]接雨水 II

给你一个 m x n 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。

https://leetcode-cn.com/problems/trapping-rain-water-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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from queue import PriorityQueue

class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
if not heightMap:
return 0

q = PriorityQueue()
visited = set()

m = len(heightMap)
n = len(heightMap[0])

# 把四周放进去
for i in range(m):
q.put((heightMap[i][0],i,0))
visited.add((i,0))
q.put((heightMap[i][n-1],i,n-1))
visited.add((i,n-1))

for j in range(1,n-1):
q.put((heightMap[0][j], 0 ,j))
visited.add((0,j))
q.put((heightMap[m-1][j],m-1,j))
visited.add((m-1,j))

ret = 0
while not q.empty():
h,x,y = q.get()

steps = [(0,-1),(0,1),(1,0),(-1,0)]

for step in steps:
new_x,new_y = x+step[0],y+step[1]
if 0 <= new_x < m and 0 <= new_y < n and (new_x,new_y) not in visited:
if heightMap[new_x][new_y] < h:
ret += (h - heightMap[new_x][new_y])
heightMap[new_x][new_y] = h
q.put((heightMap[new_x][new_y],new_x,new_y))
visited.add((new_x,new_y))

return ret

[72]编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

1
2
3
插入一个字符
删除一个字符
替换一个字符

https://leetcode-cn.com/problems/edit-distance

思想:
动态规划的问题,假设已经知道如何 (1)将word1[:-1]转换成word2, 那么只要增加一步就可以将word1转换成word2;(2)将word1转换成word2[:-1],那么只要增加一步就可以将word1转换成word2;(3)将word1[:-1]转换成word2[:-1],如果word1[-1] == word2[-1]那么不用再增加步骤就已经转换完成了,如果不等,则需要再增加一步。

代码:

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 minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)

dp = [[0 for i in range(n+1)] for j in range(m+1)]

for i in range(1,m+1):
dp[i][0] = i

for i in range(1,n+1):
dp[0][i] = i

for i in range(1,m+1):
for j in range(1,n+1):
a = dp[i-1][j] + 1
b = dp[i][j-1] + 1
c = dp[i-1][j-1]
if word1[i-1] != word2[j-1]:
c += 1
dp[i][j] = min(a,b,c)

return dp[m][n]

面试高频题

[146] LRU

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。

void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该

在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。  

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?

链接:https://leetcode-cn.com/problems/lru-cache

思考:
通过一个双向链表和一个字典实现;提前构建一个虚拟的头节点和虚拟的尾节点

代码:

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
class Node:
def __init__(self, key=0, val=0) -> None:
self.key = key
self.val = val
self.prev = None
self.next = None

class LRUCache:

def __init__(self, capacity: int):
self.capacity = capacity
self.d = {}
self.head,self.tail = Node(),Node()
self.head.next,self.tail.prev = self.tail,self.head

def get(self, key: int) -> int:
if key in self.d:
node = self.d[key]
self.move_to_head(node)
return node.val
else:
return -1

def put(self, key: int, value: int) -> None:
if key in self.d:
node = self.d[key]
node.val = value
self.move_to_head(node)
else:
node = Node(key,value)
self.d[key] = node
self.add_to_head(node)
if len(self.d) > self.capacity:
node = self.pop_last_node()
del self.d[node.key]

def move_to_head(self,node):
self.remove_node(node)
self.add_to_head(node)

def remove_node(self,node):
node_prev,node_next = node.prev,node.next
node_prev.next,node_next.prev = node_next,node_prev

def add_to_head(self,node):
head_next = self.head.next
self.head.next,node.prev = node,self.head
node.next,head_next.prev = head_next,node

def pop_last_node(self):
last_node = self.tail.prev
self.remove_node(last_node)
return last_node

[885]螺旋矩阵 III

在 R 行 C 列的矩阵上,我们从 (r0, c0) 面朝东面开始

这里,网格的西北角位于第一行第一列,网格的东南角位于最后一行最后一列。

现在,我们以顺时针按螺旋状行走,访问此网格中的每个位置。

每当我们移动到网格的边界之外时,我们会继续在网格之外行走(但稍后可能会返回到网格边界)。

最终,我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

https://leetcode-cn.com/problems/spiral-matrix-iii/

思路:
模拟整个行走的过程,忽略是否在网格中。整体行走的规则是: 向右 1, 向下 1, 向左 2,向上 2,向右 3 …

代码:

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 Solution:
def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:

def valid(x,y):
if 0 <= x < R and 0 <= y < C:
return True
return False

if R*C == 0:
return []

ret = []
ret.append([r0,c0])
r,c = r0,c0
step = 1
while len(ret) < R*C:
# 向右
for i in range(1,step+1):
r,c = r,c+1
if valid(r,c): ret.append([r,c])
# 向下
for i in range(1,step+1):
r,c = r+1,c
if valid(r,c): ret.append([r,c])
step += 1
# 向左
for i in range(1,step+1):
r,c = r,c-1
if valid(r,c): ret.append([r,c])
# 向上
for i in range(1,step+1):
r,c = r-1,c
if valid(r,c): ret.append([r,c])
step += 1
return ret

[470] 用 Rand7() 实现 Rand10()

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

思考:
生成两次产生的结果为 [1,49],需要保证这个结果是均匀随机的;再截取[1,40]的结果,然后映射到[1,10]

代码:

1
2
3
4
5
6
7
8
9
class Solution:
def rand10(self):
boundary = ((7 * 7) // 10) * 10
while True:
x = 7 * (rand7() - 1) + rand7()
#
if x <= boundary:
break
return x % 10 + 1

证明1: 产生的[1,40]的概率是均等的:

$$P(1) = \frac{1}{49} + \frac{9}{49}*\frac{1}{49} + … + {\frac{9}{49}}^{n-1}*\frac{1}{49} = \frac{1}{49} * \sum\limits_{k=1}^{k= \infty }{\frac{9}{49}}^{k-1} = \frac{1}{49} * \frac{49}{40} = \frac{1}{40}$$

证明2: 调用rand7()的期望

$$E = 2 * \frac{40}{49} + 4 * \frac{9}{49} * \frac{40}{49} + … + 2n * \frac{9}{49}^{n-1} * \frac{40}{49} =
2*\frac{40}{49} \sum\limits_{k=1}^{k= \infty }k\frac{9}{49}^{k-1} = 2.45
$$

[69]x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

1
2
输入: 4
输出: 2

https://leetcode-cn.com/problems/sqrtx

思想:
通过二分查找

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def mySqrt(self, x: int) -> int:
start = 1
end = x
while start <= end:
mid = (start + end) // 2
if mid * mid < x:
start = mid + 1
elif mid * mid > x:
end = mid - 1
else:
return mid
return end

[82]删除排序链表中的重复元素 II

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

思想:
分解成子问题,递归的处理,或者线性遍历

代码:
线性遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
pre = ListNode()
ret = pre
pre.next = head
p = head
while p and p.next:
if p.val == p.next.val:
q = p
while q and q.val == p.val:
q = q.next
pre.next = q
p = q
else:
pre = p
p = p.next
return ret.next

[451] 根据字符出现频率排序

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

1
2
3
4
5
6
7
8
9
输入:
"tree"

输出:
"eert"

解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。

https://leetcode-cn.com/problems/sort-characters-by-frequency

思考:
用map存储个数,再排序之后输出

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def frequencySort(self, s: str) -> str:
d = {}
for c in s:
d[c] = d.get(c,0) + 1
buckets = [ [] for i in range(len(s)+1) ]
for c in d:
count = d[c]
buckets[count].append(c)
index = len(buckets) - 1
ret = []
while index >= 1:
if buckets[index]:
for c in buckets[index]:
for i in range(index):
ret.append(c)
index -= 1
return "".join(ret)

[912]排序数组

给你一个整数数组 nums,请你将该数组升序排列。

思路:
手写快排,分解问题实现,主要是切分的操作

代码:

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 sortArray(self, nums: List[int]) -> List[int]:
self.quicksort(nums,0,len(nums)-1)
return nums

def quicksort(self,nums,l,r):
if r - l <= 0:
return
index = self.partition(nums,l,r)
self.quicksort(nums,l,index-1)
self.quicksort(nums,index+1,r)

def partition(self,nums,l,r):
pivot = nums[l]
index = l + 1

for i in range(index,r+1):
if nums[i] < pivot:
self.swap(nums,i,index)
index += 1

self.swap(nums,l,index-1)

return index-1

def swap(self,nums,l,r):
nums[l],nums[r] = nums[r],nums[l]

[1014]最佳观光组合

给你一个正整数数组 values,其中 values[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点(i < j)组成的观光组合的得分为 values[i] + values[j] + i - j ,也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

https://leetcode-cn.com/problems/best-sightseeing-pair

思考:
遍历,同时维护max(value[i-1] + (i-1))

代码:

1
2
3
4
5
6
7
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
ret,mx = 0,values[0] + 0
for j in range(1,len(values)):
ret = max(ret,mx+values[j] - j)
mx = max(mx,values[j] + j)
return ret

[224]基本计算器

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

https://leetcode-cn.com/problems/basic-calculator/

思考:
两个栈来分别存储数字和符号,细节处理,在数字栈先存一个0,对于(- / (+ 需要在数字栈额外压一个0
如果遇到符号,要一路计算到不能再计算为止

代码:

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
class Solution:
def calculate(self, s: str) -> int:
num_stack = [0]
op_stack = []
index = 0

def calcu():
if len(num_stack) < 2 or len(op_stack) < 1:
return
b = num_stack.pop()
a = num_stack.pop()
op = op_stack.pop()
if op == '+':
num_stack.append(a+b)
else:
num_stack.append(a-b)

while index < len(s):
if s[index] == ' ':
index += 1
elif s[index].isdigit():
num = 0
while index < len(s) and s[index].isdigit():
num = num * 10 + int(s[index])
index += 1
num_stack.append(num)
elif s[index] == '(':
op_stack.append(s[index])
index += 1
if index < len(s) and s[index] in "+-":
num_stack.append(0)
elif s[index] == ')':
while op_stack and op_stack[-1] != '(':
calcu()
op_stack.pop()
index += 1
else:
while op_stack and op_stack[-1] != '(':
calcu()
op_stack.append(s[index])
index += 1

while op_stack:
calcu()

return num_stack[-1]

[10]正则表达式匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

https://leetcode-cn.com/problems/regular-expression-matching

思想:
通过递归的思想来实现,从后向前看比较合理;值得注意的是,即使包含*号的跟之前的匹配上了也可以继续匹配。

代码:

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
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not s and not p:
return True

if s and not p:
return False

# 还存在的情况是 s and not p; s and p

# 根据p[-1]的情况进行划分
if p[-1] != '*':
if not s:
return False
if self.is_match_c(s[-1],p[-1]):
return self.isMatch(s[:-1],p[:-1])
else:
return False

# 说明p[-1] == '*'
if len(p) == 1:
return False

# 说明p至少有两位, 假设*表明复制0次
ret = self.isMatch(s,p[:-2])
if ret:
return True

# 说明*至少复制了1次
if not s:
return False

if self.is_match_c(s[-1],p[-2]):
return self.isMatch(s[:-1],p)
else:
return False

def is_match_c(self,s_c,p_c):
if p_c == '.':
return True
if s_c == p_c:
return True
return False

[84]柱状图中最大的矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

思考:
通过单调栈可以求解,获取当前节点的左右边界

代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = [0] + heights + [0]
stack = [0]
ans = 0
for i in range(1,len(heights)):
while heights[stack[-1]] > heights[i]:
cur = stack.pop()
ans = max(ans, (i-1 - (stack[-1]+1) +1)*heights[cur])
stack.append(i)
return ans

[124]二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和 。

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

思考:
递归每个节点产生的增益,在递归的同时,记录最大值

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.ret = float('-inf)
self.maxGain(root)
return self.ret

def maxGain(self,node):
if not node:
return 0
left = max(0, self.maxGain(node.left))
right = max(0,self.maxGain(node.right))
# 如果node是路径的根节点
self.ret = max(self.ret,node.val + left + right)
# 返回结果,只能选择一条
return node.val + max(left,right)

[43]字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

https://leetcode-cn.com/problems/multiply-strings/

思考:
分解问题成一个数字的乘法和加法

代码:

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
class Solution:
def multiply(self, num1: str, num2: str) -> str:
# len(num1) >= len(num2)
if len(num2) > len(num1):
num1,num2 = num2,num1

if num2 == "0":
return "0"

if len(num2) == 1:
ret = []
tmp = 0
num2 = int(num2)
for i in range(len(num1)-1,-1,-1):
tmp = num2 * int(num1[i]) + tmp
ret.append(str(tmp%10))
tmp = tmp // 10
if tmp > 0:
ret.append(str(tmp))
return "".join(ret[::-1])


ret = "0"
for i in range(len(num2)-1,-1,-1):
tmp = self.multiply(num1,num2[i])
tmp = tmp + "0" * (len(num2)-1 - i)
ret = self.plus(ret,tmp)
return ret

def plus(self,num1,num2):
# len(num1) >= len(num2)
if len(num2) > len(num1):
num1,num2 = num2,num1
num2 = "0"*(len(num1)-len(num2)) + num2
# 当前num1与num2等长
tmp = 0
ret = []
for i in range(len(num1)-1,-1,-1):
tmp = int(num1[i]) + int(num2[i]) + tmp
ret.append(str(tmp%10))
tmp = tmp // 10
if tmp > 0:
ret.append(str(tmp%10))
return "".join(ret[::-1])

【300】最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

https://leetcode-cn.com/problems/longest-increasing-subsequence

思想:
通过动态规划,dp[i] 表示以nums[i]结尾的最长递增子序列,那么只要向前看即可

代码:

1

[25]K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

https://leetcode-cn.com/problems/reverse-nodes-in-k-group

思想:
模拟整个过程,有一个虚拟的头节点

代码:

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 reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if k == 1:
return head
ret = ListNode()
ret.next = head
pre_node = ret
p = head
while p:
tmp_head = p
for i in range(1,k):
if p.next:
p = p.next
else:
return ret.next
next_node = p.next
p.next = None
reversed_head,reversed_tail = self.reverse(tmp_head)
pre_node.next = reversed_head
reversed_tail.next = next_node
pre_node = reversed_tail
p = next_node
return ret.next

def reverse(self,root):
pre = None
p = root
while p.next:
p_next = p.next
p.next = pre
pre = p
p = p_next
p.next = pre
return p,root

[328] 奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

https://leetcode-cn.com/problems/odd-even-linked-list

思考:
模拟操作,最后需要标记q节点为空

代码:

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 oddEvenList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
# 说明至少有两个节点
ret = head
p = head
q = head.next
send_head = q
while p.next.next and q.next.next:
p_next = p.next.next
q_next = q.next.next
p.next = p_next
q.next = q_next
p = p.next
q = q.next
if q.next:
p.next = q.next
p = p.next
q.next = None
p.next = send_head
return ret