Skip to content

Commit b153b63

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#525 from karringqing/master
416-Week 02
2 parents 38cb586 + 32c5b44 commit b153b63

18 files changed

+862
-1
lines changed

‎Week 02/id_416/LeetCode_105_416.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.leetcode.week02;
2+
3+
import com.leetcode.week02.util.TreeNode;
4+
5+
import java.util.HashMap;
6+
7+
public class LeetCode_105_416 {
8+
// start from first preorder element
9+
int pre_idx = 0;
10+
int[] preorder;
11+
int[] inorder;
12+
HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();
13+
14+
public TreeNode helper(int in_left, int in_right) {
15+
// if there is no elements to construct subtrees
16+
if (in_left == in_right)
17+
return null;
18+
19+
// pick up pre_idx element as a root
20+
int root_val = preorder[pre_idx];
21+
TreeNode root = new TreeNode(root_val);
22+
23+
// root splits inorder list
24+
// into left and right subtrees
25+
int index = idx_map.get(root_val);
26+
27+
// recursion
28+
pre_idx++;
29+
// build left subtree
30+
root.left = helper(in_left, index);
31+
// build right subtree
32+
root.right = helper(index + 1, in_right);
33+
return root;
34+
}
35+
36+
public TreeNode buildTree(int[] preorder, int[] inorder) {
37+
this.preorder = preorder;
38+
this.inorder = inorder;
39+
40+
// build a hashmap value -> its index
41+
int idx = 0;
42+
for (Integer val : inorder)
43+
idx_map.put(val, idx++);
44+
return helper(0, inorder.length);
45+
}
46+
}

‎Week 02/id_416/LeetCode_144_416.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.leetcode.week02;
2+
3+
import com.leetcode.week02.util.TreeNode;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
/**
9+
* 给定一个二叉树，返回它的 前序 遍历。
10+
*
11+
*  示例:
12+
*
13+
* 输入: [1,null,2,3]
14+
* 1
15+
* \
16+
* 2
17+
* /
18+
* 3
19+
*
20+
* 输出: [1,2,3]
21+
*
22+
* 来源：力扣（LeetCode）
23+
* 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
24+
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
25+
*/
26+
public class LeetCode_144_416 {
27+
public List<Integer> preorderTraversal(TreeNode root) {
28+
List<Integer> list = new ArrayList<Integer>();
29+
_circleTreeNode(root,list);
30+
return list;
31+
}
32+
33+
private void _circleTreeNode(TreeNode root, List<Integer> list) {
34+
if(null != root) {
35+
list.add(root.val);
36+
37+
if(null != root.left) {
38+
_circleTreeNode(root.left,list);
39+
}
40+
41+
if(null != root.right) {
42+
_circleTreeNode(root.right,list);
43+
}
44+
45+
}
46+
}
47+
}

‎Week 02/id_416/LeetCode_1_416.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package com.leetcode.week02;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
8+
*
9+
* 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
10+
*
11+
* 示例:
12+
*
13+
* 给定 nums = [2, 7, 11, 15], target = 9
14+
*
15+
* 因为 nums[0] + nums[1] = 2 + 7 = 9
16+
* 所以返回 [0, 1]
17+
*
18+
* 来源：力扣（LeetCode）
19+
* 链接：https://leetcode-cn.com/problems/two-sum
20+
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
21+
*/
22+
public class LeetCode_1_416 {
23+
//1.暴力求解法
24+
public int[] twoSum(int[] nums, int target) {
25+
for (int i = 0; i < nums.length - 1; i++) {
26+
for (int j = i + 1; j < nums.length; j++) {
27+
if(nums[i] + nums[j] == target) {
28+
return new int[]{i,j};
29+
}
30+
}
31+
}
32+
return null;
33+
}
34+
35+
//2.Hash解法,空间换时间，多了一个HashMap，但是时间复杂度就变成了O (n) 了。
36+
public int[] twoSum1(int[] nums, int target) {
37+
Map<Integer,Integer> result = new HashMap<Integer,Integer>();
38+
for (int i = 0; i < nums.length; i++) {
39+
int a = target - nums[i];//相减的计算的结果
40+
//如果相减的结果，在HashMap中存在，那么就直接返回
41+
if(result.containsKey(a)) {
42+
return new int[]{i,result.get(a)};
43+
}
44+
result.put(nums[i],i);
45+
}
46+
return null;
47+
}
48+
}

