0%

LeetCode_&_Algorithm

索引

题目类型 题目
Hash twoSum
valid-sudoku
first-missing-positive
LinkNode add-two-numbers
merge-two-sorted-lists
swap-nodes-in-pairs
reverse-nodes-in-k-group
rotate-list
remove-duplicates-from-sorted-list-ii
remove-duplicates-from-sorted-list
partition-list
reverse-linked-list-ii
BackTrack find-median-sorted-array — Recursion
sudoku-solver
combination-sum — Recursion
permutations
permutations-ii
powx-n — Recursion
n-queens
n-queens-ii
combinations— Recursion
subsets— Recursion
subsets-ii
word-search— Recursion
gray-code— Recursion
restore-ip-addresses
scramble-string
different-ways-to-add-parentheses
letter-case-permutation
palindrome-partitioning
2DMatric longest-palindrome
rotate-image
spiral-matrix
spiral-matrix-ii
set-matrix-zeroes
Regular Expression string-to-integer-atoi
regular-expression-matchin
valid-number
Stack valid-parentheses
largest-rectangle-in-histogram
maximal-rectangle
BinaryTree generate-parentheses
Queue merge-k-sorted-lists
Bit Operation divide-two-integers
gray-code
convert-a-number-to-hexadecimal
binary-watch
Binary Search find-first-and-last-position-of-element-in-sorted-array
sqrtx
search-a-2d-matrix
search-in-rotated-sorted-array
Double Pointer trapping-rain-water
sort-colors
minimum-window-substring
remove-duplicates-from-sorted-array-ii
merge-sorted-array
Dynamic Programming wildcard-matching
maximum-subarray
jump-game
unique-paths
unique-paths-ii
minimum-path-sum
climbing-stairs
edit-distance
decode-ways
interleaving-string
split-array-with-equal-sum
Greedy Algorithm jump-game-ii
maximum-subarray
merge-intervals
insert-interval
queue-reconstruction-by-height
String valid-number
text-justification
simplify-path
Tree binary-tree-inorder-traversal
unique-binary-search-trees-ii
unique-binary-search-trees
validate-binary-search-tree
recover-binary-search-tree
same-tree
sort largest-number
kth-largest-element-in-an-array
sort-an-array
contains-duplicate-iii — bucket

剑指Offer

序号 题目 类型
1 二维数组中的查找 数组、查找
7 斐波那契数列 数组
13 调整数组顺序使奇数位于偶数前面 数组
19 顺时针打印矩阵 数组
29 最小的K个数 数组、高级算法
32 把数组排成最小的数 数组
35 数组中的逆序对 数组
37 数字在排序数组中出现的次数 数组、二分
42 和为S的两个数字 数组、双指针
49 把字符串转换成整数 数组
50 数组中重复的数字 数组
51 构建乘积数组 数组
66 机器人的运动范围 数组
67 剪绳子 数组、贪心、高级算法
2 替换空格 字符串
27 字符串的排列 字符串、动态规划
34 第一个只出现一次的字符位置 字符串
43 左旋转字符串 字符串
44 翻转单词顺序列 字符串
45 扑克牌顺子 字符串
48 不用加减乘除做加法 字符串、数学
52 正则表达式匹配 字符串
53 表示数值的字符串 字符串
54 字符流中第一个不重复的字符 字符串
3 从尾到头打印链表 链表
14 链表中倒数第K个结点 链表、双指针
15 反转链表 链表
25 复杂链表的复制 链表
36 两个链表的第一个公共结点 链表
46 圆圈中最后剩下的元素 链表
55 链表中环的入口结点 链表
56 删除链表中重复的结点 链表
4 重建二叉树 树、dfs、数组
17 树的子结构
18 二叉树的镜像
22 从上往下打印二叉树 树、队列
23 二叉搜索树的后序遍历序列 树、栈
24 二叉树中和为某一值的路径
38 二叉树的深度
39 平衡二叉树 树、dfs
57 二叉树的下一个结点
58 对称的二叉树
59 按之字形顺序打印二叉树 树、栈
60 把二叉树打印成多行 树、bfs
61 序列化二叉树 树、队列
62 二叉搜索树的第K个结点
5 用两个栈实现队列
20 包含min函数的栈
21 栈的压入、弹出序列
6 旋转数组的最小数字 二分
8 跳台阶 递归
10 矩形覆盖 递归
9 变态跳台阶 贪心
11 二进制中1的个数 数学
12 数值的整数次方 数学
33 丑数 数学、动态规划
47 求1+2+….+n 数学
16 合并两个排序的链表 分治
26 二叉搜索树与双向链表 分治
28 数组中出现次数超过一半的数字 分治、位运算
30 连续子数组的最大和 分治、动态规划
31 整数中1出现的次数(从1到n) 查找
40 数组中只出现一次的数字 位运算、哈希
41 和为S的连续正数序列 穷举、滑动窗口
63 数据流中的中位数 堆、排序
64 滑动窗口的最大值 堆、双指针
65 矩阵中的路径 dfs、回溯

Hash

1_twoSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
# @Time : 2019/9/106:55 下午
# @Author: GraceKoo
# @File: 1_twoSum.py
# @Desc: https://leetcode-cn.com/problems/two-sum/
import timeit


class Solution:
def twoSum(self, nums, target):
hashmap = {}
for loc, num in enumerate(nums):
if hashmap.get(target - num) is not None:
return [hashmap.get(target - num), loc]
hashmap[num] = loc
return None


nums = [2, 7, 3, 6, 5]
so = Solution()
start = timeit.default_timer()
print(so.twoSum(nums, 8))
end = timeit.default_timer()
print(str((end - start) * 1000), "s") # 0.052050003432668746 s

valid-sudoku

