Skip to content

Commit dcd790b

Browse files
mood321mood321
committed
算法练习
1 parent 4aecbb1 commit dcd790b

4 files changed

Lines changed: 323 additions & 6 deletions

File tree

‎src/main/java/algorithm/basic/Test.java‎

Lines changed: 79 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,9 @@
11
package algorithm.basic;
22

3+
import org.omg.PortableInterceptor.INACTIVE;
4+
5+
import java.io.Console;
6+
37
/**
48
* @Created by mood321
59
* @Date 2019/10/8 0008
@@ -14,8 +18,80 @@ public static boolean isSum(int[] arr ,int sum,int cur,int i){
1418

1519
}
1620

17-
public static void main(String[] args) {
18-
int[] ints = {2, 3, 4, 5, 7};
19-
System.out.println(isSum(ints,11,0,0));
21+
/* public static void main(String[] args) {
22+
*//* int[] ints = {2, 3, 4, 5, 7};
23+
System.out.println(isSum(ints,11,0,0));*//*
24+
printNum(1,3,9);
25+
}*/
26+
27+
/**
28+
9*1=9 8*1=8 7*1=7
29+
9*2=18 8*2=16 7*2=14
30+
9*3=27 8*3=24 7*3=21
31+
9*4=36 8*4=32 7*4=28
32+
9*5=45 8*5=40 7*5=35
33+
9*6=54 8*6=48 7*6=42
34+
9*7=63 8*7=56 7*7=49
35+
9*8=72 8*8=64 7*8=56
36+
9*9=81 8*9=72 7*9=63
37+
6*1=6 5*1=5 4*1=4
38+
6*2=12 5*2=10 4*2=8
39+
6*3=18 5*3=15 4*3=12
40+
6*4=24 5*4=20 4*4=16
41+
6*5=30 5*5=25 4*5=20
42+
6*6=36 5*6=30 4*6=24
43+
6*7=42 5*7=35 4*7=28
44+
6*8=48 5*8=40 4*8=32
45+
6*9=54 5*9=45 4*9=36
46+
3*1=3 2*1=2 1*1=1
47+
3*2=6 2*2=4 1*2=2
48+
3*3=9 2*3=6 1*3=3
49+
3*4=12 2*4=8 1*4=4
50+
3*5=15 2*5=10 1*5=5
51+
3*6=18 2*6=12 1*6=6
52+
3*7=21 2*7=14 1*7=7
53+
3*8=24 2*8=16 1*8=8
54+
3*9=27 2*9=18 1*9=9
55+
*/
56+
public static void main(String[] args)
57+
{
58+
/*for (int count=9;count>0;count--){
59+
if(count%3==0){
60+
echo(count);
61+
}
62+
}*/
63+
64+
/*echo1();*/
65+
66+
}
67+
68+
private static void echo1() {
69+
for (int s=9;s>0;){
70+
er(s);
71+
s-=3;
72+
}
73+
}
74+
75+
private static void er(int s) {
76+
for (int e=1;e<=9;e++){
77+
System.out.print(s + "*" + e + "="+s*e+ " ");
78+
System.out.print(s-1 + "*" + e + "="+(s-1*e)+ " ");
79+
System.out.print(s-2 + "*" + e + "="+(s-1*e)+ " ");
80+
System.out.println();
81+
}
82+
System.out.println();
83+
}
84+
85+
static void echo(int row) {
86+
int len=1,a=row;
87+
for (int i = 9; i >= 1; i--) {
88+
for (int j = 1; j <= 3; j++) {
89+
System.out.print(row + "*" + len + "="+row*len+ " ");
90+
row--;
91+
}
92+
len++;
93+
row = a;
94+
System.out.print("\n");
95+
}
2096
}
2197
}