‎Week 02/id_416/LeetCode_236_416.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package com.leetcode.week02;
2+
3+
import com.leetcode.week02.util.TreeNode;
4+
/**
5+
* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
6+
* 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
7+
* 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
8+
* 示例 1:
9+
* 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
10+
* 输出: 3
11+
* 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
12+
* 示例 2:
13+
* 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
14+
* 输出: 5
15+
* 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
16+
* 说明:
17+
* 所有节点的值都是唯一的。
18+
* p、q 为不同节点且均存在于给定的二叉树中。
19+
* 来源：力扣（LeetCode）
20+
* 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
21+
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
22+
*/
23+
public class LeetCode_236_416 {
24+
private TreeNode treeNode;
25+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
26+
circleTreeNode(root,p,q);
27+
return treeNode;
28+
}
29+
public boolean circleTreeNode(TreeNode currentNode, TreeNode p, TreeNode q) {
30+
if (null == currentNode) {
31+
return false;
32+
}
33+
//左边是否有当前传入的p或者q
34+
int left = circleTreeNode(currentNode.left, p, q) ? 1 : 0;
35+
//右边是否有当前传入的p或者q
36+
int right = circleTreeNode(currentNode.right, p, q) ? 1 : 0;
37+
int mid = ((currentNode == p) || (currentNode == q)) ? 1 : 0;
38+
if (left + right + mid >= 2) {//说明了当前节点下面，可以同时查找到左节点和右节点是给定的参数值
39+
this.treeNode = currentNode;
40+
}
41+
return left + right + mid > 0;
42+
}
43+
}

‎Week 02/id_416/LeetCode_242_416.java‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package com.leetcode.week02;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
7+
*
8+
* 示例 1:
9+
*
10+
* 输入: s = "anagram", t = "nagaram"
11+
* 输出: true
12+
* 示例 2:
13+
*
14+
* 输入: s = "rat", t = "car"
15+
* 输出: false
16+
* 说明:
17+
* 你可以假设字符串只包含小写字母。
18+
*
19+
* 进阶:
20+
* 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
21+
*
22+
* 来源：力扣（LeetCode）
23+
* 链接：https://leetcode-cn.com/problems/valid-anagram
24+
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
25+
*/
26+
public class LeetCode_242_416 {
27+
//1.string to char[] then sort char[] last Arrays.equals()
28+
//时间复杂度为O (nlogn)
29+
public boolean isAnagram0(String s, String t) {
30+
if(s.length() != t.length()) {
31+
return false;
32+
}
33+
char[] a = s.toCharArray();
34+
char[] b = t.toCharArray();
35+
Arrays.sort(a);
36+
Arrays.sort(b);
37+
return Arrays.equals(a,b);
38+
}
39+
//2.hash table , 26 int[] table
40+
//26个字母每个字母减去 a，就是对应0~25个下标，让当前字符串，让字符在数组中遍历，一个相加，一个相减
41+
//最后肯定都为0
42+
public boolean isAnagram1(String s, String t) {
43+
if(s.length() != t.length()) {
44+
return false;
45+
}
46+
int[] counter = new int[26];
47+
for(int i=0;i<s.length();i++) {
48+
counter[s.charAt(i) - 'a']++;
49+
counter[t.charAt(i) - 'a']--;
50+
}
51+
for (int i = 0; i < counter.length; i++) {
52+
int i1 = counter[i];
53+
if(i1 != 0) {
54+
return false;
55+
}
56+
}
57+
return true;
58+
}
59+
//3.hash table ，先将一个字符串++ ，然后在将另外一个字符串--，因为字符串长度是相等的，
60+
// 只要有一个小于零，那么就说明
61+
public boolean isAnagram2(String s, String t){
62+
if(s.length() != t.length()) {
63+
return false;
64+
}
65+
66+
int[] counter = new int[26];
67+
68+
for(int i=0;i<s.length();i++) {
69+
counter[s.charAt(i) - 'a']++;
70+
}
71+
for(int i = 0;i<t.length();i++) {
72+
counter[t.charAt(i) - 'a']--;
73+
if(counter[t.charAt(i) - 'a'] < 0) {
74+
return false;
75+
}
76+
}
77+
return true;
78+
}
79+
//3.简化代码的写法,根据第三种办法简化了代码
80+
public boolean isAnagram22(String s, String t){
81+
if(s.length() != t.length()) return false;
82+
int[] counter = new int[26];
83+
for(int i=0;i<s.length();i++) counter[s.charAt(i) - 'a']++;
84+
for(int i = 0;i<t.length();i++) if(--counter[t.charAt(i) - 'a'] < 0) return false;
85+
return true;
86+
}
87+
88+
89+
}

