8000 20200903 · BoscoSuen/leetcode@ea21740 · GitHub
[go: up one dir, main page]
Skip to content

Commit ea21740

Browse files
BoscoSuenBoscoSuen
committed
20200903
1 parent 2c07566 commit ea21740

File tree

2 files changed

+114
-0
lines changed

2 files changed

+114
-0
lines changed

‎Java/459.repeated-substring-pattern.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
* @lc app=leetcode id=459 lang=java
3+
*
4+
* [459] Repeated Substring Pattern
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
/*
10+
找到能整除的substring长度，复制substring然后和s做比较
11+
time: O(n^2)
12+
sapce: O(n)
13+
*/
14+
public boolean repeatedSubstringPattern(String s) {
15+
int n = s.length();
16+
for (int i = n / 2; i > 0; --i) {
17+
if (n % i != 0) continue;
18+
int num = n / i;
19+
String str = s.substring(0, i);
20+
StringBuilder sb = new StringBuilder();
21+
while (num-- > 0) {
22+
sb.append(str);
23+
}
24+
if (sb.toString().equals(s)) return true;
25+
}
26+
return false;
27+
}
28+
}
29+
// @lc code=end
30+

‎Java/95.unique-binary-search-trees-ii.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
/*
2+
* @lc app=leetcode id=95 lang=java
3+
*
4+
* [95] Unique Binary Search Trees II
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
/**
24+
* Definition for a binary tree node.
25+
* public class TreeNode {
26+
* int val;
27+
* TreeNode left;
28+
* TreeNode right;
29+
* TreeNode() {}
30+
* TreeNode(int val) { this.val = val; }
31+
* TreeNode(int val, TreeNode left, TreeNode right) {
32+
* this.val = val;
33+
* this.left = left;
34+
* this.right = right;
35+
* }
36+
* }
37+
*/
38+
class Solution {
39+
/*
40+
分左右区间进行recursion
41+
time: As we have to 8000 generate all the possible trees and the total number of possible
42+
trees possible is a catalan number which is (4^n)/((n^(3/2))*sqrt(pi)),
43+
which makes the time of this algorithm to be O(4^n).
44+
*/
45+
public List<TreeNode> generateTrees(int n) {
46+
return helper(1, n);
47+
}
48+
49+
private List<TreeNode> helper(int low, int high) {
50+
List<TreeNode> res = new ArrayList<>();
51+
if (low > high) return res;
52+
for (int i = low; i <= high; ++i) {
53+
List<TreeNode> left = helper(low, i - 1);
54+
List<TreeNode> right = helper(i + 1, high);
55+
if (left.size() == 0 && right.size() == 0) {
56+
res.add(new TreeNode(i));
57+
} else if (left.size() == 0) {
58+
for (TreeNode r : right) {
59+
TreeNode root = new TreeNode(i);
60+
root.right = r;
61+
res.add(root);
62+
}
63+
} else if (right.size() == 0) {
64+
for (TreeNode l : left) {
65+
TreeNode root = new TreeNode(i);
66+
root.left = l;
67+
res.add(root);
68+
}
69+
} else {
70+
for (TreeNode l : left) {
71+
for (TreeNode r : right) {
72+
TreeNode root = new TreeNode(i);
73+
root.left = l;
74+
root.right = r;
75+
res.add(root);
76+
}
77+
}
78+
}
79+
}
80+
return res;
81+
}
82+
}
83+
// @lc code=end
84+

0 commit comments

Comments
 (0)
0