解题思路:

  • 行中没有重复的数字。
  • 列中没有重复的数字。
  • 3 x 3 子数独内没有重复的数字。
    • 可以使用 box_index = (row // 3) * 3 + columns // 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# -*- coding: utf-8 -*-
# @Time: 2020/2/3 11:18 下午
# @Author: GraceKoo
# @File: 36_valid-sudoku.py
# @Desc:https://leetcode-cn.com/problems/valid-sudoku/


class Solution:
def isValidSudoku(self, board) -> bool:
rows = [{} for i in range(0, 9)] # rows记录每行的数据情况
columns = [{} for i in range(0, 9)] # rows记录每列的数据情况
boxes = [{} for i in range(0, 9)] # rows记录每个3*3子块的数据情况

for row in range(0, 9):
for column in range(0, 9):
number = board[row][column]
if number != ".":
number = int(number)
box_index = (row // 3) * 3 + column // 3 # 对应(0,1,2,3,4,5,6,7,8,9)个子单元
rows[row][number] = rows[row].get(number, 0) + 1
columns[column][number] = columns[column].get(number, 0) + 1
boxes[box_index][number] = boxes[box_index].get(number, 0) + 1

if rows[row][number] > 1 or columns[column][number] > 1 or boxes[box_index][number] > 1:
return False
return True


so = Solution()
print(so.isValidSudoku([
["8", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]))
print(so.isValidSudoku([
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
))

first-missing-positive

解题思路:使用索引作为哈希键 以及 元素的符号作为哈希值 来实现是否存在的检测。

例如,nums[2] 元素的负号意味着数字 2 出现在 nums 中。nums[3]元素的正号表示 3 没有出现在 nums 中。

解题步骤:

  • 检查 1 是否存在于数组中。如果没有,则已经完成,1 即为答案。
  • 如果 nums = [1],答案即为 2 。
  • 第一次遍历:将负数,零,和大于 n 的数替换为 1 。
  • 第二次遍历:遍历数组。当读到数字 a 时,替换第 a 个元素的符号。注意重复元素:只能改变一次符号。由于没有下标 n ,使用下标 0 的元素保存是否存在数字 n。
  • 第三次遍历:返回第一个正数元素的下标。
  • 如果 nums[0] > 0,则返回 n 。
    如果之前的步骤中没有发现 nums 中有正数元素,则返回n + 1。
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
# -*- coding: utf-8 -*-
# @Time: 2020/2/11 8:36 下午
# @Author: GraceKoo
# @File: 41_first-missing-positive.py
# @Desc: https://leetcode-cn.com/problems/first-missing-positive/
from typing import List


class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
len_nums = len(nums)
if 1 not in nums:
return 1
if len_nums == 1:
return 2

# 第一次遍历:将所有非法数字置为1
for i in range(0, len_nums):
if nums[i] <= 0 or nums[i] >= len_nums:
nums[i] = 1

# 第二次遍历:更改对应位置的符号
for i in range(0, len_nums):
val = abs(nums[i])
nums[val] = -abs(nums[val])

# 第三次遍历:遍历数组符号
for i in range(1, len_nums):
if nums[i] > 0:
return i

# 最后检查nums[0]
if nums[0] > 0:
return len_nums
else:
return len_nums + 1


so = Solution()
print(so.firstMissingPositive([7, 8, 9, 11, 12]))

interview_28

  1. Hash法:时间复杂度O(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
25
26
27
28
29
30
# -*- coding: utf-8 -*-
# @Time: 2020/6/28 19:45
# @Author: GraceKoo
# @File: interview_28.py
# @Desc: https://leetcode-cn.com/problems/
# shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
from typing import List


class Solution:
def majorityElement(self, nums: List[int]) -> int:
if not nums:
return 0
count_dict = dict()
len_nums = len(nums)
for i in range(len_nums):
count_dict[nums[i]] = count_dict.setdefault(nums[i], 0) + 1

result_count = 0
for key in count_dict.keys():
if count_dict[key] > result_count:
result_count, result_key = count_dict[key], key
if result_count >= (len_nums // 2):
return result_key
return 0


so = Solution()
print(so.majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2]))

  1. 摩尔投票法

解题思路

vote

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/28 19:45
# @Author: GraceKoo
# @File:interview_28.py
# @Desc: https://leetcode-cn.com/problems/
# shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
from typing import List


class Solution:
def majorityElement(self, nums: List[int]) -> int:
if not nums:
return 0
votes = 0
count = 0
for num in nums:
if votes == 0:
x = num
votes += 1 if num == x else -1
#  验证x是否为众数
for _ in nums:
if _ == x:
count += 1
return x if count > len(nums) // 2 else 0


so = Solution()
print(so.majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2]))

interview_34

  1. 遍历字符串 s ,使用哈希表统计 “各字符数量是否 >1 ”。
  2. 再遍历字符串 s ,在哈希表中找到首个 “数量为 1 的字符”,并返回。

Python 3.6 后,默认字典就是有序的,因此无需使用 OrderedDict()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/7/7 10:56
# @Author: GraceKoo
# @File: interview_34.py
# @Desc: https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/


class Solution:
def firstUniqChar(self, s: str) -> str:
result_dict = {}
for item in s:
result_dict[item] = item not in result_dict
for k, v in result_dict.items():
if v:
return k
return " "


so = Solution()
print(so.firstUniqChar("NXWtnzyoHoBhUJaPauJaAitLWNMlkKwDYbbigdMMaYfkVPhGZcrEwp"))

LinkNode

2_add_two_numbers

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
# -*- coding: utf-8 -*-
# @Time : 2019/9/1111:11 下午
# @Author: GraceKoo
# @File: 2_add_two_numbers.py
# @Desc: https://leetcode-cn.com/problems/add-two-numbers/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None and l2 is None:
return None
elif l1 is None:
return l2
elif l2 is None:
return l1
flag = 0
tmp = ListNode(0)
res = tmp
while l1 or l2:
tmp_sum = 0
if l1:
tmp_sum += l1.val
l1 = l1.next
if l2:
tmp_sum += l2.val
l2 = l2.next
flag = (tmp_sum + flag) // 10
tmp_sum = (tmp_sum + flag) % 10
res.next = ListNode(tmp_sum)
res = res.next
if flag:
res.mext = ListNode(1)
res = tmp.next
del tmp

return res

merge-two-sorted-lists

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/1 9:04 下午
# @Author: GraceKoo
# @File: 21_merge-two-sorted-lists.py
# @Desc: https://leetcode-cn.com/problems/merge-two-sorted-lists/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head_pre = ListNode(-1)
pre = head_pre
while l1 or l2:
if l1.value < l2.value:
pre.next = l1
l1 = l1.next
else:
pre.next = l2
l2 = l2.next
# pre指向当前计算节点的上一个节点,运算结束后需指向下一个
pre = pre.next
pre.next = l1 if l1 is not None else l2

return head_pre.next

swap-nodes-in-pairs

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/6 5:15 下午
# @Author: GraceKoo
# @File: 24_swap-nodes-in-pairs.py
# @Desc:https://leetcode-cn.com/problems/swap-nodes-in-pairs/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
head_pre = ListNode(-1)
head_pre.next = head
tmp = head_pre
while tmp.next and tmp.next.next:
a, b = tmp.next, tmp.next.next
tmp.next, a.next = b, b.next
b.next = a
tmp = tmp.next.next
return head_pre.next

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
35
36
37
38
39
40
# -*- coding: utf-8 -*-
# @Time: 2020/1/8 10:03 下午
# @Author: GraceKoo
# @File: 25_reverse-nodes-in-k-group.py
# @Desc:https://leetcode-cn.com/problems/reverse-nodes-in-k-group/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
tmp_head = ListNode(0)
tmp_head.next = head
pre = tail = tmp_head
while True:
count = k
# 将tail移动k个节点
while count and tail:
count -= 1
tail = tail.next
# 如果tail为空,则当前的这组节点数量小于k个,跳出,不进行反转
if not tail:
break
# 否则反转这k个节点
head = pre.next # head 用于记录当前这组翻转节点的第一个节点
while pre.next != tail:
current_node = pre.next # current_node 指向当前正在准备移动的节点
pre.next = current_node.next
current_node.next = tail.next
tail.next = current_node
pre = pre.next
pre, tail = head # 指向上组移动的第一个节点

return tmp_head.next

rotate-list

解题思路:

  1. 先需旋转链表,假设旋转的步长k=2,首先循环链表得到链表的长度length_of_nodes
graph LR
id2((1)) --> id3((2))
id3((2)) --> id4((3))
id4((3)) --> id5((4))
id5((4)) --> id6((5))
id6((5)) --> id7((6))
  1. 得到倒数第二个节点的索引为length_of_nodes - k,即为新的头节点

    新的尾节点的索引为length_of_nodes - k - 1

    如果k>n:

    那么新的头节点的索引为length_of_nodes - k % length_of_nodes

    新的尾节点的索引为length_of_nodes - k % length_of_nodes - 1

graph LR
id2((1)) --> id3((2))
id3((2)) --> id4((3))
id4((3)) --> id5((4))
id5((4)) -.end.-> id6((5))
id6((5)) --> id7((6))
id7((6)) --> id2((1))
  1. 串联成新的链表
graph LR
id2((1)) --> id3((2))
id3((2)) --> id4((3))
id4((3)) --> id5((4))
id6((5)) --> id7((6))
id7((6)) --> id2((1))
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
# -*- coding: utf-8 -*-
# @Time: 2020/3/4 11:55
# @Author: GraceKoo
# @File: 61_rotate-list.py
# @Desc:https://leetcode-cn.com/problems/rotate-list/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head or head.next:
return head
length_of_nodes = 1
old_tail = head

# 1.compute the length of nodes
while old_tail.next:
length_of_nodes += 1
old_tail = old_tail.next
old_tail.next = head

# 2.find the length_of_nodes - k % length_of_nodes -1 node,which is the last node
new_tail = head
for i in range(length_of_nodes - k % length_of_nodes - 1):
new_tail = new_tail.next
new_head = new_tail.next

return new_head

remove-duplicates-from-sorted-list-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
43
44
# -*- coding: utf-8 -*-
# @Time: 2020/3/26 19:29
# @Author: GraceKoo
# @File: 82_remove-duplicates-from-sorted-list-ii.py
# @Desc:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
tmp_head = ListNode("head")
tmp_head.next = head
pre, cur = None, tmp_head

while cur:
pre = cur # pre指向不重复的节点, cur指向当前节点
cur = cur.next # cur指向pre的下一个节点
while cur and cur.next and cur.next.val == cur.val:
value = cur.val
# 找到不重复的节点
while cur and cur.val == value:
cur = cur.next
pre.next = cur
return tmp_head.next


first_node = ListNode(0)
first_node.next = ListNode(2)
first_node.next.next = ListNode(2)
print(first_node.val, first_node.next.val, first_node.next.next.val)

so = Solution()
last_node = so.deleteDuplicates(first_node)
while last_node:
print(last_node.val)
last_node = last_node.next


remove-duplicates-from-sorted-list

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/26 23:28
# @Author: GraceKoo
# @File: 83_remove-duplicates-from-sorted-list.py
# @Desc:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
tmp = head
while tmp and tmp.next:
if tmp.val == tmp.next.val:
tmp.next = tmp.next.next
else:
tmp = tmp.next
return head

first_node = ListNode(0)
first_node.next = ListNode(2)
first_node.next.next = ListNode(2)
print(first_node.val, first_node.next.val, first_node.next.next.val)
so = Solution()
last_node = so.deleteDuplicates(first_node)
while last_node:
print(last_node.val)
last_node = last_node.next

partition-list

解题思路:

  1. before,after分别指向链表中值小于x的节点

  2. 创建before,after的哑节点:before_node、after_node

  3. 遍历链表,最后进行合并

after.next = None
before.next = after_node.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
if not head:
return head
# before_node、after_node是哑节点
before = before_node = ListNode(0)
after = after_node = ListNode(0)
while head:
if head.val > x:
after.next = head
after = after.next
else:
before.next = head
before = before.next
head = head.next
after.next = None
before.next = after_node.next

return before_node.next

reverse-linked-list-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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# -*- coding: utf-8 -*-
# @Time: 2020/4/6 00:06
# @Author: GraceKoo
# @File: 92_reverse-linked-list-ii.py
# @Desc: https://leetcode-cn.com/problems/reverse-linked-list-ii/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
if m == n:
return head
dummy = ListNode(-1)
dummy.next = head
a, d = dummy, dummy
for _ in range(m - 1):
a = a.next
for _ in range(n):
d = d.next
b, c = a.next, d.next
# pre, cur, next用于遍历子链表
pre = b
cur = pre.next
while cur != c:
cur.next, pre, cur = pre, cur, cur.next
# 以上写法等价于
# next = cur.next
# cur.next = pre
# pre = cur
# cur = next
# 首尾相接
a.next = d
b.next = c
return dummy.next


head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head_tmp = head
while head_tmp:
print(head_tmp.val)
head_tmp = head_tmp.next
so = Solution()
return_head = so.reverseBetween(head, 2, 3)
return_head_tmp = return_head
while return_head_tmp:
print(return_head_tmp.val)
return_head_tmp = return_head_tmp.next

从头到尾打印链表

  • 解题思路:从头到尾打印,考虑使用栈结构,也可以进行递归,但是当数据量比较大时,可能出现栈溢出,所以直接使用栈更合适。
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
# -*- coding: utf-8 -*-
# @Time: 2020/5/9 23:22
# @Author: GraceKoo
# @File: printListFromTailToHead.py
# @Desc:


class ListNode:
# 链表的构造 初始化
def __init__(self, x):
self.val = x
self.next = None


class Solution:
# 返回从尾部到头部的列表值序列,例如[1,2,3]
def printListFromTailToHead(self, list_node: ListNode):
stack = []
while list_node:
stack.append(list_node.val)
list_node = list_node.next
# 将栈进行弹出
# return stack[::-1]
while stack:
print(stack.pop())

interview_25

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
“”“第一部分”“”
def dfs(head):
if not head: return None
if head in visited:
return visited[head]
# 创建新结点
copy = Node(head.val, None, None)
visited[head] = copy
copy.next = dfs(head.next)
“”“第二部分”“”
copy.random = dfs(head.random)
return copy
  1. 首先反复运行第一部分,copy.next = dfs(head.next) 会递归得越来越深,,当 碰到 head == None 时,开始运行第二部分,准备从尾结点回溯;
  2. 回溯时,先从尾结点开始回溯:调用dfs(head.ranom)时,由于结点都保存在了哈希表中,因此 return visited[head],这时完成random指针,完成了最后一个结点,故return copy。再进行倒数第二个结点的回溯:调用dfs(head.random),return visited[head],return copy…….
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
# -*- coding: utf-8 -*-
# @Time: 2020/6/19 10:28
# @Author: GraceKoo
# @File: interview_25.py
# @Desc: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/


# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random


class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
def dfs(head):
if not head:
return None
if head in visited:
return visited[head]
copy = Node(head.val, None, None)
visited[head] = copy
copy.next = dfs(head.next)
copy.random = dfs(head.random)
return copy
visited = {}
return dfs(head)

interview_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
# -*- coding: utf-8 -*-
# @Time: 2020/5/9 23:22
# @Author: GraceKoo
# @File: interview_3.py
# @Desc: https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&
# qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class ListNode:
# 链表的构造 初始化
def __init__(self, x):
self.val = x
self.next = None


class Solution:
# 返回从尾部到头部的列表值序列,例如[1,2,3]
def printListFromTailToHead(self, list_node: ListNode):
stack = []
while list_node:
stack.append(list_node.val)
list_node = list_node.next
# 将栈进行弹出
# return stack[::-1]
while stack:
print(stack.pop())

interview_14

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
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 16:28
# @Author: GraceKoo
# @File: interview_14.py
# @Desc: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class Solution:
def FindKthToTail(self, head, k):
# write code here
if not head:
return None
# 让p,q相隔k个
p = head
q = head
count = 0
while p:
p = p.next
count += 1
# count至少大于等于2的时候才p才走
if count >= k + 1:
q = q.next
# 当k的长度比链表都长时,直接返回None
if k > count:
return None
return q

interview_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
35
36
37
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 16:29
# @Author: GraceKoo
# @File: interview_15.py
# @Desc:


class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
pre_node = None
current_node = head
while current_node:
current_node.next, pre_node, current_node = (
pre_node,
current_node,
current_node.next,
)
return pre_node


first_node = ListNode(0)
first_node.next = ListNode(1)
first_node.next.next = ListNode(2)
print(first_node.val, first_node.next.val, first_node.next.next.val)

so = Solution()
last_node = so.reverseList(first_node)
print(last_node.val, last_node.next.val, last_node.next.next.val)

interview_16

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
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 16:41
# @Author: GraceKoo
# @File: interview_16.py
# @Desc: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head_pre = ListNode(-1)
pre = head_pre
while l1 and l2:
if l1.val < l2.val:
pre.next = l1
l1 = l1.next
else:
pre.next = l2
l2 = l2.next
# pre指向当前计算节点的上一个节点,运算结束后需指向下一个
pre = pre.next
pre.next = l1 if l1 is not None else l2

return head_pre.next

interview_25

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/19 10:28
# @Author: GraceKoo
# @File: interview_25.py
# @Desc: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/


# Definition for a Node.
class Node:
def __init__(self, x: int, next: "Node" = None, random: "Node" = None):
self.val = int(x)
self.next = next
self.random = random


class Solution:
def copyRandomList(self, head: "Node") -> "Node":
def dfs(head):
if not head:
return None
if head in visited:
return visited[head]
copy = Node(head.val, None, None)
visited[head] = copy
copy.next = dfs(head.next)
copy.random = dfs(head.random)
return copy

visited = {}
return dfs(head)

interview_36

直观思路:先统计出两个链表的长度;然后让长度较长的那个链表先走Len个节点,Len表示长度差。
然后让两个指针同时向后走,如果有共同节点,那么一定会让这两个指针指向同一个节点。— from this

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 getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
temphead = headA
lenA = 0
while temphead:
temphead = temphead.next
lenA += 1
temphead = headB
lenB = 0
while temphead:
temphead = temphead.next
lenB += 1
dLen = abs(lenA-lenB)
if lenA - lenB >= 0:
#分别表示较长的链表和较短的链表
headl,heads = headA,headB
else:
headl,heads = headB,headA
while dLen > 0:
headl = headl.next
dLen -= 1
while headl and heads:
if headl == heads:
return headl
headl = headl.next
heads = heads.next
return None

进阶思路:两个链表长度分别为L1+C、L2+C, C为公共部分的长度。node1走了L1+C步后,回到node2起点走L2步;node2走了L2+C步后,回到node1起点走L1步。 当两个node走的步数都为L1+L2+C时就两个node就相遇了。

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
# -*- coding: utf-8 -*-
# @Time: 2020/8/24 19:56
# @Author: GraceKoo
# @File: interview_36.py
# @Desc: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None

node1, node2 = headA, headB
while node1 != node2:
node1 = node1.next if node1 else headB
node2 = node2.next if node2 else headA
return node1

interview_55

两个结论:(参考链接)

  1. 设置快慢指针,假如有环,他们最后一定相遇在环中。
  2. 两个指针相遇后,让两个指针分别从链表头和相遇点重新出发,每次走一步,最后一定相遇于环入口。

证明结论1:设置快慢指针fast和slow,fast每次走两步,low每次走一步。假如有环,两者一定在环中相遇。(因为low指针一旦进环,可以看作是fast指针在追slow指针,因为fast指针每次走两步,slow指针每次走一步,所以最后一定能追上(相遇))。

证明结论2

假设

链表头到环入口长度为——a,

环入口到相遇点长度为——b,

相遇点到环入口长度为——c,如图所示:

快慢指针

则相遇时,

快指针路程=a+(b+c)k+b,k>=1,其中b+c为环的长度,k为环的圈数(k>=1,即最少一圈,不能是0圈,不然快慢指针走的路程一样,矛盾)。

慢指针路程=a+b

因为快指针的路程是慢指针的路程的两倍,所以:(a+b)*2=a+(b+c)k+b

化简得:

a=(k-1)(b+c)+c,这个式子的意思是:链表头到环入口的距离=相遇点到环入口的距离+(k-1)圈数环长度。其中k>=1,所以k-1>=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
# -*- coding: utf-8 -*-
# @Time: 2020/9/28 16:16
# @Author: GraceKoo
# @File: interview_55.py
# @Desc: https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if pHead == None and pHead.next == None:
return None
onestep = pHead
twostep = pHead
# 之所以不用写twostep.next.next, 是因为如果twostep.next.next为None,则下次循环twostep就为None了,就会退出
while twostep and twostep.next:
onestep = onestep.next
twostep = twostep.next.next
if onestep == twostep:
onestep = pHead
while onestep != twostep:
onestep = onestep.next
twostep = twostep.next
return onestep
return None

interview_56

解题思路:因为重复的节点都要删除,因此需要标记重复开始前的上一个节点,又因为头结点有可能是重复的节点,为了操作方便,我们可以再链表前面设置一个空节点作为头结点,因此需要设置3个指针,第一个head指向头结点。第二个p用来标记重复节点的前面一个节点,第三个cur用来寻找重复的节点,一旦找到p就不移动了,cur继续往后寻找直到不是重复的节点。

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
# -*- coding: utf-8 -*-
# @Time: 2020/9/28 16:16
# @Author: GraceKoo
# @File: interview_56.py
# @Desc: https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&
# qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def deleteDuplication(self, pHead):
# write code here
head = ListNode(-1) # 指向头节点
p = head # 指向不重复的结点
p.next = pHead
cur = pHead # 负责找到重复结点
while cur and cur.next:
if cur.val != cur.next.val:
cur = cur.next
p = p.next
else:
cur_val = cur.val
while cur and cur.val == cur_val:
cur = cur.next
# 不相同则令p指向不重复的元素,如果cur不存在,则p指向None就好了
p.next = cur
return head.next


BackTrack

回溯思想的模板为:

1
2
3
4
5
6
7
8
9
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

4_find_median_sorted_array

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/4 12:14 上午
# @Author: GraceKoo
# @File: 4_find_median_sorted_array.py
# @Desc: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
import timeit


class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
m = len(nums1)
n = len(nums2)
k = (m + n) % 2
if k == 1:
return self.find_k(nums1, nums2, (m + n) // 2)
else:
return (
self.find_k(nums1, nums2, (m + n) // 2 - 1)
+ self.find_k(nums1, nums2, (m + n) // 2)
) / 2

def find_k(self, nums1, nums2, k):
if not nums1:
return nums2[k]
if not nums2:
return nums1[k]
# print("len nums1:", len(nums1), "len nums2:", len(nums2))
i = len(nums1) // 2
j = len(nums2) // 2
# print(i, j, k)
if k > i + j:
if nums1[i] > nums2[j]:
return self.find_k(nums1, nums2[j + 1 :], k - j - 1)
else:
return self.find_k(nums1[i + 1 :], nums2, k - i - 1)
else:
if nums1[i] > nums2[j]:
return self.find_k(nums1[:i], nums2, k)
else:
return self.find_k(nums1, nums2[:j], k)


if __name__ == "__main__":
so = Solution()
nums1 = [1, 2, 3]
nums2 = [1, 2, 3]
start = timeit.default_timer()
print(so.findMedianSortedArrays(nums1, nums2))
end = timeit.default_timer()
print(str((end - start) * 1000), "s")
nums1 = [1, 2, 3]
nums2 = [4, 5, 6]
print(so.findMedianSortedArrays(nums1, nums2))
nums1 = [1, 2, 3]
nums2 = [4, 5]
print(so.findMedianSortedArrays(nums1, nums2))
nums1 = [1, 4, 6]
nums2 = [2, 5]
print(so.findMedianSortedArrays(nums1, nums2))

sudoku-solver

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/5 9:44 上午
# @Author: GraceKoo
# @File: 37_sudoku-solver.py
# @Desc:https://leetcode-cn.com/problems/sudoku-solver/
from collections import defaultdict


class Solution:
def solveSudoku(self, board) -> None:
rows_available = [set(range(1, 10)) for _ in range(9)] # 行剩余可用数字
columns_available = [set(range(1, 10)) for _ in range(9)] # 列剩余可用数字
boxes_available = [set(range(1, 10)) for _ in range(9)] # 块剩余可用数字

# 根据board数据统计每行每列可用的数字
empty = []
for row in range(9):
for column in range(9):
if board[row][column] == ".":
empty.append((row, column))
else:
num = int(board[row][column])
rows_available[row].remove(num)
columns_available[column].remove(num)
boxes_available[(row // 3) * 3 + column // 3].remove(num)

# 回溯函数,如果当前添加的数字个数已经等于空格的个数,则证明已添加到最后一个空格,即找到答案
def backtrack(interation = 0):
if interation == len(empty):
return True
i, j = empty[interation] # 依次取出待填入空格的坐标
for value in rows_available[i] & columns_available[j] & boxes_available[(i // 3) * 3 + j // 3]:
rows_available[i].remove(value)
columns_available[j].remove(value)
boxes_available[(i // 3) * 3 + j // 3].remove(value)
board[i][j] = value
if backtrack(interation + 1):
return True
# 如果没找到答案,则进行回溯
rows_available[i].add(value)
columns_available[j].add(value)
boxes_available[(i // 3) * 3 + j // 3].add(value)
return False
backtrack()
return board


so = Solution()
print(so.solveSudoku([
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
))

combination-sum

解题思路:(注:参考链接

  • target = 7 为根结点,每一个分支做减法。减到 00 或者负数的时候,剪枝。其中,减到 0的时候添加结果。
  • 为了能够去重:把候选数组排个序,即后面选取的数不能比前面选的数还要小。

leetcode-39

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/9 11:55 上午
# @Author: GraceKoo
# @File: 39_combination-sum.py
# @Desc: https://leetcode-cn.com/problems/combination-sum/solution/

from typing import List


class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates or not target:
return []
candidates.sort()
output_list = []
path = []
begin = 0
size = len(candidates)
self._dfs(candidates, begin, size, path, output_list, target)
return output_list

def _dfs(self, candidates, begin, size, path, output_list, target):
# 递归终止的条件
if target == 0:
output_list.append(path[:])
for index in range(begin, size):
residue = target - candidates[index]
if residue < 0:
break
path.append(candidates[index])
self._dfs(candidates, index, size, path, output_list, residue)
path.pop()


if __name__ == '__main__':
candidates = [2, 3, 6, 7]
target = 7
solution = Solution()
result = solution.combinationSum(candidates, target)
print(result)

permutations

permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2020/1/13 6:40 下午
# @Author: GraceKoo
# @File: 46_permutations.py
# @Desc: https://leetcode-cn.com/problems/permutations/


class Solution:
def permute(self, nums):
def backtrack(nums, num):
if not nums:
output_list.append(num)
return
for i in range(len(nums)):
backtrack(nums[:i] + nums[i + 1 :], num + [nums[i]])

output_list = []
backtrack(nums, [])
return output_list


so = Solution()
print(so.permute([1, 2, 3]))

permutations-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
# -*- coding: utf-8 -*-
# @Time: 2020/2/18 6:40 下午
# @Author: GraceKoo
# @File: 47_permutations-ii.py
# @Desc: https://leetcode-cn.com/problems/permutations/


class Solution:
def permuteUnique(self, nums):
def backtrack(nums, num):
if not nums:
output_list.append(num)
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
backtrack(nums[:i] + nums[i + 1:], num + [nums[i]])

nums.sort() # 数组先排序
output_list = []
backtrack(nums, [])
return output_list


so = Solution()
print(so.permuteUnique([1, 1, 2]))

interview_27

permutations

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/27 14:35
# @Author: GraceKoo
# @File: interview_27.py
# @Desc: https://leetcode-cn.com/problems/
# zi-fu-chuan-de-pai-lie-lcof/
from typing import List


class Solution:
def permutation(self, s: str) -> List[str]:
if not s:
return []
# nums存放需要继续遍历的字符,tmp存放当前遍历的结果
def backtrack(nums, tmp):
if not nums:
result.add(tmp)
return
for i in range(len(nums)):
backtrack(nums[:i] + nums[i+1:], tmp+nums[i])

result = set()
backtrack(s, "")
return list(result)


so = Solution()
print(so.permutation("ryawrowv"))

powx-n

解题思路

  • 若n为偶数:$x^n = x^{\frac{n}{2}} \, \dot \, x^{\frac{n}{2}}$
  • 若n为奇数:$x ^ n = x ^ {\frac{n}{2}} \, \dot \, x^ {\frac{n}{2}} \, \dot \, x$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2020/2/21 23:37
# @Author: GraceKoo
# @File: 50_powx-n.py
# @Desc:https://leetcode-cn.com/problems/powx-n/


class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
if n == -1:
return 1 / x
half = self.myPow(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x


so = Solution()
print(so.myPow(2.00000, -10))

n-queens

一、因为:

对于所有的主对角线有 行号 + 列号 = 常数

对于所有的次对角线有 行号 - 列号 = 常数

所以,所有的主对象线元素可以用2 * n - 1个元素来表示,比如main_diagonals[0]就可以表示待解queen_map中,第queen_map[0][0]个元素的所有主对角线元素。

二、解题思路 (注:参考链接

  • 从第一个 row = 0 开始.
  • 循环列并且试图在每个 column 中放置皇后.
    • 如果方格 (row, column) 不在攻击范围内
      • 在 (row, column) 方格上放置皇后。
      • 排除对应行,列和两个对角线的位置。
      • If 所有的行被考虑过,row == N
        意味着我们找到了一个解
      • Else
        继续考虑接下来的皇后放置 backtrack(row + 1).
      • 回溯:将在 (row, column) 方格的将皇后移除。

leetcode-51

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/24 13:55
# @Author: GraceKoo
# @File: 51_n-queens.py
# @Desc:https://leetcode-cn.com/problems/n-queens/
from typing import List


class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# 判断当前位置是否可用,由当前列,主对角线,副对角线共同决定
def could_place(row, col):
return not cols[col] + main_diagonals[row - col] + counter_diagonals[row + col]

# 放置皇后
def place_queen(row, col):
queens_position.add((row, col))
cols[col] = 1
main_diagonals[row - col] = 1
counter_diagonals[row + col] = 1

# 消除皇后
def remove_queen(row, col):
queens_position.remove((row, col))
cols[col] = 0
main_diagonals[row - col] = 0
counter_diagonals[row + col] = 0

# 增加解
def add_solution():
solution = []
for _, col in sorted(queens_position):
solution.append('.' * col + 'Q' + '.' * (n - col - 1))
output.append(solution)

def backtrack(row=0):
for col in range(n):
if could_place(row, col):
place_queen(row, col)
if row + 1 == n:
add_solution()
else:
backtrack(row + 1)
remove_queen(row, col)
cols = [0] * n # 每列的Queen
main_diagonals = [0] * (2 * n - 1) # 共需要7个元素可以表示全部的主对角线元素
counter_diagonals = [0] * (2 * n - 1) # 共需要7个元素可以表示全部的副对角线元素
queens_position = set() # 用于记录当前已经摆放的位置
output = []
backtrack()
return output


so = Solution()
print(so.solveNQueens(4))

n-queens-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
43
44
45
46
47
48
# -*- coding: utf-8 -*-
# @Time: 2020/2/24 19:35
# @Author: GraceKoo
# @File: 52_n-queens-ii.py
# @Desc:https://leetcode-cn.com/problems/n-queens-ii/
from typing import List


class Solution:
def totalNQueens(self, n: int) -> int:
# 判断当前位置是否可用,由当前列,主对角线,副对角线共同决定
def could_place(row, col):
return (
not cols[col] + main_diagonals[row - col] + counter_diagonals[row + col]
)

# 放置皇后
def place_queen(row, col):
cols[col] = 1
main_diagonals[row - col] = 1
counter_diagonals[row + col] = 1

# 消除皇后
def remove_queen(row, col):
cols[col] = 0
main_diagonals[row - col] = 0
counter_diagonals[row + col] = 0

def backtrack(row=0, output = 0):
for col in range(n):
if could_place(row, col):
place_queen(row, col)
if row + 1 == n:
output += 1
else:
output = backtrack(row + 1, output)
remove_queen(row, col)
return output

cols = [0] * n # 每列的Queen
main_diagonals = [0] * (2 * n - 1) # 共需要7个元素可以表示全部的主对角线元素
counter_diagonals = [0] * (2 * n - 1) # 共需要7个元素可以表示全部的副对角线元素
return backtrack()


so = Solution()
print(so.totalNQueens(4))

combinations

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/22 22:32
# @Author: GraceKoo
# @File: 77_combinations.py
# @Desc:https://leetcode-cn.com/problems/combinations/
from typing import List


class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if n <= 0 or k <= 0 or n < k:
return []
result = []
self.__dfs(1, k, n, [], result)
return result

def __dfs(self, index, k, n, pre, result):
if len(pre) == k:
result.append(pre[:])
return
for i in range(index, n + 1):
pre.append(i)
self.__dfs(i + 1, k, n, pre, result)
pre.pop()


so = Solution()
print(so.combine(4, 2))

subsets

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/24 11:57
# @Author: GraceKoo
# @File: 78_subsets.py
# @Desc:https://leetcode-cn.com/problems/subsets/
from typing import List


class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
n = len(nums)
if n <= 0:
return result

def backtrack(start, result_tmp):
result.append(result_tmp)
for i in range(start, n):
backtrack(i + 1, result_tmp + [nums[i]])

backtrack(0, [])
return result


so = Solution()
print(so.subsets([1, 2, 3]))

subsets-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
# -*- coding: utf-8 -*-
# @Time: 2020/4/4 22:57
# @Author: GraceKoo
# @File: 90_subsets-ii.py
# @Desc: https://leetcode-cn.com/problems/subsets-ii/
from typing import List


class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()

def track_back(i, tmp):
res.append(tmp)
for j in range(i, n):
if j > i and nums[j] == nums[j - 1]:
continue
track_back(j + 1, tmp + [nums[j]])

res = []
track_back(0, [])
return res


so = Solution()
print(so.subsetsWithDup([0]))

可以参考interview_65写法更清楚明了。

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/24 21:06
# @Author: GraceKoo
# @File: 79_word-search.py
# @Desc:https://leetcode-cn.com/problems/word-search/
from typing import List


class Solution:
derections = [(0, -1), (-1, 0), (0, 1), (1, 0)]

def exist(self, board: List[List[str]], word: str) -> bool:
rows = len(board)
cols = len(board[0])
marked = [[False for _ in range(cols)] for _ in range(rows)]
for row in range(rows):
for col in range(cols):
if self.__search_word(board, word, 0, row, col, marked, rows, cols):
return True
return False

def __search_word(self, board, word, index_word, row, col, marked, rows, cols):
# 递归终止条件
if len(word) - 1 == index_word:
return board[row][col] == word[index_word]
if board[row][col] == word[index_word]:
marked[row][col] = True
for derection in self.derections:
next_x, next_y = row + derection[0], col + derection[1]
if 0 <= next_x < rows and 0 <= next_y < cols and not marked[next_x][next_y] \
and self.__search_word(board, word,
index_word + 1,
next_x, next_y,
marked, rows, cols):
return True
marked[row][col] = False
return False


so = Solution()
print(so.exist([
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
], "ABCCED"))

interview_65

此题同word_search

对比参考链接,其方法更加简洁。

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
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:58
# @Author: GraceKoo
# @File: interview_65.py
# @Desc: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
from typing import List


class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
# 递归异常退出的条件:索引超出范围或者与当前字母不匹配
if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or word[k] != board[i][j] or board[i][j] == "*":
return False
# 递归成功退出的条件
if k == len(word)-1:
return True

# 继续向上下左右进行遍历
tmp = board[i][j]
board[i][j] = "*" # *表示已经遍历过

result = dfs(i-1, j, k+1) or dfs(i+1, j, k+1) or dfs(i, j-1, k+1) or dfs(i, j+1, k+1)

board[i][j] = tmp # 不管遍历结果如何,都需要恢复相应字符
return result

# 从不同的起点出发, k代表当前遍历到的单词字母的索引
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0):
return True
return False

牛客网上的要求略有不同。

  1. 给出的是字符串,需要将matrix[row][col]写成matrix[row*cols+col]来定位
  2. 字符串是不可变变量,需要将matrix先转化为list(matrix)
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
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
def dfs(row, col, k):
# 递归异常退出的出口
if not 0<= row < rows or not 0 <= col < cols or k >= len(path) or path[k] != matrix[row*cols + col] or matrix[row*cols + col] == "*":
return False
# 递归正常退出的出口
if matrix[row*cols + col] == path[k] and k == len(path) - 1:
return True

# 继续递归
tmp = matrix[row*cols + col]
matrix[row*cols + col] = "*" # 先把已经遍历的字母赋值为"*"
if dfs(row+1, col, k+1) or dfs(row, col+1, k+1) or dfs(row-1, col, k+1) or dfs(row, col-1, k+1):
matrix[row*cols + col] = tmp
return True
matrix[row*cols + col] = tmp
return False


matrix = list(matrix)
# 起点是matrix的每个点
for row in range(rows):
for col in range(cols):
if dfs(row, col, 0):
return True
return False

interview_66

参考链接

广度优先搜索:一般使用队列来实现

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
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:58
# @Author: GraceKoo
# @File: interview_66.py
# @Desc: https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
from collections import deque


class Solution:
def movingCount_BFS(self, m: int, n: int, k: int) -> int:
# 用于计算数位和
def sum_step(row, col):
result = 0
while row > 0:
result += row % 10
row = row // 10
while col > 0:
result += col % 10
col = col // 10
return result

# 广度优先搜索
de = deque() # 用于广度优先搜索格子的坐标
de.append((0, 0))
marked = set() # 用于记录已经走过的坐标
while de:
x, y = de.popleft()
# 如果当前坐标还没有走过,并且数位和小于等于k
if (x, y) not in marked and sum_step(x, y) <= k:
marked.add((x, y))
# 只考虑向下和向右即可
for dx, dy in [(1, 0), (0, 1)]:
if x + dx < m and y + dy < n:
de.append((x+dx, y+dy))
return len(marked)

深度优先搜索:一般使用来实现

定义一个递归函数 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
31
32
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:58
# @Author: GraceKoo
# @File: interview_66.py
# @Desc: https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
# 用于计算数位和
def sum_step(row, col):
result = 0
while row > 0:
result += row % 10
row = row // 10
while col > 0:
result += col % 10
col = col // 10
return result

def dfs(x, y):
# 递归退出的条件
# 坐标超出范围、数位和大于k、当前坐标已经走过
if x >= m or y >= n or sum_step(x, y) > k or (x, y) in marked:
return

marked.add((x, y))
dfs(x + 1, y) # 向下走
dfs(x, y + 1) # 向右走

marked = set() # 记录已经走过的坐标
dfs(0, 0)
return len(marked)

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/7 23:22
# @Author: GraceKoo
# @File: 93_restore-ip-addresses.py
# @Desc:https://leetcode-cn.com/problems/restore-ip-addresses/
from typing import List


class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
r = []

def restore(count=0, ip='', s=''):
if count == 4:
if s == '':
r.append(ip[:-1])
return
if len(s) > 0:
restore(count+1, ip+s[0]+'.', s[1:])
if len(s) > 1 and s[0] != '0':
restore(count+1, ip+s[:2]+'.', s[2:])
if len(s) > 2 and s[0] != '0' and int(s[0:3]) < 256:
restore(count+1, ip+s[:3]+'.', s[3:])
restore(0, '', s)
return r


so = Solution()
print(so.restoreIpAddresses("25525511135"))

scramble-string

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/9 23:07
# @Author: GraceKoo
# @File: 87_scramble-string.py
# @Desc:https://leetcode-cn.com/problems/scramble-string/
import functools


class Solution:
@functools.lru_cache(None)
def isScramble(self, s1: str, s2: str) -> bool:
if len(s1) != len(s2):
return False
if s1 == s2:
return True
if sorted(s1) != sorted(s2):
return False
for i in range(1, len(s1)):
if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
return True
if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):
return True
return False


so = Solution()
print(so.isScramble("great", "rgtae"))

different-ways-to-add-parentheses

分治三步法:

  • 分解:按运算符分成左右两部分,分别求解
  • 解决:实现一个递归函数,输入算式,返回算式解
  • 合并:根据运算符合并左右两部分的解,得出最终解
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
# -*- coding: utf-8 -*-
# @Time: 2020/4/17 12:40
# @Author: GraceKoo
# @File: 241_different-ways-to-add-parentheses.py
# @Desc: https://leetcode-cn.com/problems/different-ways-to-add-parentheses/
from typing import List


class Solution:
def diffWaysToCompute(self, input: str) -> List[int]:
if input.isdigit():
return [int(input)]
res = []
for index, value in enumerate(input):
if value in ["+", "-", "*"]:
left = self.diffWaysToCompute(input[:index])
right = self.diffWaysToCompute(input[index + 1 :])
# 合并结果
for l in left:
for r in right:
if value == "+":
res.append(l + r)
elif value == "-":
res.append(l - r)
elif value == "*":
res.append(l * r)
return res


so = Solution()
print(so.diffWaysToCompute("2*3-4*5"))

letter-case-permutation

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/21 20:38
# @Author: GraceKoo
# @File: 784_letter-case-permutation.py
# @Desc: https://leetcode-cn.com/problems/letter-case-permutation/
from typing import List


class Solution:
def letterCasePermutation(self, S: str) -> List[str]:
result = []

def helper(s, pre):
# 递归退出条件
if not s:
result.append("".join(pre))
return
if s[0].isalpha():
helper(s[1:], pre + [s[0].upper()])
helper(s[1:], pre + [s[0].lower()])
else:
helper(s[1:], pre + [s[0]])

helper(S, [])
return result


so = Solution()
print(so.letterCasePermutation("a1b2"))

palindrome-partitioning

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/23 00:22
# @Author: GraceKoo
# @File: 131_palindrome-partitioning.py
# @Desc: https://leetcode-cn.com/problems/palindrome-partitioning/
from typing import List


class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []

def backtrack(s, tmp):
if not s:
result.append(tmp)
return
for i in range(1, len(s) + 1):
if s[:i] == s[:i][::-1]:
backtrack(s[i:], tmp + [s[:i]])

backtrack(s, [])
return result


so = Solution()
print(so.partition("aab"))

fibonacci-number

方法一:递归(递归树如下)

fibonacci-number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding: utf-8 -*-
# @Time: 2020/5/14 12:38
# @Author: GraceKoo
# @File: 509_fibonacci-number.py
# @Desc: https://leetcode-cn.com/problems/fibonacci-number/


class Solution:
def fib(self, N: int) -> int:
if N == 0:
return 0
if N == 1:
return 1
return self.fib(N-1) + self.fib(N-2)


so = Solution()
print(so.fib(5))

递归虽然有简洁的优点,但是递归是函数调用自身,而函数调用是有时间和空间消耗的,每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址及临时变量,而往栈里压入数据和弹出数据都需要时间。另外,递归中有可能很多计算都是重复的,从而也会对性能产生影响。

方法二:记忆化自底向上的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding: utf-8 -*-
# @Time: 2020/5/14 12:38
# @Author: GraceKoo
# @File: 509_fibonacci-number.py
# @Desc: https://leetcode-cn.com/problems/fibonacci-number/


class Solution:
def fib(self, N: int) -> int:
if N <= 1:
return N
f_dict = {0: 0, 1: 1}
for i in range(2, N):
f_dict[i] = f_dict[i - 1] + f_dict[i - 2]
return f_dict[N - 1]


so = Solution()
print(so.fib(4))

Interview_10

解题思路:

类似于青蛙跳台阶,当n=1时,只有一种横向排列的方式。

当n等于二时,2*2有两种选择,横向或者是竖向。

当n等于3的时候对于2*3来说,如果选择的是竖向排列,则剩下的就是2*2排列。

如果选择的是横向,则对于2*n剩下的则只有1*n的一种选择。

2*n的大矩形就相当于“跳台阶“问题中的台阶,大矩形的长度n相当于台阶的个数n;从左至右的去覆盖,把小矩形竖着放相当于跳一个台阶,把小矩阵横着放相当于跳两个台阶。故:当前n的覆盖种数 = 当前n-1的覆盖总数 + 当前n-2的覆盖总数。即:f (n) = f (n-1) + f (n-2)

rectCover

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/5/27 12:48
# @Author: GraceKoo
# @File: rectCover.py
# @Desc: https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=/ta/
# coding-interviews&qru=/ta/coding-interviews/question-ranking


class Solution:
def rectCover(self, number):
# write code here
if number == 1:
return 1
elif number == 2:
return 2
return self.rectCover(number-1) + self.rectCover(number-2)


so = Solution()
print(so.rectCover(3))

或着使用自底向上的方法,节省空间

1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number <= 2:
return number
dp = [0 for _ in range(number)]
dp[0] = 1
dp[1] = 2
for i in range(2, number):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1]

2DMatric

5_longest_palindrome

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/17 9:07 上午
# @Author: GraceKoo
# @File: 5_longest_palindrome.py
# @Desc: https://leetcode-cn.com/problems/longest-palindromic-substring/


class Solution:
def longestPalindrome(self, s: str) -> str:
longest_str = ""
longestLen = 0
matrics = [[0 for i in range(0, len(s))] for i in range(0, len(s))]

for j in range(0, len(s)):
for i in range(0, j + 1):
if j - i <= 1:
if s[i] == s[j]:
matrics[i][j] = 1
if longestLen < j - i + 1:
longestLen = j - i + 1
longest_str = s[i : j + 1]
else:
if s[i] == s[j] and matrics[i + 1][j - 1]:
matrics[i][j] = 1
if longestLen < j - i + 1:
longestLen = j - i + 1
longest_str = s[i : j + 1]
return longest_str


s = "abccba"
so = Solution()
print(so.longestPalindrome(s))

rotate-image

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/19 15:23
# @Author: GraceKoo
# @File: 48_rotate-image.py
# @Desc:https://leetcode-cn.com/problems/rotate-image/


class Solution:
def ero_matrics(self, matric):
if not matric:
return matric
# 先转置
for i in range(0, len(matric)):
for j in range(i, len(matric)):
tmp = matric[i][j]
matric[i][j] = matric[j][i]
matric[j][i] = tmp
# 再反转每一行
for i in range(0, len(matric)):
for j in range(0, len(matric) // 2):
tmp = matric[i][j]
matric[i][j] = matric[i][len(matric) - j - 1]
matric[i][len(matric) - j - 1] = tmp

return matric


so = Solution()
print(so.ero_matrics([[4, 8, 12, 16],
[3, 7, 11, 15],
[2, 6, 10, 14],
[1, 5, 9, 13]]))
print(so.ero_matrics([
[3, 6, 9],
[2, 5, 8],
[1, 4, 7]]))

spiral-matrix

解题思路来源于leetcode官网:按层模拟(注:参考链接

leetcode-54

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/26 14:27
# @Author: GraceKoo
# @File: 54_spiral-matrix.py
# @Desc:https://leetcode-cn.com/problems/spiral-matrix/
from typing import List


class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
def spiral_matrix(r1, c1, r2, c2):
for c in range(c1, c2 + 1):
yield r1, c
for r in range(r1 + 1, r2 + 1):
yield r, c2
if r1 < r2 and c1 < c2:
for c in range(c2 - 1, c1, -1):
yield r2, c
for r in range(r2, r1, -1):
yield r, c1

if not matrix:
return []
output = []
r1, r2 = 0, len(matrix) - 1
c1, c2 = 0, len(matrix[0]) - 1
while r1 <= r2 and c1 <= c2:
for r, c in spiral_matrix(r1, c1, r2, c2):
output.append(matrix[r][c])
r1 += 1
r2 -= 1
c1 += 1
c2 -= 1
return output


so = Solution()
print(so.spiralOrder([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]))

spiral-matrix-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
# -*- coding: utf-8 -*-
# @Time: 2020/3/1 18:14
# @Author: GraceKoo
# @File: 59_spiral-matrix-ii.py
# @Desc:https://leetcode-cn.com/problems/spiral-matrix-ii/
from typing import List


class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
if n < 1:
return []

def spiral_matrix(r1, c1, r2, c2):
for c in range(c1, c2 + 1):
yield r1, c
for r in range(r1 + 1, r2 + 1):
yield r, c2
if r1 < r2 and c1 < c2:
for c in range(c2 - 1, c1, -1):
yield r2, c
for r in range(r2, r1, -1):
yield r, c1

output_matrix = [[0 for i in range(n)] for i in range(n)]
r1, r2 = 0, len(output_matrix) - 1
c1, c2 = 0, len(output_matrix[0]) - 1
number = 1
while r1 <= r2 and c1 <= c2:
for r, c in spiral_matrix(r1, c1, r2, c2):
output_matrix[r][c] = number
number += 1
r1 += 1
r2 -= 1
c1 += 1
c2 -= 1
return output_matrix


so = Solution()
print(so.generateMatrix(3))

set-matrix-zeroes

解题思路如下:

matrics第一行与第一列用于存储对应行或列是否有0

flag用于存储第一行或者第一列是否存在0

  • 首先遍历第一行与第一列是否存在0,若存在将flag置为0
  • 再遍历其他行,若存在0,将相应第一行和第一列的元素置为0
  • 再次遍历第一行与第一列,将0所在的行和列中的所有元素置为0
  • 最后,若flag为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
# -*- coding: utf-8 -*-
# @Time: 2020/3/17 12:08
# @Author: GraceKoo
# @File: 73_set-matrix-zeroes.py
# @Desc:https://leetcode-cn.com/problems/set-matrix-zeroes/
from typing import List


class Solution:
def setZeroes(self, matrix: List[List[int]]) -> List:
"""
Do not return anything, modify matrix in-place instead.
"""
flag_col = False
rows = len(matrix)
cols = len(matrix[0])
for row in range(rows):
if matrix[row][0] == 0:
flag_col = True
for col in range(1, cols):
if matrix[row][col] == 0:
matrix[row][0] = matrix[0][col] = 0
for row in range(rows - 1, -1, -1):
for col in range(cols - 1, 0, -1):
if matrix[row][0] == 0 or matrix[0][col] == 0:
matrix[row][col] = 0
if flag_col:
matrix[row][0] = 0
return matrix


so = Solution()
print(so.setZeroes([
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]))

interview_1

如果从左上角开始找,“从上到下”和“从左到右”,遇到的数字都是逐渐增大的;

如果从右下角开始找,“从下到上”和“从右到左”,遇到的数字都是逐渐减小的;

所以,可以从左下或者右上开始搜索,以保证不走“回头路”

er-wei-shu-zu-zhong-de-cha-zhao-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
34
35
36
37
38
39
40
41
42
# -*- coding: utf-8 -*-
# @Time: 2020/5/7 12:31
# @Author: GraceKoo
# @File: interview.py
# @Desc: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
from typing import List


class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or target is None:
return False

rows = len(matrix)
cols = len(matrix[0])
if rows == 0 or cols == 0:
return False

# 从右上角开始搜索
x = 0
y = cols - 1
while x < rows and y >= 0:
if matrix[x][y] == target:
return True
# 从matrix[x][y]的左下角部分进行搜索
if matrix[x][y] > target:
y -= 1
else:
x += 1
return False


so = Solution()
print(so.findNumberIn2DArray([
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
], 21
))

interview_19

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
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 17:32
# @Author: GraceKoo
# @File: interview_19.py
# @Desc: https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking
from typing import List


class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# 生成器
def spiral_matrix(r1, c1, r2, c2):
# 先输出r1行的坐标
for c in range(c1, c2 + 1):
yield r1, c
# 再输出c2列的坐标
for r in range(r1 + 1, r2 + 1):
yield r, c2
# 判断r1与r2,c1与c2是否重合
if r1 < r2 and c1 < c2:
# 先输出r2行的坐标
for c in range(c2 - 1, c1, -1):
yield r2, c
# 再输出c1列的坐标
for r in range(r2, r1, -1):
yield r, c1

if not matrix:
return []
output = []
r1, r2 = 0, len(matrix) - 1
c1, c2 = 0, len(matrix[0]) - 1
# 控制大局(矩形范围):r1、r2、c1、c2
while r1 <= r2 and c1 <= c2:
# 用for去遍历这个生成器
for r, c in spiral_matrix(r1, c1, r2, c2):
output.append(matrix[r][c])
r1 += 1
r2 -= 1
c1 += 1
c2 -= 1
return output


so = Solution()
print(so.spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))

interview_51

参考链接

计算下三角

计算上三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
# @Time: 2020/9/25 14:37
# @Author: GraceKoo
# @File: interview_51.py
# @Desc: https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/
from typing import List


class Solution:
def constructArr(self, a: List[int]) -> List[int]:
b, tmp = [1] * len(a), 1
# 先计算下三角
for i in range(1, len(a)):
b[i] = b[i - 1] * a[i - 1]
# 再计算上三角
for i in range(len(a) - 2, -1, -1):
tmp *= a[i + 1]
b[i] *= tmp
return b


so = Solution()
print(so.constructArr([1, 2, 3, 4, 5]))

interview_35

方法一:暴力法

时间复杂度$O(n^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
# -*- coding: utf-8 -*-
# @Time: 2020/8/24 20:27
# @Author: GraceKoo
# @File: interview_35.py
# @Desc: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
from typing import List


class Solution:
def reversePairs(self, nums: List[int]) -> int:
if not nums:
return 0
len_nums = len(nums)
if len_nums <= 1:
return 0
result = 0
# 冒泡排序,寻找逆序数对
for i in range(len_nums):
for j in range(i + 1, len_nums):
if nums[j] < nums[i]:
result += 1
return result


so = Solution()
print(so.reversePairs([7, 5, 6, 4]))

方法二:归并排序

解题思路

归并排序的时间复杂度是$O(NlogN)$

首先复习下归并排序:

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
"""
用于分解
"""
def mergeSort(nums):
len_nums = len(nums)
# 递归的出口
if len_nums <= 1:
return nums
mid = len_nums // 2
# 分解成两个更小的数组
nums1 = mergeSort(nums[:mid])
nums2 = mergeSort(nums[mid:]
return merge(nums1, nums2)


"""
用于合并:将产生一个排好序的数组
"""
def merge(nums1, nums2):
sum_nums = [] # 用于存储两个列表合并后的结果
i, j = 0, 0
# 两个列表,逐个元素进行对比,较小的元素将添加到结果中
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
sum_nums.append(nums1[i])
i += 1
else:
sum_nums.append(nums2[j])
j += 1
# 将未添加完的元素增加到result_list后面,
# 因为每次都要移动已经添加好的元素。此方法的时间复杂度是O(n^2),下段代码会改进。这里为了便于理解
sum_nums += nums1[i:]
sum_nums += nums2[j:]
return sum_nums

在合并部分,归并是利用一个sum_nums逐个将较小的元素添加至尾部,从而得到一个顺序数组。如果现在要从数组尾部开始遍历,同样产生一个顺序数组,要怎么做呢。

可以看到,改动点只是在merge函数里,将两个列表每次比较后较大的元素,从后往前的添加到sum_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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
用于分解
"""
def mergeSort(nums):
len_nums = len(nums)
# 递归的出口
if len_nums <= 1:
return nums
mid = len_nums // 2
# 分解成两个更小的数组
nums1 = mergeSort(nums[:mid])
nums2 = mergeSort(nums[mid:]
return merge(nums1, nums2)

"""
用于合并:将产生一个排好序的数组
"""
def merge(nums1, nums2):
i, j = len(nums1) - 1, len(nums2) - 1
sum_nums = [0] * (i + j + 2) # 用于存储两个列表合并后的结果
sum_nums_index = len(sum_nums) - 1 # 当前临时列表的索
# 两个列表,逐个元素进行对比,大的元素将添加到结果中
while i >= 0 and j >= 0:
if nums1[i] > nums2[j]:
sum_nums[sum_nums_index] = nums1[i]
i -= 1
sum_nums_index -= 1
else:
sum_nums[sum_nums_index] = nums2[j]
j -= 1
sum_nums_index -= 1
# 将未添加完的元素增加到sum_nums前面,时间复杂度O(1)
while i >= 0:
sum_nums[sum_nums_index] = nums1[i]
i -= 1
sum_nums_index -= 1
while j >= 0:
sum_nums[sum_nums_index] = nums2[j]
j -= 1
sum_nums_index -= 1
return sum_num
mergeSort(nums)

现在应该一目了然了,接下来只要增加一个变量,将每次合并过程中的逆序对进行统计就可以了。因为在每次的合并过程中,nums1与nums2都是有序的,且 i,j分别指向两个数组。假如:

nums1 = [3, 6] nums2 = [2, 4]

对于6而言,6小于4( nums1[ i ] < nums2[ j ] ),构成一对逆序数。又因为两个数组都是有序的,所以我们知道,6大于nums2里 j 指向的当前最大的元素4,当然也会大于比4小的2。所以对于6而言,它能构成的逆序数对为 j + 1 == 2。( j = 0,……, len(nums2) - 1)

可以这样想,sum_nums只是保存了当前数组里的大小关系,这种顺序关系是为了便于逆序对个数的快速计算,它并没有改变原数组的顺序。

完整代码如下:利用全局变量count来记录合并过程中逆序对的个数。

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
# -*- coding: utf-8 -*-
# @Time: 2020/8/24 20:27
# @Author: GraceKoo
# @File: interview_35.py
# @Desc: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
from typing import List


class Solution:
def __init__(self):
self.count = 0 # 用于记录逆序对的个数

def reversePairs(self, nums: List[int]) -> int:
"""
用于分解
"""

def mergeSort(nums):

len_nums = len(nums)
# 递归的出口
if len_nums <= 1:
return nums
mid = len_nums // 2

# 分解成两个更小的数组
nums1 = mergeSort(nums[:mid])
nums2 = mergeSort(nums[mid:])

return merge(nums1, nums2)

"""
用于合并:将产生一个排好序的数组
"""

def merge(nums1, nums2):
i, j = len(nums1) - 1, len(nums2) - 1
sum_nums = [0] * (i + j + 2) # 用于存储两个列表合并后的结果
sum_nums_index = len(sum_nums) - 1 # 当前临时列表的索引

# 两个列表,逐个元素进行对比,大的元素将添加到结果中
while i >= 0 and j >= 0:
# 存在一对逆序
if nums1[i] > nums2[j]:
self.count += (j + 1) # 记录逆序对的个数,取决于当前的j
sum_nums[sum_nums_index] = nums1[i]
i -= 1
sum_nums_index -= 1
else:
sum_nums[sum_nums_index] = nums2[j]
j -= 1
sum_nums_index -= 1

# 将未添加完的元素增加到sum_nums后面
while i >= 0:
sum_nums[sum_nums_index] = nums1[i]
i -= 1
sum_nums_index -= 1
while j >= 0:
sum_nums[sum_nums_index] = nums2[j]
j -= 1
sum_nums_index -= 1
return sum_nums

mergeSort(nums)
return self.count


so = Solution()
print(so.reversePairs([1, 3, 2, 3, 1]))

Regular Expression

string-to-integer-atoi

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/20 1:20 下午
# @Author: GraceKoo
# @File: 8_string-to-integer-atoi.py
# @Desc: https://leetcode-cn.com/problems/string-to-integer-atoi/

import re


class Solution:
def myAtoi(self, s: str) -> int:
s = s.strip()
if len(s) > 0:
pattern = r"[+-]?\d+"
number = re.match(pattern, s)
if number:
number = int(number[0])
if number < -pow(2, 31):
return int(-pow(2, 31))
elif number > pow(2, 31) - 1:
return int(pow(2, 31) - 1)
return number
return 0


so = Solution()
print(so.myAtoi("+123"))

10_regular-expression-matchin

方法一:暴力求解, offer再见法

1
2
3
4
5
import re

class Solution:
def isMatch(self, s: str, p: str) -> bool:
return (re.fullmatch(p, s) != None)

方法二:回溯求解

参考链接

首先,考虑只有“.”的情况。这种情况下只需要从左到右依次判断s[i]与p[i]是否匹配即可。

1
2
3
4
5
6
7
8
class Solution(object):
def isMatch(self, s: str, p: str) -> bool:
# 如果p已经匹配完了,匹配结果取决于s是否为空
if not p:
return not s

first_match = s and (s[0] == p[0] or p[0] == ".")
return first_match and self.isMatch(s[1:], p[1:])

如果有“*”,它会出现在p[1]的位置,这时有两种情况:

  • ”匹配了0次前面的元素:这时直接比较”\​”后面的元素即可。如“##”与“a*##”,即self.isMatch(s, p[2:])
  • ”匹配了1次或多次前面的元素:这时忽略s的第一个元素,继续与p进行比较。如“aaab”与“a\b”,继续比较“aab”与“a*b”,可以理解为逐步走到了第一种情况。即self.isMatch(s[1:], p)
1
2
3
if len(p) > 2 and p[1] == "*":
return self.isMatch(s, p[2:]) or \
(first_match and self.isMatch(s[1:], p))

完整代码如下:

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/21 7:46 下午
# @Author: GraceKoo
# @File: 10_regular-expression-matchin.py
# @Desc:https://leetcode-cn.com/problems/regular-expression-matching/


class Solution(object):
def isMatch(self, s: str, p: str) -> bool:
if not p:
return not s # 结束条件

first_match = s and (s[0] == p[0] or p[0] == ".")

if len(p) >= 2 and p[1] == '*':
return self.isMatch(s, p[2:]) or \
(first_match and self.isMatch(s[1:], p))

else:
return first_match and self.isMatch(s[1:], p[1:])


so = Solution()
assert so.isMatch("mississippi", "mis*is*ip*.")

方法三:动态规划

参考链接

interview_52

regular-expression-matchin

valid-number

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/8 00:41
# @Author: GraceKoo
# @File: 65_valid-number.py
# @Desc:https://leetcode-cn.com/problems/valid-number/
import re


class Solution:
def isNumber(self, s: str) -> bool:
# return bool(re.match(r' *[+-]?([0-9]+(\.[0-9]*)?|\.[0-9]+)(e[+-]?[0-9]+)? *$', s))
s = s.strip()
# 去除s两边的空白符
if not s:
return False
# 去除"+"、"-"
if s[0] in ["+", "-"]:
s = s[1:]
# 判断是否含有e
if "e" in s:
s_list = s.split("e")
# 说明有两个e
if len(s_list) > 2:
return False
# 去掉e前面的"."
s_list[0] = s_list[0].replace(".", "", 1)
# 去掉e后面的"+、"-"
if len(s_list[1]) > 0 and s_list[1][0] in ["+", "-"]:
s_list[1] = s_list[1].replace(s_list[1][0], "", 1)
# 判断是否为数字
if s_list[0].isnumeric() and s_list[1].isnumeric():
return True
else:
s = s.replace(".", "", 1)
if s.isnumeric():
return True
return False


so = Solution()
print(so.isNumber("53.5e93"))

interview_53

解法一:暴力法(面试慎用)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding: utf-8 -*-
# @Time: 2020/9/28 16:16
# @Author: GraceKoo
# @File: interview_53.py
# @Desc: https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
import re


class Solution:
def isNumber(self, s: str) -> bool:
if not s:
return False
try:
float(s)
except ValueError:
return False
return True

解法二:正则表达式

依次来看下面的正则表达式:

  • 从E、e来划分,先看前半部分

匹配字符串开头^,可以有多个空格\s​,且+-号只能出现一次

^\s*[+-]{0,1}

用于匹配诸如10.111、10.1、10等数字(小数点后面必须出现数字)

(\d)+((\.)(\d)+){0,1}

用于匹配.1、.111111等数字

((\.)(\d)+)

用于匹配10.、1.等数字(小数点后面没有数字)

((\d)+(\.))

  • 再看后半部分

e或E后面可以跟+-号,且后面必须跟数字。整个指数部分可以出现0-1次。

([eE][+-]{0,1}(\d)+){0,1}

整个字符串结束前可以跟0或多个空格

\s*$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/9/28 16:16
# @Author: GraceKoo
# @File: interview_53.py
# @Desc: https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
import re


class Solution:
def isNumber(self, s: str) -> bool:
matchObj = re.match("^\s*[+-]{0,1}((\d)+((\.)(\d)+){0,1}|((\.)(\d)+)|((\d)+(\.)))([eE][+-]{0,1}(\d)+){0,1}\s*$",s)
if matchObj:
print("match --> matchObj.group() : ", matchObj.group())
return True
else:
print("No match!!")
return False

# 字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值,但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
so = Solution()
print(so.isNumber("13.e2"))

解法三:有限状态自动机

Stack

valid-parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2019/12/26 11:53 下午
# @Author: GraceKoo
# @File: 20_valid-parentheses.py
# @Desc:


class Solution:
def isValid(self, s: str) -> bool:
stack = []
dic = {"{": "}", "[": "]", "(": ")"}
for c in s:
if c in dic:
stack.append(c)
elif dic[stack.pop()] != c:
return False
return len(stack) == 0


so = Solution()
print(so.isValid("()[]{}"))

largest-rectangle-in-histogram

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/29 16:24
# @Author: GraceKoo
# @File: 84_largest-rectangle-in-histogram.py
# @Desc:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
from typing import List


class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
res = 0
heights = [0] + heights + [0]
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
tmp = stack.pop()
res = max(res, (i - stack[-1] - 1) * heights[tmp])
stack.append(i)
return res


so = Solution()
print(so.largestRectangleArea([2, 1, 5, 6, 2, 3]))


maximal-rectangle

注:参考链接

leetcode-85

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/30 22:22
# @Author: GraceKoo
# @File: 85_maximal-rectangle.py
# @Desc:https://leetcode-cn.com/problems/maximal-rectangle/
from typing import List


class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
max_area = 0
dp = [0] * len(matrix[0])
for row in range(0, len(matrix)):
for col in range(0, len(matrix[0])):
dp[col] = dp[col] + 1 if matrix[row][col] == "1" else 0
max_area = max(max_area, self.largestRectangleArea(dp))
return max_area

# from 84_largest-rectangle-in-histogram
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
res = 0
heights = [0] + heights + [0]
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
tmp = stack.pop()
res = max(res, (i - stack[-1] - 1) * heights[tmp])
stack.append(i)
return res


so = Solution()
print(so.maximalRectangle([
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"]
]))

implement-queue-using-stacks

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/12 12:40
# @Author: GraceKoo
# @File: 232_implement-queue-using-stacks.py
# @Desc: https://leetcode-cn.com/problems/implement-queue-using-stacks/


class MyQueue:

def __init__(self):
"""
Initialize your data structure here.
"""
self.stack1 = []
self.stack2 = []

def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack1.append(x)

def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.empty():
return
if len(self.stack2) == 0:
# 把stack1里面的元素全部pop至stack2
while len(self.stack1) != 0:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()

def peek(self) -> int:
"""
Get the front element.
"""
if self.empty():
return
if len(self.stack2) == 0:
while len(self.stack1) != 0:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]

def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
if len(self.stack1) == 0 and len(self.stack2) == 0:
return True
return False


# 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()

interview_20

解题思路:除了一个常规列表实现栈的操作外,再开一个辅助栈用于保存当前的最小信息:

  • 入栈操作:当辅助栈为空或者新元素小于等于辅助栈顶元素时,辅助栈入栈;否则无视
  • 出栈操作:当常规栈中待出栈的元素等于辅助栈顶元素时,辅助栈出栈一个元素,代表当前的最小值出队或者次数减1
  • 栈顶操作:仅需从常规栈顶取元素即可
  • 最小值操作:因为辅助栈中维护的都是当前状态下的最小值,所以从辅助栈顶取元素即可
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
# -*- coding: utf-8 -*-
# @Time: 2020/6/7 21:36
# @Author: GraceKoo
# @File: interview_20.py
# @Desc: https://leetcode-cn.com/problems/
# bao-han-minhan-shu-de-zhan-lcof/


class MinStack:

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

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

def pop(self) -> None:
if not self.stack:
return
x = self.stack.pop()
if self.mins and self.mins[-1] == x:
self.mins.pop()

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

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


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

interview_21

解题思路

我们使用一个辅助栈 来模拟该操作。将 pushed 数组中的每个数依次入栈,同时判断这个数是不是 popped 数组中下一个要 pop 的值,如果是就把它 pop 出来。最后检查栈是否为空。

算法

  • 初始化栈 stack,j = 0;

  • 遍历 pushed 中的元素 x;

    • 当 j < popped.size() 且栈顶元素等于 popped[j]:弹出栈顶元素;j += 1;
  • 如果栈为空,返回 True,否则返回 False。

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


class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
i_pop = 0
stack = []
for value in pushed:
stack.append(value)
while stack and popped[i_pop] == stack[-1]:
stack.pop()
i_pop += 1
return not stack


so = Solution()
print(so.validateStackSequences(pushed=[1, 2, 3, 4, 5], popped=[4, 5, 3, 2, 1]))

interview_5

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
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 11:33
# @Author: GraceKoo
# @File: interview_5.py
# @Desc: https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack1 = []
self.stack2 = []

def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack1.append(x)

def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.empty():
return
if len(self.stack2) == 0:
# 把stack1里面的元素全部pop至stack2
while len(self.stack1) != 0:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()

def peek(self) -> int:
"""
Get the front element.
"""
if self.empty():
return
if len(self.stack2) == 0:
while len(self.stack1) != 0:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]

def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
if len(self.stack1) == 0 and len(self.stack2) == 0:
return True
return False


# 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()


BinaryTree

generate-parentheses

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/2 12:06 下午
# @Author: GraceKoo
# @File: 22_generate-parentheses.py
# @Desc: https://leetcode-cn.com/problems/generate-parentheses/
# (
# ( )
# ) (
# ) )


class Solution:
def generateParenthesis(self, n: int):
output_li = []

def find_Parenthesis(s="", left=0, right=0):
if len(s) == 2 * n:
output_li.append(s)
return
if left < n:
find_Parenthesis(s + "(", left + 1, right)
if right < left:
find_Parenthesis(s + ")", left, right + 1)

find_Parenthesis()
return output_li


so = Solution()
print(so.generateParenthesis(2))

interview_4

解题思路:

  • 前序遍历的第一个节点为根节点
  • 根据前序遍历确定的根节点,可以在中序遍历中确定其左右子树

rebuildbinarytree

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/10 22:47
# @Author: GraceKoo
# @File: interview_4.py
# @Desc: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/


class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution(object):
def buildTree(self, preorder, inorder):
if not preorder:
return None
# 前序遍历第一个肯定为根节点
root_value = preorder[0]
root = TreeNode(root_value)

# 根据中序遍历结果确定根节点的左右子树
root_index = inorder.index(root_value)
# 在中序列表中的左右子树
left_in_inorder = inorder[:root_index]
right_in_inorder = inorder[root_index+1:]
# 在前序列表中的左右子树
left_in_preorder = preorder[1:root_index+1] # 左子树数量就是root_index的个数
right_in_preorder = preorder[root_index+1:]

# 递归创建子树
root.left = self.buildTree(left_in_preorder, left_in_inorder)
root.right = self.buildTree(right_in_preorder, right_in_inorder)
return root

interview_57

输入一个节点,分析该节点的下一个节点,一共有以下情况:

  1. 二叉树为空,则返回空;

  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
36
# -*- coding: utf-8 -*-
# @Time: 2020/5/11 19:47
# @Author: GraceKoo
# @File: interview_57.py
# @Desc: https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class TreeLinkNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None # 中序遍历序列的下一个节点


class Solution:
def GetNext(self, pNode):
# write code here
if not pNode:
return None
# 如果当前节点有右节点,则下一个节点为其右节点的最左侧的节点
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
return pNode
# 如果当前节点没有右节点
while pNode.next:
# 如果当前节点位于左子树上
if pNode.next.left == pNode: # pNode.next为父节点
return pNode.next
# 否则循环找,直到当前节点为其父节点的左子树
pNode = pNode.next
return None

longest-univalue-path

参考链接

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/19 23:48
# @Author: GraceKoo
# @File: 687_longest-univalue-path.py
# @Desc: https://leetcode-cn.com/problems/longest-univalue-path/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def longestUnivaluePath(self, root: TreeNode) -> int:
self.ans = 0

def arrow_length(node: TreeNode):
if node is None:
return 0
left_length = arrow_length(node.left)
right_length = arrow_length(node.right)
left_arrow = right_arrow = 0
if node.left and node.val == node.left.val:
left_arrow = left_length + 1
if node.right and node.val == node.right.val:
right_arrow = right_length + 1
self.ans = max(self.ans, left_arrow+right_arrow)
return max(left_arrow, right_arrow)
arrow_length(root)
return self.ans


interview_17

解题思路

若树 B 是树 A 的子结构,则子结构的根节点可能为树 A 的任意一个节点。因此,判断树 B 是否是树 A 的子结构,需完成以下两步工作:

  1. 先序遍历树 A中的每个节点 A。(对应函数 isSubStructure(A, B))
  2. 判断树 A 中 以A为根节点的子树 是否包含树 B 。(对应函数 recur(A, B))
  • isSubStructure(A, B) 函数:

特例处理: 当 树 A 为空 或 树 B 为空 时,直接返回 false ;
返回值: 若树 B 是树 A 的子结构,则必满足以下三种情况之一,因此用或 || 连接;
以 节点 A 为根节点的子树 包含树 B ,对应 recur(A, B);
树 B 是 树 A 左子树 的子结构,对应 isSubStructure(A.left, B);
树 B 是 树 A 右子树 的子结构,对应 isSubStructure(A.right, B);

  • recur(A, B) 函数:
  1. 终止条件:
    当节点 B 为空:说明树 B 已匹配完成(越过叶子节点),因此返回 true;
    当节点 A 为空:说明已经越过树 A 叶子节点,即匹配失败,返回 false ;
    当节点 A 和 B 的值不同:说明匹配失败,返回 false ;
  2. 返回值:
    判断 A 和 B 的左子节点是否相等,即 recur(A.left, B.left) ;
    判断 A 和 B 的右子节点是否相等,即 recur(A.right, B.right) ;

interview_17

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/2 12:32
# @Author: GraceKoo
# @File: interview_17.py
# @Desc: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not A or not B:
return False
return self.recure(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

def recure(self, A: TreeNode, B: TreeNode) -> bool:
if not B:
return True
if not A or A.val != B.val:
return False
return self.recure(A.left, B.left) and self.recure(A.right, B.right)

invert-binary-tree

  • 递归解法
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
# -*- coding: utf-8 -*-
# @Time: 2020/6/3 12:28
# @Author: GraceKoo
# @File: 226_invert-binary-tree.py
# @Desc: https://leetcode-cn.com/problems/invert-binary-tree/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return root
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return root

  • 迭代解法
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
# -*- coding: utf-8 -*-
# @Time: 2020/6/3 12:28
# @Author: GraceKoo
# @File: 226_invert-binary-tree.py
# @Desc: https://leetcode-cn.com/problems/invert-binary-tree/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return root
queue = [root]
# 广度优先搜索
while queue:
temp_root = queue.pop()
temp_root.left, temp_root.right = temp_root.right, temp_root.left
# 继续把子孩子入队
if temp_root.left:
queue.append(temp_root.left)
if temp_root.right:
queue.append(temp_root.right)
return root

interview_22_i

利用队列,广度优先遍历二叉树

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/8 19:19
# @Author: GraceKoo
# @File: interview_32_i.py
# @Desc: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
from typing import List
import collections


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:
return []
res, deque = [], collections.deque()
deque.append(root)
while deque:
node = deque.popleft()
res.append(node.val)
if node.left:
deque.append(node.left)
if node.right:
deque.append(node.right)
return res


interview_22_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
# -*- coding: utf-8 -*-
# @Time: 2020/6/8 19:28
# @Author: GraceKoo
# @File: interview_32_ii.py
# @Desc: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
from typing import List
import collections


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res, deque = [], collections.deque()
deque.append(root)
while deque:
tem = []
for _ in range(len(deque)):
node = deque.popleft()
tem.append(node.val)
if node.left:
deque.append(node.left)
if node.right:
deque.append(node.right)
res.append(tem)
return res

interview_22_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
25
26
27
28
29
30
31
32
33
34
35
# -*- coding: utf-8 -*-
# @Time: 2020/6/8 19:48
# @Author: GraceKoo
# @File: interview_32_iii.py
# @Desc: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
from typing import List
import collections


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res, deque = [], collections.deque()
deque.append(root)
while deque:
tem = []
for _ in range(len(deque)):
node = deque.popleft()
tem.append(node.val)
if node.left:
deque.append(node.left)
if node.right:
deque.append(node.right)
res.append(tem[::-1] if len(res) % 2 else tem)
return res

interview_59

此题同interview_22_iii

interview_23

解题思路

interview_23

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/15 22:18
# @Author: GraceKoo
# @File: interview_23.py
# @Desc: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
from typing import List


class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
if not postorder:
return False

# 待分析的区间
def recur(i, j):
# 已经对比完毕,返回True
if i >= j:
return True
# 根结点在最右边,左子树应该都比它小
p = i
while postorder[p] < postorder[j]:
p += 1
left_end = p
# 右子树应该都比它小
while postorder[p] > postorder[j]:
p += 1
# 若是后序遍历序列,那p应该已经和j相等了; 并且遍历左右子树序列也应该是后序遍历序列
return p == j and recur(i, left_end - 1) and recur(left_end, j - 1)

return recur(0, len(postorder) - 1)


so = Solution()
print(so.verifyPostorder([1, 3, 2, 6, 5]))

interview_24

本问题是典型的二叉树方案搜索问题,使用回溯法解决,其包含 先序遍历 + 路径记录 两部分。

参考链接

interview_24

res.append(list(path)):记录路径时若直接执行 res.append(path) ,则是将 path 列表对象 加入了 res ;后续 path 对象改变时, res 中的 path 对象 也会随之改变(因此肯定是不对的,本来存的是正确的路径 path ,后面又 append 又 pop 的,就破坏了这个正确路径)。list(path) 相当于新建并复制了一个 path 列表,因此不会受到 path 变化的影响。

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/15 23:03
# @Author: GraceKoo
# @File: interview_24.py
# @Desc: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/

from typing import List


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res, path = [], [] # 用于存放最终的结果,与当前遍历的路径

# 输入当前的遍历的节点,与当前的目标值
def recur(root, tar):
if not root:
return
path.append(root.val)
tar -= root.val
if tar == 0 and not root.left and not root.right:
res.append(list(path))
# 如果已经找到了一条路径,那么下面两行会直接return,所以这样写也没关系
recur(root.left, tar)
recur(root.right, tar)
path.pop()

recur(root, sum)
return res


interview_26

参考链接

算法流程:
dfs(cur): 递归法中序遍历;

  1. 终止条件: 当节点 cur为空,代表越过叶节点,直接返回;

  2. 递归左子树,即 dfs(cur.left)

  3. 构建链表

    1. 当 pre 为空时: 代表正在访问链表头节点,记为 head 。
    2. 当 pre 不为空时: 修改双向节点引用,即 pre.right = cur ,cur.left = pre;

    3. 保存 cur : 更新 pre = cur ,即节点 cur 是后继节点的 pre;

  4. 递归右子树,即 dfs(cur.right) ;

treeToDoublyList(root):

  1. 特例处理: 若节点 root为空,则直接返回;
  2. 初始化: 空节点 pre;
  3. 转化为双向链表: 调用 dfs(root) ;
  4. 构建循环链表: 中序遍历完成后,head指向头节点, pre指向尾节点,因此修改 head 和 pre的双向节点引用即可。
  5. 返回值: 返回链表的头节点 head 即可。
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
# -*- coding: utf-8 -*-
# @Time: 2020/6/22 22:33
# @Author: GraceKoo
# @File: interview_26.py
# @Desc: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/


"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""


class Solution:
def __init(self):
self.pre = None
self.head = None

def Convert(self, pRootOfTree):
# write code here
def dfs(current_node):
# 递归出口:代表到达尾结点
if not current_node:
return
dfs(current_node.left)

# 如果pre是空,证明当前访问的是第一个结点
if not self.pre:
self.head = current_node
# 如果不是空,则证明当前结点不是头结点,可进行修改
else:
self.pre.right, current_node.left = current_node, self.pre
# 保存当前结点为pre
self.pre = current_node

# 再去递归右子树
dfs(current_node.right)

if not pRootOfTree:
return
dfs(pRootOfTree)
# 最后将头结点和尾结点进行连接
self.pre.right, self.head.left = self.head, self.pre
return self.head

interview_18

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
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 16:43
# @Author: GraceKoo
# @File: interview_18.py
# @Desc: https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
# 递归
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = root.right, root.left
self.mirrorTree(root.left)
self.mirrorTree(root.right)
return root

# 迭代
def mirrorTree_diedai(self, root: TreeNode) -> TreeNode:
if not root:
return None
# 广度优先,将节点依次插入
queue = [root]
while queue:
node = queue.pop(0)
# 先交换
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root

interview_22

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
# -*- coding: utf-8 -*-
# @Time: 2020/6/8 19:19
# @Author: GraceKoo
# @File: interview_22.py
# @Desc: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
from typing import List
import collections


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:
return []
res, deque = [], collections.deque()
deque.append(root)
while deque:
node = deque.popleft()
res.append(node.val)
if node.left:
deque.append(node.left)
if node.right:
deque.append(node.right)
return res

maximum-depth-of-binary-tree

interview_38

此题同maximum-depth-of-binary-tree

  1. 深度优先遍历DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/8/26 20:27
# @Author: GraceKoo
# @File: interview_38.py
# @Desc: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

  1. 广度优先遍历BFS
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
# -*- coding: utf-8 -*-
# @Time: 2020/8/26 20:27
# @Author: GraceKoo
# @File: interview_38.py
# @Desc: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
queue = [root]
result = 0
while queue:
# 遍历每层的结点
tmp = []
for node in queue:
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
# 将每层的元素重新赋值给queue
queue = tmp
result += 1
return result

interview_39

思路参考

  • 方法一:从顶至底

思路是构造一个获取当前子树的深度的函数 depth(root) ,通过比较某子树的左右子树的深度差 abs(depth(root.left) - depth(root.right)) <= 1 是否成立,来判断某子树是否是二叉平衡树。若所有子树都平衡,则此树平衡。

算法流程:
isBalanced(root) 函数: 判断树 root 是否平衡

特例处理: 若树根节点 root 为空,则直接返回 true ;
返回值: 所有子树都需要满足平衡树性质,因此以下三者使用与逻辑 && 连接;

  1. abs(self.depth(root.left) - self.depth(root.right)) <= 1 :判断 当前子树 是否是平衡树;
  2. self.isBalanced(root.left) : 先序遍历递归,判断 当前子树的左子树 是否是平衡树;
  3. self.isBalanced(root.right) : 先序遍历递归,判断 当前子树的右子树 是否是平衡树;
  4. depth(root) 函数: 计算树 root 的深度

终止条件: 当 root 为空,即越过叶子节点,则返回高度 0 ;
返回值: 返回左 / 右子树的深度的最大值 +1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
# 判断以root为根的二叉树是否平衡
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
return abs(self.depth(root.left) - self.depth(root.right)) <= 1 \
and self.isBalanced(root.left) \
and self.isBalanced(root.right)

# 计算以root为根的二叉树的深度
def depth(self, root):
if not root:
return 0
return max(self.depth(root.left), self.depth(root.right)) + 1
  • 方法二:从底至顶(见思路参考)

interview_58

解题思路参考

  • 对称二叉树定义: 对于树中 任意两个对称节点 L和 R ,一定有:
    L.val = R.val:即此两对称节点值相等。
    L.left.val = R.right.val:即 L 的 左子节点 和 R 的 右子节点 对称;
    L.right.val = R.left.val:即 L 的 右子节点 和 R 的 左子节点 对称。
    根据以上规律,考虑从顶至底递归,判断每对节点是否对称,从而判断树是否为对称二叉树。

  • 算法流程:

    • isSymmetric(root) :

      特例处理 若根节点 root 为空,则直接返回 true。
      返回值: 即 recur(root.left, root.right) ;

    • recur(L, R) :

      终止条件:

      1. 当 L 和 R 同时越过叶节点: 此树从顶至底的节点都对称,因此返回 true ;
      2. 当 L 或 R 中只有一个越过叶节点: 此树不对称,因此返回 false ;
      3. 当节点 L 值 = 节点 R 值: 此树不对称,因此返回 false;
    • 递推工作:
      判断两节点 L.left 和 R.right是否对称,即 recur(L.left, R.right) ;
      判断两节点 L.right 和 R.left是否对称,即 recur(L.right, R.left) ;
      返回值: 两对节点都对称时,才是对称树,因此用与逻辑符 && 连接。

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
# -*- coding: utf-8 -*-
# @Time: 2020/9/28 20:42
# @Author: GraceKoo
# @File: interview_58.py
# @Desc: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def recur(LeftNode, RightNode):
if not LeftNode and not RightNode:
return True
if not LeftNode or not RightNode or LeftNode.val != RightNode.val:
return False
# 不满足直接退出的条件,则继续向下递归
return recur(LeftNode.left, RightNode.right) and recur(LeftNode.right, RightNode.left)

return recur(root.left, root.right) if root else True


interview_61

参考链接

序列化操作:类似于BFS,不同之处则是需要增加空结点的处理。

反序列化操作:由于序列化时建立了一颗“满二叉树”,则可基于叶结点和父结点之间的关系,对已序列化的结果进行反序列化。关系见下:

  • 如果从下标bai从1开始存储,则编号为i的结点的主要关系为:
    双亲:向下取整 (i/2)
    左孩子:2i
    右孩子:2i+1
  • 如果从下标从0开始存储,则编号为i的结点的主要关系为:
    双亲:向下取整 ((i-1)/2)
    左孩子:2i+1
    右孩子:2i+2

反序列化算法逻辑为:

  1. 特例处理: 若 data为空,直接返回 null;
  2. 初始化: 序列化列表 vals(先去掉首尾中括号,再用逗号隔开),指针 i = 1 ,根节点 root(值为 vals[0] ),队列 queue(包含 root);
  3. 按层构建: 当 queue 为空时跳出;
    1. 节点出队,记为 node;
    2. 构建 node的左子节点:node.left 的值为 vals[i],并将 node.left入队;
    3. 执行 i+=1;
    4. 构建 node的右子节点:node.left的值为 vals[i],并将 node.left入队;
    5. 执行 i+=1;
  4. 返回值: 返回根节点root即可。
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
# -*- coding: utf-8 -*-
# @Time: 2020/9/28 20:43
# @Author: GraceKoo
# @File: interview_61.py
# @Desc: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
from collections import deque


# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Codec:

def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
if not root:
return "[]"
# 广度优先搜索
result, de = [], deque()
de.append(root)
while de:
# for _ in range(len(de)):
# node = de.popleft()
# result.append(node.val)
# if node.left:
# de.append(node.left)
# else:
# result.append("null")
# if node.right:
# de.append(node.right)
# else:
# result.append("null")
# 以上可简化为
node = de.popleft()
if node:
result.append(str(node.val))
de.append(node.left)
de.append(node.right)
else:
result.append("null")

return "["+",".join(result)+"]"

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
if data == "[]":
return
values, i = data[1:-1].split(","), 1 # vals存放所有结点
root = TreeNode(values[0])
de = deque() # 存放各个结点
de.append(root)
# 类广度优先遍历,建立结点之间的关系
while de:
node = de.popleft()
if values[i] != "null":
node.left = TreeNode(int(values[i]))
de.append(node.left)
i += 1
if values[i] != "null":
node.right = TreeNode(int(values[i]))
de.append(node.right)
i += 1
return root

interview_62

参考链接

二叉搜索树的中序遍历为递增序列。因此求二叉搜索树的第K大的结点为为求此二叉搜索树中序遍历倒序的第K大的结点。(即中序遍历是会产生一个从小到大的排列[1, 2, 3, 4, 5],中序遍历的倒序则是产生一个从大到小的排列[5, 4, 3, 2, 1])

中序遍历递归顺序为:

1
2
3
4
5
6
# 打印中序遍历
def dfs(root):
if not root: return
dfs(root.left) # 左
print(root.val) # 根
dfs(root.right) # 右

倒序为

1
2
3
4
5
6
# 打印中序遍历倒序
def dfs(root):
if not root: return
dfs(root.right) # 右
print(root.val) # 根
dfs(root.left) # 左
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
# -*- coding: utf-8 -*-
# @Time: 2020/9/28 20:43
# @Author: GraceKoo
# @File: interview_62.py
# @Desc: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def __init__(self):
self.k = None
self.result_node = None

def kthLargest(self, root: TreeNode, k: int) -> int:
# 对二叉搜索树进行反中序遍历,将产生一个从大到小的序列
def dfs(root):
# 递归结束条件
if not root or self.k == 0:
return
# 先遍历右结点
dfs(root.right)

# 对当前结点进行判断,如果当前k已经减到0了,则找到第k大的结点了,返回
self.k -= 1
if self.k == 0:
self.result_node = root.val

# 再遍历左结点
dfs(root.left)

self.k = k
dfs(root)
return self.result_node

Tree

binary-tree

binary-tree-inorder-traversal

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/12 22:43
# @Author: GraceKoo
# @File: 94_binary-tree-inorder-traversal.py
# @Desc: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
from typing import List


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def backtrack(root):
if not root:
return
backtrack(root.left)
res.append(root.val)
backtrack(root.right)
backtrack(root)
return res


root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
so = Solution()
print(so.inorderTraversal(root))

unique-binary-search-trees-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
# -*- coding: utf-8 -*-
# @Time: 2020/4/14 12:28
# @Author: GraceKoo
# @File: 95_unique-binary-search-trees-ii.py
# @Desc:https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
from typing import List


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def generate_tree(start, end):
if start > end:
return [None, ]
all_trees = []

# pick a root
for i in range(start, end+1):
left_tree = generate_tree(start, i)
right_tree = generate_tree(i+1, end)
for left in left_tree:
for right in right_tree:
current_tree = TreeNode(i)
current_tree.left = TreeNode(left)
current_tree.right = TreeNode(right)
all_trees.append(current_tree)
return all_trees
return generate_tree(1, n) if n else []

unique-binary-search-trees

假设n个节点存在

令G(n)的从1到n可以形成二叉排序树个数

令f(i)为以i为根的二叉搜索树的个数

即有: G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

n为根节点,当i为根节点时,其左子树节点个数为[1,2,3,...,i-1],右子树节点个数为[i+1,i+2,...n],所以当i为根节点时,其左子树节点个数为i-1个,右子树节点为n-i,即f(i) = G(i-1)*G(n-i)

上面两式可得:G(n) = G(0)*G(n-1) + G(1)*(n-2) +...+ G(n-1)*G(0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2020/4/13 18:49
# @Author: GraceKoo
# @File: 96_unique-binary-search-trees.py
# @Desc: https://leetcode-cn.com/problems/unique-binary-search-trees/


class Solution:
def numTrees(self, n: int) -> int:
if n < 0:
return 0
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
for j in range(i):
dp[i] += dp[j] * dp[i - j - 1]
return dp[-1]


so = Solution()
print(so.numTrees(3))

validate-binary-search-tree

需要在遍历树的同时保留结点的上界与下界,在比较时不仅比较子结点的值,也要与上下界比较。这样才能保证节点的所有左子树都小于结点值,右子树都大于结点值。

参考链接

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/14 22:59
# @Author: GraceKoo
# @File: 98_validate-binary-search-tree.py
# @Desc: https://leetcode-cn.com/problems/validate-binary-search-tree/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
stack = [(root, float('-inf'), float('inf')), ]
# 深度优先遍历
while stack:
root, lower, upper = stack.pop()
# 防止append一个空子树
if not root:
continue
val = root.val
if val <= lower or val >= upper:
return False
stack.append((root.right, val, upper)) # 右子树的所有值都要大于根节点
stack.append((root.left, lower, val)) # 左子树的所有值都要小于根节点
return True

recover-binary-search-tree

参考链接

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/16 22:36
# @Author: GraceKoo
# @File: 99_recover-binary-search-tree.py
# @Desc: https://leetcode-cn.com/problems/recover-binary-search-tree/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def __init__(self):
self.pre_node = TreeNode(float("-inf"))
self.second_node = None
self.first_node = None

def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
# 中序遍历:找到第一个大于左子树的节点赋值为first_node,第一个小于右子树的节点赋值为second_node
def in_order(root):
if not root:
return
in_order(root.left)
if self.first_node is None and self.pre_node.val >= root.val:
self.first_node = self.pre_node
if self.first_node is not None and self.pre_node.val >= root.val:
self.second_node = root
self.pre_node = root
in_order(root.right)
in_order(root)
self.first_node.val, self.second_node.val = self.second_node.val, self.first_node.val

same-tree

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/16 12:29
# @Author: GraceKoo
# @File: 100_same-tree.py
# @Desc: https://leetcode-cn.com/problems/same-tree/


# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None


class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return True
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Queue

merge-k-sorted-lists

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/7 9:25 下午
# @Author: GraceKoo
# @File: 23_merge-k-sorted-lists.py
# @Desc:https://leetcode-cn.com/problems/merge-k-sorted-lists/

from queue import PriorityQueue

# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def mergeKLists(self, lists) -> ListNode:
# 使用优先队列(堆排序)存储每个list中的第一个节点,由优先队列返回优先级最高(值最低的元素)
head_pre = p = ListNode(0)
prior_queue = PriorityQueue()
for list_node in lists:
if list_node:
prior_queue.put((list_node.val, list_node))
while not prior_queue.empty():
node_val, node = prior_queue.get()
p.next = ListNode(node_val)
p = p.next
# 将当前list的头指向list中的下一个节点
node = node.next
if node:
prior_queue.put((node.val, node))
return head_pre.next

Bit Operation

divide-two-integers

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/9 9:11 下午
# @Author: GraceKoo
# @File: 29_divide-two-integers.py
# @Desc:https://leetcode-cn.com/problems/divide-two-integers/


class Solution:
def divide(self, dividend: int, divisor: int) -> int:
flag = dividend < 0 ^ divisor < 0
dividend, divisor = abs(dividend), abs(divisor)
result = 0
move_step = 0
# 移动除数直到比被除数大
while divisor <= dividend:
move_step += 1
divisor <<= 1
# 移动move_step 次使得 len(divisor) > len(dividend),则 move_step-1 次使得 len(divisor) > len(dividend)
while move_step > 0:
move_step -= 1
# 此时divisor比division大,应该向右移动一位
divisor >>= 1
# 判断是否除尽
if dividend >= divisor:
result += 1 << move_step
dividend -= divisor
if not flag:
result = -result
return result if -(1 << 31) <= result <= (1 << 31) - 1 else (1 << 31) - 1


so = Solution()
print(so.divide(-45, 2))

gray-code

解题思路:

  • 结果是当前head的移位结果 + 已有结果的倒序(注:参考链接

leetcode-89

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/4/2 23:45
# @Author: GraceKoo
# @File: 89_gray-code.py
# @Desc:https://leetcode-cn.com/problems/gray-code/
from typing import List


class Solution:
def grayCode(self, n: int) -> List[int]:
res, head = [0], 1
for i in range(n):
for j in range(len(res) - 1, -1, -1):
res.append(head + res[j])
head <<= 1
return res


so = Solution()
print(so.grayCode(2))

convert-a-number-to-hexadecimal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2020/4/19 10:54
# @Author: GraceKoo
# @File: 405_convert-a-number-to-hexadecimal.py
# @Desc: https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal/


class Solution:
def toHex(self, num: int) -> str:
num &= 0xFFFFFFFF
mask = 0b1111
s = "0123456789abcdef"
result = ""
while num > 0:
# 从num低4位开始,每隔4位依次取结果,并对应到s的相应数字
result += s[num & mask]
num >>= 4 # num向右移动4位
return result[::-1] if result else "0"


so = Solution()
print(so.toHex(26))

binary-watch

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/20 12:38
# @Author: GraceKoo
# @File: 401_binary-watch.py
# @Desc:https://leetcode-cn.com/problems/binary-watch/
from typing import List


class Solution:
def readBinaryWatch(self, num: int) -> List[str]:
def count_binary_1(i):
return bin(i).count("1")

# 1~59分钟转换成二进制里面分别有多少1
dict_binary = {i: count_binary_1(i) for i in range(60)}
res = []
for h in range(12):
for m in range(60):
# hour 与 minutes 亮灯的两者之和与num相等
if dict_binary[h] + dict_binary[m] == num:
hour = str(h)
m = str(m) if m > 9 else "0" + str(m)
res.append(hour + ":" + m)
return res


so = Solution()
print(so.readBinaryWatch(1))

interview_11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 15:41
# @Author: GraceKoo
# @File: interview_11.py
# @Desc: https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/


class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
count = 1 # 牛客网要求只输出该数32位二进制表示中1的个数,故利用count来计数
while n and count <= 32:
res += n & 1
n >>= 1
count += 1
return res


so = Solution()
print(so.hammingWeight(-1))

interview_48

题解来源

因为不允许采用四则运算,所以只能考虑位运算了。

其实就是用二进制来模拟加法操作。首先将两个数最低位相加,如果都是 1 ,那么就得到 0 ,并且进位 1 ,然后接着算下一位。

但是这样一位一位模拟不方便实现,更简单的实现方法是直接把两个数对应位相加,不管进位。然后进位单独计算,如果某一位两个数都是 1 ,那么进位就会对下一位产生影响。然后接着算不进位求和加上进位的值,再计算新的进位,依次重复下去,直到进位为 0 为止。

用一个实际的例子来演示一下,计算 3+7 的值,其中 s 表示每一步不考虑进位的求和,c 表示每一步的进位,最后得到结果 1010 ,也就是十进制的 10

interview_48

Python 负数的存储:
Python,Java 等语言中的数字都是以 补码 形式存储的。但 Python 没有 int , long 等不同长度变量,即在编程时无变量位数的概念。
获取负数的补码: 需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字 32 位以上的数字(将 32 位以上都变为 00 ),从无限长度变为一个 32 位整数。
返回前数字还原: 若补码 a 为负数( 0x7fffffff 是最大的正数的补码 ),需执行 ~(a ^ x) 操作,将补码还原至 Python 的存储格式。 a ^ x 运算将 1 至 32 位按位取反; ~ 运算是将整个数字取反;因此, ~(a ^ x) 是将 32 位以上的位取反,1 至 32 位不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/9/25 14:37
# @Author: GraceKoo
# @File: interview_48.py
# @Desc: https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/


class Solution:
def add(self, a: int, b: int) -> int:
a &= 0xffffffff
b &= 0xffffffff
while b != 0:
c = ((a & b) << 1) & 0xffffffff # 进位用与操作
a ^= b # 不考虑进位的结果用异或操作
b = c
return a if a <= 0x7fffffff else ~(a ^ 0xffffffff) # 负数需要恢复成原码


so = Solution()
print(so.add(-3, -2))

interview_49

参考链接

数字越界处理:

题目要求返回的数值范围应在[ -2^31, 2 ^ 31 − 1] ,因此需要考虑数字越界问题。而由于题目指出环境只能存储 32 位大小的有符号整数 ,因此判断数字越界时,要始终保持 res 在 int 类型的取值范围内。

interview_49

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
# -*- coding: utf-8 -*-
# @Time: 2020/9/25 14:37
# @Author: GraceKoo
# @File: interview_49.py
# @Desc: https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/


class Solution:
def strToInt(self, str: str) -> int:
if not str:
return 0
# string = str.split()[0] # 不使用split,strip等方法可以将空间复杂度降到O(1)
result, i, sign, len_str = 0, 0, 1, len(str) # 结果,开始的索引,正负号,str的长度
int_max, int_min, boundary = 2 ** 31 - 1, -2 ** 31, 2 ** 31 // 10

# 去除空格
while str[i] == " ":
i += 1
if i == len_str: # 空字符串
return 0

# 判断符号
if str[i] == "-":
sign = -1
if str[i] in ("+", "-"):
i += 1

# 整数拼接
for c in str[i:]:
if not "0" <= c <= "9":
break
if result > boundary or (result == boundary and c > "7"):
return int_max if sign == 1 else int_min
result = result * 10 + ord(c) - ord("0") # 结果通过字符与"0"的ASCII码求得
return sign * result


so = Solution()
print(so.strToInt("+123i adf"))

支持小数

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
# -*- coding: utf-8 -*-
# @Time: 2020/9/25 14:37
# @Author: GraceKoo
# @File: interview_49.py
# @Desc: https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/

class Solution:
def strToInt(self, str: str) -> int:
if not str:
return 0
# string = str.split()[0] # 不使用split,strip等方法可以将空间复杂度降到O(1)
result, i, sign, len_str = 0, 0, 1, len(str) # 结果,开始的索引,正负号,str的长度
int_max, int_min, boundary = 2 ** 31 - 1, -(2 ** 31), 2 ** 31 // 10

# 去除空格
while str[i] == " ":
i += 1
if i == len_str: # 空字符串
return 0

# 判断符号
if str[i] == "-":
sign = -1
if str[i] in ("+", "-"):
i += 1

# 整数拼接
for c in str[i:]:
i += 1
if not "0" <= c <= "9":
break
if result > boundary or (result == boundary and c > "7"):
return int_max if sign == 1 else int_min
result = result * 10 + ord(c) - ord("0") # 结果通过字符与"0"的ASCII码求得

# 求小数部分
x = 1
if str[i-1] == ".":
for c in str[i:]:
if not "0" <= c <= "9":
break
if result > boundary or (result == boundary and c > "7"):
return int_max if sign == 1 else int_min
result = result + (ord(c) - ord("0")) * 0.1 ** x
x += 1

return sign * result


so = Solution()
print(so.strToInt("+12.3"))


Binary Search

find-first-and-last-position-of-element-in-sorted-array

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/2 11:18 上午
# @Author: GraceKoo
# @File: 34_find-first-and-last-position-of-element-in-sorted-array.py
# @Desc: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/


class Solution:
def find_left_right_index(self, nums, target, left_right_flag):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] > target or (left_right_flag and nums[mid] == target):
right = mid
else:
left = mid + 1
return left

def searchRange(self, nums, target: int):
# 找到左边界
left_index = self.find_left_right_index(nums, target, True)
if left_index == len(nums) or nums[left_index] != target:
return [-1, -1]
# 找到右边界
return [left_index, self.find_left_right_index(nums, target, False) - 1]


so = Solution()
print(so.searchRange([5, 7, 7, 8, 8, 10], 8))

sqrtx

x ≥ 2 时,它的整数平方根一定小于 x / 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
# -*- coding: utf-8 -*-
# @Time: 2020/3/11 11:57
# @Author: GraceKoo
# @File: 69_sqrtx.py
# @Desc:https://leetcode-cn.com/problems/sqrtx/


class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
left = 2
right = x // 2
while left <= right:
middle = left + (right - left) // 2
if middle * middle > x:
right = middle - 1
elif middle * middle < x:
left = middle + 1
else:
return middle
return right


so = Solution()
print(so.mySqrt(8))

search-a-2d-matrix

将整个matric当做一个列表,进行二分查找。其中对应的元素与其行列的索引为:

middle = (left + right) // 2

row_index = middle // cols

col_index = middle % cols

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/17 19:59
# @Author: GraceKoo
# @File: 74_search-a-2d-matrix.py
# @Desc:https://leetcode-cn.com/problems/search-a-2d-matrix/
from typing import List


class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or len(matrix) == 0:
return False
rows = len(matrix)
cols = len(matrix[0])
left = 0
right = rows * cols - 1
while left <= right:
middle = (left + right) // 2
row = middle // cols
col = middle % cols
if matrix[row][col] == target:
return True
if matrix[row][col] > target:
right = middle - 1
else:
left = middle + 1
return False


so = Solution()
print(so.searchMatrix([
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
], 3))

search-in-rotated-sorted-array

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/1 4:43 下午
# @Author: GraceKoo
# @File: 33_search-in-rotated-sorted-array.py
# @Desc: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/


class Solution:
def search(self, nums, target: int) -> int:
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 右半部分是有序的
if nums[mid] < nums[right]:
# target在右半部分里
if nums[mid] < target < nums[right]:
left = mid + 1
else:
right = mid - 1
# 左半部分是有序的
else:
# target在左半部分里
if nums[left] < target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1


so = Solution()
print(so.search([4, 5, 6, 7, 0, 1, 2], 0))

find-minimum-in-rotated-sorted-array

参考链接

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/26 12:39
# @Author: GraceKoo
# @File: 153_find-minimum-in-rotated-sorted-array.py
# @Desc: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
from typing import List


class Solution:
def findMin(self, nums: List[int]) -> int:
len_nums = len(nums)
if len_nums <= 1:
return nums[0]
left = 0
right = len_nums - 1
while left <= right:
middle = (left + right) // 2
# 退出条件
if nums[middle - 1] > nums[middle]:
return nums[middle]
if nums[middle] > nums[middle + 1]:
return nums[middle + 1]

# 左边为有序,寻找在右边的变化点
if nums[middle] > nums[left]:
left = middle + 1
# 右边为有序,寻找在左边的变化点
else:
right = middle - 1


so = Solution()
print(so.findMin([3, 4, 5, 1, 2]))

search-in-rotated-sorted-array-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
# -*- coding: utf-8 -*-
# @Time: 2020/3/26 19:16
# @Author: GraceKoo
# @File: 81_search-in-rotated-sorted-array-ii.py
# @Desc:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/


class Solution:
def search(self, nums, target: int) -> int:
if not nums:
return False
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
# 右半部分是有序的
if nums[mid] < nums[right]:
# target在右半部分里
if nums[mid] < target < nums[right]:
left = mid + 1
else:
right = mid - 1
# 左半部分是有序的
else:
# target在左半部分里
if nums[left] < target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return False


so = Solution()
print(so.search([2, 5, 6, 0, 0, 1, 2], 3))

min-value-in-rotated-array

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/25 12:37
# @Author: GraceKoo
# @File: min-value-in-rotated-array.py
# @Desc: https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=1&ru=/ta/
# coding-interviews&qru=/ta/coding-interviews/question-ranking


class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
len_rotatearray = len(rotateArray)
if len_rotatearray <= 1:
return rotateArray
left = 0
right = len_rotatearray - 1
while left < right:
middle = (left + right) // 2
if rotateArray[middle] > rotateArray[right]:
left = middle + 1
else:
right = middle
return rotateArray[left]


so = Solution()
print(so.minNumberInRotateArray([1, 2, 3, 4, 5, 6, 7]))
print(so.minNumberInRotateArray([4, 5, 6, 7, 1, 2, 3]))
print(so.minNumberInRotateArray([6, 7, 1, 2, 3, 4, 5]))

find-peak-element

  • 时间复杂度 : O(log_2(n))。 每一步都将搜索空间减半。因此,总的搜索空间只需要 log_2(n)步。其中 n 为 num 数组的长度。
  • 空间复杂度 : O(1)。 只使用了常数空间。
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
# -*- coding: utf-8 -*-
# @Time: 2020/4/27 12:46
# @Author: GraceKoo
# @File: 162_find-peak-element.py
# @Desc: https://leetcode-cn.com/problems/find-peak-element/
from typing import List


class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while left < right:
middle = (left + right) // 2
# 从middle左侧开始找峰值
if nums[middle] > nums[middle + 1]:
right = middle
# 从middle右侧开始找峰值
else:
left = middle + 1
return left


so = Solution()
print(so.findPeakElement([1, 2, 1, 3, 5, 6, 4]))

interview_50

参考链接

  • 方法一:暴力

时间复杂度O(N)

空间复杂度O(N)

1
2
3
4
5
6
7
class Solution:
def findRepeatNumber(self, nums: [int]) -> int:
dic = set()
for num in nums:
if num in dic: return num
dic.add(num)
return -1
  • 方法二:原地根据索引交换

时间复杂度O(N)

空间复杂度O(1)

索引处存放的值为对应的索引。

注:此方法不能保证重复数字出现的先后顺序(若有两个重复数字,如果需要返回第一个重复的数字,那么此方法不能保证返回的顺序正确)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
if not nums:
return -1
i = 0
while i < len(nums):
if nums[i] == i:
i += 1
continue
if nums[i] == nums[nums[i]]:
return nums[i]
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]

return -1

interview_6

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/25 12:37
# @Author: GraceKoo
# @File: interview_6.py
# @Desc: https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=1&ru=/ta/
# coding-interviews&qru=/ta/coding-interviews/question-ranking


class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
len_rotatearray = len(rotateArray)
if len_rotatearray <= 1:
return rotateArray
left = 0
right = len_rotatearray - 1
while left < right:
middle = (left + right) // 2
if rotateArray[middle] > rotateArray[right]:
left = middle + 1
else:
right = middle
return rotateArray[left]


so = Solution()
print(so.minNumberInRotateArray([1, 2, 3, 4, 5, 6, 7]))
print(so.minNumberInRotateArray([4, 5, 6, 7, 1, 2, 3]))
print(so.minNumberInRotateArray([6, 7, 1, 2, 3, 4, 5]))

interview_37

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/25 12:37
# @Author: GraceKoo
# @File: interview_6.py
# @Desc: https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1
# coding-interviews&qru=/ta/coding-interviews/question-ranking

class Solution:
def GetNumberOfK(self, data, k):
# write code here
if not data:
return 0
len_data = len(data)
left, right = 0, 0
# 先找最左边等于k的位置
for i in range(0, len_data - 1):
if data[i] == k:
left = i
break
# 再找最右边等于k的位置
for j in range(len_data - 1, -1, -1):
if data[j] == k:
right = j
break
# 判断临界条件
if left == 0 and right == 0:
if data[left] == k:
return 1
else:
return 0
return right - left + 1

Double Pointer

trapping-rain-water

直接思路:

  • 对于每个元素而言,它对应的水的数量由其左右两边最大的高度决定,即:
    • 当前元素向左扫描得到最大的高度max_left_height
    • 当前元素向右扫描得到最大的高度max_right_height
    • 取min(max_left_height, max_right_height),得到min_height
    • 再将min_height 与当前元素的height相减,即为当前元素所能注得的水量
  • 时间复杂度: $O(n^2)$ ,因数组中的每个元素都需要向左向右扫描。

本题采用双指针法:时间复杂度为 $O(n)$ ,空间复杂度为 $O(1)$

思路如下:

  • 如果一端有更高的条形块(例如右端),积水的高度依赖于当前方向的高度(从左到右)。

  • 当另一侧(左侧)的条形块高度较高时,积水的高度依赖于(从右到左)方向的高度。

伪代码如下:

  • 初始化left指针为 0 并且right 指针为 size-1

  • While left < right, do:

    • If height[left] < height[right]

      • if height_left_max <= height[left]: 更新height_left_max

      • else:

    • result += height_left_max - height[left]

    • else:

      • if height_right_max <= height[right]: 更新height_right_max

      • else:

        result += height_right_max - height[right]

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/14 09:11
# @Author: GraceKoo
# @File: 42_trapping-rain-water.py
# @Desc: https://leetcode-cn.com/problems/trapping-rain-water

from typing import List


class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
result = 0
while left < right:
# 因为是从0,size-1开始比较的,每次比较相当于间接确定了height[left] < height[left_max] < height[right]
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
result += (left_max - height[left])
left += 1
# height[right] < height[right_max] < height[left]
else:
if height[right] >= right_max:
right_max = height[right]
else:
result += (right_max - height[right])
right -= 1
return result


so = Solution()
print(so.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

sort-colors

解题思路:

  • left指向0、right指向2
  • 当nums[current] = 0或2时,跟left、right指向的元素进行交换
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
# -*- coding: utf-8 -*-
# @Time: 2020/3/18 23:41
# @Author: GraceKoo
# @File: 75_sort-colors.py
# @Desc:https://leetcode-cn.com/problems/sort-colors
from typing import List


class Solution:
def sortColors(self, nums: List[int]) -> List:
if len(nums) <= 1:
return nums
left = 0
right = len(nums) - 1
current = 0
while left <= right:
if nums[current] == 0:
nums[left], nums[current] = nums[current], nums[left]
left += 1
current += 1
elif nums[current] == 1:
nums[right], nums[current] = nums[current], nums[right]
right -= 1
else:
current += 1
return nums


so = Solution()
print(so.sortColors([2, 0, 2, 1, 1, 0]))

minimum-window-substring

解题思路:

滑动窗口的思想

left指针仅在当前窗口满足条件之后才会移动:即当前窗口中满足要求,left会试着移动以此减少结果的长度

right 指针不停向右移动,找寻满足条件的窗口

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/21 22:48
# @Author: GraceKoo
# @File: 76_minimum-window-substring.py
# @Desc:https://leetcode-cn.com/problems/minimum-window-substring
from collections import Counter
from collections import defaultdict


class Solution1:
def minWindow1(self, s: str, t: str) -> str:
left, right = 0, 0
length_s = len(s)
result = s + s # 随便设定一个比s长的字符串,便于后续处理
t_dict = Counter(t) # t各个数字的出现的次数
count_dict = defaultdict(lambda: 0) # 创建一个默认值为0的字典

# 判断当前字典与目标字典长度、存储的值是否相同
def contains(t_dict, count_dict):
if len(count_dict) < len(t_dict):
return False
for key in count_dict:
if count_dict[key] < t_dict[key] or key not in t_dict:
return False
return True

# 触发right移动
for right in range(length_s):
if s[right] in t_dict:
count_dict[s[right]] += 1

# 触发left移动: 当前存储的字典中与目标字典中长度、包含的值相同
while left < length_s and contains(t_dict, count_dict):
# 更新结果
if right - left + 1 < len(result):
result = s[left:right + 1]
if s[left] in t_dict:
count_dict[s[left]] -= 1
left += 1
return "" if result == s + s else result


so = Solution1()
print(so.minWindow1("ADOBECODEBANC", "ABC"))
# -*- coding: utf-8 -*-
# @Time: 2020/3/22 22:32
# @Author: GraceKoo
# @File: 77_combinations.py
# @Desc:https://leetcode-cn.com/problems/combinations/
from typing import List


class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if n <= 0 or k <= 0 or n < k:
return []
result = []
self.__dfs(1, k, n, [], result)
return result

def __dfs(self, index, k, n, pre, result):
if len(pre) == k:
result.append(pre[:])
return
for i in range(index, n + 1):
pre.append(i)
self.__dfs(i + 1, k, n, pre, result)
pre.pop()


so = Solution()
print(so.combine(4, 2))

remove-duplicates-from-sorted-array-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
# -*- coding: utf-8 -*-
# @Time: 2020/3/26 14:00
# @Author: GraceKoo
# @File: 80_remove-duplicates-from-sorted-array-ii.py
# @Desc:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
from typing import List


class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# j指向需要覆盖的位置
j, count = 1, 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
count += 1
else:
count = 1

if count <= 2:
nums[j] = nums[i]
j += 1
return j


so = Solution()
print(so.removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3]))

interview_41

窗口何时扩大,何时缩小?

  • 当窗口的和小于 target 的时候,窗口的和需要增加,所以要扩大窗口,窗口的右边界向右移动
  • 当窗口的和大于 target 的时候,窗口的和需要减少,所以要缩小窗口,窗口的左边界向右移动
  • 当窗口的和恰好等于 target 的时候,我们需要记录此时的结果。设此时的窗口为 [i, j),那么我们已经找到了一个 i 开头的序列,也是唯一一个 i 开头的序列,接下来需要找 i+1 开头的序列,所以窗口的左边界要向右移动。
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
# -*- coding: utf-8 -*-
# @Time: 2020/9/23 18:33
# @Author: GraceKoo
# @File: interview_41.py
# @Desc: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
from typing import List


class Solution:
def findContinuousSequence(self, target: int) -> List[List[int]]:
i = 1 # 左边界,做减法
j = 1 # 右边界,做加法
sum_current = 0 # 当前滑动窗口中的总和
result = []

# 左边界不得超过target的中值
while i <= target // 2:
if sum_current < target:
sum_current += j
j += 1
elif sum_current > target:
sum_current -= i
i += 1
else:
result.append(list(range(i, j)))
sum_current -= i
i += 1
return result


so = Solution()
print(so.findContinuousSequence(10))

interview_42

算法流程:

  • 初始化: 双指针 i , j分别指向数组 nums 的左右两端 (俗称对撞双指针)。
  • 循环搜索: 当双指针相遇时跳出;
    • 计算和 s = nums[i] + nums[j];
      若 s > targets ,则指针 j 向左移动,即执行 j = j - 1;
      若 s < targets ,则指针 i 向右移动,即执行 i = i + 1;
      若 s = targets ,立即返回数组 [nums[i], nums[j]] ;
      返回空数组,代表无和为 target的数字组合。

interview_42

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
# -*- coding: utf-8 -*-
# @Time: 2020/9/23 18:33
# @Author: GraceKoo
# @File: interview_42.py
# @Desc: https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/
from typing import List


class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i, j = 0, len(nums)-1
if j < 0:
return nums
while i != j:
if nums[i] + nums[j] > target:
# j 向右移动
j -= 1
elif nums[i] + nums[j] < target:
# i 向左移动
i += 1
else:
return [nums[i], nums[j]]
return []


so = Solution()
print(so.twoSum([1, 2, 3, 4, 5], 7))

interview_64

如果使用暴力解法,可能会被面试官直接微笑回去等消息。即以下这种酸爽解法。

1
2
3
4
5
6
7
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if len(nums) == 0 or k == 0: return []
ans = []
for i in range(0,len(nums)-k+1):
ans.append(max(nums[i:i+k]))
return ans

为降低时间复杂度,此题难点是:

如何在每次窗口滑动后,将 “获取窗口内最大值” 的时间复杂度从 O(k) 降低至 O(1) 。

此题与interview_20(包含min函数的栈)一起食用最佳。即:

维护一个队列。保持队列是单调递减,即加入时把前面比其小的数pop掉。

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
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:58
# @Author: GraceKoo
# @File: interview_64.py
# @Desc: https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
from typing import List
import collections


class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if k == 0:
return []
de = collections.deque() # 构建一个双向单调递减队列,队列头记录当前窗口的最大值
result, len_nums = [], len(nums)
for left, right in zip(range(1 - k, len_nums + 1 - k), range(len_nums)):
# 为队列元素同步滑动窗口:队列内仅包含窗口内的元素,每轮窗口滑动移除了元素 nums[left - 1] ,需将队列内的对应元素一起删除。
# 如果不相等,则证明当前最大不等于滑动窗口刚滑过的元素
if left > 0 and de[0] == nums[left-1]:
de.popleft()

# 为保持队列的单调性:若队列中最小的元素小于待比较的元素,则将队尾元素弹出,新元素加入队尾
while de and de[-1] < nums[right]:
de.pop()

# 如果本身就小于队尾元素,则直接加入队尾
de.append(nums[right])

# 将每次比较的结果添加到返回列表中
if left >= 0:
result.append(de[0])
return result

Dynamic Programming

wildcard-matching

解题思路:

  • 状态 dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配 (true 的话表示匹配)

  • 状态转移方程:

    • 当 s[i] == p[j],或者 p[j] == ? 那么 dp[i][j] = dp[i - 1][j - 1]

    • 当 p[j] == * 且 dp[i][j] = dp[i][j - 1] || dp[i - 1][j]

  • 初始化:

    • dp[0][0] 表示什么都没有,其值为 true

    • 第一行 dp[0][j] ,换句话说,s 为空,与 p 匹配,所以只要 p 开始为 * 才为 true

    • 第一列 dp[i][0] ,当然全部为 false

  • 例如

    s = "abcd" p ="ab*" ,其状态矩阵如下:

true false false false
false true false false
false false true true
false false false true
false false false true
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
# -*- coding: utf-8 -*-
# @Time: 2020/2/16 09:45
# @Author: GraceKoo
# @File: 44_wildcard-matching.py
# @Desc:https://leetcode-cn.com/problems/wildcard-matching/


class Solution:
def isMatch(self, s: str, p: str) -> bool:
s_len = len(s)
p_len = len(p)
dp = [[False] * (p_len + 1) for i in range(s_len + 1)]
dp[0][0] = True
# 初始化,如果s为空,且p的第一个字符为"*",则置为True
for i in range(1, p_len + 1):
if p[i-1] == "*":
dp[0][i] = dp[0][i-1]

for i in range(1, s_len + 1):
for j in range(1, p_len + 1):
if s[i-1] == p[j-1] or p[j-1] == "?":
dp[i][j] = dp[i-1][j-1]
elif p[j - 1] == "*":
dp[i][j] = dp[i-1][j] or dp[i][j-1]
return dp[-1][-1]


so = Solution()
print(so.isMatch("adceb", "*a*b"))

maximum-subarray

  • 解法1:贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/2/25 09:52
# @Author: GraceKoo
# @File: 53_maximum-subarray.py
# @Desc:https://leetcode-cn.com/problems/maximum-subarray/
from typing import List


class Solution:
def maxSubArray_GA(self, nums: List[int]) -> int:
len_nums = len(nums)
current_sum = max_sum = nums[0]
for i in range(1, len_nums):
# 寻找局部最优解
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sum


so = Solution()
print(so.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

  • 解法2:动态规划
1
2
3
4
5
6
7
8
def maxSubArray_DP(self, nums: List[int]) -> int:
len_nums = len(nums)
max_sum = nums[0]
for i in range(1, len_nums):
if nums[i-1] > 0:
nums[i] += nums[i-1]
max_sum = max(max_sum, nums[i])
return max_sum

jump-game

解题思路:

从右向左迭代,对于每个节点我们检查是否存在一步跳跃可以到达 GOOD 的位置(currPosition + nums[currPosition] >= leftmostGoodIndex)。如果可以到达,当前位置也标记为 GOOD ,同时,这个位置将成为新的最左边的 GOOD 位置,一直重复到数组的开头,如果第一个坐标标记为 GOOD 意味着可以从第一个位置跳到最后的位置。

Index 0 1 2 3 4
Nums 2 0 1 1 4
Good/Bad *Good
*Good Good
*Good Good Good
False(1+0 < 2)
*Good(0+2 >= 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/2/27 12:08
# @Author: GraceKoo
# @File: 55_jump-game.py
# @Desc:https://leetcode-cn.com/problems/jump-game/
from typing import List


class Solution:
def canJump(self, nums: List[int]) -> bool:
last_true_index = nums[-1]
for i in range(len(nums) - 1, 0, -1):
if i + nums[i] >= last_true_index:
last_true_index = nums[i]
else:
return False
return True


so = Solution()
print(so.canJump([2, 3, 1, 1, 4]))

unique-paths

解题思路:

  • 假设dp[row][col]代表到格子[i][j]的路径个数,其中第一行dp[0][j]与第一列dp[i][0]都为1。

  • 那么每个格子的路径个数取决于它左边格子的路径个数+它上边格子的路径个数。

    dp[i][j]=dp[i][j-1]+dp[i-1][j]

  • 为了节省空间,利用两个数组pre与cur来代表上一行与当前行。初始化都为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/3/5 20:13
# @Author: GraceKoo
# @File: 62_unique-paths.py
# @Desc:https://leetcode-cn.com/problems/unique-paths/


class Solution:
def uniquePaths(self, m: int, n: int) -> int:
pre = [1] * n
cur = [1] * n
for row in range(1, m):
for col in range(1, n):
cur[col] = cur[col-1] + pre[col]
pre = cur
return pre[-1]


so = Solution()
print(so.uniquePaths(7, 3))

unique-paths-ii

解题思路:

  • 与上一题思路类似,让obstacleGrid存储到达各个单元的路径。
  • 首先进行边界初始化,边界上的元素,只有自身为0(代表本身无障碍)且上一个单元值为1(已初始化,此时的1代表无障碍,有1条路可以通行)时,自身的值才被置为1(代表有路径可走)。
  • 根据相邻单元的路径情况,进行自身路径的计算即可。
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
# -*- coding: utf-8 -*-
# @Time: 2020/3/5 21:51
# @Author: GraceKoo
# @File: 63_unique-paths-ii.py
# @Desc:https://leetcode-cn.com/problems/unique-paths-ii/
from typing import List


class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
row = len(obstacleGrid)
col = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1:
return 0
obstacleGrid[0][0] = 1
# 1.边界初始化
for i in range(1, col):
obstacleGrid[0][i] = int(obstacleGrid[0][i-1] == 1 and obstacleGrid[0][i] == 0)
for j in range(1, row):
obstacleGrid[j][0] = int(obstacleGrid[j-1][0] == 1 and obstacleGrid[j][0] == 0)
print(obstacleGrid)
# 2.计算路径
for i in range(1, row):
for j in range(1, col):
if obstacleGrid[i][j] == 1:
obstacleGrid[i][j] = 0
else:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
return obstacleGrid[-1][-1]


so = Solution()
print(so.uniquePathsWithObstacles([
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]))

minimum-path-sum

解题思路:

  1. 将Grid二维数组自身进行修改,使其存储当前元素到最右下角元素的路径值
  2. 从数组右下角元素开始遍历
  3. 最后一行的元素,路径等于自身加右侧的权值
  4. 除最后一行,其他行的最后一列,路径等于同列的下一行的权值加自身值
  5. 其他元素的路径,等于自身加上右侧权值与下侧路径的较小值
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
# -*- coding: utf-8 -*-
# @Time: 2020/3/8 00:12
# @Author: GraceKoo
# @File: 64_minimum-path-sum.py
# @Desc:https://leetcode-cn.com/problems/minimum-path-sum/
from typing import List


class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
row_len = len(grid)
col_len = len(grid[0])
for row in range(row_len-1, -1, -1):
for col in range(col_len-1, -1, -1):
# 1.最后一行的元素,路径等于自身加右侧的权值
if row == row_len-1 and col != col_len-1:
grid[row][col] += grid[row][col+1]
# 2. 除最后一行,其他行的最后一列,路径等于同列的下一行的权值加自身值
elif row != row_len-1 and col == col_len-1:
grid[row][col] += grid[row+1][col]
# 3. 其他元素的路径,等于自身加上右侧权值与下侧路径的较小值
elif row != row_len-1 and col != col_len-1:
grid[row][col] += min(grid[row+1][col], grid[row][col+1])
return grid[0][0]


so = Solution()
print(so.minPathSum([
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]))

# output
7

climbing-stairs

dp用于存储到达每个台阶的方法总数。

则到达第n阶,有dp[i-1]+dp[i-2]种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding: utf-8 -*-
# @Time: 2020/3/11 12:09
# @Author: GraceKoo
# @File: 70_climbing-stairs.py
# @Desc:https://leetcode-cn.com/problems/climbing-stairs/


class Solution:
def climbStairs(self, n: int) -> int:
dp = [i for i in range(n)]
dp[0] = 1
dp[1] = 2
for i in range(2, n):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1]


so = Solution()
print(so.climbStairs(3))

climbing-stairsII

f(n)=f(n-1)+f(n-2)+……f(1)
f(n-1)=f(n-2)+……f(1)
得f(n)=2f(n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding: utf-8 -*-
# @Time: 2020/5/26 12:35
# @Author: GraceKoo
# @File: jumpFloorII.py
# @Desc: https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&tPage=1&rp=1&ru=/ta/
# coding-interviews&qru=/ta/coding-interviews/question-ranking


class Solution:
def jumpFloorII(self, number):
# write code here
if number <= 1:
return number
n = 1
for i in range(2, number+1):
n = 2 * n
return n

edit-distance

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/16 12:03
# @Author: GraceKoo
# @File: 72_edit-distance.py
# @Desc:https://leetcode-cn.com/problems/edit-distance/


class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n1 = len(word1)
n2 = len(word2)
dp = [[0] * (n2+1) for _ in range(n1+1)]
# 第一行,进行初始化
for i in range(1, n2 + 1):
dp[0][i] = dp[0][i - 1] + 1
# 第一列,进行初始化
for j in range(1, n1 + 1):
dp[j][0] = dp[j - 1][0] + 1
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
return dp[-1][-1]


so = Solution()
print(so.minDistance(word1="horse", word2="ros"))

decode-ways

解题思路

dp[i+1]:代表s[0:i]的译码方式总数。

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/5 22:40
# @Author: GraceKoo
# @File: 91_decode-ways.py
# @Desc: https://leetcode-cn.com/problems/decode-ways/


class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == "0":
return 0
dp = [1, 0]
dp[1] = 1 if s[0] != 0 else 0 # dp[i] -> s[i-1]
n = len(s)
for i in range(1, n):
dp.append(0)
if s[i] != "0":
dp[i+1] += dp[i]
if "10" <= s[i-1:i+1] <= "26":
dp[i+1] += dp[i-2]
# print(dp)
return dp[-1]


so = Solution()
print(so.numDecodings("226"))

interleaving-string

dp[i][j]代表s1[:i]与s2[:j]能否构成s3[:i+j]

参考链接

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/12 21:47
# @Author: GraceKoo
# @File: 97_interleaving-string.py
# @Desc: https://leetcode-cn.com/problems/interleaving-string/


class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
len_s1 = len(s1)
len_s2 = len(s2)
len_s3 = len(s3)
if len_s1 + len_s2 != len_s3:
return False
dp = [[False for _ in range(len_s2+1)] for _ in range(len_s1+1)]
dp[0][0] = True
# 初始化第一行
for j in range(1, len_s2+1):
dp[0][j] = True if s3[j-1] == s2[j-1] else False
# 初始化第一列
for i in range(1, len_s1+1):
dp[i][0] = True if s3[i-1] == s1[i-1] else False
for i in range(1, len_s1+1):
for j in range(1, len_s2+1):
if dp[i-1][j] and s1[i-1] == s3[i+j-1]:
dp[i][j] = True
if dp[i][j-1] and s2[j-1] == s3[i+j-1]:
dp[i][j] = True
return dp[-1][-1]


so = Solution()
print(so.isInterleave(s1="aabcc", s2="dbbca", s3="aadbbcbcac"))

split-array-with-equal-sum

参考链接

这道题确定i,j,k的取值范围是关键。

通过j去约定i和k的范围,可以减少复杂度。

split-array-with-equal-sum

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/13 12:33
# @Author: GraceKoo
# @File: 548_split-array-with-equal-sum.py
# @Desc: https://leetcode-cn.com/problems/split-array-with-equal-sum/
from typing import List


class Solution:
def splitArray(self, nums: List[int]) -> bool:
len_nums = len(nums)
if len_nums < 7:
return False
sum_list = list()
sum_list.append(nums[0])
for i in range(1, len_nums):
sum_list.append(sum_list[i - 1] + nums[i])
# 用中间的j去约定i与k的范围
for j in range(3, len_nums - 3):
sum_set = set()
for i in range(1, j - 1):
if sum_list[i - 1] == sum_list[j - 1] - sum_list[i]:
sum_set.add(sum_list[i - 1])
for k in range(j + 2, len_nums - 1):
if sum_list[-1] - sum_list[k] == sum_list[k - 1] - sum_list[j] \
and (sum_list[k - 1] - sum_list[j]) in sum_set:
return True
return False


so = Solution()
print(so.splitArray([1, 2, 1, 2, 1, 2, 1]))

interview_33

解题思路

丑数的递推性质: 丑数只包含因子 2, 3, 5。因此有 “丑数 == 某较小丑数 × 某因子” (例如:10 = 5 ×2)

interview_33

指针a,b,c分别代表*2、*3、*5的三个指针,它们指向的丑数一旦完成计算,则继续指向下一个丑数。

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
# -*- coding: utf-8 -*-
# @Time: 2020/7/3 10:21
# @Author: GraceKoo
# @File: interview_33.py
# @Desc: https://leetcode-cn.com/problems/chou-shu-lcof/


class Solution:
def nthUglyNumber(self, n: int) -> int:
if n <= 0:
return 0
dp, a, b, c = [1] * n, 0, 0, 0
for i in range(1, n):
# 从三个倍数中选一个最小的
min_ugly = min(dp[a] * 2, dp[b] * 3, dp[c] * 5)
dp[i] = min_ugly
if min_ugly == dp[a] * 2:
a += 1
if min_ugly == dp[b] * 3:
b += 1
if min_ugly == dp[c] * 5:
c += 1
return dp[-1]


so = Solution()
print(so.nthUglyNumber(10))

interview_7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 11:36
# @Author: GraceKoo
# @File: interview_7.py
# @Desc: https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class Solution:
def fib(self, N: int) -> int:
if N <= 1:
return N
f_dict = {0: 0, 1: 1}
for i in range(2, N):
f_dict[i] = f_dict[i - 1] + f_dict[i - 2]
return f_dict[N - 1]


so = Solution()
print(so.fib(4))

interview_8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 11:38
# @Author: GraceKoo
# @File: interview_8.py
# @Desc: https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qr
# u=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class Solution:
def climbStairs(self, n: int) -> int:
if 0 <= n <= 2:
return n
dp = [i for i in range(n)]
dp[0] = 1
dp[1] = 2
for i in range(2, n):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]


so = Solution()
print(so.climbStairs(3))

interview_9

f(n)表示青蛙跳上n阶台阶的跳法数,设定f(0) = 1;

n = 1 时,只有一种跳的方式,一阶跳,f(1) = 1

n = 2 时,有两种跳的方式,一阶跳和两阶跳,f(2) = f(1) + f(0) = 2

n = 3 时,有三种跳的方式,第一次跳出一阶后,后面还有f(3-1)中跳法; 第一次跳出二阶后,后面还有f(3-2)中跳法;第一次跳出三阶后,后面还有f(3-3)种跳法,f(3) = f(2) + f(1) + f(0) = 4

当n = n 时,第一次跳出一阶后,后面还有f(n-1)中跳法; 第一次跳出二阶后,后面还有f(n-2)中跳法……第一次跳出n阶后,后面还有f(n-n)中跳法,即

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-n) = f(0) + f(1) + f(2) + ... + f(n-1)

又因为f(n-1) = f(0) + f(2) + f(3) + ... + f(n-2)

两式相减得:f(n) = 2 * f(n-1) ( n >= 2)

​ | 0,n = 0

f(n) = | 1, n = 1

​ | 2 * f(n-1) , n >= 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding: utf-8 -*-
# @Time: 2020/5/26 12:35
# @Author: GraceKoo
# @File: interview_9.py
# @Desc: https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&tPage=1&rp=1&ru=/ta/
# coding-interviews&qru=/ta/coding-interviews/question-ranking


class Solution:
def jumpFloorII(self, number):
# write code here
if number <= 1:
return number
n = 1
for i in range(2, number + 1):
n = 2 * n
return n

interview_67

参考链接

方法一:暴力递归

  • 时间复杂度:$O(2^N)$。
  • 空间复杂度:$O(2^N)$。

F(n)为长度为 n 的绳子可以得到的最大乘积,对于每一个 F(n),注意到我们每次将一段绳子剪成两段时,剩下的部分可以继续剪,也可以不剪。这就得到了递归函数:

F(n) = max( i * ( n-i ) , i * F( n-1) ), i=1,2,…,n−2

递归树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:59
# @Author: GraceKoo
# @File: interview_67.py
# @Desc: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

class Solution:
def cuttingRope(self, n: int) -> int:
if n < 1:
return 0
if n == 1 or n == 2:
return 1
result = -1
# 1 * F(n-1)、2 * F(n-2).....、i * F(n - i)
for i in range(1, n):
# 剪或不剪
result = max(result, max(i * (n-i), i * memorize(n - i)))
return result

方法二:记忆化技术(自顶向下)

暴力法超时的原因是因为重复计算了F(N),为了避免重复计算可以使用 记忆化(memoization) 技术。

记忆化技术的代码中经常需要建立函数 memoize 辅助实现。我们使用数组 f 来保存长度为 i时的最大长度 f[i],最后返回 f[n]即可。

由于利用数组保存了中间结果,所以可以将空间复杂度降低至$O(N)$

  • 时间复杂度:$O(2^N)$。
  • 空间复杂度:$O(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
25
26
27
28
29
30
31
32
33
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:59
# @Author: GraceKoo
# @File: interview_67.py
# @Desc: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/


class Solution:
def cuttingRope(self, n: int) -> int:
if n < 1:
return 0

def memorize(n):
if n == 2:
return 1
if fn[n] != 0:
return fn[n]

result = -1
# 1 * F(n-1)、2 * F(n-2).....、i * F(n - i)
for i in range(1, n):
# 剪或不剪
result = max(result, max(i * (n-i), i * memorize(n - i)))
fn[n] = result
return result

fn = [0 for _ in range(n+1)] # 用于计算已计算过的函数变量
return memorize(n)


so = Solution()
print(so.cuttingRope(10))

方法三:记忆化技术(自底向上)(推荐贪心法:简洁易懂)

自底向上

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
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:59
# @Author: GraceKoo
# @File: interview_67.py
# @Desc: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/


class Solution:
def cuttingRope(self, n: int) -> int:
if n < 1:
return 0
dp = [0 for _ in range(n+1)] # 用于计算已计算过的函数变量
dp[1] = 1
dp[2] = 1
# 遍历dp: 即F(n)
for i in range(3, n+1):
# 求解loop,求每个F(n)的解
# j代表在i长的绳子上要怎么剪,j==0or==i都代表不需要剪
for j in range(i):
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))
return dp[n]


so = Solution()
print(so.cuttingRope(10))

Greedy Algorithm

jump-game-ii

本题使用贪心算法求解,寻找局部最优解

  • 即在可跳范围内选择能跳的最远的位置
  • 当前位置在“2”,可跳位置为“3”,“1”,其中可跳的最远的位置为“3”,则选择“3”
  • 当前位置在“3”,可跳位置为“1”、“1”、“4”,其中可跳的最远的位置为“4”,则选择“4”
  • 跳跃结束,step为2
步数
Step1 2(当前位置) *3 *1 1 4
Step1 2 3(当前位置) *1 *1 *4
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
# -*- coding: utf-8 -*-
# @Time: 2020/2/17 09:45
# @Author: GraceKoo
# @File: 45_jump-game-ii.py
# @Desc: https://leetcode-cn.com/problems/jump-game-ii/
from typing import List


class Solution:
def jump(self, nums: List[int]) -> int:
max_position = 0 # 记录局部可跳跃的最大值
end = 0 # 记录每次跳跃的最大值的下标
step = 0 # 记录跳跃的步数
if len(nums) < 2:
return step
for i in range(len(nums)-1):
# 寻找局部最优解
max_position = max(max_position, nums[i] + i)
if i == end:
end = max_position
step += 1
return step


so = Solution()
print(so.jump([2, 3, 1, 1, 4]))

maximum-subarray

  • 解法1:贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/2/25 09:52
# @Author: GraceKoo
# @File: 53_maximum-subarray.py
# @Desc:https://leetcode-cn.com/problems/maximum-subarray/
from typing import List


class Solution:
def maxSubArray_GA(self, nums: List[int]) -> int:
len_nums = len(nums)
current_sum = max_sum = nums[0]
for i in range(1, len_nums):
# 寻找局部最优解
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sum


so = Solution()
print(so.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

  • 解法2:动态规划
1
2
3
4
5
6
7
8
def maxSubArray_DP(self, nums: List[int]) -> int:
len_nums = len(nums)
max_sum = nums[0]
for i in range(1, len_nums):
if nums[i-1] > 0:
nums[i] += nums[i-1]
max_sum = max(max_sum, nums[i])
return max_sum

interview_30

此题同maximum_subarray

interview_30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2020/6/30 14:52
# @Author: GraceKoo
# @File: interview_30.py
# @Desc: https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&
# qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
from typing import List


class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
max_number = nums[0]
for i in range(1, len(nums)):
nums[i] += max(nums[i-1], 0)
max_number = max(max_number, nums[i])
return max_number


so = Solution()
print(so.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

merge-intervals

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/28 11:49
# @Author: GraceKoo
# @File: 56_merge-intervals.py
# @Desc:https://leetcode-cn.com/problems/merge-intervals/
from typing import List


class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
seq = sorted(intervals) # 先按照seq[0]排序,若seq[0]一样,则按照seq[1]排序
i = 1
while i < len(seq):
if seq[i-1][0] <= seq[i][0] <= seq[i-1][1]:
if seq[i][1] > seq[i-1][1]:
seq[i-1][1] = seq[i][1]
seq.remove(seq[i])
else:
i += 1

return seq


so = Solution()
print(so.merge([[1, 3], [1, 6], [1, 80], [15, 7]]))

insert-interval

参考链接

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/29 11:45
# @Author: GraceKoo
# @File: 57_insert-interval.py
# @Desc:https://leetcode-cn.com/problems/insert-interval/
from typing import List


class Solution:
def insert(self, intervals: 'List[Interval]', newInterval: 'Interval') -> 'List[Interval]':
start, end = newInterval
current, n = 0, len(intervals)
output = []

# 将newInterval之前的序列直接添加到output中
while current < n and intervals[current][0] < start:
output.append(intervals[current])
current += 1

# 添加newInterval到output中
if not output and output[-1][1] < start:
output.append(newInterval)
else:
output[-1][1] = max(end, output[-1][1])

# 添加剩余的interval
while current < n:
if output[-1][1] < intervals[current][0]:
output.append(intervals[current])
else:
output[-1][1] = max(intervals[current][1], output[-1][1])
current += 1
return output


so = Solution()
print(so.insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))

queue-reconstruction-by-height

这道题的关键思想是官网所说的:“因为个子矮的人相对于个子高的人是 “看不见” 的,所以可以先安排个子高的人。”

即,先按照身高对每个人进行排序,然后再根据个子矮的人所对应的索引,插入到个子高的人中,因为个子矮的人相对于个子高的人是 “看不见” 的,所以插入过程中并不会影响前面已经排好序的个子高的人。

过程如下:具体解题思路见官网。

  • 排序:
    • 按高度降序排列。
    • 在同一高度的人中,按 k 值的升序排列。
  • 逐个地把它们放在输出队列中,索引等于它们的 k 值。
  • 返回输出队列

queue-reconstruction-by-height

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/5/14 19:37
# @Author: GraceKoo
# @File: 406_queue-reconstruction-by-height.py
# @Desc: https://leetcode-cn.com/problems/queue-reconstruction-by-height/
from typing import List


class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 按照x[0]的逆序(所以为-x[0]),x[1]的正序进行排序
people.sort(key=lambda x: (-x[0], x[1]), reverse=False)
out_put_people = []
# 根据索引,依次做插入操作
for person in people:
out_put_people.insert(person[1], person)
return out_put_people


so = Solution()
print(so.reconstructQueue([[7, 0], [4, 4], [7, 1], [5, 2], [6, 1], [5, 0]]))
# out_put : [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

remove-duplicate-letters

参考链接

remove-duplicate-letters

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
# -*- coding: utf-8 -*-
# @Time: 2020/5/17 23:06
# @Author: GraceKoo
# @File: 316_remove-duplicate-letters.py
# @Desc: https://leetcode-cn.com/problems/remove-duplicate-letters/


class Solution:
def removeDuplicateLetters(self, s: str) -> str:
if s == "":
return s
stack = []
value_in_stack = set()
last_occurance = {k:i for i, k in enumerate(s)}
for i, c in enumerate(s):
if c not in value_in_stack:
# stack[-1] > c:如果栈顶元素的字典序大于当前的c
# last_occurance[stack[-1]] > i:且栈顶元素还会在后续s中出现
# 则将栈顶元素弹出,并压入当前元素
while stack and stack[-1] > c and last_occurance[stack[-1]] > i:
value_in_stack.discard(stack.pop())
stack.append(c)
value_in_stack.add(c)
return "".join(stack)


so = Solution()
print(so.removeDuplicateLetters("cbacdcbc"))

String

在合并两个数组或者字符串时,如果从前往后复制每个数字(或者字符)需要重复移动数字(或字符)多次,则可以考虑从后往前复制,就能减少移动的次数。

3_length_of_longest_substring

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
# -*- coding: utf-8 -*-
# @Time : 2019/10/8 8:17 下午
# @Author: GraceKoo
# @File: 3_length_of_longest_substring.py
# @Desc: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
import timeit


class Solution:
def lengthoflongestsubstring(self, s: str) -> int:
tem_length = 0
max_length = 0
s_set = set()
for i in range(len(s)):
if s[i] in s_set:
s_set.remove(s[i])
tem_length = 0
else:
s_set.add(s[i])
tem_length += 1

if tem_length > max_length:
max_length = tem_length

return max_length


if __name__ == "__main__":
so = Solution()
test_list = "pwdflkkkpwdsadf"
start = timeit.default_timer()
print(so.lengthoflongestsubstring(test_list))
end = timeit.default_timer()
print(str((end - start) * 1000), "s") # s0.034690000006776245 s

valid-number

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/8 00:41
# @Author: GraceKoo
# @File: 65_valid-number.py
# @Desc:https://leetcode-cn.com/problems/valid-number/
import re


class Solution:
def isNumber(self, s: str) -> bool:
# return bool(re.match(r' *[+-]?([0-9]+(\.[0-9]*)?|\.[0-9]+)(e[+-]?[0-9]+)? *$', s))
s = s.strip()
# 去除s两边的空白符
if not s:
return False
# 去除"+"、"-"
if s[0] in ["+", "-"]:
s = s[1:]
# 判断是否含有e
if "e" in s:
s_list = s.split("e")
# 说明有两个e
if len(s_list) > 2:
return False
# 去掉e前面的"."
s_list[0] = s_list[0].replace(".", "", 1)
# 去掉e后面的"+、"-"
if len(s_list[1]) > 0 and s_list[1][0] in ["+", "-"]:
s_list[1] = s_list[1].replace(s_list[1][0], "", 1)
# 判断是否为数字
if s_list[0].isnumeric() and s_list[1].isnumeric():
return True
else:
s = s.replace(".", "", 1)
if s.isnumeric():
return True
return False


so = Solution()
print(so.isNumber("53.5e93"))

text-justification

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/9 19:20
# @Author: GraceKoo
# @File: 68_text-justification.py
# @Desc:https://leetcode-cn.com/problems/text-justification/
from typing import List


class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
if not words:
return []
result = []
current_chars_number = 0 # 当前行存储的字符个数(不包括空格)
current_words_number = 0 # 当前行存储的单词个数,用于统计
word_list = [] # 当前行的单词列表
for index, value in enumerate(words):
current_word_length = len(value)
# 当前字符数量大于最大限制
if current_chars_number + current_word_length + current_words_number > maxWidth:
if current_words_number == 1:
result.append(word_list[0] + " " * (maxWidth - current_chars_number))
else:
blank_space_number = maxWidth - current_chars_number # 当前的空格数量
if blank_space_number % (current_words_number - 1) == 0: # 空格可以平均分配
result.append((" "* (blank_space_number // (current_words_number - 1))).join(word_list))
else:
# 空格不能平均分配
more_blankspace = blank_space_number % (current_words_number - 1) # 多余的空格
stand_blankspace = blank_space_number // (current_words_number - 1) # 标准的最少空格
res = word_list[0]
for i in range(more_blankspace):
res += " " * (stand_blankspace+1) + word_list[i+1]
for i in range(more_blankspace+1, len(word_list)):
res += " " * stand_blankspace + word_list[i]
result.append(res)
current_chars_number = current_word_length
current_words_number = 1
word_list = [value]
else:
current_chars_number += current_word_length
current_words_number += 1
word_list.append(value)
return result


so = Solution()
print(so.fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16))

simplify-path

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/12 12:01
# @Author: GraceKoo
# @File: 71_simplify-path.py
# @Desc:https://leetcode-cn.com/problems/simplify-path/


class Solution:
def simplifyPath(self, path: str) -> str:
if not path:
return ""
result_list = []
path = path.split("/")
for value in path:
if value == "..":
if result_list:
result_list.pop()
elif value and value != ".":
result_list.append(value)
return "/" + "/".join(result_list)


so = Solution()
print(so.simplifyPath("/a/./b/../../c/"))

Interview_2

  • 方法一:时间复杂度O(n),空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding: utf-8 -*-
# @Time: 2020/5/8 22:38
# @Author: GraceKoo
# @File: interview_2.py
# @Desc: https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/


class Solution:
def replaceSpace(self, s: str) -> str:
return s.replace(" ", "%20")


so = Solution()
print(so.replaceSpace("We are happy."))

  • 方法二:时间复杂度O(n),空间复杂度O(n)

这里用list而不是str直接处理的原因是。str是不可变数据类型,也就是说每在一个str后面加了一个字符,都是新的str。这样导致空间开销太大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/5/8 22:38
# @Author: GraceKoo
# @File: interview_2.py
# @Desc: https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/


class Solution:
def replaceSpace(self, s: str) -> str:
s_list = list()
for s_value in s:
if s_value == " ":
s_list.append("%20")
else:
s_list.append(s_value)

return "".join(s_list)


so = Solution()
print(so.replaceSpace("We are happy."))

interview_43

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding: utf-8 -*-
# @Time: 2020/9/23 18:33
# @Author: GraceKoo
# @File: interview_43.py
# @Desc: https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/


class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
len_s = len(s)
if n >= len_s or n <= 0:
return s
return s[n:] + s[:n]


so = Solution()
print(so.reverseLeftWords("abcdefg", 2))


interview_44

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2020/9/24 15:15
# @Author: GraceKoo
# @File: interview_44.py
# @Desc: https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/


class Solution:
def reverseWords(self, s: str) -> str:
if not s:
return s
s_rotate = s.split()
# " "的情况,直接返回s
if len(s_rotate) <= 1:
return s
return " ".join(s_rotate[::-1])


so = Solution()
print(so.reverseWords("abc bvc nbm"))

interview_45

先对数组执行排序

  • 判别重复: 排序数组中的相同元素位置相邻,因此可通过遍历数组,判断 nums[i] = nums[i + 1]是否成立来判重。
  • 获取最大 / 最小的牌: 排序后,数组末位元素 nums[4] 为最大牌;元素 nums[joker]为最小牌,其中 joker为大小王的数量。

interview_45

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
# -*- coding: utf-8 -*-
# @Time: 2020/9/24 15:16
# @Author: GraceKoo
# @File: interview_45.py
# @Desc: https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/
from typing import List


class Solution:
def isStraight(self, nums: List[int]) -> bool:
if not nums:
return False
joker = 0
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == 0:
joker += 1
elif nums[i] == nums[i + 1]:
return False
return nums[4] - nums[joker] < 5


so = Solution()
print(so.isStraight([0, 0, 1, 2, 5]))

Sort

introduction

排序算法 平均时间复杂度 最差时间复杂度 额外空间复杂度 稳定性 备注
冒泡排序 $o(n^2)$ $o(n^2)$ $o(1)$ 稳定 n小时效果好
选择排序 $o(n^2)$ $o(n^2)$ $o(1)$ 不稳定 n小时效果好
交换排序 $o(n^2)$ $o(n^2)$ $o(1)$ 不稳定 n小时效果好
插入排序 $o(n^2)$ $o(n^2)$ $o(1)$ 稳定 n小时效果好
快速排序 $o(nlogn)$ $o(n^2)$ $o(nlogn)-o(n)$ 不稳定 n大时效果好
归并排序 $o(nlogn)$ $o(nlogn)$ $o(n)$ 稳定 n大时效果好
堆排序 $o(nlogn)$ $o(nlogn)$ $o(1)$ 不稳定 n大时效果好
希尔排序 $o(nlogn)$ $o(n^s)$ 1<s<2 $o(1)$ 不稳定 s是所选分组
基数排序 $o(log_RB)($线性复杂度) $o(log_RB)$ $o(n)$ 稳定 B是真数(0-9),R是基数(个十百)
计数排序 $o(n)$ $o(nlogn)$ 稳定 0
划分排序 $o(n)$ 0 0 稳定 0
桶排序 $o(n)$ 0 0 稳定 0

https://leetcode-cn.com/problems/sort-an-array/solution/python-shi-xian-de-shi-da-jing-dian-pai-xu-suan-fa/

桶排序

冒泡排序

快速排序

堆排序

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。

a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换,将最大元素”沉”到数组末端;

c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

归并排序

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
def mergesort(seq):
"""归并排序"""
if len(seq) <= 1:
return seq
mid = len(seq) / 2 # 将列表分成更小的两个列表
# 分别对左右两个列表进行处理,分别返回两个排序好的列表
left = mergesort(seq[:mid])
right = mergesort(seq[mid:])
# 对排序好的两个列表合并,产生一个新的排序好的列表
return merge(left, right)

def merge(left, right):
"""合并两个已排序好的列表,产生一个新的已排序好的列表"""
result = [] # 新的已排序好的列表
i = 0 # 下标
j = 0
# 对两个列表中的元素 两两对比。
# 将最小的元素,放到result中,并对当前列表下标加1
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result

seq = [5,3,0,6,1,4]
print '排序前:',seq
result = mergesort(seq)

largest-number

自定义排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/4/23 21:18
# @Author: GraceKoo
# @File: 179_largest-number.py
# @Desc: https://leetcode-cn.com/problems/largest-number/
from typing import List


class LargerNumKey(str):
def __lt__(x, y):
return x + y < y + x


class Solution:
def largestNumber(self, nums):
return_value = "".join(sorted(map(str, nums), key=LargerNumKey, reverse=True)).lstrip("0")
return "0" if return_value[0] == "0" else return_value


so = Solution()
print(so.largestNumber([3, 30, 34, 5, 9]))

interview_32

同上一题:largest-number,这题不加任何技巧。类似于冒泡排序。

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
# -*- coding: utf-8 -*-
# @Time: 2020/7/2 11:54
# @Author: GraceKoo
# @File: interview_32.py
# @Desc: https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
from typing import List


class Solution(object):
def minNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
if not nums:
return None
for i in range(len(nums)):
nums[i] = str(nums[i])
# 冒泡排序:每次把最小的元素放在第一位
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if (nums[i] + nums[j]) > (nums[j] + nums[i]):
nums[i], nums[j] = nums[j], nums[i]

return ''.join(nums)


so = Solution()
print(so.minNumber([3, 30, 34, 5, 9]))

Top-K Sort

kth-largest-element-in-an-array

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding: utf-8 -*-
# @Time: 2020/4/25 12:43
# @Author: GraceKoo
# @File: 215_kth-largest-element-in-an-array.py
# @Desc: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
from typing import List
import heapq


class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return heapq.nlargest(k, nums)[-1]


so = Solution()
print(so.findKthLargest([3, 2, 1, 5, 6, 4], 2))

interview_29

解题思路

  1. 方法一:堆排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding: utf-8 -*-
# @Time: 2020/6/29 16:40
# @Author: GraceKoo
# @File: interview_29.py
# @Desc: https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?
# tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
from typing import List
import heapq


class Solution:
def findKthLargest(self, arr: List[int], k: int) -> int:
len_tinput = len(tinput)
if k > len_tinput:
return []
return heapq.nsmallest(k, arr)


so = Solution()
print(so.findKthLargest([3, 2, 1, 5, 6, 4], 2))
  1. 方法2:利用快速排序思想

interview_29

这个 partition 操作是原地进行的,需要 O(n)的时间,接下来,快速排序会递归地排序左右两侧的数组。而快速选择(quick select)算法的不同之处在于,接下来只需要递归地选择一侧的数组。快速选择算法想当于一个“不完全”的快速排序,因为我们只需要知道最小的 k 个数是哪些,并不需要知道它们的顺序。

我们的目的是寻找最小的 k 个数。假设经过一次 partition 操作,枢纽元素位于下标 m,也就是说,左侧的数组有 m 个元素,是原数组中最小的 m 个数。那么:

  • 若 k = m,我们就找到了最小的 k 个数,就是左侧的数组;
  • 若 k < m ,则最小的 k 个数一定都在左侧数组中,我们只需要对左侧数组递归地 parition 即可;
  • 若 k > m,则左侧数组中的 m 个数都属于最小的 k 个数,我们还需要在右侧数组中寻找最小的 k-m 个数,对右侧数组递归地 partition 即可。
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
# -*- coding: utf-8 -*-
# @Time: 2020/6/29 16:40
# @Author: GraceKoo
# @File: interview_29.py
# @Desc: https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?
# tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
from typing import List


class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k <= 0 or k > len(arr):
return []
start = 0
end = len(arr) - 1
pivot = self.quicksort(arr, start, end)
while pivot != k - 1:
if pivot > k - 1:
end = pivot - 1
pivot = self.quicksort(arr, start, end)
if pivot < k - 1:
start = pivot + 1
pivot = self.quicksort(arr, start, end)
return arr[:k]

def quicksort(self, arr, left, right):
"""
简单版快速排序
返回一个坐标,坐标左侧都小于返回值,右侧都大于返回值
"""
i = left
j = right
temp = arr[left]
while i < j:
# 从右侧搜索小元素,并进行交换
while i < j and arr[j] >= temp:
j -= 1
arr[i] = arr[j]
# 从左侧搜索大元素,并进行交换
while i < j and arr[i] < temp:
i += 1
arr[j] = arr[i]
# 最初left上的数字已经被覆盖了,所以需要重新赋值
arr[i] = temp
return i


so = Solution()
print(so.getLeastNumbers([4, 5, 1, 6, 2], 4))

sort-an-array

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/28 22:52
# @Author: GraceKoo
# @File: 912_sort-an-array.py
# @Desc: https://leetcode-cn.com/problems/sort-an-array/
from typing import List


class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
if not nums:
return []
n = len(nums)

# 快速排序
def quick(left, right):
if left >= right:
return nums
# 哨兵
pivot = left
i = left
j = n - 1
while i < j:
# 寻找右半部分
while i < j and nums[j] > nums[pivot]:
j -= 1
# 寻找左半部分
while i < j and nums[i] <= nums[pivot]:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[pivot], nums[j] = nums[j], nums[pivot]
quick(left, j-1)
quick(j+1, right)
return nums

return quick(0, n - 1)
# 插入排序
# def insertion_sort(nums):
# n = len(nums)
# for i in range(1, n):
# while i > 0 and nums[i - 1] > nums[i]:
# nums[i - 1], nums[i] = nums[i], nums[i - 1]
# i -= 1
# return nums


so = Solution()
print(so.sortArray([5, 1, 1, 2, 0, 0]))

maximum-gap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2020/4/29 12:39
# @Author: GraceKoo
# @File: 164_maximum-gap.py
# @Desc: https://leetcode-cn.com/problems/maximum-gap/
from typing import List


class Solution:
def maximumGap(self, nums: List[int]) -> int:
len_nums = len(nums)
if len_nums < 2:
return 0
nums.sort(reverse=False)
max_gap = abs(nums[1] - nums[0])
for i in range(2, len_nums):
max_gap = max(max_gap, abs(nums[i] - nums[i - 1]))
return max_gap


so = Solution()
print(so.maximumGap([3, 6, 9, 1]))

contains-duplicate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
# @Time: 2020/4/30 17:45
# @Author: GraceKoo
# @File: 217_contains-duplicate.py
# @Desc: https://leetcode-cn.com/problems/contains-duplicate/
from typing import List


class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
if not nums:
return False
# 先排序
nums.sort(reverse=False)
# 再比较
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return True
return False


so = Solution()
print(so.containsDuplicate([1, 2, 3, 1, 2, 3]))

contains-duplicate-ii

用散列表来维护这个k大小的滑动窗口。

遍历数组,对于每个元素做以下操作:

  • 在散列表中搜索当前元素,如果找到了就返回 true。

  • 在散列表中插入当前元素。

  • 如果当前散列表的大小超过了 k, 删除散列表中最旧的元素。

返回 false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
# @Time: 2020/4/30 17:46
# @Author: GraceKoo
# @File: 219_contains-duplicate-ii.py
# @Desc: https://leetcode-cn.com/problems/contains-duplicate-ii/
from typing import List


class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
nums_sort = list()
nums_sort.append(nums[0])
for i in range(1, len(nums)):
if nums[i] in nums_sort:
return True
elif len(nums_sort) >= k:
nums_sort.pop(0)
nums_sort.append(nums[i])
return False


so = Solution()
print(so.containsNearbyDuplicate([1, 2, 3, 4, 2, 3], 2))

contains-duplicate-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
25
26
27
28
29
# -*- coding: utf-8 -*-
# @Time: 2020/5/5 21:24
# @Author: GraceKoo
# @File: 220_contains-duplicate-iii.py
# @Desc: https://leetcode-cn.com/problems/contains-duplicate-iii
from typing import List


class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
if len(nums) <= 1:
return False
nums_sort = list()
nums_sort.append(nums[0])
for i in range(1, len(nums)):
if len(nums_sort) > k:
nums_sort.pop(0)
# 查询当前子列表中的每个元素是否满足t的要求
tmp_nums_sored = sorted(nums_sort, reverse=False)
for v in tmp_nums_sored:
if abs(nums[i] - v) <= t:
return True
nums_sort.append(nums[i])
return False


so = Solution()
print(so.containsNearbyAlmostDuplicate(nums=[1, 5, 9, 1, 5, 9], k=2, t=3))

方法二:桶排序

由于本题对索引有要求,考虑使用桶排序。

  • 每个数字nums[i] 都被分配到一个桶中
  • 每个桶序号代表存放t的倍数的数 nums[i] // (t + 1)
    • 不相邻的桶一定不满足相差小于等于t,且同一个桶内的数字最多相差t
    • 因此如果命中同一个桶内,那么直接返回True
    • 如果命中相邻桶,我们再判断一下是否满足相差 <= t
  • 题目有索引相差k的要求,因此要维护一个大小为k的窗口,定期清除桶中过期的数字。bucket.pop(nums[i - k] // (t + 1)) 即清除当前i前的第k个元素所对应的桶序号。
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
# -*- coding: utf-8 -*-
# @Time: 2020/5/5 21:24
# @Author: GraceKoo
# @File: 220_contains-duplicate-iii.py
# @Desc: https://leetcode-cn.com/problems/contains-duplicate-iii
from typing import List


class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
bucket = dict()
if t < 0:
return False
for i in range(0, len(nums)):
# 每个桶序号代表存放t的倍数的数
bucket_nth = nums[i] // (t + 1)
if bucket_nth in bucket:
return True
if bucket_nth - 1 in bucket and abs(bucket[bucket_nth - 1] - nums[i]) <= t:
return True
if bucket_nth + 1 in bucket and abs(bucket[bucket_nth + 1] - nums[i]) <= t:
return True
bucket[bucket_nth] = nums[i]
# 当桶大于k时,代表窗口已经越界,越界元素可以进行清除
if i >= k:
bucket.pop(nums[i - k] // (t + 1))
return False


so = Solution()
print(so.containsNearbyAlmostDuplicate(nums=[1, 5, 9, 1, 5, 9], k=2, t=3))

interview_63

参考链接

复杂度分析:

  • 时间复杂度:
    查找中位数 O(1) : 获取堆顶元素使用 O(1)时间;(二分查找等则需要O(log N))
    添加数字 O(log N) : 堆的插入和弹出操作使用 O(log N) 时间。(线性插入O(N))
  • 空间复杂度 O(N): 其中 N 为数据流中的元素数量,小顶堆 B 和大顶堆 A最多同时保存 N 个元素。

算法利用大顶堆A和小顶堆B,A存放较小的元素,B存放较大的元素。使得B的最小的元素也比A中最大的元素大,保证数据流保持有序。

B保持比A多一个的状态,当数据流长度时为奇数时,则向A中插入元素;偶数时,则向B中插入元素。

Python 中 heapq 模块是小顶堆。实现 大顶堆 方法: 小顶堆的插入和弹出操作均将元素 取反 即可。

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
# -*- coding: utf-8 -*-
# @Time: 2020/10/10 11:58
# @Author: GraceKoo
# @Fil
e: interview_63.py
# @Desc: https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
from heapq import *


class MedianFinder:

def __init__(self):
"""
initialize your data structure here.
"""
self.A = [] # 大顶堆,存放较小的元素
self.B = [] # 小顶堆,存放较大的元素,使得B的最小的元素也比A中最大的元素大,保证数据流保持有序

def addNum(self, num: int) -> None:
# 数据流长度为奇数时,需向A中插入元素:先向B中插入num,再将B的堆顶元素插入至A,保证B比A大
if len(self.A) != len(self.B):
heappush(self.B, num)
heappush(self.A, -heappop(self.B))
# 数据流长度为偶数时,需向B中插入元素:先向A中插入num,再将A的堆顶元素插入至B,保证B比A大
else:
heappush(self.A, -num)
heappush(self.B, -heappop(self.A))

def findMedian(self) -> float:
if len(self.A) != len(self.B):
return self.B[0]
else:
# A由于是存放的都是相反数,所以计算时,A中最大的数其实在A[0],也就是-A[0]是A中最大的数
return (-self.A[0] + self.B[0]) / 2.0

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

Math

interview_12

1
2
3
4
2^3
2^3 = 2^1 * 2^1 * 2
2^1 = 2^0 * 2
2^0 = 1
1
2
3
4
5
2^4
2^4 = 2^2 * 2^2
2^2 = 2^1 * 2^1
2^1 = 2^0 * 2
2^0 = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
# @Time: 2020/7/16 16:24
# @Author: GraceKoo
# @File: interview_12.py
# @Desc: https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&q
# ru=%2Fta%2Fcoding-interviews%2Fquestion-ranking


class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
if n == -1:
return 1 / x
half = self.myPow(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x


so = Solution()
print(so.myPow(2.00000, -10))

Other

remove-duplicates-from-sorted-array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/1/2 11:53 下午
# @Author: GraceKoo
# @File: 26_remove-duplicates-from-sorted-array.py
# @Desc: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/


class Solution:
def removeDuplicates(self, nums):
if len(nums) == 0:
return 0
i = 0
for j in range(1, len(nums)):
if nums[i] != nums[j]:
i += 1
nums[i] = nums[j]
return i + 1


so = Solution()
print(so.removeDuplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]))

remove-element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/1/3 11:41 下午
# @Author: GraceKoo
# @File: 27_remove-element.py
# @Desc:https://leetcode-cn.com/problems/remove-element/


class Solution:
def removeElement(self, nums, val: int):
if not nums:
return 0
i = 0
for j in range(0, len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i


so = Solution()
print(so.removeElement([0, 1, 2, 2, 3, 0, 4, 2], 2))

implement-strstr

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/4 8:45 下午
# @Author: GraceKoo
# @File: 28_implement-strstr.py
# @Desc:https://leetcode-cn.com/problems/implement-strstr/


class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# haystack.find(needle)
if len(haystack) < len(needle):
return -1
j = 0
for i in range(0, len(haystack) - len(needle) + 1):
index = i
for j in range(0, len(needle)):
if haystack[i] != needle[j]:
break
i += 1
if j == len(needle) - 1:
return index
return -1


so = Solution()
print(so.strStr("hello", "ll"))

substring-with-concatenation-of-all-words

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/14 10:25 下午
# @Author: GraceKoo
# @File: 30_substring-with-concatenation-of-all-words.py
# @Desc:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/


class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
if len(s) == 0 or not words:
return []

words_number = len(words)
words_len = len(words[0])
s_len = len(s)

# 将words中的单词与个数存储到字典中
word_dic = {}
for word in words:
if word in word_dic.keys():
word_dic[word] += 1
else:
word_dic[word] = 1

output_list = []
# 按照word的长度设三段切词的起点
for i in range(words_len):
# 将s按照word的长度截取words_number段
start_index = i

# 先对s进行切割
s_cut_list = []
cut_number = 0
# 切词
while s_len - start_index >= words_len:
s_cut_list.append(s[start_index : start_index + words_len])
cut_number += 1
start_index += words_len

# 再对切割后的s进行判断,检验长度要求,个数要求
start_cut_i = 0
while cut_number - start_cut_i > words_number:
# count记录当前已经匹配完成的个数
count = 0
w_dic = {}
# 在s_cut_list中截取n个单词
for s_word in s_cut_list[start_cut_i : start_cut_i + words_number]:
if s_word in word_dic.keys():
if s_word in w_dic.keys():
w_dic[s_word] += 1
if w_dic[s_word] > word_dic[s_word]:
break
count += 1
else:
w_dic[s_word] = 1
count += 1
else:
break
if count == words_number:
output_list.append(i + start_cut_i * words_len)
start_cut_i += 1

return output_list


so = Solution()
print(so.findSubstring("barfoothefoobarman", ["foo", "bar"]))

next-permutation

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/19 12:18 下午
# @Author: GraceKoo
# @File: 31_next-permutation.py
# @Desc: https://leetcode-cn.com/problems/next-permutation/


class Solution:
def nextPermutation(self, nums) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums:
return []
left = -1
for i in range(len(nums) - 1, 0, -1):
# 从右开始,找到第一个升序的数
if nums[i - 1] < nums[i]:
left = i - 1
break
# 如果不存在left,则为降序数列,翻转整个数组
if left == -1:
return nums[::-1]

# 否则找到第一个比nums[left]大的数,至少有一个(为nums[left+1])
for right in range(len(nums) - 1, left, -1):
if nums[right] > nums[left]:
nums[right], nums[left] = nums[left], nums[right]
break
# 此时nums[left+1]依旧为降序数列,翻转nums[left+1]
nums_left = nums[left + 1 : len(nums)]
nums_left = nums_left[::-1]
nums[left + 1 : len(nums)] = nums_left
return nums


so = Solution()
print(so.nextPermutation([1, 2, 3, 7, 4]))

longest-valid-parentheses

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
# -*- coding: utf-8 -*-
# @Time: 2020/1/21 12:58 下午
# @Author: GraceKoo
# @File: 32_longest-valid-parentheses.py
# @Desc: https://leetcode-cn.com/problems/longest-valid-parentheses/


class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s or len(s) == 1:
return 0
maxlen = 0
# 当前字符为"(",left+=1,")"right+=1

# 正向搜索: 即")"必须与"("相同
left, right = 0, 0
for i in range(len(s)):
if s[i] == "(":
left += 1
else:
right += 1
if left == right:
maxlen = right * 2 if maxlen < right * 2 else maxlen
elif right > left:
left = right = 0

# 反向搜索:即"("必须与")"相同
left, right = 0, 0
for i in range(len(s) - 1, -1, -1):
if s[i] == "(":
left += 1
else:
right += 1
if left == right:
maxlen = left * 2 if maxlen < left * 2 else maxlen
elif left > right:
left = right = 0

return maxlen


so = Solution()
print(so.longestValidParentheses("())((())"))

search-insert-position

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2020/1/5 6:22 下午
# @Author: GraceKoo
# @File: 35_search-insert-position.py
# @Desc:https://leetcode-cn.com/problems/search-insert-position/


class Solution:
def searchInsert(self, nums, target: int) -> int:
for i in range(0, len(nums) - 1):
if nums[i] == target:
return i
elif nums[i] < target <= nums[i + 1]:
return i + 1
elif nums[i] > target:
return -1
return len(nums)


so = Solution()
print(so.searchInsert([1, 3, 5, 6], 7))

combination-sum-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
43
44
# -*- coding: utf-8 -*-
# @Time: 2020/2/10 2:57 下午
# @Author: GraceKoo
# @File: 40_combination-sum-ii.py
# @Desc:https://leetcode-cn.com/problems/combination-sum-ii/

from typing import List


class Solution:

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates or not target:
return []
candidates.sort()
output_list = []
path = []
begin = 0
size = len(candidates)
self._dfs(candidates, begin, size, path, output_list, target)
return output_list

def _dfs(self, candidates, begin, size, path, output_list, target):
# 递归终止的条件
if target == 0:
output_list.append(path[:])
for index in range(begin, size):
residue = target - candidates[index]
if residue < 0:
break

if index > begin and candidates[index - 1] == candidates[index]:
continue
path.append(candidates[index])
self._dfs(candidates, index+1, size, path, output_list, residue)
path.pop()


if __name__ == '__main__':
candidates = [2, 5, 2, 1, 2]
target = 5
solution = Solution()
result = solution.combinationSum(candidates, target)
print(result)

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/15 11:17
# @Author: GraceKoo
# @File: 43_multiply-strings.py
# @Desc: https://leetcode-cn.com/problems/multiply-strings/


class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return 0
return_sum = 0
count = 0
for val1 in num2[::-1]:
add = 0 # 进位符
multiply_sum = 0
count1 = 0
for val2 in num1[::-1]:
multi_sum = (int(val1) * int(val2) + add) % 10
multiply_sum += multi_sum * (10 ** count1)
add = (int(val1) * int(val2) + add) // 10
count1 += 1
return_sum += multiply_sum * (10 ** count)
count += 1

return str(return_sum)


so = Solution()
print(so.multiply("123", "456"))

group-anagrams

解题方法:

  • collections类中的defaultdict()方法来为字典提供默认值。

  • 按排序数组分类

    • ans = {(“a”,e”,”r”):[“are”,”ear”,”era”],

      ​ (“a”,”b”,”t”):[“bat”,”tab”]

      ​ (“e”,”c”,”d”,”o”):[“code”]}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding: utf-8 -*-
# @Time: 2020/2/20 00:01
# @Author: GraceKoo
# @File: 49_group-anagrams.py
# @Desc:https://leetcode-cn.com/problems/group-anagrams/

import collections


class Solution:
def groupAnagrams(self, strs):
ans = collections.defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return ans.values()


so = Solution()
print(so.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

plus-one

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
# -*- coding: utf-8 -*-
# @Time: 2020/2/22 19:31
# @Author: GraceKoo
# @File: 66_plus-one.py
# @Desc:https://leetcode-cn.com/problems/plus-one/
from typing import List


class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
if not digits:
return []
len_digits = len(digits)
add = (digits[len_digits-1] + 1) // 10
digits[len_digits-1] = (digits[len_digits-1] + 1) % 10

for i in range(len_digits - 2, -1, -1):
add = (digits[i] + add) // 10
digits[i] = (digits[i] + add) % 10
if add == 1:
digits.insert(0, add)
return digits


so = Solution()
print(so.plusOne([9, 9, 9, 9]))

length-of-last-word

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding: utf-8 -*-
# @Time: 2020/3/1 18:01
# @Author: GraceKoo
# @File: 58_length-of-last-word.py
# @Desc:https://leetcode-cn.com/problems/length-of-last-word/


class Solution:
def lengthOfLastWord(self, s: str) -> int:
if not s:
return 0
return len(s.split()[-1])


so = Solution()
print(so.lengthOfLastWord("Hello World"))

permutation-sequence

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
# -*- coding: utf-8 -*-
# @Time: 2020/3/2 12:07
# @Author: GraceKoo
# @File: 60_permutation-sequence.py
# @Desc:https://leetcode-cn.com/problems/permutation-sequence/
import math


class Solution:
def getPermutation(self, n: int, k: int) -> str:
nums = [str(i) for i in range(1, n + 1)]
output_str = ""
n -= 1
while n > -1:
number_combination = math.factorial(n) # 每组组合数总和
output_number_index = math.ceil(k / number_combination) - 1 # 不用\\的原因是因为 1 1希望输出的是0,"\\"会输出1
output_str += nums[output_number_index]
nums.pop(output_number_index)
k %= number_combination
n -= 1
return output_str


so = Solution()
print(so.getPermutation(4, 9))

6_convert

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/18 11:52 下午
# @Author: GraceKoo
# @File: 6_convert.py
# @Desc: https://leetcode-cn.com/problems/zigzag-conversion/
class Solution:
def convert(self, s: str, numRows: int) -> str:
if not s:
return ""
elif len(s) == 1:
return s

outstr = [""] * numRows
i = 0
while i < len(s):
for j in range(0, numRows):
if i < len(s):
outstr[j] += s[i]
i += 1
for j in range(numRows - 2, 0, -1):
if i < len(s):
outstr[j] += s[i]
i += 1
outstr = "".join(outstr)
return outstr


s = "ABCDE"
so = Solution()
print(so.convert(s, 3))

7_reverse-integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
# @Time: 2019/12/19 1:05 下午
# @Author: GraceKoo
# @File: 7_reverse-integer.py
# @Desc: https://leetcode-cn.com/problems/reverse-integer/


class Solution:
def reverse(self, x: int) -> int:
if not x:
return x

len_x = len(str(x))
reverse_x = ""
for i in range(0, len_x):
middle_x = (x % pow(10, i + 1)) // pow(10, i)
reverse_x = reverse_x + str(middle_x)
return reverse_x


s = 123456789
so = Solution()
print(so.reverse(s))

palindrome_number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
# @Time: 2019/12/20 11:38 下午
# @Author: GraceKoo
# @File: 9_palindrome_number.py
# @Desc: https://leetcode-cn.com/problems/palindrome-number/


class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x % 10 == 0 and x != 0):
return False
return_num = 0
# 只对比一半
while x > return_num:
return_num = return_num * 10 + x % 10
x = x // 10
# x是偶数则相等 奇数要去掉最后一位
return x == return_num or x == return_num // 10


so = Solution()
print(so.isPalindrome(1221))

container-with-most-water

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/23 11:33 下午
# @Author: GraceKoo
# @File: 11_container-with-most-water.py
# @Desc: https://leetcode-cn.com/problems/container-with-most-water/


class Solution:
def maxArea(self, height) -> int:
if not height:
return 0
i, j = 0, len(height) - 1
max_size = 0
while i < j:
if height[i] < height[j]:
tmp_size = (j - i) * height[i]
i += 1
else:
tmp_size = (j - i) * height[j]
j -= 1
max_size = tmp_size if tmp_size > max_size else max_size
return max_size


so = Solution()
assert so.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])

integer-to-roman

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/25 7:29 下午
# @Author: GraceKoo
# @File: 12_integer-to-roman.py
# @Desc: https://leetcode-cn.com/problems/integer-to-roman/


class Solution:
def intToRoman(self, num: int) -> str:
output = ""
roman_dict = {
1000: "M",
900: "CM",
500: "D",
400: "CD",
100: "C",
90: "XC",
50: "L",
40: "XL",
10: "X",
9: "IX",
5: "V",
4: "IV",
1: "I",
}
while num > 0:
for key, value in roman_dict.items():
if num >= key:
output += value
num -= key
break
return output


so = Solution()
print(so.intToRoman(999))

roman-to-integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
# @Time: 2019/12/25 7:43 下午
# @Author: GraceKoo
# @File: 13_roman-to-integer.py
# @Desc: https://leetcode-cn.com/problems/roman-to-integer/


class Solution:
def romanToInt(self, s):
output = 0
roman_dict = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
for i in range(len(s)):
if i < len(s) - 1 and roman_dict[s[i]] < roman_dict[s[i + 1]]:
output -= roman_dict[s[i]]
else:
output += roman_dict[s[i]]
return output


so = Solution()
print(so.romanToInt("MCMXCIV")) # 1994

longest-common-prefix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding: utf-8 -*-
# @Time: 2019/12/25 9:12 下午
# @Author: GraceKoo
# @File: 14_longest-common-prefix.py
# @Desc: https://leetcode-cn.com/problems/longest-common-prefix/
class Solution:
def longestCommonPrefix(self, li) -> str:
if not li:
return ""
# 按照ASCII码进行排序
min_str = min(li)
max_str = max(li)
for index, value in enumerate(min_str):
if value != max_str[index]:
return max_str[:index]
return min_str


so = Solution()
print(so.longestCommonPrefix(["flower", "flow", "flight"]))

3sum

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/27 12:18 上午
# @Author: GraceKoo
# @File: 15_3sum.py
# @Desc: https://leetcode-cn.com/problems/3sum/


class Solution:
def threeSum(self, nums):
if not nums or len(nums) < 3:
return []
n = len(nums)
output = []
nums.sort()
for i in range(0, n):
if nums[i] > 0:
return output
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = n - 1
while left < right:
if nums[i] + nums[left] + nums[right] == 0:
output.append((nums[i], nums[left], nums[right]))
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif nums[i] + nums[left] + nums[right] > 0:
right -= 1
else:
left += 1
return output


so = Solution()
print(so.threeSum([-1, 0, 1, 2, -1, -4]))

3sum-closest

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/28 4:32 下午
# @Author: GraceKoo
# @File: 16_3sum-closest.py
# @Desc: https://leetcode-cn.com/problems/3sum-closest/


class Solution:
def threeSumClosest(self, nums, target) -> int:
if not nums or len(nums) < 3:
return 0
nums.sort()
n = len(nums)
result = nums[0] + nums[1] + nums[2]
for i in range(0, n - 2):
left = i + 1
right = n - 1
while left < right:
min_value = nums[i] + nums[left] + nums[left + 1]
# 最小的都比target大,后面的元素则无需进行比较
if target < min_value:
if abs(min_value - target) < abs(result - target):
result = min_value
break
# 最大的都比target小,前面的元素则无需进行比较
max_value = nums[i] + nums[right] + nums[right - 1]
if target > max_value:
if abs(max_value - target) < abs(result - target):
result = max_value
break
sum_value = nums[i] + nums[left] + nums[right]
if abs(sum_value - target) < abs(result - target):
result = sum_value
if sum_value == target:
return sum_value
if sum_value > target:
right -= 1
# 去重
while (not left == right) and nums[right] == nums[right + 1]:
right -= 1
else:
left += 1
while (not left == right) and nums[left] == nums[left - 1]:
left += 1
# 去重
while i < n - 2 and nums[i] == nums[i + 1]:
i += 1
return result


so = Solution()
print(so.threeSumClosest([-1, 2, 1, -4], 1))

letter-combinations-of-a-phone-number

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/29 5:55 下午
# @Author: GraceKoo
# @File: 17_letter-combinations-of-a-phone-number.py
# @Desc: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/


class Solution:
def letterCombinations(self, digits: str):
digit_number_dict = {
"2": ["a", "b", "c"],
"3": ["d", "e", "f"],
"4": ["g", "h", "i"],
"5": ["j", "k", "l"],
"6": ["m", "n", "o"],
"7": ["p", "q", "r", "s"],
"8": ["t", "u", "v"],
"9": ["w", "x", "y", "z"],
}
output = []

def backtrack(combination, next_digits):
if not next_digits:
output.append(combination) # "ap"、"aq"、"ar"......
else:
for letter in digit_number_dict[next_digits[0]]:
backtrack(combination + letter, next_digits[1:])

if digits:
backtrack("", digits)
return output


so = Solution()
print(so.letterCombinations("27"))

4Sum

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/30 1:15 下午
# @Author: GraceKoo
# @File: 18_4Sum.py
# @Desc: https://leetcode-cn.com/problems/4sum/


class Solution:
def fourSum(self, nums, target):
nums = sorted(nums)
if len(nums) < 4:
return []
elif sum(nums[:4]) > target:
return []
n = len(nums)
result_li = []
# 固定i与left,对middle与right进行查找与去重
for i in range(n - 2):
for left in range(i + 1, n - 1):
middle = left + 1
right = n - 1
while middle != right:
sum_value = nums[i] + nums[left] + nums[middle] + nums[right]
if (
sum_value == target
and [nums[i], nums[left], nums[middle], nums[right]]
not in result_li
):
result_li.append(
[nums[i], nums[left], nums[middle], nums[right]]
)
if sum_value <= target:
middle += 1
# 去重
while middle != right and nums[middle] == nums[middle - 1]:
middle += 1
else:
right -= 1
# 去重
while middle != right and nums[right] == nums[right + 1]:
right -= 1
return result_li


so = Solution()
print(so.fourSum([1, 0, -1, 0, -2, 2], 0))

remove-nth-node-from-end-of-list

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
# -*- coding: utf-8 -*-
# @Time: 2019/12/31 12:11 下午
# @Author: GraceKoo
# @File: 19_remove-nth-node-from-end-of-list.py
# @Desc: 通过同时向前移动两个间隔为n的指针,直到第一个指针到达最后一个节点。此时第二个指针将指向从最后一个节点数起的第n个节点

# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 哑节点用来简化某些极端情况,例如列表中只有含有一个节点,或需要删除列表的头部
head_pre = ListNode(-1)
head_pre.next, start, end = head, head_pre, head_pre
# 让end节点向前走n步
while end and n > 0:
end = end.next
# 如果end已经走到末尾,则证明比n长,直接退出
if not end:
return head
while end.next:
start, end = start.next, end.next
# 删除倒数第n个节点
start.next = start.next.next
return head

3_length_of_longest_substring

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
# -*- coding: utf-8 -*-
# @Time : 2019/10/8 8:17 下午
# @Author: GraceKoo
# @File: 3_length_of_longest_substring.py
# @Desc:
import timeit


class Solution:
def lengthoflongestsubstring(self, s: str) -> int:
tem_length = 0
max_length = 0
s_set = set()
for i in range(len(s)):
if s[i] in s_set:
s_set.remove(s[i])
tem_length = 0
else:
s_set.add(s[i])
tem_length += 1

if tem_length > max_length:
max_length = tem_length

return max_length


if __name__ == "__main__":
so = Solution()
test_list = "pwdflkkkpwdsadf"
start = timeit.default_timer()
print(so.lengthoflongestsubstring(test_list))
end = timeit.default_timer()
print(str((end - start) * 1000), "s") # s0.034690000006776245 s

merge-sorted-array

解题思路:

初阶版 — 合并后排序

时间复杂度 : O((n + m)log(n + m))、空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
from typing import List


class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> List:
"""
Do not return anything, modify nums1 in-place instead.
"""
nums1[:] = sorted(nums1[:m], nums2)
return nums1

进阶版:双指针/从前往后

最直接的算法实现是将指针p1 置为 nums1的开头, p2为 nums2的开头,在每一步将最小值放入输出数组中。

由于 nums1 是用于输出的数组,需要将nums1中的前m个元素放在其他地方,也就需要 O(m)O(m) 的空间复杂度。

时间复杂度 : O(n + m)、空间复杂度O(m)

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(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
# Make a copy of nums1.
nums1_copy = nums1[:m]
nums1[:] = []

# Two get pointers for nums1_copy and nums2.
p1 = 0
p2 = 0

# Compare elements from nums1_copy and nums2
# and add the smallest one into nums1.
while p1 < m and p2 < n:
if nums1_copy[p1] < nums2[p2]:
nums1.append(nums1_copy[p1])
p1 += 1
else:
nums1.append(nums2[p2])
p2 += 1

# if there are still elements to add
if p1 < m:
nums1[p1 + p2:] = nums1_copy[p1:]
if p2 < n:
nums1[p1 + p2:] = nums2[p2:]

高阶版:三指针/从后往前

p1、p2分别指向nums1、nums2当前准备移动的元素。p指向当前待放置的位置。

哪个指向的数字大,则将其放置于p所指的位置上。

时间复杂度 : O(n + m)、空间复杂度O(1)

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
# -*- coding: utf-8 -*-
# @Time: 2020/4/1 11:24
# @Author: GraceKoo</