‎Week 02/id_416/LeetCode_429_416.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package com.leetcode.week02;
2+
3+
import com.leetcode.week02.util.Node;
4+
5+
import java.util.*;
6+
7+
public class LeetCode_429_416 {
8+
//队列
9+
public List<List<Integer>> levelOrder(Node root) {
10+
List<List<Integer>> ret = new LinkedList<List<Integer>>();
11+
if(null == root) return ret;
12+
Queue<Node> queue = new LinkedList<Node>();
13+
queue.offer(root);//压入队列
14+
while(!queue.isEmpty()) {
15+
List<Integer> list = new LinkedList<Integer>();
16+
int len = queue.size();
17+
for(int i = 0; i<len ; i++) {
18+
Node curr = queue.poll();//弹出队列
19+
list.add(curr.val);//当前层所有值存起来
20+
for(Node chi : curr.children) queue.offer(chi);//压入队列中
21+
}
22+
ret.add(list);
23+
}
24+
return ret;
25+
}
26+
27+
//递归
28+
public List<List<Integer>> levelOrder1(Node root) {
29+
List<List<Integer>> list = new ArrayList<List<Integer>>();
30+
list.add(Arrays.asList(root.val));
31+
circleLevelNode(root.children,list);
32+
return list;
33+
}
34+
public void circleLevelNode(List<Node> children,List<List<Integer>> list) {
35+
if(null != children && children.size() > 0 ) {
36+
List<Node> childrenSecond = new ArrayList<Node>();
37+
List<Integer> rList = new ArrayList<Integer>();
38+
for(Node c : children) {//所有子节点存入
39+
rList.add(c.val);
40+
if(null != c.children && c.children.size() > 0 ) {
41+
childrenSecond.addAll(c.children);//所有子节点的子节点存入
42+
}
43+
}
44+
list.add(rList);
45+
circleLevelNode(childrenSecond,list);
46+
}
47+
}
48+
}

‎Week 02/id_416/LeetCode_49_416.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package com.leetcode.week02;
2+
3+
import java.util.*;
4+
5+
/**
6+
* 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
7+
*
8+
* 示例:
9+
*
10+
* 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
11+
* 输出:
12+
* [
13+
* ["ate","eat","tea"],
14+
* ["nat","tan"],
15+
* ["bat"]
16+
* ]
17+
* 说明：
18+
*
19+
* 所有输入均为小写字母。
20+
* 不考虑答案输出的顺序。
21+
*
22+
* 来源：力扣（LeetCode）
23+
* 链接：https://leetcode-cn.com/problems/group-anagrams
24+
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
25+
*/
26+
public class LeetCode_49_416 {
27+
public List<List<String>> groupAnagrams(String[] strs) {
28+
if(null == strs && strs.length == 0) {//空数组
29+
return null;
30+
}
31+
Map<String,List<String>> resultMap = new HashMap<String,List<String>>();
32+
for (int i = 0; i < strs.length; i++) {
33+
String str = strs[i];
34+
char[] charStr = str.toCharArray();
35+
Arrays.sort(charStr);
36+
String sortedStr = String.valueOf(charStr);
37+
if(!resultMap.containsKey(sortedStr)) {
38+
resultMap.put(sortedStr,new ArrayList<String>());
39+
}
40+
resultMap.get(sortedStr).add(str);//相同字符串的Hash值是一样的，所以相同的Hash值会散列到同一个key上面
41+
}
42+
return new ArrayList(resultMap.values()) ;
43+
}
44+
//这种方法其实和第一种方法类似，主要是寻找相同key，当做hashMap的键值，然后相同key对应的value是List
45+
//然后进行add，这里的相同key是通过计数器counter，字母首先是有顺序的，把按照顺序出现的次数都计算出来，那么就是一样的字符串，当做了key
46+
public List<List<String>> groupAnagrams1(String[] strs) {
47+
if(null == strs || strs.length == 0) {
48+
return null;
49+
}
50+
Map<String,List<String>> map = new HashMap<String,List<String>>();
51+
for(int i = 0;i< strs.length;i++) {
52+
int[] counter =null;
53+
counter = new int[26];
54+
for(int k = 0;k<strs[i].length();k++){
55+
counter[strs[i].charAt(k) - 'a']++;
56+
}
57+
StringBuffer sb = new StringBuffer();
58+
for(int j=0;j<26;j++){
59+
sb.append("#");
60+
sb.append(counter[j]);
61+
}
62+
String key = sb.toString();
63+
if(!map.containsKey(key)){
64+
map.put(key,new ArrayList());
65+
}
66+
map.get(key).add(strs[i]);
67+
}
68+
return new ArrayList(map.values());
69+
}
70+
}

0 commit comments

Comments
 (0)