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

Commitad4b7c2

Browse files
committed
sqrt
1 parentb41b082 commitad4b7c2

File tree

2 files changed

+89
-1
lines changed

2 files changed

+89
-1
lines changed

‎algorithm/interviews/uber/Example.java

Lines changed: 50 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,26 @@
22

33
importjava.util.*;
44
publicclassExample {
5+
publicstaticvoidmain(String[]strs) {
6+
printArray(sqrt2(100));
7+
printArray(sqrt2(300));
8+
printArray(sqrt2(400));
9+
printArray(sqrt2(1));
10+
printArray(sqrt2(0));
11+
printArray(sqrt2(-4));
12+
}
13+
14+
publicstaticvoidprintArray(int[]in) {
15+
for (inti =0;i <in.length;i++) {
16+
System.out.print(in[i] +" ");
17+
}
18+
19+
System.out.println();
20+
}
21+
522
/* sqrt(100) => 10,1 , sqrt(300) => 10,3 300 = 10^2 * 3 */
623
// Running time: O(sqrt(n))
7-
publicint[]sqrt(intnum){
24+
publicstaticint[]sqrt(intnum){
825
int[]rst = {-1,-1};
926

1027
if (num <0){// edge case
@@ -23,6 +40,38 @@ public int[] sqrt(int num){
2340
returnrst;
2441
}
2542

43+
// Author: Yu Zhang.
44+
publicstaticint[]sqrt2(intn) {
45+
int[]rst = {-1, -1};
46+
47+
if (n <0) {
48+
returnrst;
49+
}
50+
51+
if (n ==0) {
52+
rst[0] =0;
53+
rst[1] =0;
54+
returnrst;
55+
}
56+
57+
intsqrNum = (int)Math.sqrt(n);
58+
59+
//System.out.println("sqrNum:" + sqrNum);
60+
61+
while (sqrNum >=1) {
62+
if (n % (sqrNum *sqrNum) ==0) {
63+
rst[0] =n;
64+
rst[1] =n / (sqrNum *sqrNum);
65+
// bug: forget to return.
66+
returnrst;
67+
}
68+
69+
sqrNum--;
70+
}
71+
72+
returnrst;
73+
}
74+
2675
/* given a number, find the next prime which is bigger than it */
2776
// Running time: O(nlogm) => m is an average recursion depth for each number, how to optimize it?
2877
publicintgetNextPrime(intvalue){

‎algorithm/interviews/uber/FindEqualIndex.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,9 @@ public static void main(String[] str) {
99

1010
int[]input2 = {-4,-3,-2,-1,3,4,6,7,8,9,10,11};
1111
System.out.println(findEqual(input2));
12+
13+
int[]input3 = {-4, -3, -2, -1,3,4,6,7,9,10,11,13};
14+
System.out.println(findEqual2(input3));
1215
}
1316

1417
publicstaticArrayList<Integer>findEqual(int[]input) {
@@ -57,4 +60,40 @@ public static ArrayList<Integer> findEqual(int[] input) {
5760

5861
returnret;
5962
}
63+
64+
/*
65+
* Author: He Long.
66+
*/
67+
publicstaticArrayList<Integer>findEqual2(int[]A) {
68+
ArrayList<Integer>res =newArrayList<Integer>();
69+
if (A ==null ||A.length ==0) {
70+
returnres;
71+
}
72+
intll =0;
73+
intlr =A.length -1;
74+
while (ll <=lr) {
75+
intm =ll + (lr -ll) /2;
76+
if (A[m] -m <0) {
77+
ll =m +1;
78+
}else {
79+
lr =m -1;
80+
}
81+
}
82+
intrl =0;
83+
intrr =A.length -1;
84+
while (rl <=rr) {
85+
intm =rl + (rr -rl) /2;
86+
if (A[m] -m <=0) {
87+
rl =m +1;
88+
}else {
89+
rr =m -1;
90+
}
91+
}
92+
if (ll <=rr) {
93+
while (ll <=rr) {
94+
res.add(A[ll++]);
95+
}
96+
}
97+
returnres;
98+
}
6099
}

0 commit comments

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