FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

gsf 第四周 · feixiangcode/algorithm@7d13b34 · GitHub

/ algorithm Public
forked from algorithm001/algorithm

Commit 7d13b34

Browse files
guoshufeng
committed
gsf 第四周
1 parent 7abeb64 commit 7d13b34

5 files changed

Lines changed: 248 additions & 0 deletions

File tree

‎Week_04/id_30/LeetCode_169_30.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.shufeng.algorithm4.demo;
2+
3+
import java.util.Random;
4+
5+
/**
6+
* @author gsf
7+
* @date 2019-05-11 22:41
8+
*/
9+
public class LeetCode_169_30 {
10+
public static void main(String[] args) {
11+
int[] arr = {47,47,72,47,72,47,79,47,12,92,13,47,47,83,33,15,18,47,47,47,47,64,47,65,47,47,47,47,70,47,47,55,47,15,60,47,47,47,47,47,46,30,58,59,47,47,47,47,47,90,64,37,20,47,100,84,47,47,47,47,47,89,47,36,47,60,47,18,47,34,47,47,47,47,47,22,47,54,30,11,47,47,86,47,55,40,49,34,19,67,16,47,36,47,41,19,80,47,47,27};
12+
int i = majorityElement(arr);
13+
System.out.println(i);
14+
}
15+
16+
public static int majorityElement(int[] nums) {
17+
quickSort1(nums, 0, nums.length-1);
18+
return nums[nums.length / 2];
19+
}
20+
21+
/**
22+
* leetcode 执行和提交 结果不一致，提交代码不过。
23+
* 三路快排
24+
* 数组根据基数分成三份<、=、>
25+
*/
26+
private static void quickSort1(int[] nums, int l, int r) {
27+
if (l >= r) {
28+
return;
29+
}
30+
// 随机数基数
31+
int s = new Random().nextInt(nums.length);
32+
swap1(nums, l, s);
33+
int v = nums[l];
34+
// 左分点，分割小于和等于，i左边小v，i~k 等于v
35+
int i = l;
36+
// 循环点
37+
int k = l + 1;
38+
// 右分点，右边大于v的数
39+
int j = r + 1;
40+
41+
while (k < j) {
42+
if (nums[k] < v) {
43+
// 循环数和最左边等于V的数交换
44+
swap1(nums, k, i + 1);
45+
i++;
46+
k++;
47+
} else if (nums[k] > v) {
48+
swap1(nums, k, j - 1);
49+
j--;
50+
} else {
51+
k++;
52+
}
53+
}
54+
swap1(nums, l, i);
55+
quickSort1(nums, l, i - 1);
56+
quickSort1(nums, j, r);
57+
}
58+
59+
private static void swap1(int[] arr, int i, int j) {
60+
int tem = arr[i];
61+
arr[i] = arr[j];
62+
arr[j] = tem;
63+
}
64+
}

‎Week_04/id_30/LeetCode_455_30.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.shufeng.algorithm4.demo;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* @author gsf
7+
* @date 2019-05-12 09:34
8+
*/
9+
public class LeetCode_455_30 {
10+
public static void main(String[] args) {
11+
int[] arr = {1, 2};
12+
int[] arr1 = {1,2,3};
13+
int i = findContentChildren(arr, arr1);
14+
System.out.println(i);
15+
}
16+
17+
public static int findContentChildren(int[] g, int[] s) {
18+
Arrays.sort(g);
19+
Arrays.sort(s);
20+
int i = g.length - 1;
21+
int j = s.length - 1;
22+
int k = 0;
23+
while (j >= 0 && i >= 0) {
24+
if (g[i] > s[j]) {
25+
i--;
26+
continue;
27+
}
28+
29+
j--;
30+
i--;
31+
k++;
32+
}
33+
return k;
34+
}
35+
}

