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

Commit55f35f9

Browse files
committed
275 (2) add template solution
1 parent6c4b42a commit55f35f9

File tree

3 files changed

+210
-5
lines changed

3 files changed

+210
-5
lines changed

‎src/_275_HIndexII/Solution.java

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -19,25 +19,23 @@
1919
/** see test {@link _275_HIndexII.SolutionTest } */
2020
publicclassSolution {
2121

22+
// find first i where nums[i] >= n - i
2223
publicinthIndex(int[]nums) {
2324
intn =nums.length;
2425
if (n ==0) {
2526
return0;
2627
}
2728
intleft =0;
28-
intright =nums.length -1;
29+
intright =n -1;
2930
while (left <=right) {
3031
intmid =left + (right -left) /2;
3132
inttarget =n -mid;
32-
if (nums[mid] ==target) {
33-
returnnums[mid];
34-
}elseif (nums[mid] >target) {
33+
if (nums[mid] >=target) {
3534
right =mid -1;
3635
}else {
3736
left =mid +1;
3837
}
3938
}
4039
returnn -right -1;
4140
}
42-
4341
}
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/**
2+
* Time : O(lgN) ; Space: O(1)
3+
* @tag : Binary Search
4+
* @by : Steven Cooks
5+
* @date: Sep 25, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* Follow up for H-Index: What if the citations array is sorted in ascending
10+
* order? Could you optimize your algorithm?
11+
*
12+
* Hint: Expected runtime complexity is in O(log n) and the input is sorted.
13+
*
14+
***************************************************************************
15+
* {@link https://leetcode.com/problems/h-index-ii/ }
16+
*/
17+
package_275_HIndexII;
18+
19+
/** see test {@link _275_HIndexII.SolutionTest } */
20+
publicclassSolutionTemplate {
21+
22+
// find the first index i where nums[i] >= n - i
23+
// invariant:
24+
// the first index i where nums[i] >= n - i is within [left : right] if exists
25+
publicinthIndex(int[]nums) {
26+
intn =nums.length;
27+
if (n ==0) {
28+
return0;
29+
}
30+
intleft =0;
31+
intright =n -1;
32+
while (left +1 <right) {
33+
intmid =left + (right -left) /2;
34+
if (nums[mid] >=n -mid) {
35+
right =mid;
36+
}else {
37+
left =mid;
38+
}
39+
}
40+
41+
if (nums[left] >=n -left) {
42+
returnn -left;
43+
}elseif (nums[right] >=n -right) {
44+
returnn -right;
45+
}else {
46+
return0;
47+
}
48+
}
49+
50+
}
Lines changed: 157 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,157 @@
1+
package_275_HIndexII;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.After;
6+
importorg.junit.Before;
7+
importorg.junit.Rule;
8+
importorg.junit.Test;
9+
importorg.junit.rules.Timeout;
10+
11+
publicclassSolutionTemplateTest {
12+
13+
/** Test method for {@link _275_HIndexII.SolutionTemplate } */
14+
SolutionTemplatesolution;
15+
16+
@Rule
17+
publicTimeoutglobalTimeout =newTimeout(200);
18+
19+
@Before
20+
publicvoidsetUp()throwsException {
21+
solution =newSolutionTemplate();
22+
}
23+
24+
@After
25+
publicvoidtearDown()throwsException {
26+
solution =null;
27+
}
28+
29+
@Test
30+
publicvoidTest0() {
31+
int[]citations = { };
32+
intactual =solution.hIndex(citations);
33+
intexpected =0;
34+
assertEquals(expected,actual);
35+
}
36+
37+
@Test
38+
publicvoidTest1() {
39+
int[]citations = {0 };
40+
intactual =solution.hIndex(citations);
41+
intexpected =0;
42+
assertEquals(expected,actual);
43+
}
44+
45+
@Test
46+
publicvoidTest2() {
47+
int[]citations = {5,5,5,5,7 };
48+
intactual =solution.hIndex(citations);
49+
intexpected =5;
50+
assertEquals(expected,actual);
51+
}
52+
53+
@Test
54+
publicvoidTest3() {
55+
int[]citations = {0,5,5,6,8 };
56+
intactual =solution.hIndex(citations);
57+
intexpected =4;
58+
assertEquals(expected,actual);
59+
}
60+
61+
@Test
62+
publicvoidTest4() {
63+
int[]citations = {0,0,0,0,0 };
64+
intactual =solution.hIndex(citations);
65+
intexpected =0;
66+
assertEquals(expected,actual);
67+
}
68+
69+
@Test
70+
publicvoidTest5() {
71+
int[]citations = {1,2,3,4,5 };
72+
intactual =solution.hIndex(citations);
73+
intexpected =3;
74+
assertEquals(expected,actual);
75+
}
76+
77+
@Test
78+
publicvoidTest6() {
79+
int[]citations = {2,5 };
80+
intactual =solution.hIndex(citations);
81+
intexpected =2;
82+
assertEquals(expected,actual);
83+
}
84+
85+
@Test
86+
publicvoidTest7() {
87+
int[]citations = {1,8 };
88+
intactual =solution.hIndex(citations);
89+
intexpected =1;
90+
assertEquals(expected,actual);
91+
}
92+
93+
@Test
94+
publicvoidTest8() {
95+
int[]citations = {0,1 };
96+
intactual =solution.hIndex(citations);
97+
intexpected =1;
98+
assertEquals(expected,actual);
99+
}
100+
101+
@Test
102+
publicvoidTest9() {
103+
int[]citations = {0,0 };
104+
intactual =solution.hIndex(citations);
105+
intexpected =0;
106+
assertEquals(expected,actual);
107+
}
108+
109+
@Test
110+
publicvoidTest10() {
111+
int[]citations = {11,15 };
112+
intactual =solution.hIndex(citations);
113+
intexpected =2;
114+
assertEquals(expected,actual);
115+
}
116+
117+
@Test
118+
publicvoidTest11() {
119+
int[]citations = {100 };
120+
intactual =solution.hIndex(citations);
121+
intexpected =1;
122+
assertEquals(expected,actual);
123+
}
124+
125+
@Test
126+
publicvoidTest12() {
127+
int[]citations = {1 };
128+
intactual =solution.hIndex(citations);
129+
intexpected =1;
130+
assertEquals(expected,actual);
131+
}
132+
133+
@Test
134+
publicvoidTest13() {
135+
int[]citations = {0 };
136+
intactual =solution.hIndex(citations);
137+
intexpected =0;
138+
assertEquals(expected,actual);
139+
}
140+
141+
@Test
142+
publicvoidTest14() {
143+
int[]citations = {1,1,2,3,4,5,7 };
144+
intactual =solution.hIndex(citations);
145+
intexpected =3;
146+
assertEquals(expected,actual);
147+
}
148+
149+
@Test
150+
publicvoidTest15() {
151+
int[]citations = {0,0,1 };
152+
intactual =solution.hIndex(citations);
153+
intexpected =1;
154+
assertEquals(expected,actual);
155+
}
156+
157+
}

0 commit comments

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