BLANK
1. Array
2. DP
3. String
4. Sort
1. Array
Naive Method
时间复杂度O(n^2) 空间复杂度O(n^2)
一遍一遍的扫，指导所有的位置都满足要求。非常没有效率的方式，但是应该考虑这种类似DFS，有终止条件的实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public class Solution {
public int candy(int[] ratings) {
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
boolean flag = true;
int sum = 0;
while (flag) {
flag = false;
for (int i = 0; i < ratings.length; i++) {
if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
flag = true;
}
if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
candies[i] = candies[i - 1] + 1;
flag = true;
}
}
}
for (int candy : candies) {
sum += candy;
}
return sum;
}
} |
public class Solution {
public int candy(int[] ratings) {
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
boolean flag = true;
int sum = 0;
while (flag) {
flag = false;
for (int i = 0; i < ratings.length; i++) {
if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
flag = true;
}
if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
candies[i] = candies[i - 1] + 1;
flag = true;
}
}
}
for (int candy : candies) {
sum += candy;
}
return sum;
}
}
Two Array
经典的双向扫描，然后取最大值。
这里，由于对于位置i,左右两边相互独立，这种方式才可以proof。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public int candy(int[] ratings) {
int sum = 0;
int[] left2right = new int[ratings.length];
int[] right2left = new int[ratings.length];
Arrays.fill(left2right, 1);
Arrays.fill(right2left, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
left2right[i] = left2right[i - 1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
right2left[i] = right2left[i + 1] + 1;
}
}
for (int i = 0; i < ratings.length; i++) {
sum += Math.max(left2right[i], right2left[i]);
}
return sum;
}
} |
public class Solution {
public int candy(int[] ratings) {
int sum = 0;
int[] left2right = new int[ratings.length];
int[] right2left = new int[ratings.length];
Arrays.fill(left2right, 1);
Arrays.fill(right2left, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
left2right[i] = left2right[i - 1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
right2left[i] = right2left[i + 1] + 1;
}
}
for (int i = 0; i < ratings.length; i++) {
sum += Math.max(left2right[i], right2left[i]);
}
return sum;
}
}
Two Array：Revise
改进了存储，只用一个array，和方法2是同样的原理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Solution {
public int candy(int[] ratings) {
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
int sum = candies[ratings.length - 1];
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
sum += candies[i];
}
return sum;
}
} |
public class Solution {
public int candy(int[] ratings) {
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
int sum = candies[ratings.length - 1];
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
sum += candies[i];
}
return sum;
}
}
Single Path
非常经典并且高效的做法。O(1)的空间复杂度，O(n)的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| public class Solution {
public int count(int n) {
return (n * (n + 1)) / 2;
}
public int candy(int[] ratings) {
if (ratings.length <= 1) {
return ratings.length;
}
int candies = 0;
int up = 0;
int down = 0;
int old_slope = 0;
for (int i = 1; i < ratings.length; i++) {
int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) {
candies += count(up) + count(down) + Math.max(up, down);
up = 0;
down = 0;
}//到mountain结束的时候计算，包括终点不包括起点
//或者到达平台期，下降平台, First value is 1 one and last one decrese again
//上升平台，first value increase and the other restart form 1
if (new_slope > 0)
up++;
if (new_slope < 0)
down++;
if (new_slope == 0)
candies++;
old_slope = new_slope;
}
candies += count(up) + count(down) + Math.max(up, down) + 1;
return candies;
}
} |
public class Solution {
public int count(int n) {
return (n * (n + 1)) / 2;
}
public int candy(int[] ratings) {
if (ratings.length <= 1) {
return ratings.length;
}
int candies = 0;
int up = 0;
int down = 0;
int old_slope = 0;
for (int i = 1; i < ratings.length; i++) {
int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) {
candies += count(up) + count(down) + Math.max(up, down);
up = 0;
down = 0;
}//到mountain结束的时候计算，包括终点不包括起点
//或者到达平台期，下降平台, First value is 1 one and last one decrese again
//上升平台，first value increase and the other restart form 1
if (new_slope > 0)
up++;
if (new_slope < 0)
down++;
if (new_slope == 0)
candies++;
old_slope = new_slope;
}
candies += count(up) + count(down) + Math.max(up, down) + 1;
return candies;
}
}
2. DP
巧妙地DP
需要考虑到的是，问题和子问题的关系如何设计才满足DP
[j, i] is pal <- c[j] == c[i] && c[j+1][i-1] is pal
j+1 is always next step but i-1 the past step
i is outter loop while j is inner loop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int minCut(String s) {
char[] c = s.toCharArray();
int n = c.length;
int[] cut = new int[n];
boolean[][] pal = new boolean[n][n];
for(int i = 0; i < n; i++) {
int min = i;
for(int j = 0; j <= i; j++) {
if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true; // The table's index is different
min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
// 0 ... j-1 -> j ... i
}
}
cut[i] = min;
}
return cut[n - 1];
}
} |
class Solution {
public int minCut(String s) {
char[] c = s.toCharArray();
int n = c.length;
int[] cut = new int[n];
boolean[][] pal = new boolean[n][n];
for(int i = 0; i < n; i++) {
int min = i;
for(int j = 0; j <= i; j++) {
if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true; // The table's index is different
min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
// 0 ... j-1 -> j ... i
}
}
cut[i] = min;
}
return cut[n - 1];
}
}
3. String
Naive Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public String shortestPalindrome(String s) {
int len = s.length();
char[] a = s.toCharArray();
for(int i =len-1; i>=0; i--){
if(check(a, i)){
int start = i+1;
int end = len -1;
while(start < end){
char temp = a[start];
a[start] = a[end];
a[end] = temp;
start ++;
end --;
}
return new String(a, i+1, len - i-1) + s;
}
}
return "";
}
public boolean check(char[] a, int end){
int start = 0;
while(start < end){
if(a[start] != a[end]){
return false;
}
start++;
end--;
}
return true;
}
} |
class Solution {
public String shortestPalindrome(String s) {
int len = s.length();
char[] a = s.toCharArray();
for(int i =len-1; i>=0; i--){
if(check(a, i)){
int start = i+1;
int end = len -1;
while(start < end){
char temp = a[start];
a[start] = a[end];
a[end] = temp;
start ++;
end --;
}
return new String(a, i+1, len - i-1) + s;
}
}
return "";
}
public boolean check(char[] a, int end){
int start = 0;
while(start < end){
if(a[start] != a[end]){
return false;
}
start++;
end--;
}
return true;
}
}
KMP
A very concise video about KMP
There is a KMP trick.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public String shortestPalindrome(String s) {
String temp = s + "#" + new StringBuilder(s).reverse().toString();
int[] table = getTable(temp);
return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
}
public int[] getTable(String s){
int[] table = new int[s.length()];
int index = 0;
for(int i = 1; i < s.length(); i++){
if(s.charAt(index) == s.charAt(i)){
table[i] = table[i-1] + 1;
index ++;
}else{
index = table[i-1];
while(index > 0 && s.charAt(index) != s.charAt(i)){
index = table[index-1];
}
if(s.charAt(index) == s.charAt(i)){
index ++ ;
}
table[i] = index;
}
}
return table;
}
} |
class Solution {
public String shortestPalindrome(String s) {
String temp = s + "#" + new StringBuilder(s).reverse().toString();
int[] table = getTable(temp);
return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
}
public int[] getTable(String s){
int[] table = new int[s.length()];
int index = 0;
for(int i = 1; i < s.length(); i++){
if(s.charAt(index) == s.charAt(i)){
table[i] = table[i-1] + 1;
index ++;
}else{
index = table[i-1];
while(index > 0 && s.charAt(index) != s.charAt(i)){
index = table[index-1];
}
if(s.charAt(index) == s.charAt(i)){
index ++ ;
}
table[i] = index;
}
}
return table;
}
}
4. Sort
A good demo of redix sort
Redix Sort
时间复杂度O(dn) d is a constant, parhaps larger than logn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
//Sort Method: General built-in sort: O(nlogn)
//Radix Sort: O(dn), d = number of digits
// m is the maximal number in nums
int m = nums[0];
for (int i = 1; i < nums.length; i++) {
m = Math.max(m, nums[i]);
}
int exp = 1;
int R = 10;
int[] aux = new int[nums.length];
while (m / exp > 0) { // Go through all digits from LSB to MSB
int[] count = new int[R];
for (int i = 0; i < nums.length; i++) {
count[(nums[i] / exp) % 10]++;
}
// count times
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// accumulation
for (int i = nums.length - 1; i >= 0; i--) {
aux[--count[(nums[i] / exp) % 10]] = nums[i];
}
// restore
for (int i = 0; i < nums.length; i++) {
nums[i] = aux[i];
} //here ius coverage
// renew the original nums
exp *= 10;
}
int max = 0;
for (int i = 1; i < aux.length; i++) {
max = Math.max(max, aux[i] - aux[i - 1]);
}
return max;
}
} |
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
//Sort Method: General built-in sort: O(nlogn)
//Radix Sort: O(dn), d = number of digits
// m is the maximal number in nums
int m = nums[0];
for (int i = 1; i < nums.length; i++) {
m = Math.max(m, nums[i]);
}
int exp = 1;
int R = 10;
int[] aux = new int[nums.length];
while (m / exp > 0) { // Go through all digits from LSB to MSB
int[] count = new int[R];
for (int i = 0; i < nums.length; i++) {
count[(nums[i] / exp) % 10]++;
}
// count times
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// accumulation
for (int i = nums.length - 1; i >= 0; i--) {
aux[--count[(nums[i] / exp) % 10]] = nums[i];
}
// restore
for (int i = 0; i < nums.length; i++) {
nums[i] = aux[i];
} //here ius coverage
// renew the original nums
exp *= 10;
}
int max = 0;
for (int i = 1; i < aux.length; i++) {
max = Math.max(max, aux[i] - aux[i - 1]);
}
return max;
}
}
Bucket Sort
时间复杂度O(n)
The Pigeonhole Principle
n-1个bucket，n-2个元素，则必定有一个bucket为空，所以 max gap > 1 bukcet.length
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| public int maximumGap(int[] num) {
if (num == null || num.length < 2)
return 0;
// get the max and min value of the array
int min = num[0];
int max = num[0];
for (int i:num) {
min = Math.min(min, i);
max = Math.max(max, i);
}
// the minimum possibale gap, ceiling of the integer division
int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket
int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket
Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
// put numbers into buckets
for (int i:num) {
if (i == min || i == max)
continue;
int idx = (i - min) / gap; // index of the right position in the buckets
bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);
}
// scan the buckets for the max gap
int maxGap = Integer.MIN_VALUE;
int previous = min;
for (int i = 0; i < num.length - 1; i++) {
if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
// empty bucket
continue;
// min value minus the previous value is the current gap
maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
// update previous bucket value
previous = bucketsMAX[i];
}
maxGap = Math.max(maxGap, max - previous); // updata the final max value gap
return maxGap;
} |
public int maximumGap(int[] num) {
if (num == null || num.length < 2)
return 0;
// get the max and min value of the array
int min = num[0];
int max = num[0];
for (int i:num) {
min = Math.min(min, i);
max = Math.max(max, i);
}
// the minimum possibale gap, ceiling of the integer division
int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket
int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket
Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
// put numbers into buckets
for (int i:num) {
if (i == min || i == max)
continue;
int idx = (i - min) / gap; // index of the right position in the buckets
bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);
}
// scan the buckets for the max gap
int maxGap = Integer.MIN_VALUE;
int previous = min;
for (int i = 0; i < num.length - 1; i++) {
if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
// empty bucket
continue;
// min value minus the previous value is the current gap
maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
// update previous bucket value
previous = bucketsMAX[i];
}
maxGap = Math.max(maxGap, max - previous); // updata the final max value gap
return maxGap;
}