Skip to content

Commit c4d2f13

Browse files
znn0301znn0301
committed
dp-1
1 parent 1344994 commit c4d2f13

File tree

16 files changed

+774
-15
lines changed

16 files changed

+774
-15
lines changed

‎src/main/java/com/chen/algorithm/study/test39/Solution2.java‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,11 @@
11
package com.chen.algorithm.study.test39;
22

3+
import com.alibaba.fastjson.JSONObject;
4+
import org.junit.Test;
5+
36
import java.util.ArrayList;
47
import java.util.Arrays;
58
import java.util.List;
6-
import java.util.Stack;
79

810
/**
911
* https://leetcode-cn.com/problems/combination-sum/solution/di-gui-hui-su-tu-wen-fen-xi-ji-bai-liao-9987de-yon/
@@ -24,7 +26,7 @@ public List<List<Integer>> combinationSum(int[] candidates, int target) {
2426

2527
public void backtrack(List<List<Integer>> res, int[] candidates, int target, List<Integer> curList, int start) {
2628
if (target == 0) {
27-
res.add(new ArrayList<>(new Stack<>()));
29+
res.add(new ArrayList<>(curList));
2830
return;
2931
}
3032

@@ -39,4 +41,11 @@ public void backtrack(List<List<Integer>> res, int[] candidates, int target, Lis
3941
}
4042
}
4143

44+
@Test
45+
public void test() {
46+
int[] candidates = {2, 3, 6, 7};
47+
int target = 7;
48+
49+
System.out.println(combinationSum(candidates, target));
50+
}
4251
}

‎src/main/java/com/chen/algorithm/znn/backtrack/Test.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,4 +6,19 @@
66
* @Description: 回溯相关
77
*/
88
public class Test {
9+
10+
/**
11+
* 回溯算法的框架：
12+
*
13+
* result = []
14+
* def backtrack(路径, 选择列表):
15+
* if 满足结束条件:
16+
* result.add(路径)
17+
* return
18+
*
19+
* for 选择 in 选择列表:
20+
* 做选择
21+
* backtrack(路径, 选择列表)
22+
* 撤销选择
23+
*/
924
}

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

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
package com.chen.algorithm.znn.backtrack;
2+
3+
/**
4+
* 我们有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，
5+
* 装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
6+
*
7+
* @Auther: zhunn
8+
* @Date: 2020/11/3 14:53
9+
* @Description: 0-1背包问题:1-回溯；2-动态规划
10+
*/
11+
public class ZeroOneBag {
12+
13+
private int maxW = Integer.MAX_VALUE;
14+
private int[] items = {2, 2, 4, 6, 3}; // 物品重量
15+
private int n = 5; // 物品个数
16+
private int w = 9; // 背包承受的最大重量
17+
18+
/**
19+
* 1-回溯
20+
* // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
21+
* // f(0, 0, a, 10, 100)
22+
* <p>
23+
* 我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。
24+
* 先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
25+
*
26+
* @param i 表示考察到哪个物品了
27+
* @param cw 表示当前已经装进去的物品的重量和
28+
* items 表示每个物品的重量
29+
* n 表示物品个数
30+
* w 背包重量
31+
*/
32+
public void bag1(int i, int cw) {
33+
// cw==w表示装满了;i==n表示已经考察完所有的物品
34+
if (cw == w || i == n) {
35+
if (cw > maxW) {
36+
maxW = cw;
37+
}
38+
return;
39+
}
40+
bag1(i + 1, cw);
41+
// 已经超过可以背包承受的重量的时候，就不要再装了
42+
if (cw + items[i] <= w) {
43+
bag1(i + 1, cw + items[i]);
44+
}
45+
}
46+
47+
private boolean[][] memo = new boolean[5][10];
48+
49+
public void bag2(int i, int cw) {
50+
if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
51+
if (cw > maxW) {
52+
maxW = cw;
53+
}
54+
return;
55+
}
56+
if (memo[i][cw]) {
57+
return; // 重复状态
58+
}
59+
memo[i][cw] = true; // 记录(i, cw)这个状态
60+
bag2(i + 1, cw); // 选择不装第i个物品
61+
if (cw + items[i] <= w) {
62+
bag2(i + 1, cw + items[i]); // 选择装第i个物品
63+
}
64+
}
65+
66+
/**
67+
* 2-动态规划
68+
* 我们把整个求解过程分为n个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。
69+
* 我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过w个（w表示背包的承载重量），也就是例子中的9。于是，我们就成功避免了每层状态个数的指数级增长。
70+
* 我们用一个二维数组states[n][w+1]，来记录每层可以达到的不同状态。
71+
* 第0个（下标从0开始编号）物品的重量是2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是0或者2。我们用states[0][0]=true和states[0][2]=true来表示这两种状态。
72+
* 第1个物品的重量也是2，基于之前的背包状态，在这个物品决策完之后，不同的状态有3个，背包中物品总重量分别是0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用states[1][0]=true，states[1][2]=true，states[1][4]=true来表示这三种状态。
73+
* 以此类推，直到考察完所有的物品后，整个states状态数组就都计算好了。我把整个计算的过程画了出来，你可以看看。图中0表示false，1表示true。我们只需要在最后一层，找一个值为true的最接近w（这里是9）的值，就是背包中物品总重量的最大值。
74+
*
75+
* @param weight weight:物品重量（2、2、4、6、3）
76+
* @param n n:物品个数（0-5）
77+
* @param w w:背包可承载重量（0-9）
78+
* @return
79+
*/
80+
public int knapsack(int[] weight, int n, int w) {
81+
boolean[][] states = new boolean[n][w + 1]; //默认值false
82+
states[0][0] = true; //初始化,第一行的数据要特殊处理，可以利用哨兵优化
83+
states[0][weight[0]] = true;
84+
85+
for (int i = 1; i < n; i++) { // 动态规划状态转移
86+
for (int j = 0; j <= w; j++) { // 不把第i个物品放入背包
87+
if (states[i - 1][j] == true) {
88+
states[i][j] = true;
89+
}
90+
}
91+
for (int j = 0; j + weight[i] <= w; i++) { //把第i个物品放入背包
92+
if (states[i - 1][j] == true) {
93+
states[i - 1][j + weight[i]] = true;
94+
}
95+
}
96+
}
97+
for (int i = w; i >= 0; i--) { // 输出结果
98+
if (states[n - 1][i]) {
99+
return i;
100+
}
101+
}
102+
return 0;
103+
}
104+
}

