Skip to content

Commit 5cb3977

Browse files
author
applewjg
committed
Maximum Gap && ZigZag Conversion
1 parent c2d2ee9 commit 5cb3977

2 files changed

Lines changed: 108 additions & 0 deletions

File tree

‎MaximumGap.java‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 14, 2014
4+
Problem: Maximum Gap
5+
Difficulty: Hard
6+
Source: https://oj.leetcode.com/problems/maximum-gap/
7+
Notes:
8+
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
9+
10+
Try to solve it in linear time/space.
11+
12+
Return 0 if the array contains less than 2 elements.
13+
14+
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
15+
16+
Solution: 1. Time : O(nlogn). Space : O(1);
17+
Sort the unsorted array, and find the maximum difference.
18+
2. Time : O(n). Space : O(n).
19+
Drawer Theory. If we put n numbers into (n+1) drawers,
20+
then there must be at least one empty drawer.
21+
So we can find the maximum difference between two succesive non-empty drawers.
22+
*/
23+
public class Solution {
24+
public int maximumGap_1(int[] num) {
25+
Arrays.sort(num);
26+
int res = 0;
27+
for (int i = 1; i < num.length; ++i) {
28+
res = Math.max(res, num[i] - num[i - 1]);
29+
}
30+
return res;
31+
}
32+
class node {
33+
public int low;
34+
public int high;
35+
public node() {
36+
low = -1;
37+
high = -1;
38+
}
39+
}
40+
public int maximumGap_2(int[] num) {
41+
int n = num.length;
42+
if (n < 2) return 0;
43+
int minVal = num[0], maxVal = num[0];
44+
for (int i = 1; i < n; ++i) {
45+
minVal = Math.min(minVal, num[i]);
46+
maxVal = Math.max(maxVal, num[i]);
47+
}
48+
//delta = (maxVal + 1 - minVal) / (n + 1)
49+
//idx = (val - minVal) / delta = (val - minVal) * (n + 1) / (maxVal + 1 - minVal)
50+
node[] pool = new node[n+2];
51+
for (int i = 0; i < n+2; ++i) pool[i] = new node();
52+
for (int i = 0; i < n; ++i) {
53+
int idx =(int)(Long.valueOf(num[i] - minVal)* Long.valueOf(n + 1) / Long.valueOf(maxVal + 1 - minVal));
54+
if (pool[idx].low == -1) {
55+
pool[idx].low = pool[idx].high = num[i];
56+
} else {
57+
pool[idx].low = Math.min(pool[idx].low, num[i]);
58+
pool[idx].high = Math.max(pool[idx].high, num[i]);
59+
}
60+
}
61+
int pre = pool[0].high;
62+
int res = 0;
63+
for (int i = 1; i < n + 2; ++i) {
64+
if (pool[i].low != -1) {
65+
res = Math.max(res, pool[i].low - pre);
66+
pre = pool[i].high;
67+
}
68+
}
69+
return res;
70+
}
71+
}

‎ZigZagConversion.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 13, 2014
4+
Problem: ZigZag Conversion
5+
Difficulty: Easy
6+
Source: https://oj.leetcode.com/problems/zigzag-conversion/
7+
Notes:
8+
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
9+
10+
P A H N
11+
A P L S I I G
12+
Y I R
13+
And then read line by line: "PAHNAPLSIIGYIR"
14+
Write the code that will take a string and make this conversion given a number of rows:
15+
16+
string convert(string text, int nRows);
17+
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
18+
19+
Solution: ...
20+
*/
21+
22+
public class Solution {
23+
public String convert(String s, int nRows) {
24+
int n = s.length();
25+
if (n <= 1 || nRows <= 1) return s;
26+
StringBuffer res = new StringBuffer();
27+
for (int i = 0; i < nRows; ++i) {
28+
for (int j = 0; j + i < n; j += 2*nRows - 2) {
29+
res.append(s.charAt(j+i));
30+
if (i == 0 || i == nRows - 1) continue;
31+
if (j + 2*nRows - 2 - i < n)
32+
res.append(s.charAt(j + 2*nRows - 2 - i));
33+
}
34+
}
35+
return res.toString();
36+
}
37+
}

0 commit comments

Comments
 (0)