Skip to content

Commit 59cca41

Browse files
awangdevawangdev
committed
3.2.2016
1 parent fe654f0 commit 59cca41

16 files changed

+771
-692
lines changed

‎Java/Majority Number III.java

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,12 @@
11
M
22

3-
Not Done
3+
与其他Majority Number一样。
4+
5+
出现次数多余1/k，就要分成k份count occurance.用HashMap。 存在的+1；不存在map里的，分情况:
6+
若map.size() == k,说明candidate都满了，要在map里把所有现存的都-1；
7+
若map.size() < k, 说明该加新candidate，那么map.put(xxx, 1);
8+
9+
最后在HashMap里找出所留下的occurance最大的那个数。
410

511
```
612
/*
@@ -38,7 +44,7 @@ public int majorityNumber(ArrayList<Integer> nums, int k) {
3844
if (map.containsKey(num)) {//Found duplicates, count++
3945
map.put(num, map.get(num) + 1);
4046
} else {
41-
if (map.size() == k) {//All candidates added, do count--
47+
if (map.size() == k) {//Enough candidates added, do count--
4248
Iterator<Map.Entry<Integer, Integer>> iter = map.entrySet().iterator();
4349
while (iter.hasNext()) {
4450
Map.Entry<Integer, Integer> entry = iter.next();

‎Java/Majority Number.java

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,13 @@
11
E
22

3-
Majority Number是指超半数。任何超半数，都可以用0和1count：是某个number，+1；不是这个number-1.
3+
Majority Number是指超半数。任何超半数，都可以用0和1count：是某个number，+1；不是这个number,-1.
44

55
注意：assume valid input, 是一定有一个majority number的。否则此法不成。[1,1,1,2,2,2,3]是个invalid input,结果是3，当然也错了。
66

7+
Majority Number II，超1/3, 那么就分三份处理，countA, countB来计算最多出现的两个。
8+
9+
Majority Number III, 超1/k, 那么自然分k份。这里用到 HashMap。
10+
711
```
812

913
/*

‎Java/Minimum Size Subarray Sum.java

Lines changed: 51 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,13 @@
11
M
22

3-
2 pointer:
4-
一个做base, 每次动一格：i.
5-
一个做前锋，加到满足条件为止。
6-
Note: 当sum >= s 条件在while里面满足时，end是多一个index的。所以result里面要处理好边缘情况：(end-1) 才是真的末尾位置，然后计算和开头的间隙：
7-
（end - 1） - start + 1;
3+
2 pointer, O(n). 找subarray, start 或 end pointer，每次一格这样移动.
4+
5+
好的策略: 先找一个solution, 定住end, 然后移动start; 记录每个solution if occurs； 然后再移动end，往下找。
6+
7+
Note: 虽然一眼看上去是nested loop.但是分析后，发现其实就是按照end pointer移动的Loop。start每次移动一格。总体上，还是O(n)
8+
9+
10+
Note done the O(nlogn) yet
811

912
```
1013
/*
@@ -22,17 +25,54 @@ If you have figured out the O(n) solution, try coding another solution of which
2225
*/
2326

