Skip to content

Commit 00719e3

Browse files
Serena211Serena211
committed
may.20 valid parenthese, valid anagram, all valid permutations of parentheses
1 parent a946dd3 commit 00719e3

12 files changed

Lines changed: 229 additions & 6 deletions

‎bin/Class05_BFS_Graph/TreeNode.class‎

33 Bytes
Binary file not shown.

‎bin/Class24/AllValidPermutationsOfParentheses2.class‎

1.81 KB
Binary file not shown.

‎bin/Class24/LongestValidParentheses.class‎

1.13 KB
Binary file not shown.

‎bin/Class99_Mix/RecoverBinarySearchTree.class‎

412 Bytes
Binary file not shown.

‎bin/Class99_Mix/ValidAnagram.class‎

1.85 KB
Binary file not shown.

‎bin/Class99_Mix/ValidParentheses.class‎

1.59 KB
Binary file not shown.

‎src/Class05_BFS_Graph/TreeNode.java‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,11 @@
22

33
public class TreeNode {
44
public int val;
5+
public int key;
56
public TreeNode left;
67
public TreeNode right;
78
public TreeNode(int k) {
89
this.val = k;
10+
this.key = k;
911
}
1012
}

‎src/Class24/AllValidPermutationsOfParentheses2.java‎

Lines changed: 74 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
package Class24;
22

33
import java.util.ArrayList;
4+
import java.util.Deque;
5+
import java.util.LinkedList;
46
import java.util.List;
57

68
/*
@@ -15,13 +17,82 @@
1517
public class AllValidPermutationsOfParentheses2 {
1618
public List<String> validParentheses(int l, int m, int n) {
1719
List<String> rsl = new ArrayList<String>();
18-
20+
int[] left = new int[]{l,m,n};
21+
int[] right = new int[]{l,m,n};
22+
Deque<Character> stack = new LinkedList<Character>();
23+
char[] sol = new char[2 * (l + m + n)];
24+
helper(left, right, stack, rsl, sol, 0);
1925
return rsl;
2026
}
2127

22-
public static void main(String[] args) {
23-
// TODO Auto-generated method stub
28+
private void helper(int[] left, int[] right, Deque<Character> stack,
29+
List<String> rsl, char[] sol, int index) {
30+
if ( index == sol.length) {
31+
rsl.add(new String(sol));
32+
return;
33+
}
34+
if (left[0] > 0) {
35+
sol[index] = '(';
36+
left[0] -= 1;
37+
stack.offerFirst('(');
38+
helper(left, right, stack, rsl, sol, index + 1);
39+
stack.pollFirst();
40+
left[0] += 1;
41+
}
42+
if (right[0] > left[0]) {
43+
if (stack.peekFirst().equals('(')) {
44+
sol[index] = ')';
45+
right[0] -= 1;
46+
char temp = stack.pollFirst();
47+
helper(left, right, stack, rsl, sol, index + 1);
48+
stack.offerFirst(temp);
49+
right[0] += 1;
50+
}
51+
}
52+
53+
if (left[1] > 0) {
54+
sol[index] = '[';
55+
left[1] -= 1;
56+
stack.offerFirst('[');
57+
helper(left, right, stack, rsl, sol, index + 1);
58+
stack.pollFirst();
59+
left[1] += 1;
60+
}
61+
if (right[1] > left[1]) {
62+
if (stack.peekFirst().equals('[')) {
63+
sol[index] = ']';
64+
right[1] -= 1;
65+
char temp = stack.pollFirst();
66+
helper(left, right, stack, rsl, sol, index + 1);
67+
stack.offerFirst(temp);
68+
right[1] += 1;
69+
}
70+
}
2471

72+
if (left[2] > 0) {
73+
sol[index] = '{';
74+
left[2] -= 1;
75+
stack.offerFirst('{');
76+
helper(left, right, stack, rsl, sol, index + 1);
77+
stack.pollFirst();
78+
left[2] += 1;
79+
}
80+
if (right[2] > left[2]) {
81+
if (stack.peekFirst().equals('{')) {
82+
sol[index] = '}';
83+
right[2] -= 1;
84+
char temp = stack.pollFirst();
85+
helper(left, right, stack, rsl, sol, index + 1);
86+
stack.offerFirst(temp);
87+
right[2] += 1;
88+
}
89+
}
90+
91+
}
92+
93+
public static void main(String[] args) {
94+
AllValidPermutationsOfParentheses2 sol = new AllValidPermutationsOfParentheses2();
95+
System.out.println(sol.validParentheses(3, 2, 1));
2596
}
2697

2798
}

‎src/Class24/LongestValidParentheses.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package Class24;
2+
3+
/*
4+
* Given a string containing just the characters '(' and ')', find the length of the
5+
* longest valid (well-formed) parentheses substring.
6+
*
7+
* Example:
8+
* For "(()", the longest valid parentheses substring is "()", which has length = 2.
9+
* For ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
10+
*
11+
*/
12+
public class LongestValidParentheses {
13+
public int longestValidParentheses(String s) {
14+
if (s == null || s.length() < 2) {
15+
return 0;
16+
}
17+
int[] len = new int[s.length()];
18+
// base case:
19+
// len[1] = s.charAt(0) == '(' && s.charAt(1) == ')' ? 1 : 0;
20+
int left = 0;
21+
int right = 0;
22+
for (int i = 0; i < s.length(); i++) {
23+
if (s.charAt(i) == '(') {
24+
left++;
25+
} else if (left > right && s.charAt(i) == ')') {
26+
right++;
27+
} else
28+
len[i] = 0;
29+
}
30+
return right * 2;
31+
}
32+
33+
public static void main(String[] args) {
34+
LongestValidParentheses sol = new LongestValidParentheses();
35+
String input = new String("(()");
36+
System.out.println(sol.longestValidParentheses(input));
37+
}
38+
39+
}

‎src/Class99_Mix/RecoverBinarySearchTree.java‎

Lines changed: 24 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,16 +7,37 @@
77
* recover the binary search tree.
88
*/
99
public class RecoverBinarySearchTree {
10+
11+
public TreeNode switchElement1 = null;
12+
public TreeNode switchElement2 = null;
13+
public TreeNode prev = new TreeNode(Integer.MIN_VALUE);
14+
1015
public TreeNode recover(TreeNode root) {
1116
if (root == null) {
1217
return root;
1318
}
14-
helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
19+
helper(root);
20+
int temp = switchElement1.key;
21+
switchElement1.key = switchElement2.key;
22+
switchElement2.key = temp;
1523
return root;
1624
}
1725

18-
private void helper(TreeNode root, int minValue, int maxValue) {
19-
// TODO Auto-generated method stub
26+
private void helper(TreeNode root) {
27+
if (root == null) {
28+
return;
29+
}
30+
helper(root.left);
31+
if (switchElement1 == null && root.key <= prev.key) {
32+
switchElement1 = new TreeNode(root.key);
33+
prev.key = switchElement1.key;
34+
}
35+
if (switchElement1 != null && root.key <= prev.key) {
36+
switchElement2 = new TreeNode(root.key);
37+
prev.key = switchElement2.key;
38+
}
39+
helper(root.right);
40+
2041
}
2142

2243
public static void main(String[] args) {

0 commit comments

Comments
 (0)