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

Commit0ef14c1

Browse files
[LEET-556] add 556
1 parentf29db46 commit0ef14c1

File tree

3 files changed

+119
-0
lines changed

3 files changed

+119
-0
lines changed

‎leetcode-algorithms/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
55
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
66
|557|[Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ReverseWordsinaStringIII.java) | O(n) |O(n) | Easy | String
7+
|556|[Next Greater Element III](https://leetcode.com/problems/next-greater-element-iii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/NextGreaterElementIII.java) | O(n)|O(1)| Medium | String
78
|554|[Brick Wall](https://leetcode.com/problems/brick-wall/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/BrickWall.java) | O(n) (n is total number of bricks in the wall) |O(m) (m is width of the wall) | Medium | HashMap
89
|549|[Binary Tree Longest Consecutive Sequence II](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/BinaryTreeLongestConsecutiveSequenceII.java) | O(n) |O(n) | Medium | Tree
910
|548|[Split Array with Equal Sum](https://leetcode.com/problems/split-array-with-equal-sum/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/SplitArraywithEqualSum.java) | O(n^2) |O(1) | Medium | Array
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
packagecom.stevesun.solutions;
2+
3+
/**
4+
* Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing
5+
* in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
6+
* <p>
7+
* Example 1:
8+
* Input: 12
9+
* Output: 21
10+
* <p>
11+
* Example 2:
12+
* Input: 21
13+
* Output: -1
14+
*/
15+
publicclassNextGreaterElementIII {
16+
//credit: https://discuss.leetcode.com/topic/85759/this-problem-is-the-same-to-next-permutation-algorithm-only and https://discuss.leetcode.com/topic/85755/java-solution-like-next-permutation-problem-o-n
17+
18+
publicintnextGreaterElement(intn) {
19+
char[]digits =String.valueOf(n).toCharArray();
20+
inti =digits.length -2;
21+
while (i >=0 &&digits[i +1] <=digits[i]) {
22+
i--;
23+
}
24+
if(i<0)return -1;
25+
intj =digits.length -1;
26+
while (j >=0 &&digits[j] <=digits[i]) {
27+
j--;
28+
}
29+
swap(digits,i,j);
30+
reverse(digits,i +1);
31+
try{
32+
returnInteger.parseInt(newString(digits));
33+
}
34+
catch(Exceptione){
35+
return -1;
36+
}
37+
}
38+
privatevoidreverse(char[]a,intstart) {
39+
inti =start,j =a.length -1;
40+
while (i <j) {
41+
swap(a,i,j);
42+
i++;
43+
j--;
44+
}
45+
}
46+
privatevoidswap(char[]a,inti,intj) {
47+
chartemp =a[i];
48+
a[i] =a[j];
49+
a[j] =temp;
50+
}
51+
52+
}
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
packagecom.stevesun;
2+
3+
importcom.stevesun.solutions.NextGreaterElementIII;
4+
importorg.junit.Before;
5+
importorg.junit.BeforeClass;
6+
importorg.junit.Test;
7+
8+
importstaticorg.junit.Assert.assertEquals;
9+
importstaticorg.junit.Assert.assertTrue;
10+
11+
publicclassNextGreaterElementIIITest {
12+
privatestaticNextGreaterElementIIItest;
13+
privatestaticintn;
14+
privatestaticintexpected;
15+
privatestaticintactual;
16+
17+
@BeforeClass
18+
publicstaticvoidsetup(){
19+
test =newNextGreaterElementIII();
20+
}
21+
22+
@Before
23+
publicvoidsetupForEachTest(){}
24+
25+
@Test
26+
publicvoidtest1(){
27+
n =12;
28+
expected =21;
29+
actual =test.nextGreaterElement(n);
30+
assertEquals(expected,actual);
31+
}
32+
33+
@Test
34+
publicvoidtest2(){
35+
n =21;
36+
expected = -1;
37+
actual =test.nextGreaterElement(n);
38+
assertEquals(expected,actual);
39+
assertTrue(Integer.MAX_VALUE >1999999999);
40+
}
41+
42+
@Test
43+
publicvoidtest3(){
44+
n =1999999999;
45+
expected = -1;
46+
actual =test.nextGreaterElement(n);
47+
assertEquals(expected,actual);
48+
}
49+
50+
@Test
51+
publicvoidtest4(){
52+
n =12222333;
53+
expected =12223233;
54+
actual =test.nextGreaterElement(n);
55+
assertEquals(expected,actual);
56+
}
57+
58+
@Test
59+
publicvoidtest5(){
60+
n =12443322;
61+
expected =13222344;
62+
actual =test.nextGreaterElement(n);
63+
assertEquals(expected,actual);
64+
}
65+
66+
}

0 commit comments

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