数组
找出数组中重复的数字
题目： 在一个长度为n的数组里的所有数字都在0~n-1的范围内，数组中某些数字时重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
思路：
遍历数组通过将遍历过的元素放入hash表可以以O(1)的时间复杂度验证数字是否是重复的。时间复杂度为O(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
23import java.util.HashMap;
public class Main {
public static void main(String[] args) {
int result = duplicate(new int[]{4, 3, 1, 0, 2, 4, 6});
System.out.println(result);
}
private static int duplicate(int[] numbers) {
if (numbers == null || numbers.length <= 0) {
return -1;
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int number : numbers) {
if (map.containsKey(number)) {
return number;
}
map.put(number, 1);
}
return -1;
}
}考虑到数组中的数字都在0~n-1的氛围内，如果数组中没有重复数字，那么数组元素的值应该是和数组下标对应的。那么只要将原数组中的元素放在对应的下标下即可找到有多少重复。时间复杂度O(n)，空间复杂度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
27public class Main {
public static void main(String[] args) {
int result = duplicate(new int[]{4, 3, 3, 0, 2, 4, 6});
System.out.println(result);
}
private static int duplicate(int[] numbers) {
if (numbers == null || numbers.length <= 0) {
return -1;
}
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] < 0 || numbers[i] >= numbers.length) {
throw new IllegalArgumentException("Number " + numbers[i] + " is not in rang 0~" + (numbers.length - 1));
}
while (numbers[i] != i) {
if (numbers[i] == numbers[numbers[i]]) {
return numbers[i];
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return -1;
}
}
出自《剑指offer》第二版面试题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
30public class Main {
public static void main(String[] args) {
int[][] matrix = new int[][]{
{1, 2, 8, 9},
{2, 4, 9, 12},
{4, 7, 10, 13},
{6, 8, 11, 15}
};
boolean result = find(matrix, 9);
System.out.println(result);
}
private static boolean find(int[][] matrix, int number) {
if (matrix == null || matrix.length == 0) {
return false;
}
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == number) {
return true;
} else if (matrix[row][col] < number) {
++row;
} else {
--col;
}
}
return false;
}
}
出自《剑指offer》第二版面试题4
字符串
链表
从尾到头打印链表
题目： 输入一个链表的头节点，从尾到头反过来打印每个节点的值，链表节点的定义如下：1
2
3
4class Node {
int value;
Node next;
}
*思路： 很容易发现是一个“后进先出”的问题，用栈即可实现。1
2
3
4
5
6
7
8
9private static void printList(Node header) {
Stack<Integer> stack = new Stack<>();
for (Node pNode = header; pNode != null; pNode = pNode.next) {
stack.push(pNode.value);
}
while (!stack.empty()) {
System.out.println(stack.pop());
}
}
出自《剑指offer》第二版面试题6
树
重建二叉树
题目： 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。例如，输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建二叉树并输出它的头节点。二叉树的定义如下：1
2
3
4
5class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode 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
52import java.util.Arrays;
public class Main {
public static void main(String[] args) {
BinaryTreeNode node = rebuild(new int[]{1, 2, 4, 7, 3, 5, 6, 8}, new int[]{4, 7, 2, 1, 5, 3, 8, 6});
System.out.println(node.value);
}
private static boolean isNullOrEmpty(int[] values) {
return values == null || values.length == 0;
}
private static BinaryTreeNode rebuild(int[] preOrder, int[] inOrder) {
if (isNullOrEmpty(preOrder) || isNullOrEmpty(inOrder)) {
return null;
} else if (preOrder.length != inOrder.length) {
return null;
}
return rebuildCore(preOrder, inOrder);
}
private static BinaryTreeNode rebuildCore(int[] preOrder, int[] inOrder) {
BinaryTreeNode root = new BinaryTreeNode();
root.value = preOrder[0];
if (preOrder.length == 1 && inOrder.length == 1) {
if (preOrder[0] == inOrder[0]) {
return root;
} else {
throw new IllegalArgumentException("Invalid input!");
}
}
int rootInOrder = find(inOrder, root.value);
if (rootInOrder > 0) {
root.left = rebuildCore(Arrays.copyOfRange(preOrder, 1, rootInOrder + 1),
Arrays.copyOfRange(inOrder, 0, rootInOrder));
}
if (rootInOrder + 1 < preOrder.length) {
root.right = rebuildCore(Arrays.copyOfRange(preOrder, rootInOrder + 1, preOrder.length),
Arrays.copyOfRange(inOrder, rootInOrder + 1, inOrder.length));
}
return root;
}
private static int find(int[] values, int value) {
for (int i = 0; i < values.length; i++) {
if (values[i] == value) {
return i;
}
}
return -1;
}
}
出自《剑指offer》第二版面试题7
二叉树的下一个节点
题目： 给定一颗二叉树和其中的一个节点，如何找出中序遍历的第一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
思路： 根据中序遍历的特点，如果当前节点有右子树，那么下一个节点即为它的右子树的最左节点；如果当前节点没有右子树，且是父节点的左子树，那么下一个节点即为它的父节点；如果当前节点没有右子树且不是父节点的左子树，这时候比较麻烦， 需要一直沿着父节点找到一个是它父节点的左子树的节点，如果此节点存在，那么它的父节点即为要找的节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22private static BinaryTreeNode getNextTreeNodeInOrder(BinaryTreeNode node) {
if (node == null) {
return null;
}
BinaryTreeNode nextNode;
if (node.right != null) {
BinaryTreeNode cur = node.right;
while (cur.left != null) {
cur = cur.left;
}
nextNode = cur;
} else {
BinaryTreeNode cur = node;
BinaryTreeNode parent = node.parent;
while (parent != null && parent.right == cur) {
cur = parent;
parent = cur.parent;
}
nextNode = parent;
}
return nextNode;
}
出自《剑指offer》第二版面试题8