常见算法题型(一)——Java实现
1. 找出链表中倒数第K个数字
解决方案： 我们可以使用两个指向，一个指向链表头部的链表节点A，一个指向第K-1个链表节点B，接着B节点循环直到为null的时候，同时A节点也在循环，B节点为空的时候，A节点所在节点就是倒数第K个节点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
95package com.nyist.offer;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class LinkFindK {
public static void main(String[] args) {
InputData();
}
private static void outputData(LinkNode linkNode) {
System.out.print("链表中的顺序是: ");
while (linkNode != null){
if(linkNode.getData() != null){
System.out.print(linkNode.getData()+" ");
}
linkNode = linkNode.getNextNode();
}
}
private static void InputData() {
Scanner scanner = new Scanner(System.in);
LinkNode linkNode = new LinkNode();
System.out.println("请输入你想创建链表的长度：");
Integer len = scanner.nextInt();
if(len > 0){
for(int i = 0;i < len;i++){
System.out.println("请输入"+(i+1)+"个链表的数字:");
Integer num = scanner.nextInt();
LinkNode pNode = new LinkNode(num);
LinkNode linkNode1 = linkNode;
//找到最后一个节点，然后再追加
while (linkNode1.getNextNode() != null){
linkNode1 = linkNode1.getNextNode();
}
pNode.setNextNode(linkNode1.getNextNode());
linkNode1.setNextNode(pNode);
}
}
System.out.println("输入完毕！");
outputData(linkNode);
System.out.println("链表的哪个倒数节点?");
Integer rIndex = scanner.nextInt();
findK(rIndex,linkNode);
}
private static void findK(Integer K,LinkNode linkNode){
LinkNode aNode;
int i = 0;
LinkNode linkNode1 = linkNode;
while (linkNode1 != null && i < K){
linkNode1 = linkNode1.getNextNode();
i++;
}
aNode = linkNode1;
while (linkNode1 != null){
linkNode1 = linkNode1.getNextNode();
linkNode = linkNode.getNextNode();
}
System.out.println(linkNode.getData());
}
}
class LinkNode{
private Integer data;
private LinkNode nextNode;
public LinkNode(Integer data) {
this.data = data;
}
public LinkNode() {
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public LinkNode getNextNode() {
return nextNode;
}
public void setNextNode(LinkNode nextNode) {
this.nextNode = nextNode;
}
}
注：一定注意K的大小是否在链表长度范围之内！
2.找出数组中重复的数字
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。
解题思路：我们可以将数组进行排序，然后挨个查找，也可以使用hash表（时间复杂度o(1),空间复杂度o(n)），但时间和空间复杂度都不是很理想，所以我们根据审题就可以知道数字在0~n-1,那么一个下标，要么没有元素，要么重复元素，
所以解决思路如下：
首先从第一个开始遍历，下标为i,看当前下标的元素是否v和下标i相等，如果相等，就继续遍历下一个元素，如果不等，则找出下标为v的元素，判断下标为v的元素k是否和v值相等，如果相等，则说明值为v元素出现重复，如果不相等，则进行交换元素，接着仍然对下标为i元素重复上面操作。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
36package com.nyist.offer;
public class FindRepateNum {
public static void main(String[] args) {
Integer[] nums = {1,2,3,3,5,6,7,0};
FindRepateNumMethod(nums);
}
private static void FindRepateNumMethod(Integer[] nums) {
for(int i = 0;i < nums.length;i++){
int v = nums[i];
if(v == i){
continue;
}
else{
//针对于数组中的数字不在相应范围内的问题
if(v >= nums.length){
System.out.println("数组中的数字 "+v+" 不在0~"+(nums.length-1)+"之内");
break;
}
int k = nums[v];
if(k == v){
System.out.println("数字 "+k+" 出现了重复!");
continue;
}
else{
int temp = nums[v];
nums[v] = nums[i];
nums[i] = temp;
i--;
}
}
}
}
}
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
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
134
135
136
137
138
139
140
141
142
143
144
145package com.nyist.offer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
public class HafManDemo {
public static void main(String[] args) {
ArrayList<DataNode> list = new ArrayList<>();
TreeNode node = new TreeNode();
InputData(list);
TreeNode node3 = buildHafTree(list, node);
}
private static TreeNode buildHafTree(ArrayList list,TreeNode node3) {
while (list.size() > 0){
Collections.sort(list, new Comparator<DataNode>() {
public int compare(DataNode o1, DataNode o2) {
if(o1.getData() > o2.getData()){
return 1;
}else if(o1.getData() < o2.getData()){
return -1;
}else{
return 0;
}
}
});
DataNode dataNode1 = (DataNode) list.get(0);
if(list.size() == 1){
if(dataNode1.getNode() == null){
node3 = new TreeNode(dataNode1.getData());
}
return node3;
}
DataNode dataNode2 = (DataNode) list.get(1);
TreeNode node1,node2;
if(dataNode1.getNode() == null){
node1 = new TreeNode(dataNode1.getData());
}else{
node1 = dataNode1.getNode();
}
if(dataNode2.getNode() == null){
node2 = new TreeNode(dataNode2.getData());
}else{
node2 = dataNode2.getNode();
}
node3 = new TreeNode(dataNode1.getData()+dataNode2.getData(),node1,node2);
list.remove(dataNode1);
list.remove(dataNode2);
list.add(new DataNode((dataNode1.getData()+dataNode2.getData()),node3));
}
return node3;
}
private static void InputData(ArrayList list) {
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();
list.add(new DataNode(num,null));
}
}
}
class TreeNode{
private Integer data;
private TreeNode lTreeNode;
private TreeNode rTreeNode;
public TreeNode(Integer data) {
this.data = data;
}
public TreeNode(Integer data, TreeNode lTreeNode, TreeNode rTreeNode) {
this.data = data;
this.lTreeNode = lTreeNode;
this.rTreeNode = rTreeNode;
}
public TreeNode() {
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public TreeNode getlTreeNode() {
return lTreeNode;
}
public void setlTreeNode(TreeNode lTreeNode) {
this.lTreeNode = lTreeNode;
}
public TreeNode getrTreeNode() {
return rTreeNode;
}
public void setrTreeNode(TreeNode rTreeNode) {
this.rTreeNode = rTreeNode;
}
}
class DataNode{
private Integer data;
private TreeNode node;
public DataNode(Integer data, TreeNode node) {
this.data = data;
this.node = node;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public TreeNode getNode() {
return node;
}
public void setNode(TreeNode node) {
this.node = node;
}
}
4. 二维数组的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：
根据二维数组中数字是行列都是有序的，所以我们可以首先定位到右上角的元素进行逐步定位所查找的元素，假如比右上角的大，那么所在行将被排除，如果比右上角小，那么排除最右面的一列，逐渐，二维数组被排除一部分之后，逐步缩小区域，当二维数组只有最后一个元素也没有找到，那么表示不存在。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
84package com.nyist.offer;
import java.util.Scanner;
public class FindNumByTwoArray {
public static void main(String[] args) {
int[][] arr = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
Scanner scanner = new Scanner(System.in);
System.out.println("请输入你要查询的数字:");
int num = scanner.nextInt();
Node node = findNum(arr, num);
if(node == null){
System.out.println("没有找到数字"+num);
}
else {
System.out.println("找到了数字:"+num+",位置在第"+node.getRow()+"行->第"+node.getCol()+"列！");
}
}
private static Node findNum(int[][] arr, int num) {
int row = arr.length;
int col = arr[0].length;
int row0 = 0;
int col0 = 0;
Node node = null;
while (true){
if(col <= 0 || row0 >= row){
break;
}
if(arr[row0][col-1] == num){
node = new Node(row0+1,col,true);
break;
}
else if(arr[row0][col-1] < num){
row0++;
}
else{
col--;
}
}
return node;
}
}
class Node{
private int row;
private int col;
private Boolean isFind;
public Node(int row, int col, Boolean isFind) {
this.row = row;
this.col = col;
this.isFind = isFind;
}
public Boolean getFind() {
return isFind;
}
public void setFind(Boolean find) {
isFind = find;
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public int getCol() {
return col;
}
public void setCol(int col) {
this.col = col;
}
}
注：我们可以选取右上角和左下角的元素作为起点开始以缩小二维数组的方式来定位查找的元素。但是不能从左上角和右下角开始，因为加入所找元素不等于第一个，而是大于第一个元素，那么我们将不知道是从此元素的右面或者下面继续定位元素了。
5.从尾到头打印链表
输入一个链表的头节点，从尾到头反过来打印出每个节点的值。
解题思路：首先我在不修改链表的前提下，我们审题发现要求倒着打印出链表的数据，因此和栈的数据结构很匹配，因此我们可以使用递归(空间复杂度很高，底层是栈)来解决上述问题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
74package com.nyist.offer;
import java.util.Scanner;
public class PrintLinkNodeReverse {
public static void main(String[] args) {
PrintNode node = new PrintNode();
PrintNode printNode = createLinkNode(node);
reversePrintNode(printNode);
}
private static void reversePrintNode(PrintNode node) {
if(node != null){
if(node.getNextNode() != null){
reversePrintNode(node.getNextNode());
}
System.out.print(node.getData()+" ");
}
}
private static PrintNode createLinkNode(PrintNode node) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入你要创建链表的长度：");
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 PrintNode(num);
}
else{
PrintNode inNode = node;
while (inNode.getNextNode() != null){
inNode = inNode.getNextNode();
}
PrintNode nNode = new PrintNode(num);
nNode.setNextNode(inNode.getNextNode());
inNode.setNextNode(nNode);
}
}
return node;
}
}
class PrintNode{
private Integer data;
private PrintNode printNode;
public PrintNode() {
}
public PrintNode(Integer data) {
this.data = data;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public PrintNode getNextNode() {
return printNode;
}
public void setNextNode(PrintNode printNode) {
this.printNode = printNode;
}
}