‎Week_04/id_30/LeetCode_720_30.java‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.shufeng.algorithm4.demo;
2+
3+
4+
import java.util.HashMap;
5+
import java.util.Map;
6+
7+
/**
8+
* @author gsf
9+
* @date 2019-05-09 14:16
10+
*/
11+
public class LeetCode_720_30 {
12+
13+
public static void main(String[] args) {
14+
// String[] words = {"w", "wo", "wor", "worl", "world"};
15+
// String[] words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
16+
String[] words = {"b", "br", "bre", "brea", "break", "breakf", "breakfa", "breakfas", "breakfast", "l", "lu", "lun", "lunc", "lunch", "d",
17+
"di", "din", "dinn", "dinne", "dinner"};
18+
String s = longestWord(words);
19+
System.out.println(s);
20+
}
21+
22+
23+
public static String longestWord(String[] words) {
24+
Node node = new Node(true);
25+
for (int i = 0; i < words.length; i++) {
26+
add(node, words[i]);
27+
}
28+
String str = "";
29+
for (String word : words) {
30+
if (find(node, word) && (word.length() > str.length() || word.length() == str.length() && word.compareTo(str) < 0)) {
31+
str = word;
32+
}
33+
}
34+
return str;
35+
}
36+
37+
private static class Node {
38+
// 是单词
39+
private boolean isword;
40+
// 每个字符有多个子字符
41+
private Map<Character, Node> next;
42+
43+
public Node(boolean isword) {
44+
this.isword = isword;
45+
this.next = new HashMap<>();
46+
}
47+
48+
public Node() {
49+
this(false);
50+
}
51+
}
52+
53+
/**
54+
* 查询字符串是否每加个字符都有
55+
*/
56+
public static boolean find(Node node, String word) {
57+
for (int i = 0; i < word.length(); i++) {
58+
char c = word.charAt(i);
59+
if (node.next.get(c) == null || !node.isword) {
60+
return false;
61+
}
62+
node = node.next.get(c);
63+
}
64+
65+
return true;
66+
}
67+
68+
public static void add(Node node, String word) {
69+
70+
for (int i = 0; i < word.length(); i++) {
71+
char c = word.charAt(i);
72+
if (node.next.get(c) == null) {
73+
node.next.put(c, new Node());
74+
}
75+
node = node.next.get(c);
76+
}
77+
if (!node.isword) {
78+
node.isword = true;
79+
}
80+
}
81+
82+
}

‎Week_04/id_30/LeetCode_746_30.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.shufeng.algorithm4.demo;
2+
3+
/**
4+
* @author gsf
5+
* @date 2019-05-12 11:03
6+
*/
7+
public class LeetCode_746_30 {
8+
public static void main(String[] args) {
9+
int[] cost = {10, 15, 20};
10+
// int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
11+
int i = minCostClimbingStairs(cost);
12+
System.out.println(i);
13+
14+
}
15+
16+
public static int minCostClimbingStairs(int[] cost) {
17+
18+
for (int i = 2; i < cost.length; i++) {
19+
cost[i] = Math.min(cost[i - 1], cost[i - 2]) + cost[i];
20+
}
21+
return Math.min(cost[cost.length - 1], cost[cost.length - 2]);
22+
}
23+
}

‎Week_04/id_30/LeetCode_784_30.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.shufeng.algorithm4.demo;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* @author gsf
8+
* @date 2019-05-12 10:04
9+
*/
10+
public class LeetCode_784_30 {
11+
public static void main(String[] args) {
12+
13+
String str = "a1b2";
14+
// char c = 'A';
15+
// System.out.println((int) c);
16+
// System.out.println(c);
17+
List<String> list = letterCasePermutation(str);
18+
System.out.println(list);
19+
}
20+
21+
public static List<String> letterCasePermutation(String S) {
22+
List<String> list = new ArrayList<>();
23+
char[] chars = S.toCharArray();
24+
letterCasePermutation(list, chars, "");
25+
return list;
26+
}
27+
28+
public static void letterCasePermutation(List<String> list, char[] chars, String str) {
29+
if (chars.length == str.length()) {
30+
list.add(str);
31+
return;
32+
}
33+
34+
char c = chars[str.length()];
35+
String s = String.valueOf(c);
36+
37+
if (c >= 'A' && c <= 'z') {
38+
letterCasePermutation(list, chars, str + s.toLowerCase());
39+
letterCasePermutation(list, chars, str + s.toUpperCase());
40+
} else {
41+
letterCasePermutation(list, chars, str + s);
42+
}
43+
}
44+
}

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL