常见算法题型(二)——Java实现
1. 构建二叉排序树，并广度遍历
解决方案：根据二叉排序树的定义，树的度最多为2,而且左子树小于根节点的值，右子树的值大于根节点的值。广度遍历的方式是利用队列的方式，把节点自上到下的方式把节点放入队列中，然后取出，把自身的值打印出来，把自身左右节点不为空的放入队列中，一直执行下去，直到二叉树节点不存在了并且队列中不存在元素的情况下，广度遍历结束。特别注意的是，定义树节点的时候有个属性len表示该节点的数据在二叉树中存在几个，即重复元素的处理方式。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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134package com.nyist.offer;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
/**
* 树的广度遍历
* 顺便构建二叉排序树
*/
public class TreeWideTraverse {
public static void main(String[] args) {
TreeNode node = new TreeNode();
TreeNode treeNode = createTreeNode(node);
wideTraverse(treeNode);
}
private static void wideTraverse(TreeNode node) {
Queue<TreeNode> queue = new ArrayDeque<>();
TreeNode qNode = null;
if(node != null){
queue.offer(node);
qNode = queue.poll();
while (qNode != null){
if(qNode.getLeftNode() != null){
queue.offer(qNode.getLeftNode());
}
if(qNode.getRightNode() != null){
queue.offer(qNode.getRightNode());
}
int i = 0;
while(i < qNode.getLen()){
System.out.print(qNode.getData()+" ");
i++;
}
qNode = queue.poll();
}
}
}
private static TreeNode createTreeNode(TreeNode node) {
System.out.println("请输入你需要创建树节点的个数：");
Scanner scanner = new Scanner(System.in);
int len = scanner.nextInt();
for(int i = 0;i < len;i++){
System.out.println("请输入你需要创建的第"+(i+1)+"个节点的数据：");
int num = scanner.nextInt();
if(node.getData() == null){
node = new TreeNode(num,1);
}
else{
TreeNode inNode = node;
while (inNode != null && inNode.getData() != null){
if(num > inNode.getData()){
TreeNode bNode = inNode;
inNode = inNode.getRightNode();
if(inNode == null){
bNode.setRightNode(new TreeNode(num,1));
}
}
else if(num < inNode.getData()){
TreeNode bNode = inNode;
inNode = inNode.getLeftNode();
if(inNode == null){
bNode.setLeftNode(new TreeNode(num,1));
}
}
else{
inNode.setLen(inNode.getLen()+1);
break;
}
}
}
}
return node;
}
}
class TreeNode{
private Integer data;
private TreeNode leftNode;
private TreeNode rightNode;
//标记重复的元素
private Integer len = 0;
public TreeNode(Integer data, Integer len) {
this.data = data;
this.len = len;
}
public TreeNode() {
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public TreeNode getLeftNode() {
return leftNode;
}
public Integer getLen() {
return len;
}
public void setLen(Integer len) {
this.len = len;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
}
2.重构二叉树
2.1 根据先序遍历结果和中序遍历结果进行重构二叉树
解题思路：首先知道先序遍历A集合，那么A的第一个元素就是树的根节点，接着根据根节点去中序遍历集合B中找根节点位置，得到index，然后在集合B中，index的左侧是根节点的左子树部分，index的右侧是右子树部分，然后采用递归的部分，进而分别将左右子树部分再细分为左右子树，最后得到整个树的结构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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79package com.nyist.offer;
import java.util.Arrays;
public class RebuildBinaryTree {
public static void main(String[] args) {
int[] preTraverse = {1,2,4,7,3,5,6,8};
int[] inTraverse = {4,7,2,1,5,3,8,6};
TreeNode node = reBuildTree(preTraverse, inTraverse);
System.out.println(node);
}
private static TreeNode reBuildTree(int[] preTraverse, int[] inTraverse) {
if(preTraverse.length == 0 || inTraverse.length == 0){
return null;
}
TreeNode node = new TreeNode(preTraverse[0]);
int index = -1;
for(int i = 0;i < inTraverse.length;i++){
if(inTraverse[i] == node.getData()){
index = i;
break;
}
}
int[] leftPre = Arrays.copyOfRange(preTraverse,1,index+1);
int[] leftIn = Arrays.copyOfRange(inTraverse,0,index);
int[] rightPre = Arrays.copyOfRange(preTraverse,index+1,preTraverse.length);
int[] rightIn = Arrays.copyOfRange(inTraverse,index+1, inTraverse.length);
node.setLeftNode(reBuildTree(leftPre,leftIn));
node.setRightNode(reBuildTree(rightPre,rightIn));
return node;
}
}
class TreeNode{
private Integer data;
private TreeNode leftNode;
private TreeNode rightNode;
public TreeNode(Integer data) {
this.data = data;
}
public TreeNode() {
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public TreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
}
2.2 根据后序遍历结果和中序遍历结果进行重构二叉树
1 | package com.nyist.offer; |
3.用两个栈实现队列
题目：用两个栈实现一个队列，在函数的appendTail和deleteHead方法内部完成队列尾部插入数据和队列首部删除节点的功能
解题思路：自定义栈，里面有实现扩容的部分，定义了栈的先进后出的规定，两个栈结合起来，stack1负责存储，stack2负责模拟队列在首部取出数据的方式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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111package com.nyist.offer;
import java.util.Arrays;
import java.util.Scanner;
public class StackOperate {
public static void main(String[] args) {
MyQueue queue = new MyQueue();
Scanner scanner = new Scanner(System.in);
System.out.println("请输入队列的长度:");
int len = scanner.nextInt();
for(int i = 0;i < len;i++){
System.out.print("请输入队列第"+(i+1)+"个数据:");
Integer numData = scanner.nextInt();
queue.appendTail(numData);
}
for(int i = 0;i < len;i++){
Integer num = queue.deleteHead();
System.out.println("取出队列第"+(i+1)+"个元素为:"+num);
}
}
}
class MyQueue{
private MyStack stack1 = new MyStack();
private MyStack stack2 = new MyStack();
public void appendTail(Integer data){
if(stack1.getCount() == 0 && stack2.getCount() != 0){
int len = stack1.getCount();
for(int i = 0;i < len;i++){
stack1.push(stack2.pop());
}
stack2 = new MyStack();
stack2.setCount(0);
}
stack1.push(data);
}
public Integer deleteHead(){
if(stack2.getCount() == 0 && stack1.getCount() != 0){
int len = stack1.getCount();
for(int i = 0;i < len;i++){
stack2.push(stack1.pop());
};
stack1 = new MyStack();
stack1.setCount(0);
}
Integer num = stack2.pop();
return num;
}
public MyStack getStack1() {
return stack1;
}
public void setStack1(MyStack stack1) {
this.stack1 = stack1;
}
public MyStack getStack2() {
return stack2;
}
public void setStack2(MyStack stack2) {
this.stack2 = stack2;
}
}
class MyStack{
private int len = 10;
private Integer[] arr = new Integer[len];
private int count = 0;
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public void push(int num){
if(count >= arr.length){
int newLen = arr.length+(arr.length>>1);
Integer[] newArr = new Integer[newLen];
System.arraycopy(arr,0,newArr,0,count);
arr = newArr;
}
arr[count] = num;
count++;
}
public Integer pop(){
Integer v = null;
if(count >= 0){
v = arr[--count];
return v;
}
else{
return null;
}
}
}
4.求斐波那契问题
题目：在不使用递归的条件下，求出输入的Num值的斐波那契值。
解题思路： 首先分析斐波那契规律，除了第一二项之外，其他项都等于前两项的和，因此，我们可以反复循环赋值的方式来处理这个问题。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
37package com.nyist.offer;
import java.util.Scanner;
public class FibonacciSolution {
public static void main(String[] args) {
System.out.println("请输入你需要求斐波那契数字：");
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int result = getFibonacciResult(num);
System.out.println(num+"斐波那契结果是:"+result);
}
private static int getFibonacciResult(int num) {
if(num > 0){
if(num == 1 || num == 2){
return 1;
}
else{
int i = 2;
int num1 = 1, num2 = 1;
int result = 0;
while (i < num){
result = num1 + num2;
num1 = num2;
num2 = result;
i++;
}
return result;
}
}
return 0;
}
}
5. 青蛙跳台问题(斐波那契规律)
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共需要多少种跳法。
解题思路：
首先考虑n等于0、1、2时的特殊情况，f(0) = 0 f(1) = 1 f(2) = 2 其次，当n=3时，青蛙的第一跳有两种情况：跳1级台阶或者跳两级台阶，假如跳一级，那么 剩下的两级台阶就是f(2)；假如跳两级，那么剩下的一级台阶就是f(1)，因此f(3)=f(2)+f(1) 当n = 4时，f(4) = f(3) +f(2),以此类推………..可以联想到Fibonacci数列。
采用非递归的方式实现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
43package com.nyist.offer;
import java.util.Scanner;
public class FibonacciSolution {
public static void main(String[] args) {
System.out.println("青蛙跳台的阶数：");
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int result = getFibonacciResult(num);
System.out.println(num+"青蛙跳法共有:"+result+"种");
}
private static int getFibonacciResult(int num) {
if(num > 0){
if(num == 0){
return 0;
}
else if(num == 1){
return 1;
}
else if(num == 2){
return 2;
}
else{
int i = 2;
int num1 = 1, num2 = 2;
int result = 0;
while (i < num){
result = num1 + num2;
num1 = num2;
num2 = result;
i++;
}
return result;
}
}
return 0;
}
}
算法很有趣，继续攻破更多的算法题，目前已经上瘾…