2427
/*
25-
Thoughts:
28+
3.2.2016
29+
Clearner:
30+
1. Move 'end' for first possbile solution
31+
2. Store it and remove one 'start' element from sum. Save any solution if occurs, in while loop.
32+
3. Go back to step 1, until 'end' hits nums.length
33+
*/
34+
35+
public class Solution {
36+
public int minimumSize(int[] nums, int s) {
37+
if (nums == null || nums.length == 0) {
38+
return -1;
39+
}
40+
int min = Integer.MAX_VALUE;
41+
int start = 0;
42+
int end = 0;
43+
int sum = 0;
44+
45+
while (end < nums.length) {
46+
while (end < nums.length && sum < s) {
47+
sum += nums[end];
48+
end++;
49+
}
50+
while (sum >= s) {
51+
min = Math.min(min, end - start);
52+
sum -= nums[start];
53+
start++;
54+
}
55+
}
56+
return (min == Integer.MAX_VALUE) ? -1 : min;
57+
}
58+
}
59+
60+
61+
/*
62+
Thoughts: old solution O(n), not prefered.
2663
Create a subarray range: (i,j). Use i as start and j as end. Check if within the range, sum >= s.
2764
Shift the range every time: i += 1.
65+
66+
2 pointer:
67+
一个做base, 每次动一格：i.
68+
一个做前锋，加到满足条件为止。
69+
Note: 当sum >= s 条件在while里面满足时，end是多一个index的。所以result里面要处理好边缘情况：(end-1) 才是真的末尾位置，然后计算和开头的间隙：
70+
（end - 1） - start + 1;
71+
72+
2873
*/
2974

