跳转至

算法目录

Tip

剑指Offer(Code Interviews)简写CI
LeetCode简写LC

剑指Offer 第二版

Question Comment topic
(3)数组中重复的数字 LC-41-First Missing Positive Array
(4)二维数组中的查找 LC-74-Search a 2D Matrix
选取左下角或右上角这种中间位置的数字开始,每次判断可以剔除一行或一列
Array
(5)替换空格 统计空格个数确定新串长度,创建新串,开始复制 String
(6)从尾到头打印链表 栈或递归 Linked List
(7)重建二叉树 LC-105-Construct Binary Tree from Preorder and Inorder Traversal
先在前序序列找到根节点,然后在中序序列中找到该节点,左边就是左子树,右边就是右子树
Tree
(8)二叉树的下一个节点 Tree
(9)用两个栈实现队列 相关题目:两个队列实现一个栈 Stack Queue
(10)斐波那契数列 相关题目:青蛙跳台阶问题、矩形填充问题 Recursion
(11)旋转数组的最小数字 LC-81-Search in Rotated Sorted Array II
先二分查找,当lo=mid=hi时,需要进行顺序查找
Binary Search
(12)矩阵中的路径 LC-79-Word Search Backtracking
(13)机器人的运动范围 Backtracking
(14)剪绳子 Greedy:当n>=5时,我们尽可能多地剪长度为3的绳子;当剩下的绳子长度为4时,把绳子剪成两段长度为2的绳子 Dynamic Programming Greedy
(15)二进制中1的个数 把一个整数减去1,再和原整数做位与运算,会把该整数最右边的1变成0
相关题目:用一条语句判断一个整数是不是2的整数次方
相关题目:输入两个整数m和n,计算需要改变m的二进制表示中的多少位才能得到n
Bit Manipulation
(16)数值的整数次方 LC-50-Pow(x, n)
(17)打印1到最大的n位数 大数问题,可以使用全排列的思路
(18)删除链表的节点 O(1) 时间内删除一个节点,可以采取复制节点值的方法
第二小题同LC-82-Remove Duplicates from Sorted List II
Linked List
(19)正则表达式匹配 字符‘.’表示任意一个字符,而‘*’表示它前面的字符可以出现任意次(含0次)
LC-10-Regular Expression Matching
Recursion
(20)表示数值的字符串 LC-65-Valid Number
(21)调整数组顺序使奇数位于偶数前面 Two Pointer
(22)链表中倒数第k个结点 LC-19-Remove Nth Node From End of List
相关题目:求链表的中间节点。如果链表为奇数,返回中间节点;如果是偶数,则返回中间两个的任意一个。
举一反三:两个指针遍历链表
Linked List
(23)链表中环的入口结点 使用两个指针 Linked List
(24)反转链表 本题扩展:使用递归实现 Linked List
(25)合并两个排序的链表 LC-21-Merge Two Sorted Lists
注意操作列表最好不要直接操作入参列表,所以合并的时候会创建一些节点
Linked List
(26)树的子结构 Tree Recursion
(27)二叉树的镜像 交换左右子节点,并对左右子节点进行递归 Tree Recursion
(28)对称的二叉树 LC-101-Symmetric Tree
先比较根节点,然后递归比较左子树的左节点与右子树的右节点、左子树的右节点与右子树的子节点
Tree Recursion
(29)顺时针打印矩阵 LC-54-Spiral Matrix
注意边界条件的判断
Array
(30)包含min函数的栈 额外使用一个辅助栈,栈中同步保存每次进栈操作时栈中最小值 Stack
(31)栈的压入、弹出序列 使用辅助栈 Stack
(32)从上到下打印二叉树 (2)LC-102-Binary Tree Level Order Traversal
(3)LC-103-Binary Tree Zigzag Level Order Traversal
Tree
(33)二叉搜索树的后序遍历序列 二叉搜索树的特征、后序遍历序列特征
相关题目:输入一个整数数组,判断该数组是不是某二叉搜索树的前序遍历结果
Tree
(34)二叉树中和为某一值的路径 Tree Recursion
(35)复杂链表的复制 Linked List
(36)二叉搜索树与双向链表 Tree
(37)序列化二叉树 Tree
(38)字符串的排列 全排列问题
LC-46-Permutations
相关题目:LC-51-N-QueensLC-52-N-Queens II
Backtracking
(39)数组中出现次数超过一半的数字 利用快排思想求数组的中位数
利用数组的特点
Array
(40)最小的k个数 利用快排思想
直接利用最小堆
利用容量为k的最大堆,堆满后保存堆顶和值的较小者,这样每次都会挤出最大堆中最大值,而保留较小值
Heap
(41)数据流中的中位数 使用最大堆和最小堆,中位数在最大堆和最小堆的堆顶中取得 Heap
(42)连续子数组的最大和 LC-53-Maximum Subarray
如果某步累加的结果不是正数,那么这些累加是可以抛弃的;否则可正常进行累加
Array Dynamic Programming
(43)从1到n整数中1出现的次数 Dynamic Programming
(44)数字序列中某一位的数字
(45)把数组排成最小的数
(46)把数字翻译成字符串 Recursion
(47)礼物的最大价值 LC-64-Minimum Path Sum Dynamic Programming
(48)最长不含重复字符的子字符串 LC-3-Longest Substring Without Repeating Characters Set
(49)丑数 根据丑数的定义,丑数应该是另一个丑数乘以2、3或者5的结果。
(50)第一个只出现一次的字符 基于字符的ASCII码创建一个简单的哈希表数组 Hash Table
(51)数组中的逆序对 Merge Sort
(52)两个链表的第一个公共节点 两个指针,先在长链表上走上差值的步数,最后两个指针一起走 Linked List
(53)在排序数组中查找数字 Binary Search
(54)二叉搜索树的第k个结点 树的中序遍历算法 Tree
(55)二叉树的深度 (1)LC-104-Maximum Depth of Binary Tree
(2)LC-110-Balanced Binary Tree
判断是不是平衡二叉树可以采用后序遍历算法
Tree
Recursion
(56)数组中数字出现的次数 任何一个数字异或它自己都等于0 Bit Manipulation
(57)和为s的数字 Array
(58)翻转字符串 多次不同范围的翻转可以解决问题 String
(59)队列的最大值 Queue Deque
(60)n个骰子的点数
(61)扑克牌的顺子
(62)圆圈中最后剩下的数字 数学解法:f(n,m)=\begin{cases} 0 & n=1 \\ [f(n-1,m)+m]\%n & n>1 \end{cases} Linked List
(63)股票的最大利润 保存目前数据中最小的数,用当前的数减去最小数得到当前利润,取当前利润和之前最大利润的最大值即可
(64)求1+2+…+n
(65)不用加减乘除做加法 CPU加法器的实现:使用位运算
相关问题,交换两个变量的值:
1. a = a + b; b = a - b; a = a - b;
2. a = a ^ b; b = a ^ b; a = a ^ b;
Bit Manipulation
(66)构建乘积数组
(67)把字符串转换成整数 LC-8-String to Integer (atoi) String
(68)树中两个结点的最低公共祖先 先求路径,然后在求最低公共祖先 Tree

LeetCode

Question Comment topic
1. Two Sum 利用HashTable的性质 Array Hash Table
2. Add Two Numbers Linked List
3. Longest Substring Without Repeating Characters CI-(48)最长不含重复字符的子字符串 String [Set
4. Median of Two Sorted Arrays 题目要求要O(log(m+n))的时间复杂度,所以只能二分递归查找 Binary Search Divide and Conquer
5. Longest Palindromic Substring 需要以i为end点,以max为标准进行扩展,判断max+1或max+2长度的字符串是不是回数 String
6. ZigZag Conversion 定义row个StringBuilder,遇到第0行或倒数第1行掉头,按顺序取字符即可 String
7. Reverse Integer 先处理无符号int,用long保存临时结果,每次累加后判断是不是溢出,最后加上符号
8. String to Integer (atoi) trim()清除头尾的空白字符串,然后判断第一位是不是符号位,然后在当前位是数字的情况下进行累加,每次累加完成后判断有没有溢出 String
9. Palindrome Number
10. Regular Expression Matching
11. Container With Most Water
12. Integer to Roman
13. Roman to Integer
14. Longest Common Prefix
15. 3Sum
16. 3Sum Closest
17. Letter Combinations of a Phone Number
18. 4Sum
19. Remove Nth Node From End of List
20. Valid Parentheses
21. Merge Two Sorted Lists
22. Generate Parentheses
23. Merge k Sorted Lists
24. Swap Nodes in Pairs
25. Reverse Nodes in k-Group
26. Remove Duplicates from Sorted Array
27. Remove Element
28. Implement strStr()
29. Divide Two Integers
30. Substring with Concatenation of All Words
31. Next Permutation
32. Longest Valid Parentheses
33. Search in Rotated Sorted Array
34. Find First and Last Position of Element in Sorted Array
35. Search Insert Position
36. Valid Sudoku
37. Sudoku Solver
38. Count and Say
39. Combination Sum
40. Combination Sum II
41. First Missing Positive
42. Trapping Rain Water
43. Multiply Strings
44. Wildcard Matching
45. Jump Game II
46. Permutations
47. Permutations II
48. Rotate Image
49. Group Anagrams
50. Pow(x, n)
51. N-Queens
52. N-Queens II
53. Maximum Subarray
54. Spiral Matrix
55. Jump Game
56. Merge Intervals
57. Insert Interval
58. Length of Last Word
59. Spiral Matrix II
60. Permutation Sequence
61. Rotate List
62. Unique Paths
63. Unique Paths II
64. Minimum Path Sum
65. Valid Number
66. Plus One
67. Add Binary
68. Text Justification
69. Sqrt(x)
70. Climbing Stairs
71. Simplify Path
72. Edit Distance
73. Set Matrix Zeroes
74. Search a 2D Matrix
75. Sort Colors
76. Minimum Window Substring
77. Combinations
78. Subsets
79. Word Search
80. Remove Duplicates from Sorted Array II
81. Search in Rotated Sorted Array II CI-(11)旋转数组的最小数字
82. Remove Duplicates from Sorted List II CI-18-2-删除链表中重复的结点
83. Remove Duplicates from Sorted List
84. Largest Rectangle in Histogram
85. Maximal Rectangle
86. Partition List
87. Scramble String
88. Merge Sorted Array
89. Gray Code
90. Subsets II
91. Decode Ways
92. Reverse Linked List II
93. Restore IP Addresses
94. Binary Tree Inorder Traversal
95. Unique Binary Search Trees II
96. Unique Binary Search Trees
97. Interleaving String
98. Validate Binary Search Tree
99. Recover Binary Search Tree
100. Same Tree
101. Symmetric Tree
102. Binary Tree Level Order Traversal
103. Binary Tree Zigzag Level Order Traversal
104. Maximum Depth of Binary Tree
105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
107. Binary Tree Level Order Traversal II
108. Convert Sorted Array to Binary Search Tree
109. Convert Sorted List to Binary Search Tree
110. Balanced Binary Tree
111. Minimum Depth of Binary Tree
112. Path Sum
113. Path Sum II
114. Flatten Binary Tree to Linked List
115. Distinct Subsequences
116. Populating Next Right Pointers in Each Node
117. Populating Next Right Pointers in Each Node II
118. Pascal’s Triangle
119. Pascal’s Triangle II
120. Triangle

常用技巧

Java中的最大(小)堆

在Java中可以利用PriorityQueue实现最小堆、最大堆。注意类型需要实现Comparable接口或者在创建PriorityQueue时需要注入Comparator实现。

// 最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(n, new Comparator<Integer>(){
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});
// lambda实现
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(n, (o1, o2) -> o2 - o1);

char ↔ int

  • int i = ch;
  • char ch = (char) i;

位运算

  1. 把一个整数减去1,再和原整数做位与运算,会把该整数最右边的1变成0
    这也可以判断一个数是不是2的整数次方
  2. 位运算交换两个变量的值:a = a ^ b; b = a ^ b; a = a ^ b;
  3. 任何一个数字异或它自己都等于0

最后更新: 2021年3月4日

评论