‎src/main/java/com/chen/algorithm/znn/backtrack/test36/Solution.java‎

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
1+
package com.chen.algorithm.znn.backtrack.test36;
2+
3+
import org.junit.Test;
4+
5+
import java.util.HashSet;
6+
7+
/**
8+
* https://leetcode-cn.com/problems/valid-sudoku/solution/javawei-yun-suan-1ms-100-li-jie-fang-ge-suo-yin-by/
9+
*
10+
* @Auther: zhunn
11+
* @Date: 2020/11/3 13:54
12+
* @Description: 有效的数独：1-哈希数组；2-位运算数组
13+
*/
14+
public class Solution {
15+
16+
/**
17+
* 1-哈希数组
18+
*
19+
* @param board
20+
* @return
21+
*/
22+
public boolean isValidSudoku(char[][] board) {
23+
HashSet<Integer>[] rows = new HashSet[9];
24+
HashSet<Integer>[] cols = new HashSet[9];
25+
HashSet<Integer>[] boxes = new HashSet[9];
26+
for (int i = 0; i < 9; i++) {
27+
rows[i] = new HashSet<>();
28+
cols[i] = new HashSet<>();
29+
boxes[i] = new HashSet<>();
30+
}
31+
for (int i = 0; i < 9; i++) {
32+
for (int j = 0; j < 9; j++) {
33+
if (board[i][j] == '.')
34+
continue;
35+
int tmp = board[i][j] - '0';
36+
if (rows[i].contains(tmp) //本行中已有数字
37+
|| cols[j].contains(tmp) //本列中已有数字
38+
|| boxes[(i / 3) * 3 + j / 3].contains(tmp)) //本方格中已有数字
39+
return false;
40+
rows[i].add(tmp); //添加到本行
41+
cols[j].add(tmp); //添加到本列
42+
boxes[(i / 3) * 3 + j / 3].add(tmp); //添加到本方格
43+
}
44+
}
45+
return true;
46+
}
47+
48+
/**
49+
* 2-位运算数组
50+
*/
51+
public boolean isValidSudoku2(char[][] board) {
52+
int[] rows = new int[9]; //行的位运算数组
53+
int[] cols = new int[9]; //列的位运算数组
54+
int[] boxes = new int[9]; //方格的位运算数组
55+
for (int i = 0; i < 9; i++) {
56+
for (int j = 0; j < 9; j++) {
57+
if (board[i][j] == '.')
58+
continue;
59+
int tmp = board[i][j] - '0';
60+
int boxIndex = i / 3 * 3 + j / 3;
61+
if ((rows[i] >> tmp & 1) == 1 //rows[i] >> tmp & 1取出第i行的tmp数字，看是否已填，如果等于1，代表已填
62+
|| (cols[j] >> tmp & 1) == 1 //cols[j] >> tmp & 1取出第j列的tmp数字，看是否已填，如果等于1，代表已填
63+
|| (boxes[boxIndex] >> tmp & 1) == 1) //boxes[boxIndex] >> tmp & 1取出第boxIndex个方格的tmp数字，看是否已填，如果等于1，代表已填
64+
return false;
65+
rows[i] = rows[i] | (1 << tmp); //将tmp数字加入到第i行的位运算数组
66+
cols[j] = cols[j] | (1 << tmp); //将tmp数字加入到第j列的位运算数组
67+
boxes[boxIndex] = boxes[boxIndex] | (1 << tmp); //将tmp数字加入到第boxIndex个方格的位运算数组
68+
}
69+
}
70+
return true;
71+
}
72+
73+
public boolean isValidSudoku1(char[][] board) {
74+
int[][] row = new int[9][10]; // 哈希表存储每一行的每个数是否出现过，默认初始情况下，每一行每一个数都没有出现过
75+
// 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
76+
int[][] col = new int[9][10]; // 存储每一列的每个数是否出现过，默认初始情况下，每一列的每一个数都没有出现过
77+
int[][] box = new int[9][10]; // 存储每一个box的每个数是否出现过，默认初始情况下，在每个box中，每个数都没有出现过。整个board有9个box。
78+
for (int i = 0; i < 9; i++) {
79+
for (int j = 0; j < 9; j++) {
80+
if (board[i][j] == '.') {
81+
continue;
82+
}
83+
84+
// 遍历到第i行第j列的那个数,我们要判断这个数在其所在的行有没有出现过，
85+
// 同时判断这个数在其所在的列有没有出现过
86+
// 同时判断这个数在其所在的box中有没有出现过
87+
int curNum = board[i][j] - '0';
88+
if (row[i][curNum] == 1) {
89+
return false;
90+
}
91+
if (col[j][curNum] == 1) {
92+
return false;
93+
}
94+
if (box[j / 3 + (i / 3) * 3][curNum] == 1) {
95+
return false;
96+
}
97+
row[i][curNum] = 1; // 之前都没出现过，现在出现了，就给它置为1，下次再遇见就能够直接返回false了。
98+
col[j][curNum] = 1;
99+
box[j / 3 + (i / 3) * 3][curNum] = 1;
100+
}
101+
}
102+
return true;
103+
}
104+
105+
@Test
106+
public void test() {
107+
char[][] board = {
108+
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
109+
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
110+
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
111+
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
112+
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
113+
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
114+
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
115+
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
116+
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
117+
};
118+
boolean res = isValidSudoku(board);
119+
System.out.println(res);
120+
}
121+
}

