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

Commit273ed68

Browse files
committed
069 (3) add binary search template solution
1 parent63ebfda commit273ed68

File tree

3 files changed

+119
-0
lines changed

3 files changed

+119
-0
lines changed

‎src/_069_Sqrtx/Solution.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
/** see test {@link _069_Sqrtx.SolutionTest } */
1818
publicclassSolution {
1919

20+
// find the last value that value*value <= x
2021
publicintmySqrt(intx) {
2122
if (x ==0) {
2223
return0;
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/**
2+
* Time : O(logN); Space: O(1)
3+
* @tag : Math; Binary Search
4+
* @by : Steven Cooks
5+
* @date: Jun 5, 2015
6+
*************************************************************************
7+
* Description
8+
*
9+
* Implement int sqrt(int x).
10+
* Compute and return the square root of x.
11+
*
12+
*************************************************************************
13+
* {@link https://leetcode.com/problems/sqrtx/ }
14+
*/
15+
package_069_Sqrtx;
16+
17+
/** see test {@link _069_Sqrtx.SolutionTest } */
18+
publicclassSolutionTemplate {
19+
20+
// take advantage of binary search template
21+
/**
22+
* Since target is in [left, right], reduce to only two numbers left,
23+
* then solve the subproblem.
24+
*/
25+
publicintmySqrt(intx) {
26+
if (x <=0) {
27+
return0;
28+
}
29+
intleft =1;
30+
intright =x;
31+
while (left +1 <right) {
32+
intmid =left + (right -left) /2;
33+
if (mid >x /mid) {
34+
right =mid;
35+
}else {
36+
left =mid;
37+
}
38+
}
39+
// [left, target, right], choose between left and right
40+
if (left ==x /left) {
41+
returnleft;
42+
}elseif (right ==x /right) {
43+
returnright;
44+
}else {
45+
returnleft;
46+
}
47+
}
48+
49+
}
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package_069_Sqrtx;
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 _069_Sqrtx.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+
publicvoidTest1() {
31+
intx =4;
32+
intactual =solution.mySqrt(x);
33+
intexpected = (int)Math.sqrt(x);
34+
assertEquals(expected,actual);
35+
}
36+
37+
@Test
38+
publicvoidTest2() {
39+
intx =1;
40+
intactual =solution.mySqrt(x);
41+
intexpected = (int)Math.sqrt(x);
42+
assertEquals(expected,actual);
43+
}
44+
45+
@Test
46+
publicvoidTest3() {
47+
intx =9;
48+
intactual =solution.mySqrt(x);
49+
intexpected = (int)Math.sqrt(x);
50+
assertEquals(expected,actual);
51+
}
52+
53+
@Test
54+
publicvoidTest4() {
55+
intx =5;
56+
intactual =solution.mySqrt(x);
57+
intexpected = (int)Math.sqrt(x);
58+
assertEquals(expected,actual);
59+
}
60+
61+
@Test
62+
publicvoidTest5() {
63+
intx =2147483647;
64+
intactual =solution.mySqrt(x);
65+
intexpected = (int)Math.sqrt(x);
66+
assertEquals(expected,actual);
67+
}
68+
69+
}

0 commit comments

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