Skip to content

Commit cb5dc93

Browse files
Serena211Serena211
committed
recursion
1 parent a0630a4 commit cb5dc93

14 files changed

Lines changed: 316 additions & 0 deletions

‎bin/Class02_Recursion/ClassicBinarySearch.class‎

1.07 KB
Binary file not shown.

‎bin/Class02_Recursion/ClosestInSortedArray.class‎

1.24 KB
Binary file not shown.

‎bin/Class02_Recursion/Fibonacci.class‎

851 Bytes
Binary file not shown.

‎bin/Class02_Recursion/FirstOccurrence.class‎

1.05 KB
Binary file not shown.

‎bin/Class02_Recursion/LastOccurrence.class‎

1.08 KB
Binary file not shown.

‎bin/Class02_Recursion/aToThePowerOfb.class‎

1.06 KB
Binary file not shown.

‎bin/Class06_Graph2/Cents99_arraylist.class‎

0 Bytes
Binary file not shown.

‎src/Class02_Recursion/ClassicBinarySearch.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package Class02_Recursion;
2+
/*
3+
* Given a target integer T and an integer array A sorted in
4+
* ascending order, find the index i such that A[i] == T or
5+
* return -1 if there is no such index.
6+
*
7+
* Assumptions
8+
* There can be duplicate elements in the array, and you can
9+
* return any of the indices i such that A[i] == T.
10+
*
11+
* Examples
12+
* A = {1, 2, 3, 4, 5}, T = 3, return 2
13+
* A = {1, 2, 3, 4, 5}, T = 6, return -1
14+
* A = {1, 2, 2, 2, 3, 4}, T = 2, return 1 or 2 or 3
15+
*
16+
* Corner Cases
17+
* What if A is null or A is of zero length?
18+
* We should return -1 in this case.
19+
* */
20+
public class ClassicBinarySearch {
21+
public static int binarySearch(int[] array, int target) {
22+
if(array == null || array.length == 0) {
23+
return -1;
24+
}
25+
int rsl = helper(array, target, 0, array.length - 1);
26+
return rsl;
27+
}
28+
private static int helper(int[] array, int target, int left, int right) {
29+
// TODO Auto-generated method stub
30+
// if don't find target, return -1
31+
if(left > right ) {
32+
return -1;
33+
}
34+
//base case:
35+
int mid = left + (right - left) / 2;
36+
if(array[mid] == target) {
37+
return mid;
38+
}
39+
//recursion rules:
40+
if (array[mid] < target) {
41+
return helper(array, target, mid + 1, right);
42+
} else {
43+
return helper(array, target, left, mid - 1);
44+
}
45+
}
46+
public static void main(String[] args) {
47+
// TODO Auto-generated method stub
48+
int[] arr = new int[]{1,3,5,7,12,13,19,22};
49+
int rsl = binarySearch(arr, 4);
50+
System.out.println(rsl);
51+
}
52+
53+
}

‎src/Class02_Recursion/ClosestInSortedArray.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package Class02_Recursion;
2+
/*
3+
* Given a target integer T and an integer array A sorted
4+
* in ascending order, find the index i in A such that A[i]
5+
* is closest to T.
6+
*
7+
* Assumptions
8+
* There can be duplicate elements in the array, and we can
9+
* return any of the indices with same value.
10+
*
11+
* Examples
12+
* A = {1, 2, 3}, T = 2, return 1
13+
* A = {1, 4, 6}, T = 3, return 1
14+
* A = {1, 4, 6}, T = 5, return 1 or 2
15+
* A = {1, 3, 3, 4}, T = 2, return 0 or 1 or 2
16+
*
17+
* Corner Cases
18+
* What if A is null or A is of zero length?
19+
* We should return -1 in this case.
20+
* */
21+
public class ClosestInSortedArray {
22+
public static int closest(int[] array, int target) {
23+
//corner case:
24+
if(array == null || array.length == 0) {
25+
return -1;
26+
}
27+
return helper(array, target, 0, array.length - 1, -1, Integer.MAX_VALUE);
28+
}
29+
private static int helper(int[] array, int target, int left, int right, int tempRsl, int gap) {
30+
if (left > right) {
31+
return tempRsl;
32+
}
33+
int mid = left + (right - right) / 2;
34+
if(array[mid] == target) {
35+
tempRsl = mid;
36+
return tempRsl;
37+
} else if(array[mid] < target) {
38+
int tempGap = Math.abs(target - array[mid]);
39+
if(tempGap < gap) {
40+
gap = tempGap;
41+
tempRsl = mid;
42+
}
43+
return helper(array, target, mid + 1, right, tempRsl,gap);
44+
} else {
45+
int tempGap = Math.abs(target - array[mid]);
46+
if(tempGap < gap) {
47+
gap = tempGap;
48+
tempRsl = mid;
49+
}
50+
return helper(array, target, left, mid - 1, tempRsl, tempGap);
51+
}
52+
}
53+
public static void main(String[] args) {
54+
// TODO Auto-generated method stub
55+
int[] arr = new int[]{0};
56+
int rsl = closest(arr, 0);
57+
System.out.println(rsl);
58+
}
59+
60+
}

‎src/Class02_Recursion/Fibonacci.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package Class02_Recursion;
2+
/*
3+
* Get the Kth number in the Fibonacci Sequence.
4+
* (K is 0-indexed, the 0th Fibonacci number is
5+
* 0 and the 1st Fibonacci number is 1).
6+
*
7+
* Examples
8+
* 0th fibonacci number is 0
9+
* 1st fibonacci number is 1
10+
* 2nd fibonacci number is 1
11+
* 6th fibonacci number is 8
12+
*
13+
* Corner Cases
14+
* 1. What if K < 0? in this case, we should always return 0.
15+
* 2. Is it possible the result fibonacci number is overflowed?
16+
* We can assume it will not be overflowed when we solve this
17+
* problem on this online judge, but we should also know that
18+
* it is possible to get an overflowed number, and sometimes we
19+
* will need to use something like BigInteger.
20+
* */
21+
public class Fibonacci {
22+
public static long fibonacci(int K) {
23+
if (K <= 0) {
24+
return 0;
25+
}
26+
long[] fn = new long[3];
27+
for (int i = 0; i <= K; i++) {
28+
if (i == 0) {
29+
fn[0] = 0;
30+
} else if(i == 1) {
31+
fn[1] = 1;
32+
} else {
33+
fn[2] = fn[0] + fn[1];
34+
fn[0] = fn[1];
35+
fn[1] = fn[2];
36+
}
37+
}
38+
return fn[1];
39+
}
40+
public static void main(String[] args) {
41+
long rsl = fibonacci(50);
42+
System.out.println(rsl);
43+
}
44+
45+
}

0 commit comments

Comments
 (0)