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

Commit0c84040

Browse files
[LEET-487] add 487
1 parent4dafe03 commit0c84040

File tree

3 files changed

+105
-0
lines changed

3 files changed

+105
-0
lines changed

‎leetcode-algorithms/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@
2929
|494|[Target Sum](https://leetcode.com/problems/target-sum/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/TargetSum.java)| O(2^n)|O(1)| Medium|
3030
|492|[Construct the Rectangle](https://leetcode.com/problems/construct-the-rectangle/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ConstructTheRectangle.java) | O(n) |O(1) | Easy| Array
3131
|490|[The Maze](https://leetcode.com/problems/the-maze/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/TheMaze.java) | O(m*n) |O(m*n) | Medium| BFS
32+
|487|[Max Consecutive Ones II](https://leetcode.com/problems/max-consecutive-ones-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MaxConsecutiveOnesII.java) | O(n) |O(n) | Medium| Array
3233
|485|[Max Consecutive Ones](https://leetcode.com/problems/max-consecutive-ones/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MaxConsecutiveOnes.java) | O(n) |O(1) | Easy| Array
3334
|482|[License Key Formatting](https://leetcode.com/problems/license-key-formatting/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/LicenseKeyFormatting.java)| O(n)|O(n)| Medium|
3435
|477|[Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/TotalHammingDistance.java) | O(n) |O(1) | Medium| Bit Manipulation
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packagecom.stevesun.solutions;
2+
3+
/**
4+
* Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.
5+
6+
Example 1:
7+
8+
Input: [1,0,1,1,0]
9+
Output: 4
10+
11+
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
12+
After flipping, the maximum number of consecutive 1s is 4.
13+
14+
Note:
15+
The input array will only contain 0 and 1.
16+
The length of input array is a positive integer and will not exceed 10,000
17+
18+
Follow up:
19+
What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
20+
*/
21+
publicclassMaxConsecutiveOnesII {
22+
//TODO: could be optimized to O(1) space
23+
publicintfindMaxConsecutiveOnes(int[]nums) {
24+
int[]numSums =newint[nums.length];
25+
numSums[0] =nums[0];
26+
for (inti =1;i <nums.length;i++) {
27+
if (nums[i] ==1) {
28+
numSums[i] =numSums[i-1]+1;
29+
}else {
30+
numSums[i] =0;
31+
}
32+
}
33+
intmax =0;
34+
for (inti =0;i <nums.length;i++) {
35+
if (nums[i] ==0) {
36+
intright =i+1;
37+
while (right <nums.length &&nums[right] !=0) {
38+
right++;
39+
}
40+
intnewMax = (i >0) ?numSums[i-1] +1 +numSums[right-1] :1 +numSums[right-1];
41+
max =Math.max(max,newMax);
42+
}
43+
if (i ==0 &&nums[i] ==1)max =1;
44+
max =Math.max(max,numSums[i]);
45+
}
46+
returnmax;
47+
}
48+
49+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
packagecom.stevesun;
2+
3+
importcom.stevesun.solutions.MaxConsecutiveOnesII;
4+
importorg.junit.Before;
5+
importorg.junit.BeforeClass;
6+
importorg.junit.Test;
7+
8+
importstaticjunit.framework.Assert.assertEquals;
9+
10+
publicclassMaxConsecutiveOnesIITest {
11+
privatestaticMaxConsecutiveOnesIItest;
12+
privatestaticintexpected;
13+
privatestaticintactual;
14+
privatestaticint[]nums;
15+
16+
@BeforeClass
17+
publicstaticvoidsetup(){
18+
test =newMaxConsecutiveOnesII();
19+
}
20+
21+
@Before
22+
publicvoidsetupForEachTest(){}
23+
24+
@Test
25+
publicvoidtest1(){
26+
nums =newint[]{1,0,1,1,0};
27+
expected =4;
28+
actual =test.findMaxConsecutiveOnes(nums);
29+
assertEquals(expected,actual);
30+
}
31+
32+
@Test
33+
publicvoidtest2(){
34+
nums =newint[]{1};
35+
expected =1;
36+
actual =test.findMaxConsecutiveOnes(nums);
37+
assertEquals(expected,actual);
38+
}
39+
40+
@Test
41+
publicvoidtest3(){
42+
nums =newint[]{0};
43+
expected =1;
44+
actual =test.findMaxConsecutiveOnes(nums);
45+
assertEquals(expected,actual);
46+
}
47+
48+
@Test
49+
publicvoidtest4(){
50+
nums =newint[]{1,1};
51+
expected =2;
52+
actual =test.findMaxConsecutiveOnes(nums);
53+
assertEquals(expected,actual);
54+
}
55+
}

0 commit comments

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