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

week4 · feixiangcode/algorithm@3fbc187 · GitHub

/ algorithm Public
forked from algorithm001/algorithm

Commit 3fbc187

Browse files
zhangruihao.zhang
committed
week4
1 parent 5c077ff commit 3fbc187

3 files changed

Lines changed: 231 additions & 0 deletions

File tree

‎Week_04/id_108/LeetCode_169_108.java‎

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package com.algorithm;
2+
3+
import java.util.Arrays;
4+
import java.util.HashMap;
5+
import java.util.Map;
6+
7+
/**
8+
* @author zhangruihao.zhang
9+
* @version v1.0.0
10+
* @since 2019/05/12
11+
*/
12+
public class LeetCode_169_108 {
13+
14+
// 遍历一遍，相同则加1，不相同则减1，最后剩余的item就是众数
15+
class Solution1 {
16+
public int majorityElement(int[] nums) {
17+
int count = 1;
18+
int item = nums[0];
19+
20+
for (int i = 1; i < nums.length; i++) {
21+
if (count == 0) {
22+
item = nums[i];
23+
count = 1;
24+
} else if (nums[i] == item) {
25+
count++;
26+
} else {
27+
count--;
28+
}
29+
}
30+
31+
return item;
32+
}
33+
}
34+
35+
// 统计每个数字的词频，统计出现次数大于n/2的
36+
class Solution2 {
37+
public int majorityElement(int[] nums) {
38+
Map<Integer, Integer> map = new HashMap<>();
39+
int maxCount = 0;
40+
int maxItem = 0;
41+
for (int num : nums) {
42+
int count = map.getOrDefault(num, 0) + 1;
43+
if (map.keySet().isEmpty()) {
44+
maxCount = 1;
45+
maxItem = num;
46+
}
47+
if (map.keySet().contains(num)) {
48+
if (count > maxCount) {
49+
maxCount = count;
50+
maxItem = num;
51+
}
52+
53+
}
54+
map.put(num, map.getOrDefault(num, 0) + 1);
55+
}
56+
57+
return maxItem;
58+
}
59+
}
60+
61+
//分治方法
62+
class Solution3 {
63+
public int majorityElement(int[] nums) {
64+
65+
if (nums.length == 1) {
66+
return nums[0];
67+
}
68+
int mid = nums.length / 2;
69+
70+
int[] left = Arrays.copyOfRange(nums, 0, mid);
71+
int[] right = Arrays.copyOfRange(nums, mid, nums.length);
72+
int a = majorityElement(left);
73+
int b = majorityElement(right);
74+
75+
if (a == b) {
76+
return a;
77+
}
78+
return count(a, nums) > (nums.length / 2) ? a : b;
79+
}
80+
81+
private int count(int num, int[] nums) {
82+
int count = 0;
83+
for (int i : nums) {
84+
if (num == i) {
85+
count++;
86+
}
87+
}
88+
return count;
89+
}
90+
}
91+
}

‎Week_04/id_108/LeetCode_720_108.java‎

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,113 @@
1+
2+
import java.util.Arrays;
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
/**
7+
* @author zhangruihao.zhang
8+
* @version v1.0.0
9+
* @since 2019/05/12
10+
*/
11+
public class LeetCode_720_108 {
12+
13+
14+
class Solution1 {
15+
// 方法一：比较次数较多
16+
public String longestWord(String[] words) {
17+
Arrays.sort(words);
18+
Set<String> set = new HashSet<>();
19+
String longest = "";
20+
for (String word : words) {
21+
if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
22+
set.add(word);
23+
if (word.length() > longest.length()) {
24+
longest = word;
25+
}
26+
}
27+
}
28+
return longest;
29+
}
30+
}
31+
32+
class Solution2 {
33+
//方法二：trie树，比较耗内存
34+
private TreeNode root;
35+
private char startChar = 'a';
36+
private String longest = "";
37+
38+
public String longestWord(String[] words) {
39+
for (String word : words) {
40+
insert(word);
41+
}
42+
findLongest(root, "");
43+
return longest;
44+
}
45+
46+
private void insert(String word) {
47+
if (root == null) {
48+
root = new TreeNode();
49+
}
50+
TreeNode tmp = root;
51+
52+
for (int i = 0; i < word.length(); i++) {
53+
int index = word.charAt(i) - startChar;
54+
TreeNode child = tmp.getChildren()[index];
55+
if (child == null) {
56+
TreeNode node = new TreeNode();
57+
node.setTimes(1).setWord(i == word.length() - 1);
58+
tmp.getChildren()[index] = node;
59+
} else {
60+
boolean isWord = child.isWord;
61+
child.setTimes(child.getTimes() + 1).setWord(isWord || i == word.length() - 1);
62+
}
63+
tmp = tmp.getChildren()[index];
64+
}
65+
}
66+
67+
private void findLongest(TreeNode node, String word) {
68+
for (int index = 0; index < 26; index++) {
69+
if (node.getChildren()[index] != null && node.getChildren()[index].isWord) {
70+
String newWord = word + (char) ('a' + index);
71+
if (newWord.length() > longest.length()) {
72+
longest = newWord;
73+
}
74+
findLongest(node.getChildren()[index], newWord);
75+
}
76+
}
77+
}
78+
79+
private class TreeNode {
80+
private boolean isWord;
81+
private TreeNode[] children = new TreeNode[26];
82+
private int times;
83+
84+
public boolean isWord() {
85+
return isWord;
86+
}
87+
88+
public TreeNode setWord(boolean word) {
89+
isWord = word;
90+
return this;
91+
}
92+
93+
public TreeNode[] getChildren() {
94+
return children;
95+
}
96+
97+
public TreeNode setChildren(TreeNode[] children) {
98+
this.children = children;
99+
return this;
100+
}
101+
102+
public int getTimes() {
103+
return times;
104+
}
105+
106+
public TreeNode setTimes(int times) {
107+
this.times = times;
108+
return this;
109+
}
110+
}
111+
}
112+
113+
}

‎Week_04/id_108/LeetCode_746_108.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
import java.util.Arrays;
2+
3+
/**
4+
* @author zhangruihao.zhang
5+
* @version v1.0.0
6+
* @since 2019/05/12
7+
*/
8+
public class LeetCode_746_108 {
9+
10+
class Solution {
11+
public int minCostClimbingStairs(int[] cost) {
12+
if (cost.length < 2) {
13+
return 0;
14+
}
15+
if (cost.length == 2) {
16+
return Math.min(cost[0], cost[1]);
17+
}
18+
19+
int sum[] = Arrays.copyOfRange(cost, 0, cost.length);
20+
21+
for (int i = 2; i < sum.length; i++) {
22+
sum[i] = sum[i] + Math.min(sum[i - 1], sum[i - 2]);
23+
}
24+
return Math.min(sum[sum.length - 1], sum[sum.length - 2]);
25+
}
26+
}
27+
}

0 commit comments

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