Skip to content

Commit fcbc039

Browse files
author
chenweijie
committed
合并区间、搜索单词、零钱兑换、后序遍历二叉树
1 parent 27e5f80 commit fcbc039

File tree

11 files changed

+370
-51
lines changed

11 files changed

+370
-51
lines changed

‎src/main/java/com/chen/Test.java

Lines changed: 0 additions & 35 deletions
This file was deleted.

‎src/main/java/com/chen/CacheMap.java renamed to ‎src/main/java/com/chen/algorithm/CacheMap.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.chen;
1+
package com.chen.algorithm;
22

33
import java.util.LinkedHashMap;
44
import java.util.Map;

‎src/main/java/com/chen/algorithm/exercise/tree/traverseTree/InorderTraversal.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -68,4 +68,46 @@ public static void inOrderIteration(TreeNode head, List<Integer> list) {
6868
}
6969

7070

71+
72+
73+
74+
public static void inOrderIteration2(TreeNode head, List<Integer> list) {
75+
76+
if (head == null ){
77+
return;
78+
}
79+
Stack<TreeNode> stack = new Stack<>();
80+
stack.push(head);
81+
TreeNode current = head;
82+
83+
while (!stack.isEmpty() || current != null) {
84+
while (current != null) {
85+
stack.push(current);
86+
current = current.left;
87+
}
88+
current = stack.pop();
89+
list.add(current.val);
90+
current = current.right;
91+
}
92+
}
93+
94+
95+
96+
97+
98+
99+
100+
101+
102+
103+
104+
105+
106+
107+
108+
109+
110+
111+
112+
71113
}

‎src/main/java/com/chen/algorithm/exercise/tree/traverseTree/PostorderTraversal.java

Lines changed: 30 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ public void postOrder(List<Integer> result, TreeNode node) {
4545
result.add(node.val);
4646
}
4747

