給自己的目標：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一題
在做題的過程中記錄下解題的思路或者重要的代碼碎片以便后來翻閱。
項目源碼：github上的Leetcode
41. First Missing Positive
題目：給出一組無序數(shù)組，找出第一個缺少的正整數(shù)。要求時間復(fù)雜度為O(n),空間為O(1)
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
正整數(shù)從1開始，所以可以將數(shù)組的下標序號與此一一對應(yīng)。
比如說4,3,6,1,5的數(shù)組，第一個數(shù)為4,，則與第四個數(shù)交換 -> 1,3,6,4,5. 此時第一個數(shù)為1，不再交換進行下一輪。
第二個數(shù)為3，則與第三個數(shù)交換 -> 1,6,3,4,5.此時第2個數(shù)為6，沒有與序號對應(yīng)需要再次交換，但此時6已經(jīng)超過數(shù)組的長度所以跳過進入下一輪。
第三個數(shù)為3，與序號相等,下一輪...
直到完全交換完成，再次遍歷整個數(shù)組，找出第一個沒有對應(yīng)的序號則是我們要求的數(shù)，這個例子則是為第二個數(shù)，所以返回2.
public class Solution {
public int firstMissingPositive(int[] nums) {
int i = 0;
while (i < nums.length) {
int value = nums[i];
if (value == i + 1 || value <= 0 || value >= nums.length) {
i++;
} else {
int temp = nums[value - 1];
if (temp == nums[i]) {
i++;
continue;
}
nums[value - 1] = nums[i];
nums[i] = temp;
}
}
for (int k = 0; k < nums.length; k++) {
if (nums[k] != k + 1) {
return k + 1;
}
}
return nums.length + 1;
}
}
42. Trapping Rain Water
題目：給出一組數(shù)字代表柱高，求能夠容量的雨水體積。
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
與 ContainerWithMostWater 的思路類似，也是采取從兩邊向中間遍歷的方法。我們使用兩個指針，一個從左向右遍歷，一個從右向左遍歷。從左向右遍歷時，記錄下上次左邊的峰值，如果右邊一直沒有比這個峰值高的，就已經(jīng)加上這些差值。從右向左遍歷時，記錄下上次右邊的峰值，如果左邊一直沒有比這個峰值高的，就加上這些差值。難點在于，當(dāng)兩個指針遍歷到相鄰的峰時，我們要選取較小的那個峰值來計算差值。所以，我們在遍歷左指針或者右指針之前，要先判斷左右兩個峰值的大小。
public class Solution {
public int trap(int[] height) {
int secHight = 0;
int left = 0;
int right = height.length - 1;
int area = 0;
while (left < right) {
if (height[left] < height[right]) {
secHight = Math.max(height[left], secHight);
area += secHight - height[left];
left++;
} else {
secHight = Math.max(height[right], secHight);
area += secHight - height[right];
right--;
}
}
return area;
}
}
43. Multiply Strings
題目：輸入兩個由數(shù)字組成的字符串，求他們的乘積。兩個字符串的長度小于110，且都是有0-9組成，沒有包含前置0，不能用 BigInteger 或者直接將字符串轉(zhuǎn)化成數(shù)字來進行計算。
大數(shù)的乘法計算，我采取的是最傳統(tǒng)的做法：挨個相乘并做大數(shù)的加法，最后得到解，算法并不算是最優(yōu)解。
public class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
StringBuilder result = new StringBuilder();
for (int i = 0; i < num1.length(); i++) {
int k = num1.charAt(i) - '0';
if (result.length() != 0) {
result.append("0");
}
result = add(result, singleMul(k, num2));
}
return result.toString();
}
public StringBuilder add(StringBuilder s1, StringBuilder s2) {
int s = 0;
StringBuilder sb = new StringBuilder();
int len1 = s1.length() - 1;
int len2 = s2.length() - 1;
while (len1 >= 0 || len2 >= 0) {
int m1 = len1 >= 0 ? s1.charAt(len1) - '0' : 0;
int m2 = len2 >= 0 ? s2.charAt(len2) - '0' : 0;
sb.insert(0, (m1 + m2 + s) % 10);
s = (m1 + m2 + s) / 10;
len1--;
len2--;
}
if (s != 0) {
sb.insert(0, s);
}
return sb;
}
public StringBuilder singleMul(int num, String num2) {
StringBuilder sb = new StringBuilder();
int s = 0;
for (int i = num2.length() - 1; i >= 0; i--) {
int k = num2.charAt(i) - '0';
sb.insert(0, (num * k + s) % 10);
s = (num * k + s) / 10;
}
if (s != 0) {
sb.insert(0, s);
}
return sb;
}
}
最優(yōu)的解法是
設(shè)兩個數(shù)長度為m,n,然后定義一個數(shù)組a[m+n-1]，其各位乘積的規(guī)律為a[i+j] += (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
public class Solution {
public String multiply(String num1, String num2) {
if(num1.equals("0")||num2.equals("0")) return "0";
int m = num1.length(), n = num2.length();
int[] digits = new int[m + n -1];
for(int i=m-1; i>=0; i--){
for(int j=n-1; j>=0; j--){
digits[i+j] += (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
}
}
int carry = 0;
String rs = "";
for(int i=m+n-2; i>=0; i--){
int temp = digits[i]+carry;
carry = temp/10;
rs = (temp%10) + rs;
}
rs = (carry==0?"":carry) + rs;
return rs;
}
}
44. Wildcard Matching
題目：字符串匹配
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
剛開始用的是遞歸算法，很遺憾的是TLE了，后面用的是暴力解法，當(dāng)遇到 '*' 號時做上標記，當(dāng)后續(xù)無法繼續(xù)匹配下去時回到 '*' 的位置開始匹配
public class Solution {
public boolean isMatch(String s, String p) {
int m = 0, n = 0, index = 0, star = -1;
while (m < s.length()) {
if (n < p.length() && (s.charAt(m) == p.charAt(n) || p.charAt(n) == '?')) {
m++;
n++;
} else if (n < p.length() && p.charAt(n) == '*') {
index = m;
star = n;
n++;
} else if (star != -1) {
n = star + 1;
index++;
m = index;
} else return false;
}
while (n < p.length() && p.charAt(n) == '*')
n++;
return n == p.length();
}
}
45. Jump Game II
題目：跳棋。給出一組數(shù)據(jù)，里面的值表示為可跳的最大范圍，求從第一個數(shù)可以跳到最后一個數(shù)最小的步數(shù)。
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
動態(tài)規(guī)范，每一步都取 i + nums[i] 最大的那一步來走。
public class Solution {
public int jump(int[] nums) {
int res = 0, i = 0, cur = 0, n = nums.length;
while (cur < n - 1) {
int pre = cur;
while (i <= pre) {
cur = Math.max(cur, i + nums[i]);
++i;
}
++res;
if (pre == cur) return -1;
}
return res;
}
}
