Skip to content

Commit b80d6a0

Browse files
walnutownwalnutown
committed
Target 7 today!!
1 parent 94bdf07 commit b80d6a0

4 files changed

Lines changed: 170 additions & 0 deletions

File tree

‎LeetCode/ClimbingStairs.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
// no pass the large judge, time limit exceed
2+
3+
public int climbingStairs(int num){
4+
if (num == 0){
5+
return 0;
6+
}
7+
if (num == 1){
8+
return 1;
9+
}
10+
if (num == 2){
11+
return 2;
12+
}
13+
14+
return climbingStairs(num -1) + 1 + climbingStairs(num -2) + 2;
15+
}
16+
17+
// DP memoization, pass both
18+
public class Solution {
19+
public int climbStairs(int n) {
20+
// Start typing your Java solution below
21+
// DO NOT write main() function
22+
23+
ArrayList<Integer> mem = new ArrayList<Integer>();
24+
mem.add(0, 0);
25+
mem.add(1, 1);
26+
mem.add(2, 2);
27+
int i = 3;
28+
while ( i <= n){
29+
mem.add(i, mem.get(i-2) + mem.get(i-1)) ;
30+
i++;
31+
}
32+
33+
return mem.get(n);
34+
}
35+
}

‎LeetCode/Pow.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
// not pass large judge
2+
public class Solution {
3+
public double pow(double x, int n) {
4+
// Start typing your Java solution below
5+
// DO NOT write main() function
6+
if (n == 0){
7+
return 1;
8+
}
9+
10+
boolean neg = x < 0 && n%2 != 0 ? true: false;
11+
x = Math.abs(x);
12+
double res = 1;
13+
if (n > 0){
14+
res = x;
15+
for (int i = 1; i < n; i++){
16+
res *= x;
17+
}
18+
}
19+
if (n < 0){
20+
res = 1/x;
21+
for (int i = -1; i > n; i--){
22+
res /= x;
23+
}
24+
}
25+
26+
return neg? -res : res;
27+
28+
}
29+
}
30+
31+
32+
public class Solution {
33+
public double pow(double x, int n) {
34+
// Start typing your Java solution below
35+
// DO NOT write main() functio
36+
37+
if (n < 0){
38+
return 1.0 / power(x, -n);
39+
}
40+
else if (n > 0){
41+
return power(x, n);
42+
}
43+
else{
44+
return 1.0;
45+
}
46+
47+
}
48+
49+
public double power(double x, int n){
50+
if (n == 0){
51+
return 1;
52+
}
53+
double v = power(x, n/2);
54+
if (n % 2 == 0){
55+
return v * v;
56+
}
57+
else{
58+
return v * v * x;
59+
}
60+
}
61+
}

‎LeetCode/SortColors.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
// counting sort, and reconstruct the array
2+
3+
public void sortColors(){
4+
5+
}
6+
7+
// use 3 ints to store the pos of 3 colors, seem to be the same as storing num of colors
8+
// radix sort

‎LeetCode/Sqrt.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
public class Solution {
2+
public int sqrt(int x) {
3+
// Start typing your Java solution below
4+
// DO NOT write main() function
5+
if (x == 0){
6+
return 0;
7+
}
8+
if (x == 1){
9+
return 1;
10+
}
11+
12+
int start = 0;
13+
//int end = x;
14+
int end = x/2 < Math.sqrt(Integer.MAX_VALUE)? x/2 + 1 : (int)Math.sqrt(Integer.MAX_VALUE);
15+
while (start <= end){
16+
int mid = start + (end - start)/2;
17+
int sqr = mid * mid;
18+
if (sqr < x){
19+
start = mid +1;
20+
}
21+
else if (sqr > x){
22+
end = mid -1;
23+
}
24+
else{
25+
return mid;
26+
}
27+
28+
}
29+
30+
return (start+end)/2;
31+
}
32+
}
33+
34+
35+
// no nned to judge mid < sqrt(INT_MAX), use mid < x/mid, instead of mid * mid < x, to avoid overflows
36+
public class Solution {
37+
public int sqrt(int x) {
38+
// Start typing your Java solution below
39+
// DO NOT write main() function
40+
if (x == 0){
41+
return 0;
42+
}
43+
// avoid mid == 0
44+
if (x == 1){
45+
return 1;
46+
}
47+
48+
int start = 0;
49+
int end = x;
50+
while (start <= end){
51+
int mid = start + (end - start)/2;
52+
int temp = x/mid;
53+
if (mid < temp){
54+
start = mid +1;
55+
}
56+
else if (mid > temp){
57+
end = mid -1;
58+
}
59+
else{
60+
return mid;
61+
}
62+
63+
}
64+
return (start+end)/2;
65+
}
66+
}

0 commit comments

Comments
 (0)