48-
public static void postOrderIteration(TreeNode head,List<Integer> list) {
48+
public static void postOrderIteration(TreeNode head, List<Integer> list) {
4949
if (head == null) {
5050
return;
5151
}
@@ -68,5 +68,34 @@ public static void postOrderIteration(TreeNode head,List<Integer> list) {
6868
}
6969

7070

71+
public static void postOrderIteration2(TreeNode head, List<Integer> list) {
72+
73+
74+
if (head == null) {
75+
return;
76+
}
77+
78+
Stack<TreeNode> stack1 = new Stack<>();
79+
Stack<TreeNode> stack2 = new Stack<>();
80+
stack1.push(head);
81+
82+
while (!stack1.isEmpty()) {
83+
TreeNode node = stack1.pop();
84+
stack2.push(node);
85+
86+
if (node.left != null) {
87+
stack1.push(node.left);
88+
}
89+
90+
if (node.right != null) {
91+
stack1.push(node.right);
92+
}
93+
}
94+
95+
while (!stack2.isEmpty()){
96+
list.add(stack2.pop().val);
97+
}
98+
}
99+
71100

72101
}

‎src/main/java/com/chen/algorithm/jianzhi/test66/Solution.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package com.chen.algorithm.jianzhi.test66;
2+
3+
import org.junit.Test;
4+
5+
import java.util.Arrays;
6+
7+
/**
8+
* 整体思路，结果集中任何一个元素 = 其左边所有元素的乘积 * 其右边所有元素的乘积。
9+
* 一轮循环构建左边的乘积并保存在结果集中，
10+
* 二轮循环 构建右边乘积的过程，乘以左边的乘积，并将最终结果保存
11+
*
12+
* @author : chen weijie
13+
* @Date: 2020-09-12 19:31
14+
*/
15+
public class Solution {
16+
17+
18+
public int[] constructArr(int[] a) {
19+
20+
if (a == null || a.length == 0) {
21+
return new int[0];
22+
}
23+
24+
int[] b = new int[a.length];
25+
b[0] = 1;
26+
int temp = 1;
27+
28+
for (int i = 1; i < a.length; i++) {
29+
b[i] = b[i - 1] * a[i - 1];
30+
}
31+
32+
33+
for (int i = a.length - 2; i >= 0; i--) {
34+
temp = a[i + 1] * temp;
35+
b[i] = temp * b[i];
36+
}
37+
38+
return b;
39+
}
40+
41+
42+
@Test
43+
public void testCase() {
44+
int[] a = {1, 2, 3, 4, 5};
45+
int[] res = constructArr(a);
46+
47+
System.out.println(Arrays.toString(res));
48+
}
49+
50+
51+
}

‎src/main/java/com/chen/algorithm/jianzhi/test67/Solution.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.chen.algorithm.jianzhi.test67;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2020-09-12 19:02
8+
*/
9+
public class Solution {
10+
11+
12+
public int strToInt(String str) {
13+
char[] c = str.trim().toCharArray();
14+
if (c.length == 0) {
15+
return 0;
16+
}
17+
int res = 0, bndry = Integer.MAX_VALUE / 10;
18+
int i = 1, sign = 1;
19+
if (c[0] == '-') {
20+
sign = -1;
21+
} else if (c[0] != '+') {
22+
i = 0;
23+
}
24+
for (int j = i; j < c.length; j++) {
25+
if (c[j] < '0' || c[j] > '9') {
26+
break;
27+
}
28+
if (res > bndry || res == bndry && c[j] > '7') {
29+
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
30+
}
31+
res = res * 10 + (c[j] - '0');
32+
}
33+
return sign * res;
34+
35+
}
36+
37+
38+
@Test
39+
public void testCase() {
40+
41+
String str = "2147483646";
42+
System.out.println(strToInt(str));
43+
}
44+
45+
}

‎src/main/java/com/chen/algorithm/study/test34/Solution1.java

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,9 @@ public class Solution1 {
1313

1414

1515
public int[] searchRange(int[] nums, int target) {
16-
if (nums.length == 0) return new int[]{-1, -1};
16+
if (nums.length == 0) {
17+
return new int[]{-1, -1};
18+
}
1719
return new int[]{searchLeft(nums, target), searchRight(nums, target)};
1820
}
1921

@@ -22,12 +24,18 @@ public int searchLeft(int[] nums, int target) {
2224
int right = nums.length;
2325
while (left < right) {
2426
int mid = (left + right) >>> 1;
25-
if (nums[mid] == target) right = mid;
26-
else if (nums[mid] < target) left = mid + 1;
27-
else if (nums[mid] > target) right = mid;
27+
if (nums[mid] == target) {
28+
right = mid;
29+
} else if (nums[mid] < target) {
30+
left = mid + 1;
31+
} else if (nums[mid] > target) {
32+
right = mid;
33+
}
2834
}
2935
int pos = (left < nums.length) ? left : nums.length - 1;
30-
if (nums[pos] != target) return -1;
36+
if (nums[pos] != target) {
37+
return -1;
38+
}
3139
return left;
3240
}
3341

‎src/main/java/com/chen/algorithm/study/test34/Solution3.java

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package com.chen.algorithm.study.test34;
2+
3+
import org.junit.Test;
4+
5+
import java.util.Arrays;
6+
7+
/**
8+
* @author : chen weijie
9+
* @Date: 2020-09-14 01:34
10+
*/
11+
public class Solution3 {
12+
13+
14+
public int[] searchRange(int[] nums, int target) {
15+
16+
int left = 0, right = nums.length - 1;
17+
int[] res = new int[2];
18+
19+
res[0] = leftIndex(target, nums);
20+
res[1] = rightIndex(target, nums);
21+
22+
return res;
23+
}
24+
25+
26+
private int leftIndex(int target, int[] nums) {
27+
int left = 0, right = nums.length - 1;
28+
while (left <= right) {
29+
int mid = (right - left) / 2 + left;
30+
if (nums[mid] < target) {
31+
left = mid + 1;
32+
} else {
33+
right = mid - 1;
34+
}
35+
}
36+
if (left <= nums.length - 1 && nums[left] == target) {
37+
return left;
38+
}
39+
40+
return -1;
41+
}
42+
43+
private int rightIndex(int target, int[] nums) {
44+
int left = 0, right = nums.length - 1;
45+
while (left <= right) {
46+
int mid = (right - left) / 2 + left;
47+
if (nums[mid] <= target) {
48+
left = mid + 1;
49+
} else {
50+
right = mid - 1;
51+
}
52+
}
53+
if (right >= 0 && nums[right] == target) {
54+
return right;
55+
}
56+
57+
return -1;
58+
}
59+
60+
@Test
61+
public void testCase() {
62+
int[] nums = {5, 7, 7, 8, 8, 10};
63+
int[] res = searchRange(nums, 8);
64+
System.out.println(Arrays.toString(res));
65+
66+
}
67+
}

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

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package com.chen.algorithm.study.test56;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
/**
8+
* https://leetcode-cn.com/problems/merge-intervals/solution/merge-intervals-by-ikaruga/
9+
*
10+
* 对 vector<vector<int>> 排序，需要按照先比较区间开始，如果相同再比较区间结束，使用默认的排序规则即可
11+
* 使用双指针，左边指针指向当前区间的开始
12+
* 使用一个变量来记录连续的范围 t
13+
* 右指针开始往后寻找，如果后续的区间的开始值比 t 还小，说明重复了，可以归并到一起
14+
* 此时更新更大的结束值到 t
15+
* 直到区间断开，将 t 作为区间结束，存储到答案里
16+
* 然后移动左指针，跳过中间已经合并的区间
17+
*
18+
* @author : chen weijie
19+
* @Date: 2020-09-15 00:04
20+
*/
21+
public class Solution2 {
22+
23+
24+
public int[][] merge(int[][] intervals) {
25+
26+
List<int[]> inter = Arrays.asList(intervals);
27+
List<int[]> newInter = new ArrayList<>(inter);
28+
29+
newInter.sort((o1, o2) -> o1[0] - o2[0]);
30+
31+
List<int[]> res = new ArrayList<>();
32+
33+
for (int i = 0; i < newInter.size(); ) {
34+
int t = newInter.get(i)[1];
35+
int j = i + 1;
36+
37+
while (j < newInter.size() && newInter.get(j)[0] <= t) {
38+
t = Math.max(t, newInter.get(j)[1]);
39+
j++;
40+
}
41+
42+
res.add(new int[]{newInter.get(i)[0], t});
43+
i = j;
44+
}
45+
46+
int[][] ans = new int[res.size()][2];
47+
for (int i = 0; i < res.size(); i++) {
48+
ans[i][0] = res.get(i)[0];
49+
ans[i][1] = res.get(i)[1];
50+
}
51+
52+
return ans;
53+
54+
}
55+
}

0 commit comments

Comments
 (0)