Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5cb3977

Browse files
author
applewjg
committed
Maximum Gap && ZigZag Conversion
1 parentc2d2ee9 commit5cb3977

File tree

2 files changed

+108
-0
lines changed

2 files changed

+108
-0
lines changed

‎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+
publicclassSolution {
24+
publicintmaximumGap_1(int[]num) {
25+
Arrays.sort(num);
26+
intres =0;
27+
for (inti =1;i <num.length; ++i) {
28+
res =Math.max(res,num[i] -num[i -1]);
29+
}
30+
returnres;
31+
}
32+
classnode {
33+
publicintlow;
34+
publicinthigh;
35+
publicnode() {
36+
low = -1;
37+
high = -1;
38+
}
39+
}
40+
publicintmaximumGap_2(int[]num) {
41+
intn =num.length;
42+
if (n <2)return0;
43+
intminVal =num[0],maxVal =num[0];
44+
for (inti =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 =newnode[n+2];
51+
for (inti =0;i <n+2; ++i)pool[i] =newnode();
52+
for (inti =0;i <n; ++i) {
53+
intidx =(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+
intpre =pool[0].high;
62+
intres =0;
63+
for (inti =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+
returnres;
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+
publicclassSolution {
23+
publicStringconvert(Strings,intnRows) {
24+
intn =s.length();
25+
if (n <=1 ||nRows <=1)returns;
26+
StringBufferres =newStringBuffer();
27+
for (inti =0;i <nRows; ++i) {
28+
for (intj =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+
returnres.toString();
36+
}
37+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp