Skip to content

Commit 2daa774

Browse files
NoteXYXNoteXYX
committed
ok
1 parent 7d6f63c commit 2daa774

File tree

4 files changed

+320
-17
lines changed

4 files changed

+320
-17
lines changed

‎src/com/leetcode/Main200.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.leetcode;
2+
3+
/**
4+
* 200. 岛屿数量
5+
* 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
6+
*
7+
* 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
8+
*
9+
* 此外，你可以假设该网格的四条边均被水包围。
10+
*
11+
*  
12+
*
13+
* 示例 1:
14+
*
15+
* 输入:
16+
* [
17+
* ['1','1','1','1','0'],
18+
* ['1','1','0','1','0'],
19+
* ['1','1','0','0','0'],
20+
* ['0','0','0','0','0']
21+
* ]
22+
* 输出: 1
23+
*/
24+
public class Main200 {
25+
public int numIslands(char[][] grid) {
26+
if (grid== null || grid.length < 1) {
27+
return 0;
28+
}
29+
int rows = grid.length;
30+
int cols = grid[0].length;
31+
int res = 0;
32+
for (int i = 0; i < rows; i++) {
33+
for (int j = 0; j < cols; j++) {
34+
if (grid[i][j] == '1') {
35+
res += 1;
36+
dfs(grid, i, rows, j, cols);
37+
}
38+
}
39+
}
40+
return res;
41+
42+
}
43+
public void dfs(char[][] grid, int row, int rows, int col, int cols) {
44+
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
45+
return;
46+
}
47+
grid[row][col] = '0';
48+
dfs(grid, row-1, rows, col, cols);
49+
dfs(grid, row+1, rows, col, cols);
50+
dfs(grid, row, rows, col-1, cols);
51+
dfs(grid, row, rows, col+1, cols);
52+
}
53+
}

‎src/com/leetcode/Main300.java‎

Lines changed: 22 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
package com.leetcode;
22

3+
import java.util.ArrayList;
34
import java.util.Arrays;
5+
import java.util.List;
46

57
/**
68
* 300. 最长上升子序列
@@ -10,39 +12,42 @@
1012
* 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
1113
*/
1214
public class Main300 {
13-
// public int lengthOfLIS(int[] nums) {
14-
// if (nums==null || nums.length==0)
15-
// return 0;
16-
// int[] dp = new int[nums.length];
17-
// dp[0] = 1;
18-
// int maxAns = 1;
19-
// for (int i = 1; i < dp.length; i++) {
20-
// int curMax = 0;
21-
// for (int j = 0; j < i; j++) {
22-
// if (nums[i] > nums[j])
23-
// curMax = Math.max(curMax, dp[j]);
24-
// }
25-
// dp[i] = curMax + 1;
26-
// maxAns = Math.max(dp[i], maxAns);
27-
// }
28-
// return maxAns;
29-
// }
3015
public int lengthOfLIS(int[] nums) {
3116
int len = nums.length;
3217
if (len < 2) {
3318
return len;
3419
}
3520
int[] dp = new int[len];
3621
Arrays.fill(dp, 1);
22+
List<Integer> list = new ArrayList<>();
23+
int pos = 0;
24+
int posDp = 0;
3725
int maxAns = 1;
3826
for (int i = 1; i < len; i++) {
3927
for (int j = 0; j < i; j++) {
4028
if (nums[j] < nums[i]) {
4129
dp[i] = Math.max(dp[i], dp[j] + 1);
30+
if (dp[i] >= maxAns)
31+
pos = i;
4232
}
4333
}
4434
maxAns = Math.max(maxAns, dp[i]);
4535
}
36+
posDp = maxAns;
37+
list.add(nums[pos]);
38+
for (int i = pos-1; i >= 0 ; i--) {
39+
if (dp[i] == posDp-1) {
40+
list.add(0, nums[i]);
41+
posDp -= 1;
42+
}
43+
}
44+
System.out.println(list);
4645
return maxAns;
4746
}
47+
48+
public static void main(String[] args) {
49+
Main300 m = new Main300();
50+
int[] nums = {10,9,2,5,3,7,18,118,1};
51+
System.out.println(m.lengthOfLIS(nums));
52+
}
4853
}

‎src/com/leetcode/Pack.java‎

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package com.leetcode;
2+
3+
public class Pack {
4+
public static void main(String[] args) {
5+
int[] w = {2, 1, 3, 2};
6+
int[] v = {12, 10, 20, 15};
7+
int[] m = {2, 3, 3, 6};
8+
Pack01 pack01 = new Pack01();
9+
System.out.println(pack01.knapSack(w, v, 5));
10+
System.out.println(pack01.youhua(w, v, 5));
11+
Packwq packwq = new Packwq();
12+
System.out.println(packwq.wqpack(w, v, 5));
13+
System.out.println(packwq.youhua(w, v, 5));
14+
Packdc packdc = new Packdc();
15+
System.out.println(packdc.dcpack(w, v, m, 5));
16+
System.out.println(packdc.youhua(w, v, m, 5));
17+
}
18+
}
19+
20+
class Pack01 {
21+
public int knapSack(int[] w, int[] v, int cap) { //未优化
22+
int num = w.length;
23+
if (num == 0 || cap == 0)
24+
return 0;
25+
int[][] dp = new int[num][cap+1];
26+
for (int i = 0; i <= cap; i++) {
27+
dp[0][i] = w[0]<=i ? v[0] : 0; //先初始化放入第一个物品
28+
}
29+
for (int i = 1; i < num; i++) {
30+
for (int j = 0; j <=cap ; j++) {
31+
dp[i][j] = dp[i-1][j]; //默认为不放当前第i个物品
32+
if (w[i] <= j)
33+
dp[i][j] = Math.max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
34+
}
35+
}
36+
return dp[num-1][cap];
37+
}
38+
public int youhua(int[] w, int[] v, int cap) { //优化后
39+
int num = w.length;
40+
int[] dp = new int[cap+1];
41+
for (int i = 0; i < num; i++) {
42+
for (int j = cap; j >= w[i]; j--) { //从最后一个背包开始装
43+
dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
44+
}
45+
}
46+
return dp[cap];
47+
}
48+
}
49+
50+
class Packwq {
51+
public int wqpack(int[] w, int[] v, int cap) {
52+
//dp[i][j] = max{dp[i-1][t - w[i] * k] + v[i] * k}; （0 <= k * w[i] <= j）
53+
int[][] dp = new int[v.length+1][cap+1];
54+
for(int i = 0; i < v.length; i++) {
55+
for(int j = 0; j <= cap; j++) {
56+
for(int k=0; k * w[i] <= j; k++)
57+
dp[i+1][j]=Math.max(dp[i+1][j], dp[i][j - k * w[i]] + k * v[i]);
58+
}
59+
}
60+
return dp[v.length][cap];
61+
}
62+
public int youhua(int[] w, int[] v, int cap) { //优化后的算法
63+
//dp[j] = max(dp[j], dp[j-w[i]]+v[i])
64+
int[] dp = new int[cap+1];
65+
for (int i = 0; i < v.length; i++) {
66+
for (int j = w[i]; j <= cap; j++) { //从第一个可装的背包开始装
67+
dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
68+
}
69+
}
70+
return dp[cap];
71+
}
72+
}
73+
74+
class Packdc {
75+
public int dcpack(int[] w, int[] v, int[] m, int cap) {
76+
int[][] dp = new int[v.length+1][cap+1];
77+
for (int i = 0; i < v.length; i++) {
78+
for (int j = 0; j <= cap; j++) {
79+
for (int k = 0; k<=m[i] && k*w[i]<=j ; k++) {
80+
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j - k * w[i]] + k * v[i]);
81+
}
82+
}
83+
}
84+
return dp[v.length][cap];
85+
}
86+
public int youhua(int[] w, int[] v, int[] m, int cap) {
87+
int[] dp = new int[cap+1];
88+
for (int i = 0; i < v.length; i++) {
89+
int k = 1;
90+
for (int j = w[i]; k<=m[i] && j<=cap ; j++) {
91+
dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
92+
k++;
93+
}
94+
}
95+
return dp[cap];
96+
}
97+
}

