《剑指 Offer》算法题(10/68)

Reference


赋值运算符函数

Java 不支持用户自定义操作符重载。


实现 Singleton 模式

设计一个类,我们只能生成该类的一个实例。

饿汉式

1
2
3
4
5
6
7
8
9
public class SingleTon{
private static SingleTon mSingleTon = new SingleTon();
private SingleTon() {}
public static SingleTon getInstance() {
return mSingleTon;
}
}

懒汉式(线程不安全)

1
2
3
4
5
6
7
8
9
10
11
12
public class SingleTon{
private static SingleTon mSingleTon = null;
private SingleTon() {}
public static SingleTon getInstance() {
if(mSingleTon == null) {
mSingleTon = new SingleTon();
}
return mSingleTon;
}
}

懒汉式(线程安全)

1
2
3
4
5
6
7
8
9
10
11
12
public class SingleTon{
private static SingleTon mSingleTon = null;
private SingleTon() {}
public static synchronized SingleTon getInstance() {
if(mSingleTon == null) {
mSingleTon = new SingleTon();
}
return mSingleTon;
}
}

懒汉式(双重校验锁,线程不一定安全)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class SingleTon{
private static SingleTon mSingleTon = null;
private SingleTon() {}
public static SingleTon getInstance() {
if(mSingleTon == null){
synchronized(SingleTon.class) {
if(mSingleTon == null) {
mSingleTon = new SingleTon();
}
}
}
return mSingleTon;
}
}

懒汉式(双重校验锁,线程安全)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class SingleTon{
private static volatile SingleTon mSingleTon = null;
private SingleTon() {}
public static SingleTon getInstance() {
if(mSingleTon == null){
synchronized(SingleTon.class) {
if(mSingleTon == null) {
mSingleTon = new SingleTon();
}
}
}
return mSingleTon;
}
}

枚举

1
2
3
4
5
enum SingleTon {
SINGLE
}
SingleTon.SINGLE

静态内部类

1
2
3
4
5
6
7
8
9
10
11
public class SingleTon {
private static class InnerClass {
static SingleTon mSingleTon = new SingleTon();
}
private SingleTon() {}
public static SingleTon getInstance() {
return InnerClass.mSingleTon;
}
}

数组中重复的数字

找出数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了。也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3},那么对应的输出是重复的数字 2 或者 3。

思路:
观察值的范围,当数组中没有重复数字时,排序之后的结果应该是值和索引一一对应。以此为突破口,尝试给数组排序。
遍历数组,当值和索引相等时,继续处理下个索引的值;否则,比较当前值(arr[i] == m)和值作为索引的值(arr[m]),如果相等则说明找到了重复的数字,否则,交换两个值,再执行该过程。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int find(int[] arr) {
for (int i = 0, size = arr.length; i < size; i++) {
while (arr[i] != i) {
if (arr[i] == arr[arr[i]]) {
return arr[i];
}
int temp = arr[i];
arr[i] = arr[temp];
arr[temp] = temp;
}
}
return -1;
}

1
2
3
int[] arr = {2, 3, 1, 0, 2, 5, 3};
int value = find(arr);
System.out.println("value:" + value);

时间复杂度:O(n)。代码中尽管有一个两重循环,但每个数字最多只要交换两次就能找到位置。
空间复杂度:O(1)。所有操作都是在输入数组上进行,不需要额外分配内存。

不修改数组找出重复的数字

在一个长度为 n + 1 的数组里的所有数字都在 1 到 n 的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为 8 的数组 {2, 3, 5, 4, 3, 2, 6, 7},那么对应的输出是重复的数字 2 或者 3。

思路:
将值按照大于 m 值的和不大于 m 值的分为大、小两个区间,数组如果不重复(n 个元素对应 1~n),则大区间中必有 m 个元素,且小区间中必有 n - m 个元素,但是由于多 1 个元素,所以至少有大区间元素个数大于 m,或小区间元素个数大于 m - 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
public static int find(int[] arr) {
int start = 1;
int end = arr.length - 1;
while (end >= start) {
int middle = ((end - start) >> 1) + start;
int count = count(arr, start, middle);
if (start == middle) {
if (count > 1) {
return start;
} else {
break;
}
}
if (count > middle - start + 1) {
end = middle;
} else {
start = middle + 1;
}
}
return -1;
}
private static int count(int[] arr, int start, int middle) {
int count = 0;
for (int i : arr) {
if (i >= start && i <= middle) {
count++;
}
}
return count;
}

