This is a record of my craking process for 剑指offer.
1. 二维数组中的查找
1.1 问题描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
1.2 解决方案
先将坐标定位在右上角，然后将该位置的值与target比较，如果target值比较大则坐标向下移动，否则坐标向左移动。
1
2
3
4
5
6
7
8
9
10
| public boolean Find(int target, int [][] array) {
int m = array.length - 1;
int n = array[0].length - 1;
for(int i = 0, j = n; i <= m && j >= 0;) {
if(array[i][j] == target) return true;
if(array[i][j] < target) i++;
else j--;
}
return false;
}
|
2 替换空格
2.1 问题描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
2.2 解决方案
这个问题只需要遍历一遍str就可以了，重点看一下StringBuffer的api
1
2
3
4
5
| public String replaceSpace(StringBuffer str) {
for(int i = 0; i < str.length(); i++)
if(str.charAt(i) == ' ') str.replace(i, i+1, "%20");
return str.toString();
}
|
3 从尾到头打印链表
3.1 问题描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
3.2 解决方案
这个问题只需要遍历一遍链表然后把得到的数值插入ArrayList的第一个位置上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
while(listNode != null) {
res.add(0,listNode.val);
listNode = listNode.next;
}
return res;
}
}
|
4 重建二叉树
4.1 问题描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
4.2 解决方案
根据前序遍历的第一个元素为根结点，然后在中序遍历中找到根结点的位置则中序遍历中根前面的一段数组为根的左子树，中序遍历中后一半数组为根的右子树。而后递归求解。
举例：前序遍历数组中第一个元素为1，说明根结点为1 然后在中序遍历数组中寻找1的左子树为{4,7,2},右子树为{5,3,8,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
31
32
33
34
35
|
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root = new TreeNode(pre[0]);
for(int i = 0; i < in.length; i++) {
if(pre[0] == in[i]) {
root.left = helper(pre, in, 1, i, 0, i - 1);
root.right = helper(pre, in, i + 1, pre.length - 1, i + 1, in.length - 1);
return root;
}
}
return null;
}
private TreeNode helper(int[] pre, int[] in, int lpre, int rpre,
int lin, int rin) {
if(lpre == rpre) return new TreeNode(pre[lpre]);
for(int i = lin; i <= rin; i++) {
if(in[i] == pre[lpre]) {
TreeNode root = new TreeNode(pre[lpre]);
root.left = helper(pre, in, lpre + 1, lpre + i - lin, lin, i - 1);
root.right = helper(pre, in, lpre + i - lin + 1, rpre, i + 1, rin);
return root;
}
}
return null;
}
}
|
5 用两个栈实现队列
5.1 问题描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
5.2 解决方案
第一个栈只负责将新入队列的数值押入栈。当进行出“队列”操作时，先检测右边的栈是否为空，如果为空，则将第一个栈中的数字依次弹出并将数值依次押入第二个栈，然后再从第二个栈中pop出一个值。如果第二个栈不为空，则直接从第二个栈中pop一个数值。
核心思想是利用两个栈将输入的值逆序存放在第二个栈中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack2.size() != 0) return stack2.pop();
while(!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
|
6 旋转数组的最小数字
6.1 问题描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
6.2 解决方案
从左向右扫描数组，默认是递增的，如果发现后一个数字比前一个数字小，则后一个数字一定是最小的数字。
1
2
3
4
5
6
7
8
9
10
| import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0) return 0;
for(int i = 1; i < array.length; i++) {
if(array[i] < array[i - 1]) return array[i];
}
return array[0];
}
}
|
7 斐波那契数列
7.1 问题描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
7.2 解决方案
=.=不解释了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Solution {
public int Fibonacci(int n) {
if( n == 0) return 0;
if( n == 1) return 1;
if( n == 2) return 1;
int num1 = 1, num2 = 1;
for(int i = 3; i <= n; i++) {
int temp = num1 + num2;
num2 = num1;
num1 = temp;
}
return num1;
}
}
|
8 跳台阶
8.1 问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
N.2 解决方案
每次跳一阶或者两阶，直接递归求解
1
2
3
4
5
6
7
8
| public class Solution {
public int JumpFloor(int target) {
if(target == 1) return 1;
if(target == 2) return 2;
if(target == 0) return 0;
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
|
9 变态跳台阶
9.1 问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
9.2 解决方案
青蛙跳n阶台阶有如下几种跳法
从第 1 阶跳 n-1 台阶
从第 2 阶跳 n-2 台阶
从第 3 阶跳 n-3 台阶
从第 4 阶跳 n-4 台阶
从第 5 阶跳 n-5 台阶
…
从第 n-1 阶跳 1 阶
那么总的跳法 f(n) = f(1) + f(2) + … + f(n - 1)
又因为f(n - 1) = f(1) + f(2) + … + f(n - 2)
所以 f(n) = 2 * f(n - 1) 【递推式已有】
1
2
3
4
5
6
7
8
| public class Solution {
public int JumpFloorII(int target) {
if(target == 0) return 0;
if(target == 1) return 1;
if(target == 2) return 2;
return 2 * JumpFloorII(target - 1);
}
}
|
10.矩形覆盖
10.1 问题描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
10.2 解决方案
覆盖2 * 1（宽 * 长）只有一种办法
覆盖(2*2)矩形有横着铺两块竖着铺两块两种方法
覆盖(23)矩形有覆盖(22)的方法 + 覆盖(2*1)的方法
覆盖2 * n面积的矩形有覆盖n*(n - 2)的方法 + 覆盖n*(n-1)的方法
1
2
3
4
5
6
7
8
| public class Solution {
public int RectCover(int target) {
if(target == 0) return 0;
if(target == 1) return 1;
if(target == 2) return 2;
return RectCover(target - 1) + RectCover(target - 2);
}
}
|
11 二进制中1的个数
11.1 问题描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
11.2 解决方案
每次只关心n的二进制最后一位
如果最后一位是1，那么 n - 1 最后一位就是零，进行一次 n & (n - 1)后最后一位变为0，然后逐步向前继续寻找1。
如果最后一位是0，那么就不管他了直接看倒数第二位，如果倒数第二位是1 同理经过 n & (n - 1)后倒数第二位的1也置0了计数器加一。
以此类推知道原来的数字全变为0了，做了几次n & (n - 1)就说明原来的数字有几个1
1
2
3
4
5
6
7
8
9
10
| public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0) {
n &= n - 1;
count++;
}
return count;
}
}
|
12 数值的整数次方
12.1 问题描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
12.2 解决方案
2的4次方可以拆成 (2^2)^(4/2)
3的四次方可以拆成 (3^2)^(4/2)
注意处理exponent为负数以及奇数的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution {
public double Power(double base, int exponent) {
if(exponent == 0) return 1.0;
if(base == 0) return 0.0;
if(exponent >= 0)
return PositivePower(base, exponent);
else
return 1/PositivePower(base, 0-exponent);
}
public double PositivePower(double base, int exponent){
if(exponent == 1 || exponent == 0)
return base;
else if(exponent % 2 == 0)
return Power(base * base, exponent / 2);
else
return Power(base * base, exponent / 2) * base;
}
}
|
13 调整数组顺序使奇数位于偶数前面
13.1 问题描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
13.2 解决方案
定义两个变量i,j i找到第一个偶数，j从i+1的位置开始找找到第一个奇数，i到j之间的数字必为偶数。将 i 到 j 的数字依次后移，然后将j位置的奇数放到前面去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution {
public void reOrderArray(int [] array) {
int p = 0, q = 0;
while(p < array.length) {
while(p < array.length && array[p] % 2 != 0) p++;
q = p + 1;
while(q < array.length && array[q] % 2 != 1) q++;
if(q >= array.length) break;
int tmp = array[q];
for(int i = q - 1; i >= p; i--) {
array[i + 1] = array[i];
}
array[p++] = tmp;
}
}
}
|
14 链表中倒数第k个结点
14.1 问题描述
输入一个链表，输出该链表中倒数第k个结点。
14.2 解决方案
没啥好说的定义两个指针同时向后移动。注意testcase 有 链表为空或者k=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
|
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null) return head;
if(k == 0) return null;
ListNode p = head;
ListNode q = head;
for(int i = 0; i < k; i++) {
if(q == null) return null;
q = q.next;
}
while(q != null) {
p = p.next;
q = q.next;
}
return p;
}
}
|
15 反转链表
15.1 问题描述
输入一个链表，反转链表后，输出新链表的表头。
15.2 解决方案
定义一个虚拟头部dummy,做正常的反转操作即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p = head;
while(p.next != null) {
ListNode point = p.next.next;
p.next.next = dummy.next;
dummy.next = p.next;
p.next = point;
}
return dummy.next;
}
}
|
16 合并两个排序的链表
16.1 问题描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
16.2 解决方案
归并排序思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode p = list1;
ListNode q = list2;
ListNode dummy = new ListNode(0);
ListNode ans = dummy;
while(p != null && q != null) {
if(p.val <= q.val) {
dummy.next = p;
p = p.next;
} else {
dummy.next = q;
q = q.next;
}
dummy = dummy.next;
}
if(p == null) dummy.next = q;
else dummy.next = p;
return ans.next;
}
}
|
17 工具模版
17.1 问题描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
17.2 解决方案
递归比较就好了～
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root2 == null) return false;
if(root1 == null) return false;
return helper(root1, root2) ||
HasSubtree(root1.left, root2) ||
HasSubtree(root1.right, root2);
}
public boolean helper(TreeNode root1, TreeNode root2) {
if(root2 == null) return true;
if(root1 == null) return false;
return root1.val == root2.val &&
helper(root1.left, root2.left) &&
helper(root1.right, root2.right);
}
}
|
18 二叉树的镜像
18.1 问题描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
18.2 解决方案
先把根结点左右节点交换，然后再对左右节点递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class Solution {
public void Mirror(TreeNode root) {
if(root == null) return;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
Mirror(root.left);
Mirror(root.right);
}
}
|
19 顺时针打印矩阵
19.1 问题描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
19.2 解决方案
旋转打印就好 向右 向下 向左 向上 …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> ans = new ArrayList<Integer>();
if(matrix.length == 0) return ans;
int m = matrix.length;
int n = matrix[0].length;
int i = 0,j = 0;
int direction = 0;
for(int count = 0; count < m * n; count++) {
if(direction % 4 == 0) {
ans.add(matrix[i][j]);
if(j == n - 1 - direction / 4) {
direction += 1;
i++;
} else {
j++;
}
} else if(direction % 4 == 1) {
ans.add(matrix[i][j]);
if(i == m - 1 - direction / 4) {
direction += 1;
j--;
}
else
i++;
} else if(direction % 4 == 2) {
ans.add(matrix[i][j]);
if(j == 0 + direction / 4) {
direction += 1;
i--;
}
else
j--;
} else {
ans.add(matrix[i][j]);
if(i == 1 + direction / 4) {
direction += 1;
j++;
}
else
i--;
}
}
return ans;
}
}
|
20 包含min函数的栈
20.1 问题描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
20.2 解决方案
准备两个栈，一个栈做正常的push，pop操作。第二个栈记录当前的最小值，如果最小值即将从第一个栈中pop出去，那么他也从第二个栈中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
| import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
if(stack2.empty() || node < stack2.peek()) {
stack2.push(node);
}
}
public void pop() {
if(stack1.peek() == stack2.peek()) stack2.pop();
stack1.pop();
}
public int top() {
return stack1.peek();
}
public int min() {
return stack2.peek();
}
}
|
21 栈的压入、弹出序列
21.1 问题描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
21.2 解决方案
解法如下根据popA的结果来模拟原来栈的插入和弹出过程。
- 如果栈顶元素和popA的当前元素不同，则继续push元素
- 如果栈顶元素和popA的当前元素相同，则弹出栈的当前元素并把popA的当前位置后移一个
- 最后如果pushA数组中的元素完全进入了栈中，则弹出序列已经无法更改，直接把栈中元素一个个弹出和popA数组的剩余元素比就好了
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
| import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0) return false;
if(pushA.length == 1) return pushA[0] == popA[0];
Stack<Integer> stack = new Stack<>();
int i = 0, j = 0;
while(i < pushA.length) {
if(stack.empty() || stack.peek() != popA[j]) {
stack.push(pushA[i++]);
} else {
stack.pop();
j++;
}
}
if(j == popA.length - 1) return true;
else {
for(int k = j; k < popA.length; k++) {
if(popA[k] != stack.pop()) return false;
}
return true;
}
}
}
|
22 从上往下打印二叉树
22.1 问题描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
22.2 解决方案
很简单的队列操作 每次把根结点的值提出来然后把他的对应的子节点押入新队列然后用新队列替换掉老队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if(root == null) return new ArrayList<Integer>();
ArrayList<TreeNode> helperArr = new ArrayList<>();
ArrayList<Integer> ans = new ArrayList<>();
if(root.left == null && root.right == null) {
ans.add(root.val);
return ans;
}
helperArr.add(root);
while(helperArr.size() != 0) {
ArrayList<TreeNode> temp = new ArrayList<>();
for(int i = 0; i < helperArr.size(); i++) {
TreeNode node = helperArr.get(i);
ans.add(node.val);
if(node.left != null) {
temp.add(node.left);
}
if(node.right != null) {
temp.add(node.right);
}
}
helperArr = temp;
}
return ans;
}
}
|
23 二叉搜索树的后序遍历序列
23.1 问题描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
23.2 解决方案
递归操作，根据二叉搜索树的特点寻找左子树与右子树的分界点然后递归操作就可以啦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length == 0) return false;
return verify(sequence, 0, sequence.length - 1);
}
private boolean verify(int [] sequence, int l, int r) {
if(l >= r) return true;
int i = r;
while(i > l && sequence[i] >= sequence[r]) --i;
for(int j = i - 1; j >= l; j--)
if(sequence[j] > sequence[r])
return false;
return verify(sequence,l, i - 1) && verify(sequence, i, r - 1);
}
}
|
24 二叉树中和为某一值的路径
24.1 问题描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
24.2 解决方案
标准深度优先遍历 注意corner case
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
| import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) return new ArrayList<>();
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
helper(ans, new ArrayList(), root, target);
return ans;
}
private void helper(ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> tempList, TreeNode node,int target) {
if(target == node.val && node.left == null && node.right == null) {
tempList.add(node.val);
ans.add(new ArrayList<Integer>(tempList));
tempList.remove(tempList.size()-1);
} else {
if(node.left != null) {
tempList.add(node.val);
helper(ans, tempList, node.left, target - node.val);
tempList.remove(tempList.size()-1);
}
if(node.right != null) {
tempList.add(node.val);
helper(ans, tempList, node.right, target - node.val);
tempList.remove(tempList.size()-1);
}
}
}
}
|
N 工具模版
N.1 问题描述
xxx
N.2 解决方案
xxx
1
| System.out.println("工具人");
|