Skip to content

Commit a77b6df

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#690 from yuqiu-pp/master
Week04_006
2 parents 3ebc1c0 + d7db0ad commit a77b6df

5 files changed

Lines changed: 360 additions & 0 deletions

File tree

‎Week_04/id_6/LeetCode_241_6.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
2+
3+
// LeetCode 241
4+
5+
6+
// [ 1. 分治 ]
7+
8+
// 已运算符为界， 分为left和right，递归的计算
9+
public List<Integer> diffWaysToCompute(String input) {
10+
List<Integer> rst = new ArrayList<Integer>();
11+
Stack<Integer> stack = new Stack<>();
12+
13+
int i = 0;
14+
int val = 0;
15+
for (i = 0; i < input.length(); i++) {
16+
List<Integer> left = new ArrayList<Integer>();
17+
List<Integer> right = new ArrayList<Integer>();
18+
char c = input.charAt(i);
19+
if (c=='+' || c=='-' || c=='*'){
20+
left = diffWaysToCompute(input.substring(0, i));
21+
right = diffWaysToCompute(input.substring(i+1, input.length()));
22+
23+
// 返回的两个集合再根据运算符合并
24+
for (int j = 0; j < left.size(); j++) {
25+
for (int k = 0; k < right.size(); k++) {
26+
if (c == '+'){
27+
val = left.get(j) + right.get(k);
28+
}else if (c == '-'){
29+
val = left.get(j) - right.get(k);
30+
}else {
31+
val = left.get(j) * right.get(k);
32+
}
33+
rst.add(val);
34+
}
35+
}
36+
}
37+
}
38+
// 纯数字时
39+
if (rst.size() == 0){
40+
rst.add(Integer.valueOf(input));
41+
}
42+
return rst;
43+
}

‎Week_04/id_6/LeetCode_455_6.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
2+
3+
// LeetCode 455
4+
5+
6+
// [ 1. 贪心算法 ]
7+
8+
9+
// 遍历每个孩子，依次选出适合他的最小饼干
10+
public int findContentChildren(int[] g, int[] s) {
11+
Arrays.sort(g);
12+
Arrays.sort(s);
13+
14+
int num = 0;
15+
int curr = 0;
16+
for (int i = 0; i < g.length; i++) {
17+
for (int j = curr; j < s.length; j++) {
18+
curr++;
19+
if (g[i] <= s[j]){
20+
num ++;
21+
break;
22+
}
23+
24+
}
25+
if (curr > s.length){
26+
break;
27+
}
28+
}
29+
30+
return num;
31+
}

‎Week_04/id_6/LeetCode_720_6.java‎

Lines changed: 161 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,161 @@
1+
2+
3+
// LeetCode 104
4+
5+
6+
// [ 2. Trie树 ]
7+
8+
// 从最短的字符串开始建树，后面下一个，如果减1能找到，插入并记录为rst
9+
public String longestWord(String[] words) {
10+
Set<Integer> set = new TreeSet<>();
11+
HashMap<Integer, List<String>> map = new HashMap<>();
12+
TrieNode p = root;
13+
14+
for (int i = 0; i < words.length; i++) {
15+
int len = words[i].length();
16+
set.add(len);
17+
List<String> list = null;
18+
if (map.containsKey(len)){
19+
list = map.get(len);
20+
}else {
21+
list = new ArrayList<>();
22+
}
23+
list.add(words[i]);
24+
map.put(len, list);
25+
}
26+
27+
// 去重，排序
28+
int[] wordsLen = new int[set.size()];
29+
int k = 0;
30+
for (Integer n : set) {
31+
wordsLen[k++] = n;
32+
}
33+
Arrays.sort(wordsLen);
34+
String rst = "";
35+
// 按word长度递增顺序，开始建trie树
36+
// 先用word去掉尾字符在trie树中查询，找到rst记录，并插入树
37+
for (int i = 0; i < wordsLen.length; i++) {
38+
int len = wordsLen[i];
39+
List<String> list = map.get(len);
40+
for (String word : list){
41+
char[] text = word.toCharArray();
42+
char[] txt = Arrays.copyOf(text, text.length-1);
43+
if (text.length > 1){
44+
if (find(txt)){
45+
insert(text);
46+
if (rst.length() == word.length()){
47+
if (rst.compareTo(word) > 0){
48+
rst = word;
49+
}
50+
}else {
51+
rst = word;
52+
}
53+
}
54+
}else {
55+
if (rst.length() == 0){
56+
rst = word;
57+
}else if (rst.compareTo(word) > 0){
58+
rst = word;
59+
}
60+
insert(text);
61+
}
62+
}
63+
}
64+
65+
return rst;
66+
}
67+
68+
class TrieNode {
69+
70+
public char data;
71+
public TrieNode[] children = new TrieNode[26];
72+
public boolean isEndingChar = false;
73+
public TrieNode(char data){
74+
this.data = data;
75+
}
76+
}
77+
78+
// root
79+
TrieNode root = new TrieNode('\\');
80+
81+
// 插入一个字符
82+
public void insert(char[] text){
83+
TrieNode p = root;
84+
85+
int len = text.length;
86+
for (int i = 0; i < len; i++) {
87+
// 字符插入位置索引
88+
int index = text[i] - 'a';
89+
// 根据索引插入children中。如果已经存在则不处理
90+
if (p.children[index] == null){
91+
p.children[index] = new TrieNode(text[i]);
92+
}
93+
// 到下一层遍历
94+
p = p.children[index];
95+
}
96+
p.isEndingChar = true;
97+
}
98+
99+
100+
// 查找一个字符串
101+
public boolean find(char[] pattern){
102+
TrieNode p = root;
103+
104+
for (int i = 0; i < pattern.length; i++) {
105+
int index = pattern[i] - 'a';
106+
if (p.children[index] == null){
107+
return false;
108+
}
109+
// 继续向下一层查询
110+
p = p.children[index];
111+
}
112+
if (p.isEndingChar == false){
113+
return true;
114+
}
115+
116+
return true;
117+
}
118+
119+
120+
121+
122+
123+
// [ 1. 哈希表 ]
124+
125+
126+
// 通过单词长度递减，然后在words中查询，如果能找到，符合题目要求
127+
public String longestWord1(String[] words) {
128+
int[] wordsLen = new int[words.length];
129+
HashMap<String, Integer> map = new HashMap<>();
130+
TrieNode p = root;
131+
132+
for (int i = 0; i < words.length; i++) {
133+
int len = words[i].length();
134+
wordsLen[i] = len;
135+
if (!map.containsKey(words[i])){
136+
map.put(words[i], 1);
137+
}
138+
}
139+
140+
String rst = "";
141+
for (int i = 0; i < words.length; i++) {
142+
String wd = words[i];
143+
int len = wd.length();
144+
int j = 0;
145+
for (j = 1; j < len; j++) {
146+
wd = wd.substring(0, len - j);
147+
// 子串在words中没有
148+
if (!map.containsKey(wd)){
149+
break;
150+
}
151+
}
152+
if (j == len){
153+
if (rst.length() == 0 || rst.length() < len){
154+
rst = words[i];
155+
}else if (rst.length() == len && rst.compareTo(words[i]) > 0){
156+
rst = words[i];
157+
}
158+
}
159+
}
160+
return rst;
161+
}

‎Week_04/id_6/LeetCode_746_6.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
2+
3+
// LeetCode 746
4+
5+
6+
// [ 1. 动态规划 ]
7+
8+
// 到达每个点的花费的集合 看成状态集合，然后根据这个集合推导下一个点的花费集合
9+
// 因为题目只求花费的最小值，所以集合只保留一个值即可
10+
// 动态的向前推进
11+
// 推导依据：f(n) = f(n-1) + f(n-2) + val(n) 斐波那契数
12+
// 到达第cost.length个点(数组外的点)时，花费值即为所求
13+
public int minCostClimbingStairs(int[] cost) {
14+
int n = cost.length;
15+
if (n == 1){
16+
return cost[0];
17+
}
18+
if (n == 2){
19+
return Math.min(cost[0], cost[1]);
20+
}
21+
22+
int[] sum = new int[n+1];
23+
sum[0] = cost[0];
24+
sum[1] = cost[1];
25+
int i = 2;
26+
// 计算每个点的花费集合，只保留最小值
27+
for (i = 2; i < n; i++) {
28+
sum[i] = Math.min(sum[i - 1], sum[i - 2]) + cost[i];
29+
}
30+
31+
return Math.min(sum[i - 1], sum[i - 2]);
32+
}
33+
34+
35+

‎Week_04/id_6/LeetCode_784_6.java‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
2+
3+
// LeetCode 784
4+
5+
6+
// [ 2. 回溯 ]
7+
8+
// "a1b2"
9+
// 每个字符有两种选择
10+
// 第一种选择时，计算后面字符的所有组合（递归）
11+
// 第二种选择时，同样方式
12+
public List<String> letterCasePermutation(String S) {
13+
if (S.length() == 0){
14+
List<String> lt = new ArrayList<>();
15+
lt.add("");
16+
return lt;
17+
}
18+
19+
List<String> rst = new ArrayList<>();
20+
dfs("", S, S.length(), rst);
21+
return rst;
22+
}
23+
24+
25+
public void dfs(String curr, String other, int len, List<String> rst){
26+
if (curr.length() == len){
27+
rst.add(curr);
28+
return;
29+
}
30+
31+
for (int i = 0; i < other.length(); i++) {
32+
char c = other.charAt(i);
33+
if (Character.isAlphabetic(c)){
34+
// 每个字符有两种选择
35+
dfs(curr + Character.toLowerCase(c), other.substring(i+1, other.length()), len, rst);
36+
dfs(curr + Character.toUpperCase(c), other.substring(i+1, other.length()), len, rst);
37+
return;
38+
}else {
39+
curr = curr + c;
40+
}
41+
}
42+
43+
// 都是数字 可以用递归，也可以i==length直接加入rst
44+
dfs(curr, "", len, rst);
45+
}
46+
47+
48+
49+
// [ 1. 分治 ]
50+
51+
// 第一个字符的集合 与 其它剩余字符集合 的组合
52+
// 其它剩余字符集合 递归用此方法
53+
public List<String> letterCasePermutation(String S) {
54+
if (S.length() == 0){
55+
List<String> lt = new ArrayList<>();
56+
lt.add("");
57+
return lt;
58+
}
59+
60+
List<String> rst = new ArrayList<>();
61+
String num = "";
62+
int i = 0;
63+
for (i = 0; i < S.length(); i++) {
64+
// 找到字母停止循环
65+
char c = S.charAt(i);
66+
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
67+
break;
68+
}
69+
}
70+
List<String> left = new ArrayList<>();
71+
List<String> right = new ArrayList<>();
72+
// 没找到字符
73+
if (i == S.length()){
74+
left.add(S);
75+
right.add("");
76+
}else {
77+
left.add(S.substring(0, i) + Character.toLowerCase(S.charAt(i)));
78+
left.add(S.substring(0, i) + Character.toUpperCase(S.charAt(i)));
79+
right = letterCasePermutation(S.substring(i+1, S.length()));
80+
}
81+
82+
// 合并
83+
for (String p : left){
84+
for (String q : right){
85+
rst.add(p + q);
86+
}
87+
}
88+
89+
return rst;
90+
}

0 commit comments

Comments
 (0)