1
2
3
int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
int value = find(arr);
System.out.println("value:" + value);

时间复杂度:O(nlogn)。数组长度为 n,是 O(n),二分查找是 O(logn),所以总时间是 O(nlogn)。
空间复杂度:O(1)。


二维数组中的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

思路:
二维数组行、列都是有序的,所以如果列的第一个元素大于目标值时,则目标值不可能在此列;同理,行也一样。以此为突破口,先用二分法缩小目标可能存在的范围,再遍历。
使用二分法找到中间列,判断列的第一个元素和目标值的大小关系,如果等于,说明找到了,直接返回;如果大于,记录位置为 C1;如果小于,记录位置为 C2。重复此过程,直到 C2 >= C1,则找到了列在遍历时的最大值 C2 - 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
44
45
46
47
48
49
50
51
52
53
54
public static boolean contain(int[][] arr, int target) {
int maxCol = findMaxCol(arr, target);
if (arr[0][maxCol] == target) {
return true;
}
int maxRow = findMaxRow(arr, target);
if (arr[maxRow][0] == target) {
return true;
}
for (int j = maxCol; j >= 0; j--) {
for (int i = maxCol - j; i <= maxRow; i++) {
if (arr[i][j] == target) {
return true;
} else if (arr[i][j] > target) {
break;
}
}
}
return false;
}
private static int findMaxCol(int[][] arr, int target) {
int start = 0;
int end = arr[0].length - 1;
while (end >= start) {
int middle = ((end - start) >> 1) + start;
if (arr[0][middle] == target) {
return middle;
} else if (arr[0][middle] > target) {
end = middle - 1;
} else {
start = middle + 1;
}
}
return start - 1;
}
private static int findMaxRow(int[][] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (end >= start) {
int middle = ((end - start) >> 1) + start;
if (arr[middle][0] == target) {
return middle;
} else if (arr[middle][0] > target) {
end = middle - 1;
} else {
start = middle + 1;
}
}
return start - 1;
}

1
2
3
int[][] arr = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
boolean b = contain(arr, 7);
System.out.println("contain:" + b);

时间复杂度:
空间复杂度:O(1)。


替换空格

请实现一个函数,把字符串中的每个空格替换成”%20”。例如,输入”We are happy.”,则输出”We%20are%20happy.”。

思路:
操作同一个数组时,如果从前往后替换会导致后面的数据被覆盖。因为每替换 1 个空格,数组所需的长度需要 + 2,所以可以以此为突破口,从后往前替换。
统计字符串中空格的个数,先计算出替换后的长度,由于 Java 数组长度不可变,所以以计算出的长度重新申请一块内存,然后再从后往前遍历,遇到空格时替换为%20,否则直接复制。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void convert(StringBuffer stringBuffer) {
int count = 0;
for (int i = 0, size = stringBuffer.length(); i < size; i++) {
if (stringBuffer.charAt(i) == ' ') {
count++;
}
}
int oldLen = stringBuffer.length();
int newLen = oldLen + (count << 1);
stringBuffer.setLength(newLen);
for (int i = oldLen - 1, j = newLen - 1; i >= 0; i--, j--) {
char c = stringBuffer.charAt(i);
if (c == ' ') {
stringBuffer.setCharAt(j, '0');
stringBuffer.setCharAt(--j, '2');
stringBuffer.setCharAt(--j, '%');
} else {
stringBuffer.setCharAt(j, c);
}
}
}

1
2
3
4
StringBuffer stringBuffer = new StringBuffer("We are happy.");
System.out.println("stringBuffer:" + stringBuffer.toString());
convert(stringBuffer);
System.out.println("stringBuffer:" + stringBuffer.toString());

时间复杂度:O(n)。
空间复杂度:O(n)。

相关题目:把数组 A2 中的所有数字插入数组 A1 中

有两个排序的数组 A1 和 A2,内存在 A1 的末尾有足够多的空余空间容纳 A2。请实现一个函数,把 A2 中的所有数字插入 A1 中,并且所有的数字是排序的。

思路:
合并两个数组,可以知道两个数组占用的总的空间大小。以此为突破口,合并数组 A2 到 A1。
计算总大小,比较数组 A1 和 A2 各自最后位置的元素的大小,将更大的元素放到末尾。

