Skip to content

Commit 7486c24

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#369 from mrglint/master
006-Week 02
2 parents 8c026d5 + 1609234 commit 7486c24

13 files changed

+953
-2
lines changed

‎Week 02/id_006/LeetCode_104_006.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.mrglint.leetcode.week02.solution104;
2+
3+
import com.mrglint.leetcode.TreeNode;
4+
5+
import java.util.Objects;
6+
7+
/**
8+
* @author luhuancheng
9+
* @since 2019-10-27 13:35
10+
*/
11+
public class Solution {
12+
public int maxDepth(TreeNode root) {
13+
if (Objects.isNull(root)) {
14+
return 0;
15+
}
16+
return Math.max(maxDepth(root.left, 1), maxDepth(root.right, 1));
17+
}
18+
19+
private int maxDepth(TreeNode node, int level) {
20+
if (Objects.isNull(node)) {
21+
return level;
22+
}
23+
return Math.max(maxDepth(node.left, level + 1), maxDepth(node.right, level + 1));
24+
}
25+
}
26+

‎Week 02/id_006/LeetCode_111_006.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.mrglint.leetcode.week02.solution111;
2+
3+
import com.mrglint.leetcode.TreeNode;
4+
5+
import java.util.Objects;
6+
7+
/**
8+
* @author luhuancheng
9+
* @since 2019-10-27 13:45
10+
*/
11+
public class Solution {
12+
public int minDepth(TreeNode root) {
13+
if (root == null) {
14+
return 0;
15+
}
16+
return minDepth(root, 1);
17+
}
18+
19+
private int minDepth(TreeNode node, int level) {
20+
if (Objects.isNull(node)) {
21+
return level;
22+
}
23+
if (Objects.isNull(node.left)) {
24+
return minDepth(node.right) + level;
25+
}
26+
if (Objects.isNull(node.right)) {
27+
return minDepth(node.left) + level;
28+
}
29+
return Math.min(minDepth(node.left, level + 1), minDepth(node.right, level + 1));
30+
}
31+
}
32+

‎Week 02/id_006/LeetCode_144_006.java‎

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
package com.mrglint.leetcode.week02.solution144;
2+
3+
import com.mrglint.leetcode.TreeNode;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
import java.util.Objects;
8+
import java.util.Stack;
9+
10+
/**
11+
* @author luhuancheng
12+
* @since 2019-10-26 07:07
13+
*/
14+
public class Solution {
15+
16+
/**
17+
* 递归
18+
* @param root
19+
* @return
20+
*/
21+
public List<Integer> preorderTraversal1(TreeNode root) {
22+
List<Integer> result = new ArrayList<>();
23+
preorderTraversal(root, result);
24+
return result;
25+
}
26+
private void preorderTraversal(TreeNode node, List<Integer> result) {
27+
if (Objects.isNull(node)) {
28+
return;
29+
}
30+
result.add(node.val);
31+
preorderTraversal(node.left, result);
32+
preorderTraversal(node.right, result);
33+
}
34+
35+
/**
36+
* 栈写法一
37+
* @param root
38+
* @return
39+
*/
40+
public List<Integer> preorderTraversal2(TreeNode root) {
41+
List<Integer> result = new ArrayList<>();
42+
Stack<TreeNode> stack = new Stack<>();
43+
44+
TreeNode currentNode = root;
45+
while (currentNode != null || !stack.isEmpty()) {
46+
while (currentNode != null) {
47+
stack.push(currentNode);
48+
result.add(currentNode.val);
49+
currentNode = currentNode.left;
50+
}
51+
TreeNode stackTop = stack.pop();
52+
currentNode = stackTop.right;
53+
}
54+
return result;
55+
}
56+
57+
/**
58+
* 栈写法二
59+
* @param root
60+
* @return
61+
*/
62+
public List<Integer> preorderTraversal3(TreeNode root) {
63+
if (Objects.isNull(root)) {
64+
return new ArrayList<>();
65+
}
66+
List<Integer> result = new ArrayList<>();
67+
Stack<TreeNode> stack = new Stack<>();
68+
69+
stack.push(root);
70+
while (!stack.isEmpty()) {
71+
TreeNode stackTop = stack.pop();
72+
result.add(stackTop.val);
73+
if (Objects.nonNull(stackTop.right)) {
74+
stack.push(stackTop.right);
75+
}
76+
77+
if (Objects.nonNull(stackTop.left)) {
78+
stack.push(stackTop.left);
79+
}
80+
}
81+
return result;
82+
}
83+
84+
/**
85+
* 栈写法三：简化判空代码
86+
* @param root
87+
* @return
88+
*/
89+
public List<Integer> preorderTraversal(TreeNode root) {
90+
List<Integer> result = new ArrayList<>();
91+
Stack<TreeNode> stack = new Stack<>();
92+
stack.push(root);
93+
94+
while (!stack.isEmpty()) {
95+
TreeNode pop = stack.pop();
96+
if (Objects.nonNull(pop)) {
97+
result.add(pop.val);
98+
stack.push(pop.right);
99+
stack.push(pop.left);
100+
}
101+
}
102+
return result;
103+
}
104+
}
105+

‎Week 02/id_006/LeetCode_1_006.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.mrglint.leetcode.week02.solution1;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @author luhuancheng
8+
* @since 2019/9/5 9:33 下午
9+
*/
10+
public class Solution {
11+
12+
public int[] twoSum(int[] nums, int target) {
13+
Map<Integer, Integer> m = new HashMap<>();
14+
for (int i = 0; i < nums.length; i++) {
15+
int anotherNumber = target - nums[i];
16+
if (m.containsKey(anotherNumber)) {
17+
// 先返回前一个数的索引
18+
return new int[]{m.get(anotherNumber), i};
19+
} else {
20+
m.put(nums[i], i);
21+
}
22+
}
23+
throw new IllegalArgumentException("no such result");
24+
}
25+
}
26+

‎Week 02/id_006/LeetCode_226_006.java‎

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package com.mrglint.leetcode.week02.solution226;
2+
3+
import com.mrglint.leetcode.TreeNode;
4+
5+
import java.util.LinkedList;
6+
import java.util.Objects;
7+
import java.util.Queue;
8+
import java.util.Stack;
9+
10+
/**
11+
* @author luhuancheng
12+
* @since 2019-10-27 10:16
13+
*/
14+
public class Solution {
15+
16+
/**
17+
* 递归方式
18+
* @param root
19+
* @return
20+
*/
21+
public TreeNode invertTree1(TreeNode root) {
22+
if (root == null) {
23+
return null;
24+
}
25+
// 翻转左子树后，返回左子树
26+
TreeNode left = invertTree1(root.left);
27+
// 翻转右子树后，返回右子树
28+
TreeNode right = invertTree1(root.right);
29+
// 将翻转后的子树，挂到根节点
30+
root.left = right;
31+
root.right = left;
32+
return root;
33+
}
34+
35+
/**
36+
* 迭代法，跟利用队列进行层序遍历的方式雷同。
37+
* @param root
38+
* @return
39+
*/
40+
public TreeNode invertTree2(TreeNode root) {
41+
Queue<TreeNode> queue = new LinkedList<>();
42+
queue.offer(root);
43+
44+
while (!queue.isEmpty()) {
45+
TreeNode queueHead = queue.poll();
46+
if (Objects.nonNull(queueHead)) {
47+
TreeNode left = queueHead.left;
48+
queueHead.left = queueHead.right;
49+
queueHead.right = left;
50+
if (Objects.nonNull(queueHead.left)) {
51+
queue.offer(queueHead.left);
52+
}
53+
if (Objects.nonNull(queueHead.right)) {
54+
queue.offer(queueHead.right);
55+
}
56+
}
57+
}
58+
return root;
59+
}
60+
61+
/**
62+
* 使用栈
63+
* @param root
64+
* @return
65+
*/
66+
public TreeNode invertTree(TreeNode root) {
67+
if (Objects.isNull(root)) {
68+
return null;
69+
}
70+
71+
Stack<TreeNode> stack = new Stack<>();
72+
stack.push(root);
73+
74+
while (!stack.isEmpty()) {
75+
TreeNode top = stack.pop();
76+
TreeNode temp = top.left;
77+
top.left = top.right;
78+
top.right = temp;
79+
80+
if (Objects.nonNull(top.left)) {
81+
stack.push(top.left);
82+
}
83+
if (Objects.nonNull(top.right)) {
84+
stack.push(top.right);
85+
}
86+
}
87+
return root;
88+
}
89+
90+
}
91+

