Skip to content

Commit a0fa9c2

Browse files
awangdevawangdev
committed
clean up
1 parent 572d824 commit a0fa9c2

53 files changed

Lines changed: 2955 additions & 1463 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎Java/Implement strStr().java‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,12 +15,19 @@
1515
/*
1616
Implement strStr().
1717
18-
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
18+
Returns the index of the first occurrence of needle in haystack,
19+
or -1 if needle is not part of haystack.
1920
2021
Hide Company Tags Facebook
2122
Hide Tags Two Pointers String
2223
Hide Similar Problems (H) Shortest Palindrome
2324
25+
Clarification
26+
Do I need to implement KMP Algorithm in an interview?
27+
28+
- Not necessary. When this problem occurs in an interview,
29+
the interviewer just want to test your basic implementation ability.
30+
2431
*/
2532

2633
class Solution {

‎Java/Maximum Subarray II.java‎

Lines changed: 105 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2,15 +2,26 @@
22
1525363049
33
tags: Greedy, Array, DP, Sequence DP
44

5+
给一串数组, 找数组中间 两个不交互的 subarray 数字之和的最大值
6+
57
#### DP
6-
- 考虑两个方向的dp[i]: 包括i在内的subarray max sum
7-
- 但是不够, 需要找maxLeft[] 和 maxRight[]
8+
- 考虑两个方向的dp[i]: 包括i在内的subarray max sum.
9+
- dp[i] 的特点是: 如果上一个 dp[i - 1] + nums[i - 1] 小于 nums[i-1], 那么就舍弃之前, 从头再来:
10+
- dp[i] = Math.max(dp[i - 1] + nums.get(i - 1), nums.get(i - 1));
11+
- 缺点: 无法track全局max, 需要记录max.
12+
- 因为我们现在要考虑从左边/右边来的所有max, 所以要记录maxLeft[] 和 maxRight[]
13+
- maxLeft[i]: 前i个元素的最大sum是多少 (不断递增); maxRight反之, 从右边向左边
814
- 最后比较maxLeft[i] + maxRight[i] 最大值
15+
- Space, Time O(n)
16+
- Rolling array, reduce some space, but can not reduce maxLeft/maxRight
917

10-
#### prefix sum.
11-
- 注意：右边算prefix sum， 看上去好像是什么postfix sum? 其实不是。其实都和prefix一样。
12-
- 我们需要的那部分prefix sum，其实就是一段数字的总和。
13-
- 所以从右边累计上来的。也是一样可以的。
18+
#### preSum, minPreSum
19+
- preSum是[0, i] 每个数字一次加起来的值
20+
- 如果维持一个minPreSum, 就是记录[0, i]sum的最小值(因为有可能有负数)
21+
- preSum - minPreSum 就是在 [0, i]里, subarray的最大sum值
22+
- 把这个最大subarray sum 记录在array, left[] 里面
23+
- right[] 是一样的道理
24+
- enumerate一下元素的排列顺位, 最后 max = Math.max(max, left[i] + right[i + 1])
1425

1526
```
1627
/*
@@ -91,6 +102,94 @@ public int maxTwoSubArrays(List<Integer> nums) {
91102
}
92103

93104

105+
// Rolling array
106+
public class Solution {
107+
/*
108+
* @param nums: A list of integers
109+
* @return: An integer denotes the sum of max two non-overlapping subarrays
110+
*/
111+
public int maxTwoSubArrays(List<Integer> nums) {
112+
if (nums == null || nums.size() == 0) {
113+
return 0;
114+
}
115+
int n = nums.size();
116+
int[] dpLeft = new int[2];
117+
int[] dpRight = new int[2];
118+
dpLeft[0] = 0;
119+
dpRight[n % 2] = 0;
120+
121+
int[] maxLeft = new int[n + 1];;
122+
int[] maxRight = new int[n + 1];
123+
maxLeft[0] = Integer.MIN_VALUE;
124+
maxRight[n] = Integer.MIN_VALUE;
125+
126+
// Left
127+
for (int i = 1; i <= n; i++) {
128+
dpLeft[i % 2] = Math.max(dpLeft[(i - 1) % 2] + nums.get(i - 1), nums.get(i - 1));
129+
maxLeft[i] = Math.max(maxLeft[i - 1], dpLeft[i % 2]);
130+
}
131+
132+
// Right
133+
for (int j = n - 1; j >= 0; j--) {
134+
dpRight[j % 2] = Math.max(dpRight[(j + 1) % 2] + nums.get(j), nums.get(j));
135+
maxRight[j] = Math.max(maxRight[j + 1], dpRight[j % 2]);
136+
}
137+
138+
// Combine
139+
int max = Integer.MIN_VALUE;
140+
for (int i = 1; i < n; i++) {
141+
max = Math.max(max, maxLeft[i] + maxRight[i]);
142+
}
143+
144+
return max;
145+
}
146+
}
147+
148+
// Futher simplify:
149+
// use 1 for loop for both left and right
150+
public class Solution {
151+
/*
152+
* @param nums: A list of integers
153+
* @return: An integer denotes the sum of max two non-overlapping subarrays
154+
*/
155+
public int maxTwoSubArrays(List<Integer> nums) {
156+
if (nums == null || nums.size() == 0) {
157+
return 0;
158+
}
159+
int n = nums.size();
160+
int[] dpLeft = new int[2];
161+
int[] dpRight = new int[2];
162+
dpLeft[0] = 0;
163+
dpRight[n % 2] = 0;
164+
165+
int[] maxLeft = new int[n + 1];;
166+
int[] maxRight = new int[n + 1];
167+
maxLeft[0] = Integer.MIN_VALUE;
168+
maxRight[n] = Integer.MIN_VALUE;
169+
170+
171+
for (int i = 1; i <= n; i++) {
172+
// Left
173+
dpLeft[i % 2] = Math.max(dpLeft[(i - 1) % 2] + nums.get(i - 1), nums.get(i - 1));
174+
maxLeft[i] = Math.max(maxLeft[i - 1], dpLeft[i % 2]);
175+
176+
// Right
177+
int j = n - i;
178+
dpRight[j % 2] = Math.max(dpRight[(j + 1) % 2] + nums.get(j), nums.get(j));
179+
maxRight[j] = Math.max(maxRight[j + 1], dpRight[j % 2]);
180+
}
181+
182+
// Combine
183+
int max = Integer.MIN_VALUE;
184+
for (int i = 1; i < n; i++) {
185+
max = Math.max(max, maxLeft[i] + maxRight[i]);
186+
}
187+
188+
return max;
189+
}
190+
}
191+
192+
94193
/*
95194
Thoughts： 11.23.2015
96195
Similar to Maximum Subarray。 Now just try to build 2 maximum subbary, from left/right.

‎Java/Maximum Subarray III.java‎

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,16 @@
1+
H
2+
3+
```
14
/*
25
3-
Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.
6+
Given an array of integers and a number k,
7+
find k non-overlapping subarrays which have the largest sum.
48
59
The number in each subarray should be contiguous.
610
711
Return the largest sum.
812
9-
Have you met this question in a real interview? Yes
13+
1014
Example
1115
Given [-1,4,-2,3,-2,3], k=2, return 8
1216
@@ -17,17 +21,16 @@
1721
LintCode Copyright Dynamic Programming Subarray Array
1822
*/
1923

20-
/*
21-
NOT DONE
22-
*/
24+
// Should be partition DP
2325
public class Solution {
2426
/**
2527
* @param nums: A list of integers
2628
* @param k: An integer denote to find k non-overlapping subarrays
2729
* @return: An integer denote the sum of max k non-overlapping subarrays
2830
*/
29-
public int maxSubArray(ArrayList<Integer> nums, int k) {
30-
// write your code
31+
public int maxSubArray(int[] nums, int k) {
32+
// write your code here
3133
}
3234
}
3335

36+
```

‎Java/Maximum Subarray.java‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22
1525331164
33
tags: DP, Sequence DP, Array, Divide and Conquer
44

5+
给一串数组, 找数组中间 subarray 数字之和的最大值
6+
57
#### Sequence DP
68
- dp[i]: 前i个element, 包括element i 在内的 continous subsequence 的最大sum是多少?
79
- 因为continous sequence, 所以不满足条件的时候, 会断: track overall max,

‎Java/Median.java‎

Lines changed: 101 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,17 @@
1+
E
2+
1525410641
3+
tags: Quick Sort, Quick Select, Array
4+
5+
给一串无序数组, 找到median(sort之后 位置在中间的数字).
6+
7+
#### Quick Select
8+
- 与quickSort不同在于, 每次只要在一半list里面recurring, 所以把O(logn)的时间复杂度降到O(n)
9+
- quickSelect 可以找到 kth 最小的元素
10+
- 利用这个原理, 找这个kth最小值, 然后如果 == target index, 就找到了我们的median
11+
- quick select 的template要熟悉一下, 一下子可能想得到, 但写不出来
12+
- 主要步骤: partition, dfs, only recur on one part of the array
13+
14+
```
115
/*
216
Given a unsorted array with integers, find the median of it.
317
@@ -18,6 +32,70 @@
1832
1933
2034
*/
35+
36+
/*
37+
Thoughts:
38+
Goal: Find the median, which is N/2-th.
39+
Enumerate a few examples and find median index = (nums.length - 1) / 2
40+
41+
Quick sort has the nature of putting all smaller items on left, and larger numbers on right.
42+
If that pivot point happends to hit the midian index, that's our target.
43+
We don't necessarily need to sort all items, but just need to locate the median index.
44+
*/
45+
public class Solution {
46+
/**
47+
* @param nums: A list of integers
48+
* @return: An integer denotes the middle number of the array
49+
*/
50+
public int median(int[] nums) {
51+
if (nums == null || nums.length == 0) {
52+
return 0;
53+
}
54+
if (nums.length == 1) {
55+
return nums[0];
56+
}
57+
int n = nums.length;
58+
return quickSelect(nums, 0, n - 1, (n - 1)/ 2);
59+
}
60+
61+
private int quickSelect(int[] nums, int start, int end, int target) {
62+
int index = partition(nums, start, end);
63+
if (index == target) {
64+
return nums[index];
65+
} else if (index < target) {
66+
return quickSelect(nums, index + 1, end, target);
67+
} else {
68+
return quickSelect(nums, start, index - 1, target);
69+
}
70+
}
71+
72+
private int partition(int[] nums, int low, int high) {
73+
int pivot = high; // end
74+
int pivotValue = nums[pivot];
75+
76+
while (low < high) {
77+
while (low < high && nums[low] < pivotValue) {
78+
low++;
79+
}
80+
while (low < high && nums[high] >= pivotValue) {
81+
high--;
82+
}
83+
swap(nums, low, high);
84+
}
85+
86+
swap(nums, low, pivot);
87+
88+
return low;
89+
}
90+
91+
private void swap(int[] nums, int x, int y) {
92+
int temp = nums[x];
93+
nums[x] = nums[y];
94+
nums[y] = temp;
95+
}
96+
}
97+
98+
2199
/*
22100
Recap 12.09.2015.
23101
O(n) means just run through it. It's similar to Partition array: it tries to split the list into 2 parts, and find the pivot.
@@ -36,72 +114,52 @@
36114
*/
37115
public class Solution {
38116
/**
39-
* @param nums: A list of integers.
40-
* @return: An integer denotes the middle number of the array.
117+
* @param nums: A list of integers
118+
* @return: An integer denotes the middle number of the array
41119
*/
42120
public int median(int[] nums) {
43121
if (nums == null || nums.length == 0) {
44122
return 0;
45123
}
46-
if (nums.length % 2 == 0) {
47-
return helper(nums, 0, nums.length - 1, nums.length/2 - 1);
48-
} else {
49-
return helper(nums, 0, nums.length - 1, nums.length/2);
124+
if (nums.length == 1) {
125+
return nums[0];
50126
}
127+
int n = nums.length;
128+
return quickSort(nums, 0, n - 1, (n - 1)/ 2);
51129
}
52130

53-
public void swap(int[] nums, int x, int y){
54-
int temp = nums[x];
55-
nums[x] = nums[y];
56-
nums[y] = temp;
57-
}
58-
59-
public int helper(int[] nums, int start, int end, int mid) {
131+
private int quickSort(int[] nums, int start, int end, int target) {
60132
int pivot = end;
61-
int num = nums[pivot];
133+
int pivotValue = nums[pivot];
62134
int low = start;
63135
int high = end;
64136
while (low < high) {
65-
while(low < high && nums[low] < num) {
137+
while (low < high && nums[low] < pivotValue) {
66138
low++;
67139
}
68-
while(low < high && nums[high] >= num) {
140+
while (low < high && nums[high] >= pivotValue) {
69141
high--;
70142
}
71143
swap(nums, low, high);
72144
}
145+
73146
swap(nums, low, pivot);
74-
if (low == mid) {
147+
// dfs
148+
if (low == target) {
75149
return nums[low];
76-
} else if (low < mid) {
77-
return helper(nums, low + 1, end, mid);
150+
} else if (low < target) {
151+
return quickSort(nums, low + 1, end, target);
78152
} else {
79-
return helper(nums, start, low - 1, mid);
153+
return quickSort(nums, start, low - 1, target);
80154
}
81155
}
156+
157+
private void swap(int[] nums, int x, int y) {
158+
int temp = nums[x];
159+
nums[x] = nums[y];
160+
nums[y] = temp;
161+
}
82162
}
83163

84164

85-
86-
87-
88-
89-
90-
91-
92-
93-
94-
95-
96-
97-
98-
99-
100-
101-
102-
103-
104-
105-
106-
107-
165+
```

0 commit comments

Comments
 (0)