‎src/main/java/algorithm/basic04/Code_06_IsBalancedTree.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package algorithm.basic04;
2+
3+
/**
4+
* @Created by mood321
5+
* @Date 2019/11/4 0004
6+
* @Description TODO
7+
*/
8+
public class Code_06_IsBalancedTree {
9+
10+
public static class Node {
11+
int data;
12+
Node left;
13+
Node right;
14+
15+
public Node(int data) {
16+
this.data = data;
17+
}
18+
}
19+
20+
public static boolean isBalance(Node head) {
21+
boolean[] res = new boolean[1];
22+
res[0] = true;
23+
getHeight(head, 1, res);
24+
return res[0];
25+
}
26+
27+
public static int getHeight(Node head, int level, boolean[] res) {
28+
if (head == null) {
29+
return level;
30+
}
31+
int height = getHeight(head.left, level + 1, res);
32+
if(!res[0]){
33+
return level;
34+
}
35+
int rightHeight=getHeight(head.right,level+1,res);
36+
if (!res[0])
37+
return level;
38+
39+
if(Math.abs(height-rightHeight)>0){
40+
res[0]=false;
41+
}
42+
return Math.max(height,rightHeight);
43+
}
44+
45+
public static void main(String[] args) {
46+
Node head = new Node(1);
47+
head.left = new Node(2);
48+
head.right = new Node(3);
49+
head.left.left = new Node(4);
50+
head.left.right = new Node(5);
51+
head.right.left = new Node(6);
52+
head.right.right = new Node(7);
53+
54+
System.out.println(isBalance(head));
55+
56+
}
57+
}

‎src/main/java/algorithm/basic04/Code_07_IsBSTAndCBT.java‎

Lines changed: 171 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,171 @@
1+
package algorithm.basic04;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
import java.util.Stack;
6+
7+
/**
8+
* @Created by mood321
9+
* @Date 2019/11/4 0004
10+
* @Description TODO
11+
*/
12+
public class Code_07_IsBSTAndCBT {
13+
public static class Node {
14+
int data;
15+
Node left;
16+
Node right;
17+
18+
public Node(int data) {
19+
this.data = data;
20+
}
21+
}
22+
23+
// 非递归版本中序遍历
24+
public static boolean isBST1(Node head) {
25+
if (head == null) {
26+
return true;
27+
}
28+
Stack<Node> stack = new Stack<>();
29+
Node pre = new Node(Integer.MIN_VALUE);
30+
while (!stack.isEmpty() || head != null) {
31+
if (head != null) {
32+
stack.push(head);
33+
head = head.left;
34+
} else {
35+
Node pop = stack.pop();
36+
if (pre.data > pop.data)
37+
return false;
38+
pre = pop;
39+
head = pop.right;
40+
41+
}
42+
}
43+
return true;
44+
}
45+
46+
public static void main(String[] args) {
47+
Node head = new Node(4);
48+
head.left = new Node(2);
49+
head.right = new Node(6);
50+
head.left.left = new Node(1);
51+
head.left.right = new Node(3);
52+
head.right.left = new Node(5);
53+
54+
/* printTree(head);*/
55+
System.out.println(isBST(head));//morris 遍历 判断是否是搜索树
56+
System.out.println(isBST1(head));// 非递归遍历 判断是否是搜索树
57+
System.out.println(isBST2(head));// 递归遍历 判断是否是搜索树
58+
System.out.println(isCBT(head));// 判断是否是一个 完全二叉树
59+
60+
61+
}
62+
63+
/**
64+
* 判断时候是完全二叉树
65+
* 1. 有右子节点 无左子树 一定不是
66+
* 2. 有左子树 无右子树 接下来所有节点必须是叶子节点 才是完全二叉树
67+
* @param head
68+
* @return
69+
*/
70+
public static boolean isCBT(Node head) {
71+
if(head==null){
72+
return true;
73+
}
74+
Queue<Node> queue = new LinkedList<>();
75+
queue.offer(head);
76+
Node l=null;
77+
Node r=null;
78+
//
79+
boolean flag=false;
80+
while (!queue.isEmpty()){
81+
head = queue.poll();
82+
l=head.left;
83+
r=head.right;
84+
// 在第一种情况下 左为空 右不为空 不是
85+
// 在第二种情况下 已经发生 节点必须是叶子节点 进入这种情况 左子不为空
86+
if ((flag && (l != null || r != null)) || (l == null && r != null))
87+
return false;
88+
89+
// 逻辑与上面相等
90+
/*if(l == null && r != null)
91+
return false;
92+
if(flag){
93+
if(l != null || r != null)
94+
return false;
95+
}*/
96+
//
97+
if(l!=null)
98+
queue.offer(l);
99+
if(r!=null)
100+
queue.offer(r);
101+
}
102+
103+
return true;
104+
105+
}
106+
public static boolean isBST(Node head) {
107+
if (head == null) {
108+
return true;
109+
}
110+
boolean res = true;
111+
Node pre = null;
112+
Node cur1 = head;
113+
Node cur2 = null;
114+
while (cur1 != null) {
115+
cur2 = cur1.left;
116+
if (cur2 != null) {
117+
while (cur2.right != null && cur2.right != cur1) {
118+
cur2 = cur2.right;
119+
}
120+
if (cur2.right == null) {
121+
cur2.right = cur1;
122+
cur1 = cur1.left;
123+
continue;
124+
} else {
125+
cur2.right = null;
126+
}
127+
}
128+
if (pre != null && pre.data > cur1.data) {
129+
res = false;
130+
}
131+
pre = cur1;
132+
cur1 = cur1.right;
133+
}
134+
return res;
135+
}
136+
137+
// 递归
138+
private static boolean isBST2(Node head) {
139+
if (head == null) {
140+
return true;
141+
}
142+
Boolean[] res = {true};
143+
checkNode(head, head.data, false, res);
144+
return res[0];
145+
}
146+
147+
private static void checkNode(Node head, int minValue, boolean flag, Boolean[] res) {
148+
if (head == null) {
149+
return;
150+
151+
}
152+
153+
checkNode(head.left, head.data, false, res);
154+
if (!res[0] ) {
155+
return;
156+
}
157+
if (!flag) {
158+
if (minValue < head.data)
159+
res[0] = false;
160+
} else {
161+
if (minValue > head.data)
162+
res[0] = false;
163+
}
164+
165+
checkNode(head.right, head.data, true, res);
166+
if (!res[0] ) {
167+
return;
168+
}
169+
170+
}
171+
}

‎src/main/resources/note/Algorithm/算法学习基本数据结构和算法原型.md‎

Lines changed: 16 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -27,12 +27,12 @@
2727
<p> 用栈模拟 递归压栈 出栈
2828
<p> 3 Morris遍历(..)
2929
<p><a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic04/Code_01_PreInPosTraversal.java">code</a>
30-
+ 如何直观的打印一颗二叉树
30+
+ 2 如何直观的打印一颗二叉树
3131
<p> 题外： 在有前序和中序的时候 是能逆推出一颗树的 :
3232
<p> 这种树还原要么节点值都不一样 要么数组传入的是原树的节点对象 （思路是前序第一个一定是首节点,在中序中他左边的一定是他的左节点 右边的一定是他的右节点 递归一定能拿到颗正确的二叉树
3333
<p> <a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/offer/前序遍历和中序推出二叉树.java">前序和中序逆推二叉树code</a>
3434
<p><a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic04/Code_02_PrintBinaryTree.java">左神打印二叉树code</a>
35-
+ 在二叉树中找到一个节点的后继节点
35+
+ 3 在二叉树中找到一个节点的后继节点
3636
<p>【题目】 现在有一种新的二叉树节点类型如下：
3737
<pre><code>
3838
public class Node {
@@ -55,9 +55,22 @@
5555
<p> 前驱逻辑相反
5656
<p> <a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic04/Code_03_SuccessorNode.java">找后继code</a>
5757

58-
+ 介绍二叉树的序列化和反序列化
58+
+ 4 介绍二叉树的序列化和反序列化
5959
<p> 1. 每个节点用!隔开,空节点用#表示
6060
<p> 2.
6161
<p> <a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic04/Code_04_SerializeAndReconstructTree.java">code</a>
62+
+ 6 判断一棵二叉树是否是平衡二叉树
63+
<p> 平衡二叉树的严格定义
64+
<p> 左子树和右子树高度差不大于1
65+
<p> 思路: 左子树不是平衡树 整棵树一定不是 右子同理 ，左子和右子都是 他们高度差大于1 不是
66+
<p> <a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic04/Code_06_IsBalancedTree.java">code</a>
6267

68+
+ 7 判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树
69+
<p> 搜索二叉树 左子节点比父节点小 右子节点比父节点大 一般不包含重复的节点（重复节点可放在同一节点）
70+
<p> 判断是否是搜索二叉树 中序遍历 值一定是递增的
71+
<p> 判断时候是完全二叉树
72+
<p>1. 有右子节点 无左子树 一定不是
73+
<p>2. 有左子树 无右子树 接下来所有节点必须是叶子节点 才是完全二叉树
74+
<p> 注: 深度遍历用栈 广度用队列
75+
6376
###

0 commit comments

Comments
 (0)