‎src/main/java/com/chen/algorithm/znn/backtrack/test39/Solution.java‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.chen.algorithm.znn.backtrack.test39;
2+
3+
import com.alibaba.fastjson.JSONObject;
4+
import org.junit.Test;
5+
6+
import java.util.ArrayList;
7+
import java.util.Arrays;
8+
import java.util.List;
9+
10+
/**
11+
* https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
12+
*
13+
* @Auther: zhunn
14+
* @Date: 2020/11/3 15:27
15+
* @Description: 组合总和
16+
*/
17+
public class Solution {
18+
19+
public List<List<Integer>> combinationSum(int[] candidates, int target) {
20+
if (candidates == null || candidates.length == 0) {
21+
return null;
22+
}
23+
List<List<Integer>> res = new ArrayList<>();
24+
// 排序是剪枝的前提
25+
Arrays.sort(candidates);
26+
backtrack(0, target, candidates, new ArrayList<>(), res);
27+
return res;
28+
}
29+
30+
private void backtrack(int start, int target, int[] candidates, List<Integer> curList, List<List<Integer>> res) {
31+
if (target == 0) {
32+
res.add(new ArrayList<>(curList));
33+
return;
34+
}
35+
for (int i = start; i < candidates.length; i++) {
36+
if (candidates[i] > target) {
37+
continue;
38+
}
39+
curList.add(candidates[i]);
40+
//System.out.println("递归之前 => " + curList + "，剩余 = " + (target - candidates[i]));
41+
backtrack(i, target - candidates[i], candidates, curList, res);
42+
curList.remove(curList.size() - 1);
43+
//System.out.println("递归之后 => " + curList);
44+
}
45+
}
46+
//private void backtrack(int start, int target, int[] candidates, List<Integer> curList, List<List<Integer>> res) {
47+
// // 由于进入更深层的时候，小于0的部分被剪枝，因此递归终止条件值只判断等于0的情况
48+
// //if (target < 0) {
49+
// // return;
50+
// //}
51+
// if (target == 0) {
52+
// res.add(new ArrayList<>(curList));
53+
// return;
54+
// }
55+
// // 重点理解这里从start开始搜索的语意
56+
// for (int i = start; i < candidates.length; i++) {
57+
// if (candidates[i] > target) { // 重点理解这里剪枝，前提是候选数组已经有序
58+
// continue;
59+
// }
60+
// curList.add(candidates[i]);
61+
// backtrack(i, target - candidates[i], candidates, curList, res);// 注意每个元素可以重复使用，下一轮搜索的起点依然是 i
62+
// curList.remove(curList.size() - 1); //状态重置
63+
// }
64+
//}
65+
66+
@Test
67+
public void test() {
68+
int[] candidates = {2, 3, 6, 7};
69+
int target = 7;
70+
71+
System.out.println(JSONObject.toJSONString(combinationSum(candidates, target)));
72+
}
73+
}

0 commit comments

Comments
 (0)