This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static int binarySearch(int[] A, int target){ | |
if (A.length ==0 || A == null ) { | |
return -1; | |
} | |
int start = 0; | |
int end = A.length - 1; | |
int mid; | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.binarySearch; | |
/** | |
* Solution: BinarySearch, two time. 2 O(logn) --> O(logn) | |
* Search left bound first and then search right bound second time. | |
* left: end = mid. right: start = mid. keeps we don't abandon result. | |
* | |
* Take care: sequence --> target == A[start] or A[end]. left bound should check start first, right check end. | |
* | |
* @author jeffwan |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.binarySearch; | |
/** | |
* Solution: BinarySearch. it will be a sorted array if matrix expand line by line. | |
* The problem is to handle the position and element value in matrix. | |
* Only first and last element could be reached in last two situation. | |
* element = matrix[0][0]; element = matrix[matrix.length - 1][matrix[0].length - 1]; also works but not beautiful. | |
* | |
* @author jeffwan | |
* @date Mar 9, 2014 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.binarySearch; | |
/** | |
* Solution: BinarySearch, complexity is to handle different result if target could not be found. | |
* target < A[0] --> 0(start) | |
* target > A[start] && target < A[end] --> start + 1 or end | |
* target > A[end] -- end + 1 | |
* target = A[start] --> start | |
* target = A[end] --> end | |
* We could combine these situations to following codes. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.binarySearch; | |
/** | |
* Solution: BinarySearch, split Array to two part; | |
* A[start] < A[mid] --> (start,end) are sorted; | |
* A[start] > A[mid] --> (mid,end) are sorted. | |
* target >= A[start] && target <= A[end] makes sure we moves range to a sorted range step by step. | |
* That means, if not in this range, move to rest part, iteratively. if yes, like general binarySearch. | |
* | |
* @author jeffwan |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.binarySearch; | |
/** | |
* Solution: Binary Search, consider A[start] == A[mid] based on Search a Rotated Array I | |
* | |
* The most important problem we need to consider the situation A[mid] = A[start] which we didn't consider in | |
* search rotated sorted array I. We can't simply user A[start] <= A[mid], Actually we can't make judgment. | |
* A[start] = A[mid] can't make sure, so start++. because A[start] == A[mid], it will not skip the target, just | |
* skip the useless number | |
* |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.binarySearch; | |
/** | |
* Solution: BinarySearch | |
* | |
* Tricky: | |
* 1. Misunderstand the question, input 5,output 2; input 2,output 1. If not found, return the closest but not -1; | |
* 2. I am not sure if 99 return 9 or 10, according to wrong answer, it seems like to be 9 even if 10 is closer. | |
* 3. Input:2147395599, Output:2147395598, Expected:46339 the problem here is overflow x=500000 25000*25000<1000000 | |
* 4. we need to change mid * mid < target --> mid < target/mid if we use int ! |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.binarySearch; | |
/** | |
* Solution: BinarySearch | |
* | |
* Tricky: | |
* 1. n could be negative. | |
* 2. n cound be Integer.MIN_VALUE(-2147483648) and Integer.MAX_VALUE(2147483647) | |
* 3. handle n == 0, 1 as terminating condition. | |
* |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.stringSimple; | |
/** | |
* Method 1: General way, remeber to check if count =0 when meet " " | |
* Do I need to change first condition to (str[i]!= ' ') ? I think it doesn't matter. | |
* | |
* | |
* Method 2: " ".isEmpty() " ".length() == false!!! If we use this way, we must include s.trim().isEmpty() at first. | |
* Or, it will splited as String[] arr, the length of arr equals to 0, so there will be a ArrayOutofBound Exception. | |
* |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package CC150.ArraysAndString; | |
import java.util.HashSet; | |
import java.util.Set; | |
public class IsUniqueChars { | |
public static void main(String args[]) { | |
System.out.println(isUniqueChars("abcdefghijklmnopqrstuvwxyz")); | |
} |
OlderNewer