Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit0716ac1

Browse files
committed
feat: add new solution.
1 parented49095 commit0716ac1

File tree

5 files changed

+177
-6
lines changed

5 files changed

+177
-6
lines changed
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
packagecom.yeahqing.medium._105;
2+
3+
/**
4+
* @FileName LeetCode105.java
5+
* @Desc java-leetcode created by YeahQing
6+
* @Author YeahQing
7+
* @Date 2022/10/26 18:04
8+
*/
9+
10+
publicclassLeetCode105 {
11+
publicstaticvoidmain(String[]args) {
12+
Solutions =newSolution();
13+
s.buildTree(newint[]{3,9,20,15,7},newint[]{9,3,15,20,7});
14+
}
15+
}

‎src/com/yeahqing/medium/_105/Solution.java

Lines changed: 1 addition & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -9,14 +9,9 @@
99
* @author YeahQing
1010
* @date 2022/10/26
1111
*/
12-
publicclassSolution {
12+
classSolution {
1313
Map<Integer,Integer>map;
1414

15-
publicstaticvoidmain(String[]args) {
16-
Solutions =newSolution();
17-
s.buildTree(newint[]{3,9,20,15,7},newint[]{9,3,15,20,7});
18-
}
19-
2015
/**
2116
* @param preorder 先序遍历序列
2217
* @param inorder 中序遍历序列
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
packagecom.yeahqing.medium._105;
2+
3+
importcom.yeahqing.structure.TreeNode;
4+
5+
importjava.util.Arrays;
6+
importjava.util.HashMap;
7+
importjava.util.Map;
8+
9+
/**
10+
* @FileName Solution1.java
11+
* @Desc leetcode-105. 从前序与中序遍历序列构造二叉树
12+
* @Author YeahQing
13+
* @Date 2022/10/26 16:24
14+
*/
15+
16+
classSolution1 {
17+
Map<Integer,Integer>map;
18+
int[]preArr,midArr;
19+
20+
publicstaticvoidmain(String[]args) {
21+
Solution1solution1 =newSolution1();
22+
solution1.buildTree(newint[]{3,9,20,15,7},newint[]{9,3,15,20,7});
23+
}
24+
25+
/**
26+
* 使用前序和中序遍历构造二叉树
27+
*
28+
* @param preorder 前序遍历节点值数组
29+
* @param inorder 中序遍历节点值数组
30+
* @return 根节点root
31+
*/
32+
publicTreeNodebuildTree(int[]preorder,int[]inorder) {
33+
intn =preorder.length;
34+
preArr =Arrays.copyOf(preorder,n);
35+
midArr =Arrays.copyOf(inorder,n);
36+
// 使用哈希表存储中序遍历中节点的下标, 方便找到根节点，区分左右子树
37+
map =newHashMap<>();
38+
for (inti =0;i <inorder.length;i++) {
39+
map.put(inorder[i],i);
40+
}
41+
returndfs(0,n -1,0,n -1);
42+
}
43+
44+
publicTreeNodedfs(intpLeft,intpRight,intmLeft,intmRight) {
45+
if (pLeft >pRight ||mLeft >mRight)returnnull;
46+
// 找到当前根节点在前序遍历和中序遍历中的位置
47+
introotIndex =map.get(preArr[pLeft]);
48+
TreeNoderoot =newTreeNode(midArr[rootIndex]);
49+
// 左子树的个数
50+
intleftTreeSize =rootIndex -mLeft;
51+
// 前序遍历中左子树的个数 = 根节点 + 左子树的个数
52+
root.left =dfs(pLeft +1,pLeft +leftTreeSize,mLeft,rootIndex -1);
53+
root.right =dfs(pLeft +leftTreeSize +1,pRight,rootIndex +1,mRight);
54+
returnroot;
55+
}
56+
57+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
packagecom.yeahqing.medium._105;
2+
3+
importcom.yeahqing.structure.TreeNode;
4+
5+
importjava.util.Deque;
6+
importjava.util.LinkedList;
7+
8+
/**
9+
* @FileName Solution2.java
10+
* @Desc leetcode-105. 从前序与中序遍历序列构造二叉树, 使用栈和指针解决
11+
* @Author YeahQing
12+
* @Date 2022/10/26 17:16
13+
*/
14+
15+
classSolution2 {
16+
Deque<TreeNode>stack;
17+
18+
publicstaticvoidmain(String[]args) {
19+
Solution2solution2 =newSolution2();
20+
solution2.buildTree(newint[]{3,9,20,15,7},newint[]{9,3,15,20,7});
21+
}
22+
23+
publicTreeNodebuildTree(int[]preorder,int[]inorder) {
24+
intn =preorder.length;
25+
intindex =0,i =0;
26+
stack =newLinkedList<>();
27+
TreeNoderoot =newTreeNode(preorder[i++]);
28+
stack.push(root);
29+
while (!stack.isEmpty() &&i <n) {
30+
TreeNodetopNode =stack.peek();
31+
TreeNodenewNode =newTreeNode(preorder[i++]);
32+
if (topNode.val !=inorder[index]) {
33+
topNode.left =newNode;
34+
}else {
35+
TreeNodetmp =stack.pop();
36+
index++;
37+
while (!stack.isEmpty() &&stack.peek().val ==inorder[index]) {
38+
tmp =stack.pop();
39+
index++;
40+
}
41+
tmp.right =newNode;
42+
}
43+
stack.push(newNode);
44+
}
45+
returnroot;
46+
}
47+
48+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packagecom.yeahqing.medium._1239;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.Arrays;
5+
importjava.util.List;
6+
7+
/**
8+
* @FileName LeetCode1239.java
9+
* @Desc java-leetcode created by YeahQing
10+
* @Author YeahQing
11+
* @Date 2022/10/27 14:14
12+
*/
13+
14+
publicclassLeetCode1239 {
15+
publicstaticvoidmain(String[]args) {
16+
Solutionsolution =newSolution();
17+
List<String>testCase =newArrayList<>(Arrays.asList("aa","bb"));
18+
System.out.println(solution.maxLength(testCase));
19+
}
20+
}
21+
22+
classSolution {
23+
intans =0;
24+
25+
publicintmaxLength(List<String>arr) {
26+
List<Integer>masks =newArrayList<Integer>();
27+
28+
for (Strings :arr) {
29+
Integermask =0;
30+
for (Characterc :s.toCharArray()) {
31+
intch =c -'a';
32+
if ((mask &1 <<ch) !=0) {
33+
mask =0;
34+
break;
35+
}
36+
mask =mask |1 <<ch;
37+
}
38+
if (mask >0) {
39+
masks.add(mask);
40+
}
41+
}
42+
dfs(masks,0,0);
43+
returnans;
44+
}
45+
46+
publicvoiddfs(List<Integer>masks,intpos,intmask) {
47+
if (pos ==masks.size()) {
48+
ans =Math.max(ans,Integer.bitCount(mask));
49+
return;
50+
}
51+
if ((mask &masks.get(pos)) ==0) {
52+
dfs(masks,pos +1,mask |masks.get(pos));
53+
}
54+
dfs(masks,pos +1,mask);
55+
}
56+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp