Skip to content

Commit 47a4776

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#688 from MrMuddle/master
第四周作业-085
2 parents a77b6df + 73741a8 commit 47a4776

6 files changed

Lines changed: 406 additions & 1 deletion

File tree

‎Week_04/id_85/LeetCode_169_085.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
public class LeetCode_169_085 {
2+
}
3+
4+
/**
5+
* @Package:
6+
* @ClassName: MajorityElement
7+
* @Description: 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
8+
* *************你可以假设数组是非空的，并且给定的数组总是存在众数。
9+
* @leetcode_url:https://leetcode-cn.com/problems/majority-element/
10+
* @Author: wangzhao
11+
* @Date: 2019-05-12 09:49:03
12+
* @Version: 1.0.0
13+
* @Since: 1.8
14+
**/
15+
class MajorityElement {
16+
17+
18+
public int majorityElement(int[] nums) {
19+
20+
if (nums == null || nums.length == 0) {
21+
return -1;
22+
}
23+
24+
int count = 0;
25+
int majority = -1;
26+
27+
for (int num : nums) {
28+
if (count == 0) {
29+
majority = num;
30+
count++;
31+
} else {
32+
if (majority == num) {
33+
count++;
34+
} else {
35+
count--;
36+
}
37+
}
38+
}
39+
40+
if (count <= 0) {
41+
return -1;
42+
}
43+
int counter = 0;
44+
for (int num : nums) {
45+
if (num == majority) {
46+
counter++;
47+
}
48+
}
49+
if (counter > nums.length / 2) {
50+
return majority;
51+
}
52+
return -1;
53+
}
54+
55+
56+
public static void main(String[] args) {
57+
58+
int[] nums = {2, 2, 1, 1, 1, 2, 2};
59+
60+
int num = new MajorityElement().majorityElement(nums);
61+
System.out.println(num);
62+
}
63+
}

‎Week_04/id_85/LeetCode_455_085.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import java.util.Arrays;
2+
3+
public class LeetCode_455_085 {
4+
}
5+
6+
/**
7+
* @Package:
8+
* @ClassName: AssignCookies
9+
* @Description: 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
10+
* **************对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。
11+
* **************如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
12+
* **************你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
13+
* **************注意：
14+
* **************你可以假设胃口值为正。
15+
* **************一个小朋友最多只能拥有一块饼干。
16+
* @leetcode_url:https://leetcode-cn.com/problems/assign-cookies/
17+
* @Author: wangzhao
18+
* @Date: 2019-05-12 10:14:17
19+
* @Version: 1.0.0
20+
* @Since: 1.8
21+
**/
22+
class AssignCookies {
23+
24+
public int findContentChildren(int[] g, int[] s) {
25+
26+
if (g == null || g.length == 0) {
27+
return 0;
28+
}
29+
if (s == null || s.length == 0) {
30+
return 0;
31+
}
32+
33+
int child = 0;
34+
int cookie = 0;
35+
Arrays.sort(g);
36+
Arrays.sort(s);
37+
38+
while (child < g.length && cookie < s.length) {
39+
if (g[child] <= s[cookie]) {
40+
child++;
41+
}
42+
cookie++;
43+
}
44+
45+
return child;
46+
}
47+
48+
public static void main(String[] args) {
49+
50+
int[] g = {1, 2};
51+
int[] s = {1, 2, 3};
52+
int num = new AssignCookies().findContentChildren(g, s);
53+
System.out.println(num);
54+
}
55+
56+
}

‎Week_04/id_85/LeetCode_720_085.java‎

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
public class LeetCode_720_085 {
2+
}
3+
4+
5+
/**
6+
* @Package:
7+
* @ClassName: LongestWordInDictionary
8+
* @Description: 给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。
9+
* **************若其中有多个可行的答案，则返回答案中字典序最小的单词。
10+
* **************若无答案，则返回空字符串。
11+
* @leetcode url:https://leetcode-cn.com/problems/longest-word-in-dictionary/
12+
* @Author: wangzhao
13+
* @Date: 2019-05-11 21:21:44
14+
* @Version: 1.0.0
15+
* @Since: 1.8
16+
**/
17+
class LongestWordInDictionary {
18+
19+
private String longestWord="";
20+
public String longestWord(String[] words) {
21+
22+
if (words == null || words.length == 0) {
23+
return null;
24+
}
25+
Trie trie = new Trie();
26+
for (String word : words) {
27+
trie.insert(word);
28+
}
29+
30+
search(new StringBuffer(),trie.nodes);
31+
32+
return longestWord;
33+
}
34+
35+
private void search(StringBuffer sb,TreeNode4[] node4s) {
36+
if (node4s == null || node4s.length == 0) {
37+
return;
38+
}
39+
40+
for (TreeNode4 node4 : node4s) {
41+
if (node4 != null && node4.end) {
42+
sb.append(node4.val);
43+
if (sb.length()>longestWord.length()){
44+
longestWord=sb.toString();
45+
}
46+
search(sb,node4.children);
47+
sb.deleteCharAt(sb.length()-1);
48+
}
49+
}
50+
51+
}
52+
53+
54+
public static void main(String[] args) {
55+
// String[] words = {"w", "wo", "wor", "worl", "world"};
56+
String[] words= {"a", "banana", "app", "appl", "ap", "apply", "apple"};
57+
String longestWord = new LongestWordInDictionary().longestWord(words);
58+
System.out.println(longestWord);
59+
}
60+
}
61+
62+
class Trie {
63+
64+
TreeNode4[] nodes;
65+
66+
public Trie() {
67+
this.nodes = new TreeNode4[26];
68+
}
69+
70+
public void insert(String word) {
71+
if (word == null || word.length() == 0) {
72+
return;
73+
}
74+
75+
insert(0, word.toCharArray(), nodes);
76+
77+
}
78+
79+
private void insert(int i, char[] chars, TreeNode4[] children) {
80+
81+
int idx = chars[i] - 'a';
82+
83+
if (children[idx] == null) {
84+
children[idx] = new TreeNode4(chars[i]);
85+
}
86+
87+
if (i == chars.length - 1) {
88+
children[idx].end = true;
89+
return;
90+
}
91+
92+
if (children[idx].children == null) {
93+
children[idx].children = new TreeNode4[26];
94+
}
95+
96+
insert(i + 1, chars, children[idx].children);
97+
}
98+
}
99+
100+
class TreeNode4 {
101+
102+
char val;
103+
boolean end;
104+
TreeNode4[] children;
105+
106+
public TreeNode4(char val) {
107+
this.val = val;
108+
}
109+
}

