剑指offer
题目来自leetcode剑指offer。
字符串
剑指 Offer 20. 表示数值的字符串(中等)
题目
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
- 若干空格
- 一个 小数 或者 整数
- （可选）一个
'e'或'E'，后面跟着一个 整数 - 若干空格
小数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（
'+'或'-'） - 下述格式之一：
- 至少一位数字，后面跟着一个点
'.' - 至少一位数字，后面跟着一个点
'.'，后面再跟着至少一位数字 - 一个点
'.'，后面跟着至少一位数字
- 至少一位数字，后面跟着一个点
整数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（
'+'或'-'） - 至少一位数字
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
示例：
示例1：
输入：s = "0"
输出：true
示例2：
输入：s = "e"
输出：false
示例3：
输入：s = "."
输出：false
示例4：
输入：s = " .1 "
输出：true
解法
- 如果当前字符c是数字：将hasNum置为true，index往后移动一直到非数字或遍历到末尾位置；如果已遍历到末尾(index == n)，结束循环
- 如果当前字符c是’e’或’E’：如果e已经出现或者当前e之前没有出现过数字，返回fasle；否则令hasE = true，并且将其他3个flag全部置为false，因为要开始遍历e后面的新数字了
- 如果当前字符c是+或-：如果已经出现过+或-或者已经出现过数字或者已经出现过’.’，返回flase；否则令hasSign = true
- 如果当前字符c是’.’：如果已经出现过’.’或者已经出现过’e’或’E’，返回false；否则令hasDot = true
- 如果当前字符c是’ ‘：结束循环，因为可能是末尾的空格了，但也有可能是字符串中间的空格，在循环外继续处理
- 如果当前字符c是除了上面5种情况以外的其他字符，直接返回false
class Solution {
public boolean isNumber(String s) {
int n = s.length();
int index = 0;
boolean hasNum = false, hasE = false;
boolean hasSign = false, hasDot = false;
while(index < n && s.charAt(index) == ' ')
index++;
while(index < n){
while(index < n && s.charAt(index) >= '0' && s.charAt(index) <= '9'){
index++;
hasNum = true;
}
if(index == n){
break;
}
char c = s.charAt(index);
if(c == 'e' || c == 'E'){
if(hasE || !hasNum){
return false;
}
hasE = true;
hasNum = false; hasSign = false; hasDot = false;
}else if(c == '+' || c == '-'){
if(hasSign || hasNum || hasDot){
return false;
}
hasSign = true;
}else if(c == '.'){
if(hasDot || hasE){
return false;
}
hasDot = true;
}else if(c == ' '){
break;
}else{
return false;
}
index++;
}
while(index < n && s.charAt(index) == ' ')
index++;
return hasNum && index == n;
}
}
剑指 Offer 67. 把字符串转换成整数(中等)
题目
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例：
示例1：
输入: "42"
输出: 42
示例2：
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例3：
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例4：
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例5：
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
解法
- 首部空格： 删除之即可；
- 符号位： 三种情况，即 ‘’+++’’ , ‘‘−-−’’ , ‘‘无符号” ；新建一个变量保存符号位，返回前判断正负即可。
- 非数字字符： 遇到首个非数字的字符时，应立即返回。
- 数字字符：
- 字符转数字： “此数字的 ASCII 码” 与 “ 000 的 ASCII 码” 相减即可；
- 数字拼接： 若从左向右遍历数字，设当前位字符为 c ，当前位数字为 x ，数字结果为 res ，则数字拼接公式为
class Solution {
public int strToInt(String str) {
// trim()方法删掉字符串首尾的空格
char[] c = str.trim().toCharArray();
if(c.length == 0)
return 0;
int res = 0, bndry = Integer.MAX_VALUE / 10;
// i是数字起始位，sign是正负号
int i = 1, sign = 1;
if(c[0] == '-')
sign = -1;
else if(c[0] != '+')
i = 0;
for(int j = i; j < c.length; j++) {
if(c[j] < '0' || c[j] > '9')
break;
// Integer.MAX_VALUE = 2147483647
if(res > bndry || res == bndry && c[j] > '7')
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (c[j] - '0');
}
return sign * res;
}
}
注意if(c.length == 0)的判断不能提前写成if(str.length() == 0)，因为后者不能判断一个空格的字符串” “的测试用例。
链表
剑指 Offer 35. 复杂链表的复制(中等)
题目
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
解法1 回溯、哈希
class Solution {
Map<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if(head == null)
return null;
if(!map.containsKey(head)) {
Node newHead = new Node(head.val);
map.put(head, newHead);
newHead.next = copyRandomList(head.next);
newHead.random = copyRandomList(head.random);
}
return map.get(head);
}
}
解法2 迭代、节点拆分
class Solution {
public Node copyRandomList(Node head) {
if(head == null)
return null;
for(Node node = head; node != null; node = node.next.next) {
Node newNode = new Node(node.val);
newNode.next = node.next;
node.next = newNode;
}
for(Node node = head; node != null; node = node.next.next) {
Node newNode = node.next;
newNode.random = (node.random == null) ? null : node.random.next;
}
Node newHead = head.next;
for(Node node = head; node != null; node = node.next) {
Node newNode = node.next;
node.next = node.next.next;
newNode.next = (newNode.next == null) ? null : newNode.next.next;
}
return newHead;
}
}
双指针
剑指 Offer 52. 两个链表的第一个公共节点(简单)
题目
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：如果两个链表没有交点，返回 null.
解法 双指针
这道题在牛客做时，确定了链表是一定有公共节点的。但是这题有可能没有公共节点。所以迭代时不能写cur1 = cur1.next == null ? headB : cur1.next;，而必须写cur1 = cur1 == null ? headB : cur1.next;。当两个链表没有公共节点时，不管两个链表长度相同还是不相同，双指针都同时指向null。
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode cur1 = headA;
ListNode cur2 = headB;
while(cur1 != cur2) {
cur1 = cur1 == null ? headB : cur1.next;
cur2 = cur2 == null ? headA : cur2.next;
}
return cur1;
}
}
剑指 Offer 58 - I. 翻转单词顺序(简单)
题目
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
解法1 双指针
倒序遍历字符串 sss ，记录单词左右索引边界 iii , jjj ；
每确定一个单词的边界，则将其添加至单词列表 resresres ；
最终，将单词列表拼接为字符串，并返回即可。
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ')
i--; // 搜索首个空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while(i >= 0 && s.charAt(i) == ' ')
i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回
}
}
解法2 分割、倒序
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
if(strs[i].equals(""))
continue; // 遇到空单词则跳过
res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
}
return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
}
}
注意：
- 使用equals()方法判断字符串是否相同；
- 判断和空字符串”“是否相同，而不是判断和空格” “是否相同。
栈与队列
剑指 Offer 59 - I. 滑动窗口的最大值(较难)
题目
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。
解法 双向队列
Deque是双向队列。滑动时，如果滑出去的值存在则位于队列头，删除；将滑进来的值添加到队尾。但是为了使队首元素最大使得方便返回窗口内最大值，应使deque递减。所以删除队尾，直到队尾的值不小于新滑进来的值（或者删到队列为空）。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
// 删除 deque 中对应的 nums[i-1]
if(i > 0 && deque.peekFirst() == nums[i - 1])
deque.removeFirst();
// 保持 deque 递减
while(!deque.isEmpty() && deque.peekLast() < nums[j])
deque.removeLast();
deque.addLast(nums[j]);
// 记录窗口最大值
if(i >= 0)
res[i] = deque.peekFirst();
}
return res;
}
}
注意双向队列的方法。可以在队首和队尾加入、删除、返回头。
剑指 Offer 59 - II. 队列的最大值(中等)
题目
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
解法
使用双向队列deque储存最大元素，使其单调不增，即在队尾加入时如果加入值大于队尾值，则弹出队尾。这样可保证双向队列队首是当前队列的最大值。
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList<>();
deque = new LinkedList<>();
}
public int max_value() {
return deque.isEmpty() ? -1 : deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
while(!deque.isEmpty() && deque.peekLast() < value)
deque.pollLast();
deque.offerLast(value);
}
public int pop_front() {
if(queue.isEmpty()) return -1;
if(queue.peek().equals(deque.peekFirst()))
deque.pollFirst();
return queue.poll();
}
}
模拟
剑指 Offer 31. 栈的压入、弹出序列(中等)
题目
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
解法
栈顶元素匹配popped，则出栈。最后判断栈是否为空。
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stk = new Stack<>();
int i = 0;
for(int num : pushed) {
stk.push(num);
while(!stk.isEmpty() && stk.peek() == popped[i]) {
stk.pop();
i++;
}
}
return stk.isEmpty();
}
}
查找算法
剑指 Offer 53 - I. 在排序数组中查找数字 I(简单)
题目
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
解法
二分寻找左右边界，然后相减求区间长度。
class Solution {
public int search(int[] nums, int target) {
return searchBndry(nums, target) - searchBndry(nums, target - 1);
}
int searchBndry(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] <= target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
}
搜索与回溯算法
剑指 Offer 26. 树的子结构(中等)
题目
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
解法
recur判断是否相同，isSubStructure递归遍历左右子树。
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
if(B == null)
return true;
if(A == null || A.val != B.val)
return false;
return recur(A.left, B.left) && recur(A.right, B.right);
}
}
剑指 Offer 12. 矩阵中的路径(中等)
题目
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
解法 dfs、剪枝
class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(dfs(board, words, i, j, 0))
return true;
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
if(i == board.length || i < 0 || j == board[0].length || j < 0 || board[i][j] != word[k])
return false;
if(k == word.length - 1)
return true;
board[i][j] = '0'; // 标记走过，防止重复
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k]; // 回溯，撤销走过的标记
return res;
}
}
剑指 Offer 13. 机器人的运动范围(中等)
题目
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：1 <= n,m <= 100 0 <= k <= 20
解法
class Solution {
int m, n, k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m; this.n = n; this.k = k;
this.visited = new boolean[m][n];
return dfs(0, 0, 0, 0);
}
public int dfs(int i, int j, int si, int sj) {
if(i >= m || j >= n || k < si + sj || visited[i][j])
return 0;
visited[i][j] = true;
return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
}
}
剑指 Offer 34. 二叉树中和为某一值的路径(中等)
题目
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
解法 回溯
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast(); // removeLast方法是LinkedList类的方法，List类没有
}
}
剑指 Offer 36. 二叉搜索树与双向链表(中等)
题目
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解法 中序遍历、双向链表
二叉搜索树的中序遍历是增序。
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null)
return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null)
return ;
dfs(cur.left);
if(pre != null)
pre.right = cur;
else
head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
剑指 Offer 54. 二叉搜索树的第k大节点(简单)
题目
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
解法 中序遍历
二叉搜索树的中序遍历为递增顺序，中序遍历的倒序为递减顺序。遍历到第k个时为第k大的节点。
class Solution {
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
public void dfs(TreeNode root) {
if(root == null)
return ;
dfs(root.right);
if(k == 0)
return ;
if(--k == 0)
res = root.val; // 由于要遍历左子树，所以下一个递归k==0才返回
dfs(root.left);
}
}
剑指 Offer 55 - II. 平衡二叉树(简单)
题目
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
解法 后序遍历、剪枝
class Solution {
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}
private int recur(TreeNode root) {
if(root == null)
return 0;
int left = recur(root.left);
int right = recur(root.right);
if(left == -1 || right == -1)
return -1;
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
}
剑指 Offer 64. 求1+2+…+n(中等)
题目
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
解法 逻辑运算符
逻辑运算符的短路效应。
class Solution {
int res = 0;
public int sumNums(int n) {
boolean x = n > 1 && sumNums(n - 1) > 0;
res += n;
return res;
}
}
分治算法
剑指 Offer 16. 数值的整数次方(中等)
题目
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
解法 快速幂
class Solution {
public double myPow(double x, int n) {
if(x == 0)
return 0;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1)
res *= x;
x *= x;
b >>= 1;
}
return res;
}
}
剑指 Offer 33. 二叉搜索树的后序遍历序列(中等)
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
解法 递归分治
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
boolean recur(int[] postorder, int left, int right) {
if(left >= right)
return true;
int i = left;
while(postorder[i] < postorder[right])
i++;
int mid = i;
while(postorder[i] > postorder[right])
i++;
return i == right && recur(postorder, left, mid - 1) && recur(postorder, mid, right - 1);
}
}
剑指 Offer 51. 数组中的逆序对(困难)
题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
解法
class Solution {
//利用归并排序解答，在合并的时候，当左边的大于右边，就计算逆序数。
//计算公式； mid-left+1
//定义一个全局的计数器变量
int count = 0;
public int reversePairs(int[] nums) {
this.count = 0;
mergeSort(nums, 0, nums.length - 1);
return count;
}
public void mergeSort(int[] nums,int left,int right){
//当只有一个节点的时候，直接返回，退出递归
if(left >= right){
return;
}
int mid = (left + right) / 2;
//左拆分
mergeSort(nums, left, mid);
//右拆分
mergeSort(nums, mid+1, right);
//合并
merge(nums, left, mid, right);
}
public void merge(int[] nums,int left,int mid,int right){
//定义一个临时数组
int[] temp = new int[right - left + 1];
//定义一个指针，指向第一个数组的第一个元素
int i = left;
//定义一个指针，指向第二个数组的第一个元素
int j = mid + 1;
//定义一个指针，指向临时数组的第一个元素
int t = 0;
//当两个数组都有元素的时候，遍历比较每个元素大小
while(i <= mid && j <= right){
//比较两个数组的元素，取较小的元素加入到，临时数组中
//并将两个指针指向下一个元素
if(nums[i] <= nums[j]){
temp[t++] = nums[i++];
}else{
//当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
//此时这个数就是，逆序数
//定义一个计数器，记下每次合并中存在的逆序数。
count += mid - i + 1;
temp[t++] = nums[j++];
}
}
//当左边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
while(i <= mid){
temp[t++] = nums[i++];
}
//当右边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
while(j <= right){
temp[t++] = nums[j++];
}
//将新数组中的元素，覆盖nums旧数组中的元素。
//此时数组的元素已经是有序的
for(int k = 0; k < temp.length; k++){
nums[left + k] = temp[k];
}
}
}
排序
剑指 Offer 45. 把数组排成最小的数(中等)
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
解法1 快速排序
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]); // int转换为String
}
quickSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
void quickSort(String[] strs, int left, int right) {
if(left >= right)
return;
int i = left, j = right;
String temp = strs[i];
while(i < j) {
while((strs[j] + strs[left]).compareTo(strs[left] + strs[j]) >= 0 && i < j)
j--;
while((strs[i] + strs[left]).compareTo(strs[left] + strs[i]) <= 0 && i < j)
i++;
temp = strs[i];
strs[i] = strs[j];
strs[j] = temp;
}
strs[i] = strs[left];
strs[left] = temp;
quickSort(strs, left, i - 1);
quickSort(strs, i + 1, right);
}
}
解法2 内置函数
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
strs[i] = String.valueOf(nums[i]);
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}
剑指 Offer 40. 最小的k个数(简单)
题目
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
解法 快速排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
quickSort(arr, 0, arr.length - 1);
return Arrays.copyOf(arr, k);
}
private void quickSort(int[] arr, int l, int r) {
// 子数组长度为 1 时终止递归
if (l >= r) return;
// 哨兵划分操作（以 arr[l] 作为基准数）
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= arr[l]) j--;
while (i < j && arr[i] <= arr[l]) i++;
swap(arr, i, j);
}
swap(arr, i, l);
// 递归左（右）子数组执行哨兵划分
quickSort(arr, l, i - 1);
quickSort(arr, i + 1, r);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
动态规划
剑指 Offer 47. 礼物的最大价值(中等)
题目
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
解法
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i > 0)
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
if(j > 0)
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
dp[i][j] += grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
剑指 Offer 46. 把数字翻译成字符串(中等)
题目
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
解法
class Solution {
public int translateNum(int num) {
char[] ch = String.valueOf(num).toCharArray();
int len = ch.length;
int[] dp = new int[len + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= len; i++) {
int n = (ch[i - 2] - '0') * 10 + (ch[i - 1] - '0');
if(n >= 10 && n <= 25)
dp[i] = dp[i - 1] + dp[i - 2];
else
dp[i] = dp[i - 1];
}
return dp[len];
}
}
剑指 Offer 48. 最长不含重复字符的子字符串(中等)
题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解法 动态规划、哈希
固定右边界 j ，设字符 s[j] 左边距离最近的相同字符为 s[i] ，即 s[i]=s[j]
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = dic.getOrDefault(s.charAt(j), -1);
dic.put(s.charAt(j), j);
tmp = tmp < j - i ? tmp + 1 : j - i;
res = Math.max(res, tmp);
}
return res;
}
}
剑指 Offer 19. 正则表达式匹配(困难)
题目
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母以及字符.和*，无连续的'*'。
解法 动态规划 (似懂非懂)
class Solution {
public boolean isMatch(String A, String B) {
int n = A.length();
int m = B.length();
boolean[][] f = new boolean[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
//分成空正则和非空正则两种
if (j == 0) {
f[i][j] = i == 0;
} else {
//非空正则分为两种情况 * 和 非*
if (B.charAt(j - 1) != '*') {
if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) {
f[i][j] = f[i - 1][j - 1];
}
} else {
//碰到 * 了，分为看和不看两种情况
//不看
if (j >= 2) {
f[i][j] |= f[i][j - 2];
}
//看
if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) {
f[i][j] |= f[i - 1][j];
}
}
}
}
}
return f[n][m];
}
}
剑指 Offer 49. 丑数(中等)
题目
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
解法 动态规划
class Solution {
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for(int i = 1; i < n; i++) {
dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
if(dp[i] == dp[a] * 2)
a++;
if(dp[i] == dp[b] * 3)
b++;
if(dp[i] == dp[c] * 5)
c++;
}
return dp[n - 1];
}
}
剑指 Offer 60. n个骰子的点数(中等)
题目
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
解法 动态规划
class Solution {
public double[] dicesProbability(int n) {
double[] dp = new double[6];
Arrays.fill(dp, 1.0 / 6.0);
for(int i = 2; i <= n; i++) {
double[] tmp = new double[5 * i + 1];
for(int j = 0; j < dp.length; j++)
for(int k = 0; k < 6; k++)
tmp[j + k] += dp[j] / 6.0;
dp = tmp;
}
return dp;
}
}
位运算
剑指 Offer 15. 二进制中1的个数(简单)
题目
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数
-3。
示例 1：
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
解法 按位与、右移
public class Solution {
public int hammingWeight(int n) {
int res = 0;
while(n != 0) {
res += n & 1;
n >>>= 1; // 右移1位
}
return res;
}
}
剑指 Offer 65. 不用加减乘除做加法(简单)
题目
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
解法
非进位和：异或；进位：与、左移
class Solution {
public int add(int a, int b) {
while(b != 0) {
int c = (a & b) << 1;
a ^= b;
b = c;
}
return a;
}
}
数学
剑指 Offer 39. 数组中出现次数超过一半的数字(简单)
题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
解法1 哈希表
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums) {
if(!map.containsKey(num))
map.put(num, 1);
else
map.put(num, map.get(num) + 1);
if(map.get(num) > nums.length / 2)
return num;
}
return 0;
}
}
解法2 数组排序
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
解法3 摩尔投票
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for(int num : nums) {
if(votes == 0)
x = num;
votes += num == x ? 1 : -1;
}
return x;
}
}
剑指 Offer 66. 构建乘积数组(中等)
题目
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
提示：
- 所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
解法 矩阵
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
if(len == 0)
return new int[0];
int[] b = new int[len];
b[0] = 1;
int tmp = 1;
// 计算矩阵上三角乘积
for(int i = 1; i < len; i++) {
b[i] = b[i - 1] * a[i - 1];
}
// 计算矩阵下三角乘积
for(int i = len - 2; i >= 0; i--) {
tmp *= a[i + 1];
b[i] *= tmp;
}
return b;
}
}
剑指 Offer 14- I. 剪绳子(中等)
题目
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
解法 数学
经过推理，分成多个3乘积最大。
class Solution {
public int cuttingRope(int n) {
if(n <= 3)
return n - 1;
int a = n / 3, b = n % 3;
if(b == 0)
return (int)Math.pow(3, a);
if(b == 1)
return (int)Math.pow(3, a - 1) * 4;
return (int)Math.pow(3, a) * 2;
}
}
剑指 Offer 14- II. 剪绳子 II(中等)
题目
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 1000
解法 大数求余
class Solution {
public int cuttingRope(int n) {
if(n <= 3)
return n - 1;
int b = n % 3, p = 1000000007;
long ret = 1;
int lineNums = n / 3; //线段被我们分成以3为大小的小线段个数
for(int i = 1; i < lineNums; i++) //从第一段线段开始验算，3的ret次方是否越界。注意是验算lineNums-1次。
ret = 3 * ret % p;
if(b == 0)
return (int)(ret * 3 % p); //刚好被3整数的，要算上前一段
if(b == 1)
return (int)(ret * 4 % p); //被3整数余1的，要算上前一段
return (int)(ret * 6 % p); //被3整数余2的，要算上前一段
}
}
剑指 Offer 57 - II. 和为s的连续正数序列(简单)
题目
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
解法 滑动窗口
public int[][] findContinuousSequence(int target) {
int i = 1; // 滑动窗口的左边界
int j = 1; // 滑动窗口的右边界
int sum = 0; // 滑动窗口中数字的和
List<int[]> res = new ArrayList<>();
while (i <= target / 2) {
if (sum < target) {
// 右边界向右移动
sum += j;
j++;
} else if (sum > target) {
// 左边界向右移动
sum -= i;
i++;
} else {
// 记录结果
int[] arr = new int[j-i];
for (int k = i; k < j; k++) {
arr[k-i] = k;
}
res.add(arr);
// 左边界向右移动
sum -= i;
i++;
}
}
return res.toArray(new int[res.size()][]);
}