‎Week 02/id_006/LeetCode_242_006.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.mrglint.leetcode.week02.solution242;
2+
3+
/**
4+
* @author luhuancheng
5+
* @since 2019-10-25 08:18
6+
*/
7+
public class Solution {
8+
9+
public boolean isAnagram(String s, String t) {
10+
if (s.length() != t.length()) {
11+
return false;
12+
}
13+
int[] counter = new int[26];
14+
15+
for (int i = 0; i < s.length(); i++) {
16+
counter[s.charAt(i) - 'a']++;
17+
counter[t.charAt(i) - 'a']--;
18+
}
19+
20+
for (int c : counter) {
21+
if (c != 0) {
22+
return false;
23+
}
24+
}
25+
return true;
26+
}
27+
}
28+

‎Week 02/id_006/LeetCode_429_006.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package com.mrglint.leetcode.week02.solution429;
2+
3+
import com.mrglint.leetcode.Node;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
import java.util.Objects;
8+
import java.util.Queue;
9+
import java.util.concurrent.LinkedBlockingQueue;
10+
11+
/**
12+
* @author luhuancheng
13+
* @since 2019-10-26 21:07
14+
*/
15+
public class Solution {
16+
17+
/**
18+
* 使用队列迭代
19+
* @param root
20+
* @return
21+
*/
22+
public List<List<Integer>> levelOrder1(Node root) {
23+
List<List<Integer>> result = new ArrayList<>();
24+
if (Objects.isNull(root)) {
25+
return result;
26+
}
27+
Queue<Node> queue = new LinkedBlockingQueue<>();
28+
queue.offer(root);
29+
while (!queue.isEmpty()) {
30+
List<Integer> subResult = new ArrayList<>();
31+
int levelCount = queue.size();
32+
while (levelCount-- > 0) {
33+
Node queueHead = queue.poll();
34+
if (Objects.nonNull(queueHead)) {
35+
subResult.add(queueHead.val);
36+
if (Objects.nonNull(queueHead.children)) {
37+
for (Node e : queueHead.children) {
38+
queue.offer(e);
39+
}
40+
}
41+
}
42+
}
43+
result.add(subResult);
44+
}
45+
return result;
46+
}
47+
48+
/**
49+
* 使用递归
50+
* @param root
51+
* @return
52+
*/
53+
public List<List<Integer>> levelOrder(Node root) {
54+
List<List<Integer>> result = new ArrayList<>();
55+
levelOrder(root, 0, result);
56+
return result;
57+
}
58+
private void levelOrder(Node node, int depth, List<List<Integer>> result) {
59+
if (Objects.isNull(node)) {
60+
return;
61+
}
62+
// 为每一层建立结果集
63+
if (depth + 1 > result.size()) {
64+
result.add(depth, new ArrayList<>());
65+
}
66+
// 将当前层的放入当前层的结果集中
67+
result.get(depth).add(node.val);
68+
// 递归处理下一层
69+
for (Node item : node.children) {
70+
if (Objects.nonNull(item)) {
71+
levelOrder(item, depth + 1, result);
72+
}
73+
}
74+
}
75+
76+
}
77+

0 commit comments

Comments
 (0)