‎Week_04/id_85/LeetCode_746_085.java‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
public class LeetCode_746_085 {
2+
}
3+
4+
/**
5+
* @Package:
6+
* @ClassName: MinCostClimbingStairs
7+
* @Description: 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
8+
* **************每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
9+
* **************您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
10+
* @leetcode_url:https://leetcode-cn.com/problems/min-cost-climbing-stairs/
11+
* @Author: wangzhao
12+
* @Date: 2019-05-12 11:53:46
13+
* @Version: 1.0.0
14+
* @Since: 1.8
15+
**/
16+
class MinCostClimbingStairs {
17+
18+
public int minCostClimbingStairs2(int[] cost) {
19+
20+
if (cost == null || cost.length == 0) {
21+
return 0;
22+
}
23+
if (cost.length == 1) {
24+
return cost[0];
25+
}
26+
27+
if (cost.length == 2) {
28+
return Math.min(cost[0], cost[1]);
29+
}
30+
31+
int length = cost.length;
32+
33+
for (int i = 2; i < length; i++) {
34+
cost[i] += Math.min(cost[i - 1], cost[i - 2]);
35+
}
36+
37+
38+
return Math.min(cost[length - 1], cost[length - 2]);
39+
}
40+
41+
public int minCostClimbingStairs(int[] cost) {
42+
43+
if (cost == null || cost.length == 0) {
44+
return 0;
45+
}
46+
47+
return minStep(cost, -1);
48+
}
49+
50+
private int minStep(int[] cost, int step) {
51+
52+
if (step >= cost.length) {
53+
return 0;
54+
}
55+
int val1 = 0;
56+
if (step + 1 < cost.length) {
57+
val1 = cost[step + 1];
58+
}
59+
60+
int val2 = 0;
61+
if (step + 2 < cost.length) {
62+
val2 = cost[step + 2];
63+
}
64+
65+
int res1 = val1 + minStep(cost, step + 1);
66+
int res2 = val2 + minStep(cost, step + 2);
67+
68+
return Math.min(res1, res2);
69+
}
70+
71+
72+
public static void main(String[] args) {
73+
// int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
74+
// int[] cost = {0, 1, 2, 2};
75+
int[] cost = {0, 2, 2, 1};
76+
77+
78+
int num = new MinCostClimbingStairs().minCostClimbingStairs2(cost);
79+
System.out.println(num);
80+
}
81+
}

‎Week_04/id_85/LeetCode_784_085.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
import java.util.ArrayList;
2+
import java.util.List;
3+
4+
public class LeetCode_784_085 {
5+
}
6+
7+
/**
8+
* @Package:
9+
* @ClassName: LetterCasePermutation
10+
* @Description: 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
11+
* @leetcode_url:https://leetcode-cn.com/problems/letter-case-permutation/
12+
* @Author: wangzhao
13+
* @Date: 2019-05-12 10:35:23
14+
* @Version: 1.0.0
15+
* @Since: 1.8
16+
**/
17+
class LetterCasePermutation {
18+
19+
20+
public List<String> letterCasePermutation(String S) {
21+
22+
List<String> result = new ArrayList<>();
23+
if (S == null || S.length() == 0) {
24+
return result;
25+
}
26+
27+
char[] chars = S.toCharArray();
28+
29+
permutation(chars,0,result);
30+
31+
return result;
32+
}
33+
34+
private void permutation(char[] chars,int cursor,List<String> result ){
35+
if (cursor>=chars.length){
36+
return;
37+
}
38+
int temp= cursor;
39+
40+
if (!result.contains(new String(chars))){
41+
result.add(new String(chars));
42+
}
43+
if (Character.isDigit(chars[cursor])){
44+
permutation(chars,++cursor,result);
45+
}else if(chars[cursor]>='a'&& chars[cursor]<='z'){
46+
permutation(chars,++cursor,result);
47+
chars[temp]=Character.toUpperCase(chars[temp]);
48+
if (!result.contains(new String(chars))){
49+
result.add(new String(chars));
50+
}
51+
permutation(chars,++temp,result);
52+
}else if (chars[cursor]>='A'&&chars[cursor]<='Z'){
53+
permutation(chars,++cursor,result);
54+
chars[temp]=Character.toLowerCase(chars[temp]);
55+
if (!result.contains(new String(chars))){
56+
result.add(new String(chars));
57+
}
58+
permutation(chars,++temp,result);
59+
}
60+
}
61+
62+
public static void main(String[] args) {
63+
64+
String S = "C";
65+
List<String> list = new LetterCasePermutation().letterCasePermutation(S);
66+
list.stream().forEach(System.out::println);
67+
68+
}
69+
}
70+

0 commit comments

Comments
 (0)