Skip to content

Commit 8134967

Browse files
author
chenweijie
committed
push test case
1 parent 6b37dec commit 8134967

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

56 files changed

+2271
-62
lines changed

‎src/main/java/com/chen/algorithm/array/ArrayFind.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.chen.algorithm.array;
2+
3+
/**
4+
* 二维数组，从上到下递增；从左到右递增；
5+
* 查找二维数组中是否含有某个整数
6+
*
7+
* @author : chen weijie
8+
* @Date: 2020-04-28 19:17
9+
*/
10+
public class ArrayFind {
11+
12+
13+
public boolean find(int target, int[][] array) {
14+
15+
int row = array.length - 1;
16+
int column = 0;
17+
18+
while (row >= 0 && column <= array[0].length) {
19+
if (array[row][column] > target) {
20+
row--;
21+
} else if (array[row][column] < target) {
22+
column++;
23+
} else {
24+
return true;
25+
}
26+
}
27+
28+
29+
return false;
30+
}
31+
32+
}

‎src/main/java/com/chen/algorithm/backtrack/Cal8queens.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package com.chen.algorithm.backtrack;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* 使用回溯算法解决8皇后问题
7+
*
8+
* @author : chen weijie
9+
* @Date: 2020-05-01 18:04
10+
*/
11+
public class Cal8queens {
12+
13+
14+
int[] result = new int[8];//全局或成员变量,下标表示行,值表示queen存储在哪一列
15+
16+
public void cal8queens(int row) { // 调用方式：cal8queens(0);
17+
if (row == 8) { // 8个棋子都放置好了，打印结果
18+
printQueens(result);
19+
return; // 8行棋子都放好了，已经没法再往下递归了，所以就return
20+
}
21+
for (int column = 0; column < 8; ++column) { // 每一行都有8中放法
22+
if (isOk(row, column)) { // 有些放法不满足要求
23+
result[row] = column; // 第row行的棋子放到了column列
24+
cal8queens(row + 1); // 考察下一行
25+
}
26+
}
27+
}
28+
29+
private boolean isOk(int row, int column) {//判断row行column列放置是否合适
30+
int leftup = column - 1, rightup = column + 1;
31+
for (int i = row - 1; i >= 0; --i) { // 逐行往上考察每一行
32+
if (result[i] == column) {
33+
return false; // 第i行的column列有棋子吗？
34+
}
35+
if (leftup >= 0) { // 考察左上对角线：第i行leftup列有棋子吗？
36+
if (result[i] == leftup) {
37+
return false;
38+
}
39+
}
40+
if (rightup < 8) { // 考察右上对角线：第i行rightup列有棋子吗？
41+
if (result[i] == rightup) {
42+
return false;
43+
}
44+
}
45+
--leftup;
46+
++rightup;
47+
}
48+
return true;
49+
}
50+
51+
private void printQueens(int[] result) { // 打印出一个二维矩阵
52+
for (int row = 0; row < 8; ++row) {
53+
for (int column = 0; column < 8; ++column) {
54+
if (result[row] == column) {
55+
System.out.print("Q ");
56+
} else {
57+
System.out.print("* ");
58+
}
59+
}
60+
System.out.println();
61+
}
62+
System.out.println();
63+
}
64+
65+
66+
@Test
67+
public void main() {
68+
cal8queens(0);
69+
}
70+
}

‎src/main/java/com/chen/algorithm/backtrack/Mindist.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.chen.algorithm.backtrack;
2+
3+
/**
4+
* 最短路径问题
5+
*
6+
* @author : chen weijie
7+
* @Date: 2020-05-01 22:25
8+
*/
9+
public class Mindist {
10+
11+
12+
// 全局变量或者成员变量
13+
private int minDist = Integer.MAX_VALUE;
14+
15+
// 调用方式：minDistBacktracing(0, 0, 0, w, n);
16+
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
17+
// 到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
18+
if (i == n && j == n) {
19+
if (dist < minDist) {
20+
minDist = dist;
21+
}
22+
return;
23+
}
24+
// 往下走，更新i=i+1, j=j
25+
if (i < n) {
26+
minDistBT(i + 1, j, dist + w[i][j], w, n);
27+
}
28+
// 往右走，更新i=i, j=j+1
29+
if (j < n) {
30+
minDistBT(i, j + 1, dist + w[i][j], w, n);
31+
}
32+
}
33+
34+
35+
}

‎src/main/java/com/chen/algorithm/backtrack/ZeroOneBag.java

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.chen.algorithm.backtrack;
2+
3+
/**
4+
* 0-1 背包问题
5+
* <p>
6+
* <p>
7+
* 我们有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，
8+
* 装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
9+
*
10+
* @author : chen weijie
11+
* @Date: 2020-05-01 18:10
12+
*/
13+
public class ZeroOneBag {
14+
15+
16+
//存储背包中物品总重量的最大值
17+
public int maxW = Integer.MIN_VALUE;
18+
19+
20+
/**
21+
* // cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
22+
* // w背包重量；items表示每个物品的重量；n表示物品个数
23+
* // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
24+
* // f(0, 0, a, 10, 100)
25+
*
26+
* 我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。
27+
* 先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
28+
*
29+
* @param i
30+
* @param cw
31+
* @param items
32+
* @param n
33+
* @param w
34+
*/
35+
public void solution(int i, int cw, int[] items, int n, int w) {
36+
// cw==w表示装满了;i==n表示已经考察完所有的物品
37+
if (cw == w || i == n) {
38+
if (cw > maxW) {
39+
maxW = cw;
40+
}
41+
return;
42+
}
43+
solution(i + 1, cw, items, n, w);
44+
// 已经超过可以背包承受的重量的时候，就不要再装了
45+
if (cw + items[i] <= w) {
46+
solution(i + 1, cw + items[i], items, n, w);
47+
}
48+
}
49+
50+
51+
52+
}

‎src/main/java/com/chen/algorithm/backtrack/ZeroOneBag2.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.chen.algorithm.backtrack;
2+
3+
/**
4+
* 0-1 背包问题
5+
* <p>
6+
* <p>
7+
* 我们有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，
8+
* 装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
9+
*
10+
* @author : chen weijie
11+
* @Date: 2020-05-01 18:10
12+
*/
13+
public class ZeroOneBag2 {
14+
15+
16+
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
17+
private int[] weight = {2, 2, 4, 6, 3}; // 物品重量
18+
private int n = 5; // 物品个数
19+
private int w = 9; // 背包承受的最大重量
20+
private boolean[][] mem = new boolean[5][10]; // 备忘录，默认值false
21+
22+
public void f(int i, int cw) { // 调用f(0, 0)
23+
if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
24+
if (cw > maxW) {
25+
maxW = cw;
26+
}
27+
return;
28+
}
29+
if (mem[i][cw]) {
30+
return; // 重复状态
31+
}
32+
mem[i][cw] = true; // 记录(i, cw)这个状态
33+
f(i + 1, cw); // 选择不装第i个物品
34+
if (cw + weight[i] <= w) {
35+
f(i + 1, cw + weight[i]); // 选择装第i个物品
36+
}
37+
}
38+
39+
40+
}

‎src/main/java/com/chen/algorithm/bsearch/HanNuoTa.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.chen.algorithm.bsearch;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2020-05-02 11:56
6+
*/
7+
public class HanNuoTa {
8+
9+
/**
10+
* 汉诺塔问题
11+
*
12+
* @param dish 盘子个数
13+
* @param from 初始塔数
14+
* @param temp 中介塔数
15+
* @param to 目标塔数
16+
*/
17+
public static void move(int dish, String from, String temp, String to) {
18+
19+
if (dish == 1) {
20+
System.out.println("将盘子" + dish + "从塔座" + from + "移动到目标塔座" + to);
21+
} else {
22+
//A为初始塔，B为目标塔，C为中介塔
23+
move(dish - 1, from, to, temp);
24+
System.out.println("将盘子" + dish + "从塔座" + from + "移动到目标塔座" + to);
25+
//B为初始塔，C为目标塔，A是中介塔
26+
move(dish - 1, temp, from, to);
27+
}
28+
}
29+
30+
31+
public static void main(String[] args) {
32+
33+
move(4, "A", "C", "B");
34+
}
35+
}

‎src/main/java/com/chen/algorithm/bsearch/Search.java

Lines changed: 0 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,6 @@ public class Search {
1717
* @return
1818
*/
1919
public static int findTwoPoint(int[] array, int key) {
20-
2120
if (array == null || array.length == 0) {
2221
return -1;
2322
}
@@ -28,13 +27,10 @@ public static int findTwoPoint(int[] array, int key) {
2827
while (max >= min) {
2928

3029
int mid = (max + min) / 2;
31-
3230
if (key == array[mid]) {
3331
return mid;
3432
}
35-
3633
if (key > array[mid]) {
37-
3834
min = mid + 1;
3935
}
4036

@@ -79,32 +75,7 @@ public static int sort(int low, int high, int[] array, int key) {
7975
}
8076

8177

82-
/**
83-
* 汉诺塔问题
84-
*
85-
* @param dish 盘子个数
86-
* @param from 初始塔数
87-
* @param temp 中介塔数
88-
* @param to 目标塔数
89-
*/
90-
public static void move(int dish, String from, String temp, String to) {
91-
92-
if (dish == 1) {
93-
System.out.println("将盘子" + dish + "从塔座" + from + "移动到目标塔座" + to);
94-
} else {
95-
//A为初始塔，B为目标塔，C为中介塔
96-
move(dish - 1, from, to, temp);
97-
System.out.println("将盘子" + dish + "从塔座" + from + "移动到目标塔座" + to);
98-
//B为初始塔，C为目标塔，A是中介塔
99-
move(dish - 1, temp, from, to);
100-
}
101-
}
102-
103-
104-
public static void main(String[] args) {
10578

106-
move(4,"A","C","B");
107-
}
10879

10980

11081
}

0 commit comments

Comments
 (0)