‎src/com/leetcode/scanBinaryTree.java‎

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
//二叉树的遍历
2+
package com.leetcode;
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
import java.util.Stack;
6+
7+
public class scanBinaryTree {
8+
private static class TreeNode {
9+
int val;
10+
TreeNode left;
11+
TreeNode right;
12+
TreeNode(int v) {
13+
val = v;
14+
}
15+
}
16+
17+
private static class Pre {
18+
ArrayList<Integer> list = new ArrayList<>();
19+
Stack<TreeNode> stack = new Stack<>();
20+
private void preOrderCur(TreeNode root) { //先序遍历递归
21+
if (root == null)
22+
return;
23+
list.add(root.val);
24+
preOrderCur(root.left);
25+
preOrderCur(root.right);
26+
}
27+
private void preOrder(TreeNode root) { //先序遍历非递归
28+
list.clear();
29+
if (root == null)
30+
return;
31+
stack.push(root);
32+
TreeNode p = root;
33+
while (!stack.empty()) {
34+
p = stack.pop();
35+
list.add(p.val);
36+
if (p.right != null)
37+
stack.push(p.right);
38+
if (p.left != null)
39+
stack.push(p.left);
40+
}
41+
}
42+
}
43+
44+
private static class In {
45+
ArrayList<Integer> list = new ArrayList<>();
46+
Stack<TreeNode> stack = new Stack<>();
47+
private void inOrderCur(TreeNode root) { //中序遍历递归
48+
if (root == null)
49+
return;
50+
inOrderCur(root.left);
51+
list.add(root.val);
52+
inOrderCur(root.right);
53+
}
54+
private void inOrder(TreeNode root) { //中序遍历非递归
55+
list.clear();
56+
TreeNode p = root;
57+
while (p != null || !stack.empty()) {
58+
while (p != null) {
59+
stack.push(p);
60+
p = p.left;
61+
}
62+
p = stack.pop();
63+
list.add(p.val);
64+
p = p.right;
65+
}
66+
}
67+
}
68+
69+
private static class Post {
70+
ArrayList<Integer> list = new ArrayList<>();
71+
Stack<TreeNode> stack = new Stack<>();
72+
private void postOrderCur(TreeNode root) { //后序遍历递归
73+
if (root == null)
74+
return;
75+
postOrderCur(root.left);
76+
postOrderCur(root.right);
77+
list.add(root.val);
78+
}
79+
private void postOrder(TreeNode root) { //后序遍历非递归
80+
list.clear();
81+
if (root == null)
82+
return;
83+
TreeNode p = root;
84+
TreeNode prev = root;
85+
while (p != null || !stack.empty()) {
86+
while (p != null) {
87+
stack.push(p);
88+
p = p.left;
89+
}
90+
p = stack.peek().right;
91+
if (p==null || p == prev) {
92+
p = stack.pop();
93+
list.add(p.val);
94+
prev = p;
95+
p = null;
96+
}
97+
}
98+
}
99+
}
100+
public static ArrayList<Integer> cengci(TreeNode root) {
101+
ArrayList<Integer> list = new ArrayList<>();
102+
LinkedList<TreeNode> queue = new LinkedList<>();
103+
if (root == null)
104+
return list;
105+
queue.offer(root);
106+
while (!queue.isEmpty()) {
107+
root = queue.poll();
108+
list.add(root.val);
109+
if (root.left != null)
110+
queue.offer(root.left);
111+
if (root.right != null)
112+
queue.offer(root.right);
113+
}
114+
return list;
115+
}
116+
117+
public static void main(String[] args) {
118+
TreeNode root = new TreeNode(1);
119+
TreeNode b = new TreeNode(2);
120+
TreeNode c = new TreeNode(3);
121+
TreeNode d = new TreeNode(4);
122+
TreeNode e = new TreeNode(5);
123+
TreeNode f = new TreeNode(6);
124+
TreeNode g = new TreeNode(7);
125+
root.left = b;
126+
root.right = c;
127+
b.right = d;
128+
c.left = e;
129+
c.right = f;
130+
f.left = g;
131+
Pre pre = new Pre();
132+
pre.preOrderCur(root);
133+
System.out.println("先序遍历递归：" + pre.list);
134+
pre.preOrder(root);
135+
System.out.println("先序遍历非递归：" + pre.list);
136+
In in = new In();
137+
in.inOrderCur(root);
138+
System.out.println("中序遍历递归：" + in.list);
139+
in.inOrder(root);
140+
System.out.println("中序遍历非递归：" + in.list);
141+
Post post = new Post();
142+
post.postOrderCur(root);
143+
System.out.println("后序遍历递归：" + post.list);
144+
post.postOrder(root);
145+
System.out.println("后序遍历非递归：" + post.list);
146+
System.out.println("层次遍历：" + cengci(root));
147+
}
148+
}

0 commit comments

Comments
 (0)