public class Solution {
// f[i] - if s.substring(0, i) can be segmented
// f[i] = f[j] && wordDict.contains(s.substring(j, i))
// f[0] = true
// result - f[s.length()]
public boolean wordBreak(String s, Set wordDict) {
if (s == null || s.length() == 0) {
return true;
}
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
for (int i = 1; i <= s.length(); i++) {
f[i] = false;
for (int j = 0; j < i; j++) {
f[i] = f[i] || (f[j] && wordDict.contains(s.substring(j, i)));
}
}
return f[s.length()];
}
}
2016年7月31日星期日
[LeetCode] #139 Word Break
[LintCode][要再做] #108 Palindrome Partitioning II
public class Solution {
/**
* @param s a string
* @return an integer
*/
public int minCut(String s) {
// state: f[i] = min cuts needed for a palindrome partitioning of s.substring(0, i)
// function: f[i] = Min(f[j] + 1, isPalindrome(s.substring(j, i)), for all j < i
// initialize: f[0] = 0
// result: f[s.length()]
// write your code here
//isPalindrome[i][j] = is s.substring(i, j + 1) a palindrome
boolean [][] isPalindrome = getIsPalindrome(s);
int f[] = new int[s.length() + 1];
f[0] = -1;
for (int i = 1; i <= s.length(); i++) {
f[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if (isPalindrome[j][i - 1]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
return f[s.length()];
}
private boolean[][] getIsPalindrome(String s) {
boolean[][] p = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
p[i][i] = true;
}
for (int i = 0; i < s.length() - 1; i++) {
p[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
}
for (int length = 2; length < s.length(); length++) {
for (int i = 0; i + length < s.length(); i++) {
p[i][i + length] = p[i + 1][i + length - 1] && s.charAt(i) == s.charAt(i + length);
}
}
return p;
}
};
2016年7月27日星期三
[LeetCode] #55 Jump Game
DP, time complexity: O(n^2) Time Limit Exceeded (这题要用贪心做T_T)
Greedy, time complexity: O(n)
public class Solution {
// state: f[i] = is ith element reachable
// function: f[i] = OR(f[j], i - j <= nums[j])
// initialize: f[0] = true
// result = f[nums.length]
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
boolean[] f = new boolean[nums.length];
f[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (f[j] && j + nums[j] >= i) {
f[i] = true;
break;
}
}
}
return f[nums.length - 1];
}
}
Greedy, time complexity: O(n)
public class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int reachable = nums[0];
for (int i = 0; i <= reachable && i < nums.length; i++) {
reachable = Math.max(reachable, i + nums[i]);
}
return reachable >= nums.length - 1;
}
}
2016年7月26日星期二
[LeetCode] #64 Minimum Path Sum
public class Solution {
//f[i][j] = min path sum from (0,0) to (i,j)
//f[i][j] = grid[i][j] + min(f[i - 1][j], f[i][j - 1])
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[][] f = new int[m][n];
f[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
f[i][0] = f[i - 1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
f[0][i] = f[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
}
}
return f[m - 1][n - 1];
}
}
[LeetCode] #70 Climbing Stairs
public class Solution {
// f[i] = how many distinct ways from i to the top
// f[i] = f[i + 1] + f[i + 2]
public int climbStairs(int n) {
if (n < 2) {
return n;
}
int[] f = new int[n + 1];
f[n] = 0;
f[n - 1] = 1;
if (n >= 2) {
f[n - 2] = 2;
}
for (int i = n - 3; i >= 0; i--) {
f[i] = f[i + 1] + f[i + 2];
}
return f[0];
}
}
[LeetCode] #63 Unique Paths II
public class Solution {
// f[i][j] = how many paths from (0,0) to (i,j)
// f[i][j] = f[i - 1][j] + f[i][j - 1]
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] f = new int[m][n];
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 1 || (i > 0 && f[i - 1][0] == 0)) {
f[i][0] = 0;
} else {
f[i][0] = 1;
}
}
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 1 || (i > 0 && f[0][i - 1] == 0)) {
f[0][i] = 0;
} else {
f[0][i] = 1;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
f[i][j] = 0;
} else {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
}
return f[m - 1][n - 1];
}
}
[LintCode] #114 Unique Path
public class Solution {
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/
public int uniquePaths(int m, int n) {
// write your code here
int[][] f = new int[m][n];
for (int i = 0; i < m; i++) {
f[i][0] = 1;
}
for (int i = 0; i < n; i++) {
f[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
}
2016年7月25日星期一
[LeetCode] #377 Combination Sum IV
public class Solution {
// state[i]: how many combinations when target = i
// state[i] += 1, when num == i
// state[i - num], num=nums[0], ..., nums[nums.length - 1]
// result = state[target];
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int state[] = new int[target + 1];
state[0] = 0;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num == i) {
state[i]++;
} else if (num < i) {
state[i] += state[i - num];
} else {
break;
}
}
}
return state[target];
}
}
2016年7月22日星期五
[LeetCode] #51 N-Queens
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
if (n <= 0) {
return result;
}
helper(result, new ArrayList<Integer>(), n);
return result;
}
private void helper(List<List<String>> result, List<Integer> path, int n) {
if (path.size() == n) {
result.add(generateResult(path));
return;
}
for (int i = 0; i < n; i++) {
if (isValid(path, i)) {
path.add(i);
helper(result, path, n);
path.remove(path.size() - 1);
}
}
}
private List<String> generateResult(List<Integer> path) {
List<String> result = new ArrayList<String>();
for (int i = 0; i < path.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < path.size(); j++) {
if (j == path.get(i)) {
sb.append('Q');
} else {
sb.append('.');
}
}
result.add(new String(sb));
}
return result;
}
private boolean isValid(List<Integer> path, int pos) {
for (int i = 0; i < path.size(); i++) {
if (path.get(i) == pos || path.get(i) == pos - path.size() + i
|| path.get(i) == pos + path.size() - i) { // Attn!
return false;
}
}
return true;
}
}
2016年7月21日星期四
[LeetCode] #93 Restore IP Addresses
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<String>();
if (s == null || s.length() == 0) {
return result;
}
helper(result, new ArrayList<String>(), s, 0);
return result;
}
private void helper(List<String> result, List<String> path, String s, int start) {
if (start == s.length()) {
if (path.size() == 4) { //Attn!
result.add(String.join(".", path));
}
return;
}
for (int i = start; i < s.length(); i++) {
if (!isValid(s.substring(start, i + 1))) {
break;
}
if (path.size() == 3 && i + 1 != s.length()) {
continue;
}
path.add(s.substring(start, i + 1));
helper(result, path, s, i + 1);
path.remove(path.size() - 1);
}
}
private boolean isValid(String s) {
if (s.length() != Integer.toString(Integer.parseInt(s)).length()) {
return false; //Attn!
}
int i = Integer.parseInt(s);
return (i >= 0 && i <= 255);
}
}
[LeetCode] #131 Palindrome Partitioning
What's time complexity for this?
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
if (s == null || s.length() == 0) {
return result;
}
helper(result, new ArrayList<String>(), s, 0);
return result;
}
private void helper(List<List<String>> result, List<String> path, String s, int start) {
if (start >= s.length()) {
result.add(new ArrayList<String>(path));
}
for (int i = start; i < s.length(); i++) {
if (!isValid(s.substring(start, i + 1))) {
continue;
}
path.add(s.substring(start, i + 1));
helper(result, path, s, i + 1);
path.remove(path.size() - 1);
}
}
private boolean isValid(String s) {
int start = 0;
int end = s.length() - 1;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
[LeetCode] #125 Valid Palindrome
这题超烦@_@
Character.toLowerCase() would make it easier :P
public class Solution {
public boolean isPalindrome(String s) {
if (s == null) {
return false;
}
int start = 0;
int end = s.length() - 1;
while (start < end) {
while (start < end && !isValid(s.charAt(start))) {
start++;
}
while (start < end && !isValid(s.charAt(end))) {
end--;
}
if (start < end && !equalsIgnoreCase(s.charAt(start), s.charAt(end))) {
return false;
}
start++;
end--;
}
return true;
}
private boolean equalsIgnoreCase(char a, char b) {
if (a == b) {
return true;
}
if (isChar(a) && isChar(b) && Math.abs(a - b) == Math.abs('A' - 'a')) {
return true;
}
return false;
}
private boolean isValid(char a) {
return isChar(a) || (a >= '0' && a <= '9');
}
private boolean isChar(char a) {
if (a >= 'a' && a <= 'z') {
return true;
}
if (a >= 'A' && a <= 'Z') {
return true;
}
return false;
}
}
Character.toLowerCase() would make it easier :P
[LeetCode] #17 Letter Combinations of a Phone Number
Time complexity: O(C^n), C = 3 or 4
Because T(n) = CT(n - 1)
Because T(n) = CT(n - 1)
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
helper(result, new StringBuilder(), digits.toCharArray(), 0);
return result;
}
private void helper(List<String> result, StringBuilder sb, char[] chars, int start) {
if (start == chars.length) {
result.add(new String(sb));
return;
}
for (char c : getLetters(chars[start])) {
sb.append(c);
helper(result, sb, chars, start + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
private char[] getLetters(char a) {
switch(a) {
case '2': return "abc".toCharArray();
case '3': return "def".toCharArray();
case '4': return "ghi".toCharArray();
case '5': return "jkl".toCharArray();
case '6': return "mno".toCharArray();
case '7': return "pqrs".toCharArray();
case '8': return "tuv".toCharArray();
case '9': return "wxyz".toCharArray();
default: return "".toCharArray();
}
}
}
[LeetCode] #216 Combination Sum III
Time complexity: O(2^n)
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
if (k < 1 || n < 1 || n > 45) {
return result;
}
helper(result, new ArrayList<Integer>(), 0, k, n, 1); // Attn: starts from 1, not 0
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int sum, int k, int n, int start) {
if (path.size() == k && sum == n) {
result.add(new ArrayList<Integer>(path));
return;
}
if (path.size() == k) {
return;
}
for (int i = start; i <= 9; i++) {
if (sum + i > n) {
break;
}
path.add(i);
helper(result, path, sum + i, k, n, i + 1);
path.remove(path.size() - 1);
}
}
}
[LeetCode] #40 Combination Sum II
Time complexity: O(2^n)
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
Arrays.sort(candidates);
helper(result, new ArrayList<Integer>(), 0, candidates, target, 0);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int sum, int[] candidates, int target, int start) {
if (sum == target) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (i > 0 && i != start && candidates[i] == candidates[i - 1]) {
continue;
}
if (sum + candidates[i] > target) {
break;
} else {
path.add(candidates[i]);
helper(result, path, sum + candidates[i], candidates, target, i + 1);
path.remove(path.size() - 1);
}
}
}
}
2016年7月20日星期三
[LeetCode] #39 Combination Sum
Time complexity: O(n!)
because T(n) = nT(n - 1) + k
because T(n) = nT(n - 1) + k
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
Arrays.sort(candidates);
helper(result, new ArrayList<Integer>(), 0, candidates, target, 0);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int sum, int[] candidates, int target, int start) {
if (sum == target) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int i = 0; i < candidates.length; i++) {
if (start > 1 && start - 1 > i) {
continue;
}
if (sum + candidates[i] <= target) {
path.add(candidates[i]);
helper(result, path, sum + candidates[i], candidates, target, i + 1);
path.remove(path.size() - 1);
} else {
break;
}
}
}
}
[LeetCode] #77 Combinations
Time complexity: O(2^n)
because T(n) = kn + T(n-1) + T(n-2) +...+ T(2) + T(1), => O(2^n) , see https://discuss.leetcode.com/topic/2163/what-is-the-time-complexity-of-the-recursive-solution-for-this-problem-how-to-get-it/3
because T(n) = kn + T(n-1) + T(n-2) +...+ T(2) + T(1), => O(2^n) , see https://discuss.leetcode.com/topic/2163/what-is-the-time-complexity-of-the-recursive-solution-for-this-problem-how-to-get-it/3
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
if (n < 1 || k < 1) {
return result;
}
helper(result, new ArrayList<Integer>(), n, k, 1);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int n, int k, int start) {
if (path.size() == k) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int i = start; i <= n; i++) {
path.add(i);
helper(result, path, n, k, i + 1);
path.remove(path.size() - 1);
}
}
}[LeetCode] #47 Permutations II
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
Arrays.sort(nums);
helper(result, new ArrayList<Integer>(), nums, new boolean[nums.length]);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] selected) {
if (path.size() == nums.length) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && selected[i - 1] == false) {
continue;
}
if (!selected[i]) {
selected[i] = true;
path.add(nums[i]);
helper(result, path, nums, selected);
path.remove(path.size() - 1);
selected[i] = false;
}
}
}
}
2016年7月19日星期二
Time Complexity of Permutations and Subsets
Subsets
T(n) = T(n - 1) + T(n-2) +...+ T(2) + T(1) + C (Q: How to calculate this?) (Wrong!)
T(n) = kn + T(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (1)
T(n - 1) = k(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (2)
(1) - (2)
<=> T(n) - T(n - 1) = kn - k(n - 1) + T(n - 1)
<=> T(n) = 2T(n - 1) + k
<=> O(2^n)
Permutations
T(n) = nT(n-1) + C
<=> O(n!)
T(n - 1) = k(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (2)
(1) - (2)
<=> T(n) - T(n - 1) = kn - k(n - 1) + T(n - 1)
<=> T(n) = 2T(n - 1) + k
<=> O(2^n)
Permutations
T(n) = nT(n-1) + C
<=> O(n!)
[LeetCode] #46 Permutations
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
Arrays.sort(nums);
helper(result, new ArrayList<Integer>(), nums, new boolean[nums.length]);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] selected) {
if (path.size() == nums.length) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && selected[i - 1] == false) {
continue;
}
if (!selected[i]) {
selected[i] = true;
path.add(nums[i]);
helper(result, path, nums, selected);
path.remove(path.size() - 1);
selected[i] = false;
}
}
}
}
2016年7月18日星期一
[LeetCode] #90 Subset II
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null ||nums.length == 0) {
return result;
}
Arrays.sort(nums);
helper(result, new ArrayList<Integer>(), nums, 0);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
result.add(new ArrayList<Integer>(path));
for (int i = start; i < nums.length; i++) {
if (i > 0 && i != start && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
helper(result, path, nums, i + 1);
path.remove(path.size() - 1);
}
}
}
[LintCode] #142 O(1) Check Power of 2
class Solution {
/*
* @param n: An integer
* @return: True or false
*/
public boolean checkPowerOf2(int n) {
// write your code here
return (Integer.bitCount(n << 1) == 1); // edge case: -2147483648
}
};
2016年7月17日星期日
[LintCode] #181 Flip Bits
class Solution {
/**
*@param a, b: Two integer
*return: An integer
*/
public static int bitSwapRequired(int a, int b) {
// write your code here
return Integer.bitCount(a ^ b);
}
};
2016年7月15日星期五
[LeetCode] #78 Subsets
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
helper(result, new ArrayList<Integer>(), nums, 0);
return result;
}
private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
helper(result, path, nums, i + 1);
path.remove(path.size() - 1);
}
}
}
2016年7月14日星期四
[笔记整理] 九章算法第二章 Binary Search & Sorted Array Part2
1. Search for a Range
<=> How many times did a number appear? range[x1, x2] => x2-x1+1
* The insertion position may not be in current array
* Find the insertion position, 3 positions to check: x<start, start<x<end, x>end
* No duplicate
* 2 possible position for mid: [mid] >= [0], [mid] < [0]
* 4 possible position for target: [0]<T<[mid], [0]<[mid]<T, T<[mid]<[0], [mid]<T<[0]
* Duplicate
* Worst case for binary search - O(n) e.g. If in every iteration, [mid]==[0]/[mid]==[length-1] =>O(n)
* Any element in row1 < Any element in row 2
* Use binary search for 2 times, 1st time find the row of target, 2nd time find the column of target
[1 0 2 4]
[1 2 6 9]
[3 5 7 10]
[7 8 9 11]
* Quadrate search O(n)
* Search from left bottom to right top, exclude 1 row/column each iteration, O(m + n)
* peak <=> A[p] > A[p - 1] && A[p] >A[p + 1]
9. Remove Duplicate from Sorted Array
10. Remove Duplicate from Sorted Array II
11. Merge Sorted Array
* Merge + Find O(m + n)
* Find kth largest O(logn)
when (m+n) is odd=>k=(m+n)/2+1
when (m+n) is even=>k1=(m+n)/2, k2=(m+n)/2+1
* How to find kth largest?
Throw away each k/2 elements in each iteration
* Sort, O(1) space O(nlogn) time
* 3 times reverse, O(1) space O(n) time
* abcdefg, offset=3 => efgabcd
* reverse each word, then reverse the entire string
[LintCode] #53 Reverse Words in a String
* reverse each word, and then reverse the entire string
sky_is_blue => yks_si_eulb => blue_is_sky
* This one not working, because of it can't remove redundant spaces
sky_is_blue => yks_si_eulb => blue_is_sky
public class Solution {
/**
* @param s : A string
* @return : A string
*/
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return s;
}
String[] A = s.split(" ");
if (A.length == 0 ) {
return "";
}
StringBuilder sb = new StringBuilder();
for (int i = A.length - 1; i >= 0; i--) {
sb.append(A[i]);
if (i != 0) {
sb.append(" ");
}
}
return new String(sb);
}
}
* This one not working, because of it can't remove redundant spaces
public class Solution {
public String reverseWords(String s) {
char[] tmp = s.toCharArray();
int start = 0;
while(start < tmp.length) {
while (start < tmp.length && tmp[start] == ' ') {
start++;
}
if (start >= tmp.length) {
break;
}
int end = start;
while (end < tmp.length && tmp[end] != ' ') {
end++;
}
if (start < tmp.length && end <= tmp.length) {
reverse(start, end - 1, tmp);
}
start = end;
}
reverse(0, tmp.length - 1, tmp);
return new String(tmp);
}
private void reverse(int start, int end, char[] A) {
while (start < end) {
char tmp = A[start];
A[start] = A[end];
A[end] = tmp;
start++;
end--;
}
}
}
2016年7月12日星期二
[LintCode] #8 Rotate String
1) when offset > str.length!!!!!
public class Solution {
/**
* @param str: an array of char
* @param offset: an integer
* @return: nothing
*/
public void rotateString(char[] str, int offset) {
// write your code here
if (str == null || str.length == 0 || offset < 0) {
return;
}
offset = offset % str.length; //T_T!!!!!!!
reverse(str, 0, str.length - offset - 1);
reverse(str, str.length - offset, str.length - 1);
reverse(str, 0, str.length - 1);
}
private void reverse(char[] str, int start, int end) {
while (start < end) {
char tmp = str[start];
str[start] = str[end];
str[end] = tmp;
start++;
end--;
}
}
}
[LintCode] #159 Find Minimum in Rotated Sorted Array
1) [mid] > [start] move right, else move left
2) edge case: the array is sorted
2) edge case: the array is sorted
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return -1;
}
if (nums[0] < nums[nums.length - 1]) { //T_T!!!!!
return nums[0];
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[0] < nums[mid]) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] < nums[end]) {
return nums[start];
} else {
return nums[end];
}
}
}
2016年7月8日星期五
[LintCode] #39 Recover Rotated Sorted Array
1) in place == re-sort O(nlogn)
2) O(n) space, O(n) time
3) 3 time reverse, O(1) space, O(n) time
2) O(n) space, O(n) time
3) 3 time reverse, O(1) space, O(n) time
public class Solution {
/**
* @param nums: The rotated sorted array
* @return: The recovered sorted array
*/
public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
// write your code
int i;
for (i = 1; i < nums.size(); i++) {
if (nums.get(i) < nums.get(i - 1)) {
break;
}
}
reverse(nums, 0, i - 1);
reverse(nums, i, nums.size() - 1);
reverse(nums, 0, nums.size() - 1);
}
private void reverse(ArrayList<Integer> nums, int start, int end) {
for (; start < end; start++, end--) {
int tmp = nums.get(start);
nums.set(start, nums.get(end));
nums.set(end, tmp);
}
}
}
2016年7月7日星期四
[LeetCode] #4 Median of Two Sorted Arrays
1) Merge + find median O(m + n)
2) Find kth largest element in two arrays O(logk), k = (m + n)/2, because every time throw away k/2^n
2) Find kth largest element in two arrays O(logk), k = (m + n)/2, because every time throw away k/2^n
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return 0.0;
}
if ((nums1.length + nums2.length) % 2 != 0) {
return findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2 + 1);
} else {
return (findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2) + findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2 + 1)) / 2.0;
}
}
private int findKthElem(int[] nums1, int[] nums2, int start1, int start2, int k) {
if (start1 >= nums1.length) {
return nums2[start2 + k - 1];
}
if (start2 >= nums2.length) {
return nums1[start1 + k - 1];
}
if (k == 1) {
return nums1[start1] > nums2[start2] ? nums2[start2] : nums1[start1];
}
int value1 = start1 + k/2 - 1 < nums1.length ? nums1[start1 + k/2 - 1] : Integer.MAX_VALUE; // use max value here to throw away first k/2 elems in nums2
int value2 = start2 + k/2 - 1 < nums2.length ? nums2[start2 + k/2 - 1] : Integer.MAX_VALUE;
if (value1 > value2) {
return findKthElem(nums1, nums2, start1, start2 + k/2, k - k/2); // the rest elems to find
} else {
return findKthElem(nums1, nums2, start1 + k/2, start2, k - k/2);
}
}
}
2016年7月6日星期三
[LintCode] #61 Search for a Range
public class Solution {
/**
*@param A : an integer sorted array
*@param target : an integer to be inserted
*return : a list of length 2, [index1, index2]
*/
public int[] searchRange(int[] A, int target) {
// write your code here
int[] result = new int[2];
result[0] = -1;
result[1] = -1;
if (A == null || A.length == 0) {
return result;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] >= target) {
end = mid;
} else {
start = mid;
}
}
if (A[start] == target) {
result[0] = start;
} else if (A[end] == target){
result[0] = end;
} else {
return result; //!!!!!
}
start = 0;
end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] <= target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] == target) {
result[1] = end;
} else if (A[start] == target) {
result[1] = start;
} else {
result[0] = -1;
}
return result;
}
}
[LintCode] #183 Wood Cut
public class Solution {
/**
*@param L: Given n pieces of wood with length L[i]
*@param k: An integer
*return: The maximum length of the small pieces.
*/
public int woodCut(int[] L, int k) {
// write your code here
if (L == null || L.length == 0) {
return 0;
}
int max = 0;
for (int i = 0; i < L.length; i++) {
max = max < L[i] ? L[i] : max;
}
int start = 0;
int end = max;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (numberOfPieces(L, mid) < k) {
end = mid;
} else {
start = mid;
}
}
if (numberOfPieces(L, end) >= k) {
return end;
} else {
return start;
}
}
private int numberOfPieces(int[] L, int length) {
int pieces = 0;
for (int i = 0; i < L.length; i++) {
pieces += L[i] / length;
}
return pieces;
}
}
2016年7月1日星期五
[LintCode] #60 Search Insert Position
attention: if target > all elements in A T_T
public class Solution {
/**
* param A : an integer sorted array
* param target : an integer to be inserted
* return : an integer
*/
public int searchInsert(int[] A, int target) {
// write your code here
if (A == null || A.length == 0) {
return 0;
}
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] >= target) {
end = mid;
} else {
start = mid;
}
}
if (A[start] >= target) {
return start;
} else if (A[end] >= target){
return end;
} else {
return end + 1; // 1st attempt failed: target > all elements in A
}
}
}
[LeetCode] #240 Search a 2D Matrix II
1) quadratic search? time complexity O(n)
2) search from bottom left of that 2D array, compare current element with target, exclude one row/column each time O(n + m)
2) search from bottom left of that 2D array, compare current element with target, exclude one row/column each time O(n + m)
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int i = matrix.length - 1;
int j = 0;
while (i >= 0 && j < matrix[0].length) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
i--;
} else {
j++;
}
}
return false;
}
}
订阅：
博文 (Atom)