3075
public class Solution {
31-
/**
32-
* @param nums: an array of integers
33-
* @param s: an integer
34-
* @return: an integer representing the minimum size of subarray
35-
*/
3676
public int minimumSize(int[] nums, int s) {
3777
if (nums == null || nums.length == 0) {
3878
return -1;

‎Java/Minimum Window Substring.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,8 @@
1+
M
2+
3+
Need look again. Had bad solution at 2nd attempt.
4+
5+
```
16
/*
27
Given a string source and a string target, find the minimum window in source which will contain all the characters in target.
38
@@ -19,7 +24,10 @@ Can you do it in time complexity O(n) ?
1924
2025
Tags Expand
2126
Hash Table
27+
*/
2228

29+
30+
/*
2331
Thoughts:
2432
The idea was from jiuzhang.com.
2533
1. count target Characters: store each Character with HashMap:tCounter<Character, # appearance>
@@ -110,3 +118,65 @@ public static void main(String[] args) {
110118
System.out.println("resutl is : " + rst);
111119
}
112120
}
121+
122+
123+
124+
125+
/*
126+
3.2.2016, another thought. But this does not work.
127+
1. record hashmap<char, list of index of matched char>
128+
2. record matched char's indexes in a arraylsit
129+
3. Use a char[256] to check through the arraylist, if any sequence match target chars, then use the position to calculate a result.
130+
4. repeat 3 and find the minimum
131+
*/
132+
public class Solution {
133+
public String minWindow(String source, String target) {
134+
if (source == null || source.length() == 0 || target == null || target.length() == 0) {
135+
return "";
136+
}
137+
int[] match = new int[256];
138+
for (int i = 0; i < target.length(); i++) {
139+
match[target.charAt(i)] += 1;
140+
}
141+
142+
ArrayList<Integer> posList = new ArrayList<Integer>();
143+
for (int i = 0; i < source.length(); i++) {
144+
if (target.indexOf(source.charAt(i)) != -1) {
145+
posList.add(i);
146+
}
147+
}
148+
149+
int[] arr = new int[256];
150+
String matchStr = Arrays.toString(match);
151+
String rst = "";
152+
int start = -1;
153+
int end = -1;
154+
for (int i = 0; i < posList.size(); i++) {
155+
int pos = posList.get(i);
156+
char c = source.charAt(pos);
157+
if (target.indexOf(c) != -1) {
158+
if (arr[c] < match[c]) {
159+
arr[c] += 1;
160+
}
161+
162+
if (start == -1) {
163+
start = pos;
164+
}
165+
}
166+
167+
if (Arrays.toString(arr).equals(matchStr)) {
168+
end = posList.get(i);
169+
String temp = source.substring(start, end + 1);
170+
if (rst.length() == 0 || temp.length() < rst.length()) {
171+
rst = temp;
172+
}
173+
arr[start] -= 1;
174+
start = -1;
175+
}
176+
}//end for
177+
178+
return rst;
179+
}
180+
}
181+
182+
```

‎Java/Permutations.java

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,10 @@
1-
还是递归： 取，或者不取。
1+
M
2+
3+
Recursive： 取，或者不取。
4+
25
Iterative: 用个queue，每次poll()出来的list, 把在nums里面能加的挨个加一遍。
6+
7+
38
```
49
/*
510
Given a list of numbers, return all possible permutations.

‎Java/Populating Next Right Pointers in Each Node II.java

Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
H
2+
3+
非perfect tree, 也就是有random的null children. DFS＋BFS
4+
5+
6+
Populating Next Right Pointers in Each Node I 里面依赖parent.next.left来作链接，但现在这个parent.next.left很可能也是Null.
7+
8+
1. 于是需要移动parent去找children level的next node。
9+
2. 并且每次在一个level, 要用BFS的思想把所有parent 过一遍，也就是把parent 正下方的children全部用.next链接起来
10+
原因: 到下一层children变成parent, 他们需要彼此之间的connection, grand children才可以相互连接。
11+
12+
13+
Note: runtime O(n * 2^log(n) ) = O(n^2), not good.
14+
15+
```
16+
/*
17+
Follow up for problem "Populating Next Right Pointers in Each Node".
18+
19+
What if the given tree could be any binary tree? Would your previous solution still work?
20+
21+
Note:
22+
23+
You may only use constant extra space.
24+
For example,
25+
Given the following binary tree,
26+
1
27+
/ \
28+
2 3
29+
/ \ \
30+
4 5 7
31+
After calling your function, the tree should look like:
32+
1 -> NULL
33+
/ \
34+
2 -> 3 -> NULL
35+
/ \ \
36+
4-> 5 -> 7 -> NULL
37+
Hide Company Tags Microsoft Bloomberg Facebook
38+
Hide Tags Tree Depth-first Search
39+
Hide Similar Problems (M) Populating Next Right Pointers in Each Node
40+
41+
*/
42+
43+
/**
44+
* Definition for binary tree with next pointer.
45+
* public class TreeLinkNode {
46+
* int val;
47+
* TreeLinkNode left, right, next;
48+
* TreeLinkNode(int x) { val = x; }
49+
* }
50+
*/
51+
52+
/*
53+
DFS to traverse the tree.
54+
Also BFS using next pointer. clear node's children level per visit
55+
*/
56+
public class Solution {
57+
public void connect(TreeLinkNode root) {
58+
if (root == null || (root.left == null && root.right == null)) {
59+
return;
60+
}
61+
dfs(root);
62+
}
63+
//Clear connection problems on each level: because the lower children level will relay on parent's level connection.
64+
public void dfs(TreeLinkNode node) {
65+
if (node == null) {
66+
return;
67+
}
68+
TreeLinkNode parent = node;
69+
while (parent != null) {
70+
//Connect left-> right in normal case
71+
if (parent.left != null) {
72+
parent.left.next = parent.right;
73+
}
74+
//Left || right: one of needs to use addRight(node) method to build the .next bridge.
75+
if (parent.left != null && parent.left.next == null) {//Fact: parent.right = null, from last step
76+
parent.left.next = addRight(parent);
77+
} else if (parent.right != null && parent.right.next == null) {
78+
parent.right.next = addRight(parent);
79+
}
80+
parent = parent.next;
81+
}
82+
83+
dfs(node.left);
84+
dfs(node.right);
85+
}
86+
87+
//Always take parentNode, and try to return the very first available node at child level
88+
public TreeLinkNode addRight(TreeLinkNode node) {
89+
while (node != null) {
90+
if (node.next == null) {
91+
return null;
92+
}
93+
if (node.next.left != null) {
94+
return node.next.left;
95+
}
96+
if (node.next.right != null) {
97+
return node.next.right;
98+
}
99+
node = node.next;
100+
}
101+
return null;
102+
}
103+
104+
}
105+
106+
107+
```

0 commit comments

Comments
 (0)