实现:

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
// 随机初始化数组中的元素
int[] arr1src = new int[10];
int[] arr2 = new int[10];
int beforeValue = 0;
for (int i = 0, size = arr1src.length; i < size; i++) {
int random = new Random().nextInt(10);
beforeValue += random;
arr1src[i] = beforeValue;
}
beforeValue = 0;
for (int i = 0, size = arr2.length; i < size; i++) {
int random = new Random().nextInt(10);
beforeValue += random;
arr2[i] = beforeValue;
}
int[] arr1 = new int[100];
System.arraycopy(arr1src, 0, arr1, 0, arr1src.length); // 由于 Java 中数组长度不可变,此处假装数组 A1 末尾有足够多的空余空间
System.out.println("arr1:" + Arrays.toString(arr1));
System.out.println("arr2:" + Arrays.toString(arr2));
int i = arr1src.length - 1, j = arr2.length - 1, index = arr1src.length + arr2.length - 1;
while (i >= 0 && j >= 0) {
int v1 = arr1[i];
int v2 = arr2[j];
if (v1 == v2) {
arr1[index--] = v1;
arr1[index--] = v2;
i--;
j--;
} else if (v1 > v2) {
arr1[index--] = v1;
i--;
} else {
arr1[index--] = v2;
j--;
}
}
if (j >= 0) { // 最小值在 A2 数组时,直接把剩余元素复制到 A1 数组开头
System.arraycopy(arr2, 0, arr1, 0, j + 1);
}
System.out.println("arr1:" + Arrays.toString(arr1));

时间复杂度: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
public class Node {
private int value;
private Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
public Node getNext() {
return this.next;
}
public int getValue() {
return this.value;
}
}
public static void print(Node node) {
if (node.getNext() != null) {
print(node.getNext());
}
System.out.println("value:" + node.getValue());
}

1
2
3
4
5
6
7
8
9
10
11
12
13
Node node = null;
for (int i = 10; i > 0; i--) {
node = new Node(i, node);
}
Node firstNode = node;
while (node != null) {
System.out.println("value:" + node.getValue());
node = node.getNext();
}
print(firstNode);

时间复杂度:O(n)。
空间复杂度:O(1)。


重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6},则重建二叉树并输出它的头节点。

思路:

(1)前序遍历看根节点;
(2)中序遍历看左子树、右子树;
(3)把子树值带回前序遍历,排在前面的是根节点;
(4)重复(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
37
38
39
40
41
42
43
44
45
public class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
public int getValue() {
return this.value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
public Node create(int[] preorderArr, int[] inorderArr) {
if (preorderArr == null || preorderArr.length == 0 ||
inorderArr == null || inorderArr.length == 0) {
return null;
}
Node node = new Node(preorderArr[0]);
for (int i = 0, size = inorderArr.length; i < size; i++) {
if (preorderArr[0] == inorderArr[i]) { // 根节点
node.setLeft(create(Arrays.copyOfRange(preorderArr, 1, i + 1), Arrays.copyOfRange(inorderArr, 0, i)));
node.setRight(create(Arrays.copyOfRange(preorderArr, i + 1, preorderArr.length), Arrays.copyOfRange(inorderArr, i + 1, inorderArr.length)));
}
}
return node;
}

1
2
3
4
5
int[] preorderArr = {1, 2, 4, 7, 3, 5, 6, 8};
int[] inorderArr = {4, 7, 2, 1, 5, 3, 8, 6};
Node node = create(preorderArr, inorderArr);
System.out.println("node:" + node.getValue());

时间复杂度:O(nlogn)。
空间复杂度:O(n)。

扩展:输入某二叉树的中序遍历和后序遍历的结果,重建出该二叉树

思路:
(1)后序遍历看根节点;
(2)中序遍历看左子树、右子树;
(3)把子树值带回后序遍历,排在前面的是根节点;
(4)重复(2)(3)过程,直到左子树、右子树为空。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private Node create(int[] inorderArr, int[] postorderArr) {
if (inorderArr == null || inorderArr.length == 0 ||
postorderArr == null || postorderArr.length == 0) {
return null;
}
Node node = new Node(postorderArr[postorderArr.length - 1]);
for (int i = 0, size = inorderArr.length; i < size; i++) {
if (postorderArr[postorderArr.length - 1] == inorderArr[i]) { // 根节点
node.setLeft(create(Arrays.copyOfRange(inorderArr, 0, i), Arrays.copyOfRange(postorderArr, 0, i)));
node.setRight(create(Arrays.copyOfRange(inorderArr, i + 1, inorderArr.length), Arrays.copyOfRange(postorderArr, i, postorderArr.length - 1)));
}
}
return node;
}

1
2
3
4
5
int[] inorderArr = {4, 7, 2, 1, 5, 3, 8, 6};
int[] postorderArr = {7, 4, 2, 5, 8, 6, 3, 1};
Node node = create(inorderArr, postorderArr);
System.out.println("node:" + node.getValue());

二叉树的下一个节点

给定一棵二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?树中的结点除了有两个分别指向左、右子节点的指针,还有一个指向父节点的指针。

思路:
分情况讨论——
(1)给出的节点有右子树,则沿着右子树向下遍历左子节点,最左子节点是下一个节点;

(2)给出的节点没有右子树,如果它是父节点的右子节点,则沿着父节点向上遍历,直到节点是父节点的左子节点,则该节点的父节点是下一个节点;

(3)给出的节点没有右子树,如果它是父节点的左子节点,则父节点是下一个节点。(3)是(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
48
49
50
51
52
53
54
55
56
57
58
59
public class Node {
private char value;
private Node left;
private Node right;
private Node parent;
public Node(char value) {
this.value = value;
}
public char getValue() {
return this.value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
left.setParent(this);
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
right.setParent(this);
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
}
public Node inorderNext(Node node) {
if (node.getRight() != null) {
node = node.getRight();
while (node.getLeft() != null) {
node = node.getLeft();
}
return node;
} else {
while (node.getParent() != null) {
if (node.equals(node.getParent().getLeft())) {
return node.getParent();
} else {
node = node.getParent();
}
}
return null;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 初始化二叉树
ArrayList<Node> list = new ArrayList<>(14);
for (int i = 0; i < 14; i++) {
list.add(new Node((char) ('A' + i)));
}
list.get(0).setLeft(list.get(1));
list.get(0).setRight(list.get(2));
list.get(1).setLeft(list.get(3));
list.get(1).setRight(list.get(4));
list.get(2).setLeft(list.get(5));
list.get(2).setRight(list.get(6));
list.get(3).setRight(list.get(7));
list.get(4).setLeft(list.get(8));
list.get(4).setRight(list.get(9));
list.get(5).setRight(list.get(10));
list.get(6).setLeft(list.get(11));
list.get(6).setRight(list.get(12));
list.get(7).setLeft(list.get(13));
for (Node node : list) {
System.out.println("node:" + node.getValue() + "; next node:" + ((node = inorderNext(node)) == null ? "null" : node.getValue()));
}

时间复杂度:
空间复杂度:O(1)。

扩展:前序遍历

思路:前序遍历的顺序是节点->左子节点->右子节点。

实现:

1
2
3
4
5
6
7
8
9
public static void preorder(ArrayList<Node> list, Node node) {
list.add(node);
if (node.getLeft() != null) {
preorder(list, node.getLeft());
}
if (node.getRight() != null) {
preorder(list, node.getRight());
}
}

1
2
3
4
5
ArrayList<Node> preorderList = new ArrayList<>(14);
preorder(preorderList, list.get(0));
for (Node node : preorderList) {
System.out.println("node:" + node.getValue());
}

扩展:中序遍历

思路:中序遍历的顺序是左子节点->节点->右子节点。

实现:

1
2
3
4
5
6
7
8
9
public static void inorder(ArrayList<Node> list, Node node) {
if (node.getLeft() != null) {
inorder(list, node.getLeft());
}
list.add(node);
if (node.getRight() != null) {
inorder(list, node.getRight());
}
}

1
2
3
4
5
ArrayList<Node> inorderList = new ArrayList<>(14);
inorder(inorderList, list.get(0));
for (Node node : inorderList) {
System.out.println("node:" + node.getValue());
}

扩展:后序遍历

思路:后序遍历的顺序是左子节点->右子节点->节点。

实现:

1
2
3
4
5
6
7
8
9
public static void postorder(ArrayList<Node> list, Node node) {
if (node.getLeft() != null) {
postorder(list, node.getLeft());
}
if (node.getRight() != null) {
postorder(list, node.getRight());
}
list.add(node);
}

1
2
3
4
5
ArrayList<Node> postorderList = new ArrayList<>(14);
postorder(postorderList, list.get(0));
for (Node node : postorderList) {
System.out.println("node:" + node.getValue());
}

扩展:给定一棵二叉树和其中的一个节点,找出前序遍历序列的下一个节点

思路:
分情况讨论——
(1)给出的节点有左子节点,则下一个节点是该左子节点;
(2)给出的节点没有左子节点,但是有右子节点,则下一个节点是该右子节点;
(3)给出的节点没有子节点,如果它是父节点的右子节点,且有兄弟节点,则下一个节点是兄弟节点;如果它是父节点的右子节点,则沿着父节点向上遍历,直到节点是父节点的左子节点,并且有兄弟节点,则下一个节点是兄弟节点。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public Node preorderNext(Node node) {
if (node.getLeft() != null) {
return node.getLeft();
} else if (node.getRight() != null) {
return node.getRight();
} else {
while (node.getParent() != null) {
if (node.equals(node.getParent().getLeft()) && node.getParent().getRight() != null) {
return node.getParent().getRight();
} else {
node = node.getParent();
}
}
}
return null;
}

1
2
3
4
Node node = list.get(0);
while (node != null) {
System.out.println("node:" + node.getValue() + "; next node:" + ((node = preorderNext(node)) == null ? "null" : node.getValue()));
}

扩展:给定一棵二叉树和其中的一个节点,找出后序遍历序列的下一个节点

思路:
分情况讨论——
(1)给出的节点没有父节点,则下一个节点是 null;
(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
public Node postorderNext(Node node) {
if (node.getParent() == null) {
return null;
} else {
if (node.equals(node.getParent().getLeft())) {
if (node.getParent().getRight() == null) {
return node.getParent();
} else {
node = node.getParent().getRight();
while (node != null) {
while (node.getLeft() != null) {
node = node.getLeft();
}
if (node.getRight() == null) {
return node;
} else {
node = node.getRight();
}
}
}
} else {
return node.getParent();
}
}
return null;
}

1
2
3
for (Node node : list) {
System.out.println("node:" + node.getValue() + "; next node:" + ((node = postorderNext(node)) == null ? "null" : node.getValue()));
}

用两个栈实现队列

用两个栈实现一个队列,分别完成在队列尾部插入节点和在队列头部删除节点的功能。

思路:
队列的特点是先进先出。栈的特点是后进先出,进栈和出栈的顺序相反,如果数据从栈 A 出栈后依次入栈 B,再从栈 B 出栈,则出栈 B 时的顺序和入栈 A 时的顺序是一致的。以此为突破口,即可实现队列。
初始化栈 A、B,栈 A 用于存数据,栈 B 用于取数据。当栈 B 没数据时,会先将栈 A 的数据导入到栈 B,然后再从栈 B 取数据;当栈 B 有数据时,就直接从栈 B 取数据,后续存入栈 A 的数据,等到栈 B 没数据时,在取数据前才从栈 A 导入到栈 B。

实现:

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
public class Queue<T> {
private Stack<T> stack1;
private Stack<T> stack2;
public Queue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(T t) {
stack1.push(t);
}
public T pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
@Override
public String toString() {
return "stack1:" + stack1.toString() + "\nstack2:" + stack2.toString();
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Queue<Integer> queue = new Queue<>();
for (int i = 0; i < 20; i++) {
int random = new Random().nextInt(128);
if ((random & 4) == 0) {
try {
Integer pop = queue.pop();
System.out.println("pop:" + pop + "\n" + queue.toString());
} catch (EmptyStackException e) {
e.printStackTrace();
}
} else {
queue.push(random);
System.out.println("push:" + random + "\n" + queue.toString());
}
}

时间复杂度:
空间复杂度:

相关题目:用两个队列实现一个栈

思路:
初始化队列 A、B,两个队列都是用于存/取数据,但是同一时刻,只能有一个队列存数据,另一个队列中的数据为空。当取数据时,将前 n - 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
public class Stack<T> {
private ArrayDeque<T> queue1;
private ArrayDeque<T> queue2;
private ArrayDeque<T> pushQueue;
private ArrayDeque<T> popQueue;
public Stack(int capacity) {
queue1 = new ArrayDeque<>(capacity);
queue2 = new ArrayDeque<>(capacity);
pushQueue = queue1;
popQueue = queue2;
}
public void push(T t) {
pushQueue.addLast(t);
}
public T pop() {
for (int i = 0, size = pushQueue.size(); i < size - 1; i++) {
popQueue.add(pushQueue.removeFirst());
}
if (pushQueue == queue1) {
pushQueue = queue2;
popQueue = queue1;
} else {
pushQueue = queue1;
popQueue = queue2;
}
return popQueue.removeFirst();
}
@Override
public String toString() {
return "queue1:" + queue1.toString() + "\nqueue2:" + queue2.toString();
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Stack<Integer> stack = new Stack<>(20);
for (int i = 0; i < 20; i++) {
int random = new Random().nextInt(128);
if ((random & 6) == 0) {
try {
Integer pop = stack.pop();
System.out.println("pop:" + pop + "\n" + stack.toString());
} catch (NoSuchElementException e) {
e.printStackTrace();
}
} else {
stack.push(random);
System.out.println("push:" + random + "\n" + stack.toString());
}
}

斐波那契数列

求斐波那契数列的第 n 项。

思路:
递归由于多次重复计算,所以效率低。可以使用循环,由下向上计算。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
int preTwo = 0;
int preOne = 1;
int value = 0;
for (int i = 2; i <= n; i++) {
value = preTwo + preOne;
preTwo = preOne;
preOne = value;
}
return value;
}
}

1
2
3
for (int n = 0; n < 10; n++) {
System.out.println("fibonacci[" + n + "]:" + fibonacci(n));
}

时间复杂度:O(n)。
空间复杂度:O(1)。

题目二:青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路:
把 n 级台阶时的跳法看成 n 的函数,计为 f(n),当 n > 2 时,如果第一次跳 1 级,则跳法数目等于剩余 n - 1 级台阶的跳法数目,即 f(n - 1);如果第一次跳 2 级,则跳法数目等于剩余 n - 2 级台阶的跳法数目,即 f(n - 2);因为第一次只能跳 1 级或 2 级,所以 f(n) = f(n - 1) + f(n - 2),就是上面的斐波那契数列了。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int jump(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
int preTwo = 1;
int preOne = 2;
int value = 0;
for (int i = 3; i <= n; i++) {
value = preTwo + preOne;
preTwo = preOne;
preOne = value;
}
return value;
}
}

1
2
3
for (int n = 1; n < 10; n++) {
System.out.println("jump[" + n + "]:" + jump(n));
}

本题扩展:青蛙跳 n 级台阶时,一次最多可以跳 n 级

在青蛙跳台阶的问题中,如果把条件改成:一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶……它也可以跳上 n 级,此时该青蛙跳上一个 n 级的台阶总共有多少种跳法?我们用数学归纳法可以证明 f(n) = 2^(n - 1)。

思路:
因为 f(n) = 2^(n - 1),所以 f(n - 1) = 2^[(n - 1) - 1] = 2^(n - 1) * 2^(-1),也就是说 f(n) 是 f(n - 1) 的 2 倍。

实现:

1
2
3
4
5
6
7
8
9
10
11
public static int jump(int n) {
if (n == 1) {
return 1;
} else {
int value = 1;
for (int i = 1; i < n; i++) {
value *= 2;
}
return value;
}
}

1
2
3
for (int n = 1; n < 10; n++) {
System.out.println("jump[" + n + "]:" + jump(n));
}

相关题目:用 2 x 1 的小矩形横着或者竖着去覆盖 2 x n 的大矩形

我们可以用 2 x 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 x 1 的小矩形无重叠地覆盖一个 2 x n 的大矩形,总共有多少种方法?

思路:
当小矩形竖着放时,剩余面积是 2 x (n - 1);当小矩形横着放时,小矩形下方也是惟一确定可以放一个小矩形,剩余面积是 2 x (n - 2);所以 f(n) = f(n - 1) + f(n - 2)。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int jump(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
int preTwo = 1;
int preOne = 2;
int value = 0;
for (int i = 3; i <= n; i++) {
value = preTwo + preOne;
preTwo = preOne;
preOne = value;
}
return value;
}
}

1
2
3
for (int n = 1; n < 10; n++) {
System.out.println("jump[" + n + "]:" + jump(n));
}

本文标题:《剑指 Offer》算法题(10/68)

文章作者:魏超

发布时间:2020年03月16日 - 23:03

最后更新:2020年03月16日 - 23:03

原始链接:http://www.weichao.io/2020/03/16/《剑指-Offer》算法题(10-68)/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

---------------------本文结束---------------------