public class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (mid >= 1 && nums[mid - 1] < nums[mid] && mid < nums.length - 2 && nums[mid] > nums[mid + 1] ) {
return mid;
} else if (mid >= 1 && nums[mid - 1] < nums[mid]) {
start = mid;
} else {
end = mid;
}
}
return nums[start] > nums[end] ? start : end;
}
}
2016年6月30日星期四
[LeetCode] #162 Find Peak Element
[LeetCode] #278 First Bad Version
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int start = 0;
int end = n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isBadVersion(mid)) {
end = mid;
} else {
start = mid;
}
}
return isBadVersion(start) ? start : end;
}
}
[LeetCode] #74 Search a 2D Matrix
1) search first column of the 2D array, get the last element that is <= target, search the row of that element to find target O(logN) + O(logM)
2) search all the elements in that 2D array 1 time O(log(M*N)) = O(logN) + O(logM) :p
2) search all the elements in that 2D array 1 time O(log(M*N)) = O(logN) + O(logM) :p
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int start = 0;
int end = matrix.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[mid][0] == target) {
return true;
} else if (matrix[mid][0] > target) {
end = mid;
} else {
start = mid;
}
}
int row = target >= matrix[end][0] ? end : start;
start = 0;
end = matrix[0].length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[row][mid] == target) {
return true;
} else if (matrix[row][mid] > target) {
end = mid;
} else {
start = mid;
}
}
if (target == matrix[row][start] || target == matrix[row][end]) {
return true;
}
return false;
}
}
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0][0] > target || matrix[matrix.length - 1][matrix[0].length - 1] < target) {
return false;
}
int start = 0;
int end = matrix.length * matrix[0].length - 1;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
int x = mid / matrix[0].length;
int y = mid % matrix[0].length;
if (matrix[x][y] == target) {
return true;
} else if (matrix[x][y] < target) {
start = mid;
} else if (matrix[x][y] > target) {
end = mid;
}
}
if (matrix[end / matrix[0].length][end % matrix[0].length] == target) {
return true;
}
if (matrix[start / matrix[0].length][start % matrix[0].length] == target) {
return true;
}
return false;
}
}
2016年6月29日星期三
[LeetCode] #81 Search in Rotated Sorted Array II
Do not try to use binary search!!!!!
worst case time complexity: O(n)
binarySearch(start, end) {
if (nums[start] == nums[mid] == nums[end]) { // if always hit this case until the last 1 elem, O(n)
binarySearch(start, mid);
binarySearch(mid + 1, end);
}
}
binarySearch(start, end) {
if (nums[start] == nums[mid] == nums[end]) { // if always hit this case until the last 1 elem, O(n)
binarySearch(start, mid);
binarySearch(mid + 1, end);
}
}
[LeetCode] #33 Search in Rotated Sorted Array
Need to consider 2 cases for mid => M' and M.
4 cases for target => S<T<M', M'<T, T<M<S, M<T<S
public class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == nums[mid]) {
return mid;
}
if (nums[mid] >= nums[start]) { // M'
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else { // M
if (target <= nums[end] && target > nums[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
}
2016年6月27日星期一
[LintCode] #141 Sqrt(x)
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
if (x == 0 || x == 1) {
return x;
}
int start = 1;
int end = x;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
int q = x / mid;
if (q == mid) {
start = mid;
} else if (q < mid) {
end = mid;
} else {
start = mid;
}
}
if ( end * end > 0 && end * end <= x ) { // x=2147483647 --> integer overflow T_T
return end;
} else {
return start;
}
}
}
T_T 溢出的那个edge case烦死了！擦！
2016年6月26日星期日
[LintCode] #31 Partition Array
public class Solution {
/**
*@param nums: The integer array you should partition
*@param k: As description
*return: The index after partition
*/
public int partitionArray(int[] nums, int k) {
//write your code here
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0;
int end = nums.length - 1;
while (start < end) {
while (start < end && nums[start] < k) {
start++;
}
while (start < end && nums[end] >= k) {
end--;
}
int tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
}
if (end == nums.length - 1 && nums[end] < k) { // edge case: all elem in the array < k
return end + 1;
} else {
return start;
}
}
}
2016年6月24日星期五
[LeetCode] #1 Two Sum
Thinking:
1) Brute force: O(n^2)
2) Sort + extra array to store index info O(nlogn) + O(n) space
3) Hash, <k,v> = <Value, Index> O(n) + O(n) space
1) Brute force: O(n^2)
2) Sort + extra array to store index info O(nlogn) + O(n) space
3) Hash, <k,v> = <Value, Index> O(n) + O(n) space
public class Solution {
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1 + 1, index2 + 1] (index1 < index2)
*/
public int[] twoSum(int[] numbers, int target) {
// write your code here
int[] result = new int[2];
if (numbers == null || numbers.length == 0) {
return result;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
map.put(numbers[i], i);
}
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[0] = i + 1;
result[1] = map.get(target - numbers[i]) + 1;
return result;
}
}
return result;
}
}
[LintCode] #50 Product of Array Exclude Itself
Thinking:
1) brute force O(n^2)
2) generate left, right array: for [1,2,3], left=[1,1,2], right=[6,3,1] O(n) + O(n) space
3) optimization: only use left array
1) brute force O(n^2)
2) generate left, right array: for [1,2,3], left=[1,1,2], right=[6,3,1] O(n) + O(n) space
3) optimization: only use left array
public class Solution {
/**
* @param A: Given an integers array A
* @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
*/
public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
// write your code
ArrayList<Long> result = new ArrayList<Long>();
if (A == null || A.size() == 0) {
return result;
}
Long[] left = new Long[A.size()];
left[0] = 1L;
for (int i = 1; i < A.size(); i++) {
left[i] = left[i - 1] * A.get(i - 1);
}
Long[] right = new Long[A.size()];
right[A.size() - 1] = 1L;
for (int i = A.size() - 2; i >= 0; i--) {
right[i] = right[i + 1] * A.get(i + 1);
}
for (int i = 0; i < A.size(); i++) {
result.add(left[i] * right[i]);
}
return result;
}
}
2016年6月23日星期四
[LintCode] #59 3Sum Closest
Thinking:
1) triple for loop -> sum nearest to target O(n^3)
2) sort + search for closest -> sum nearest to target O(n^2)
3) impossible to be done in O(n) :p
1) triple for loop -> sum nearest to target O(n^3)
2) sort + search for closest -> sum nearest to target O(n^2)
3) impossible to be done in O(n) :p
public class Solution {
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return 0;
}
Arrays.sort(nums);
int closest = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i++) {
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
int sum = nums[i] + nums[start] + nums[end];
if (sum == target) {
return sum;
} else if (sum < target) {
start++;
} else {
end--;
}
if (Math.abs(sum - target) < Math.abs(closest - target)) {
closest = sum;
}
}
}
return closest;
}
}
2016年6月22日星期三
[LeetCode] #15 3 Sum
https://leetcode.com/problems/3sum/
Too many edge cases, sucks :p
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
if (nums[i] + nums[start] + nums[end] == 0) {
List<Integer> tmp = new ArrayList<Integer>();
tmp.add(nums[i]);
tmp.add(nums[start]);
tmp.add(nums[end]);
result.add(tmp);
start++;
end--;
while (start < end && nums[start] == nums[start - 1]) {
start++;
}
while (start < end && nums[end] == nums[end + 1]) {
end--;
}
} else if (nums[i] + nums[start] + nums[end] < 0) {
start++;
} else {
end--;
}
}
}
return result;
}
}
Too many edge cases, sucks :p
[LintCode] #189 First Missing Positive
http://www.lintcode.com/en/problem/first-missing-positive/
http://www.cnblogs.com/yuzhangcmu/p/4200096.html
http://www.cnblogs.com/yuzhangcmu/p/4200096.html
public class Solution {
/**
* @param A: an array of integers
* @return: an integer
*/
public static int firstMissingPositive(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return 1;
}
for (int i = 0; i < A.length; i++) {
while (A[i] - 1 < A.length && A[i] - 1 >= 0 && A[A[i] - 1] != A[i] ) {
swap(A, i, A[i] - 1);
}
}
for (int i = 0; i < A.length; i++) {
if (A[i] != i + 1) {
return i + 1;
}
}
return A.length + 1;
}
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2016年6月20日星期一
[LintCode] #138 Subarray Sum
http://www.lintcode.com/en/problem/subarray-sum/
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
* and the index of the last number
*/
public ArrayList<Integer> subarraySum(int[] nums) {
// write your code here
ArrayList<Integer> result = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return result;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == 0) {
result.add(0);
result.add(i);
return result;
}
if (map.containsKey(sum)) {
result.add(map.get(sum) + 1);//Attention
result.add(i);
return result;
}
map.put(sum, i);
}
return result;
}
}
2016年6月19日星期日
[LintCode] #172 Remove Element
http://www.lintcode.com/en/problem/remove-element/
public class Solution {
/**
*@param A: A list of integers
*@param elem: An integer
*@return: The new length after remove
*/
public int removeElement(int[] A, int elem) {
// write your code here
if (A == null || A.length == 0) {
return 0;
}
int i = 0;
int pointer = A.length - 1;
while (i <= pointer) {
if (A[i] == elem) {
A[i] = A[pointer];
pointer--;
} else {
i++;
}
}
return i;
}
}
2016年6月18日星期六
[LintCode] #78 Longest Common Prefix
Problem: http://www.lintcode.com/en/problem/longest-common-prefix/
public class Solution {
/**
* @param strs: A list of strings
* @return: The longest common prefix
*/
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int minLen = Integer.MAX_VALUE;
for (String s : strs) {
minLen = s.length() < minLen ? s.length() : minLen;
}
for (int i = 0; i < minLen; i++) {
for (int j = 0; j < strs.length - 1; j++) {
String s1 = strs[j];
String s2 = strs[j + 1];
if (s1.charAt(i) != s2.charAt(i)) {
return s1.substring(0, i);
}
}
}
return strs[0].substring(0, minLen);
}
}
[LeetCode] #334 Increasing Triplet Subsequence
特别没劲，但是自己想不出来的一道题。T_T
public class Solution {
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (first >= nums[i]) {
first = nums[i];
continue;
} else if (second >= nums[i]) {
second = nums[i];
continue;
} else {
return true;
}
}
return false;
}
}
2016年6月17日星期五
[LintCode] #79 Longest Common Substring
Problem: http://www.lintcode.com/en/problem/longest-common-substring/
Solution1: Dynamic Programming, use 2-dimension array
Solution2(super demon version DP): http://www.jiuzhang.com/solutions/longest-common-substring/
Homework: Listen to NineChapter DP lecture :p
Solution1: Dynamic Programming, use 2-dimension array
public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// int d[i][j] : the length of the common substring nearest to the end of A.substring(i) and B.substring(j)
// d[i][j] = d[i - 1][j - 1] + 1, A[i] == B[j]
// = 0, A[i] != B[j]
int max = 0;
if (A == null || B == null) {
return max;
}
int d[][] = new int[A.length() + 1][B.length() + 1];
for (int i = 0; i <= A.length(); i++) {
for (int j = 0; j <= B.length(); j++) {
if (i == 0 || j == 0) {
d[i][j] = 0; //init
continue;
}
if (A.charAt(i - 1) == B.charAt(j - 1)) {
d[i][j] = d[i - 1][j - 1] + 1;
} else {
d[i][j] = 0;
}
max = max > d[i][j] ? max : d[i][j];
}
}
return max;
}
}
Solution2(super demon version DP): http://www.jiuzhang.com/solutions/longest-common-substring/
Homework: Listen to NineChapter DP lecture :p
2016年6月16日星期四
[LintCode] #171 Anagrams
Problem: http://www.lintcode.com/en/problem/anagrams/
Solution1 (Dumb version :p):
Solution2 (Hashing :p): http://www.jiuzhang.com/solutions/anagrams/
Q: How to figure out the correct a and b to use in Hashing function? How to prevent collision?
Homework:
Read Terry's lecture note on hashing and hash table :p
Solution1 (Dumb version :p):
public class Solution {
/**
* @param strs: A list of strings
* @return: A list of strings
*/
public List<String> anagrams(String[] strs) {
List<String> result = new ArrayList<String>();
boolean[] selected = new boolean[strs.length];
for (int i = 0; i < selected.length; i++) {
selected[i] = false;
}
for (int i = 0; i < strs.length; i++) {
for (int j = i + 1; j < strs.length; j++) {
String s1 = strs[i];
String s2 = strs[j];
if (s1.length() != s2.length())
{
continue;
}
HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
for (char c : s1.toCharArray()) {
map1.put(c, map1.containsKey(c) ? map1.get(c) + 1 : 1);
}
for (char c : s2.toCharArray()) {
map2.put(c, map2.containsKey(c) ? map2.get(c) + 1 : 1);
}
if (map1.equals(map2)) {
if (!selected[i]) {
result.add(s1);
selected[i] = true;
}
if (!selected[j]) {
result.add(s2);
selected[j] = true;
}
}
}
}
return result;
}
}
Solution2 (Hashing :p): http://www.jiuzhang.com/solutions/anagrams/
Q: How to figure out the correct a and b to use in Hashing function? How to prevent collision?
Homework:
Read Terry's lecture note on hashing and hash table :p
订阅：
博文 (Atom)