给自己的目标：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一题
在做题的过程中记录下解题的思路或者重要的代码碎片以便后来翻阅。
项目源码：github上的Leetcode
41. First Missing Positive
题目：给出一组无序数组，找出第一个缺少的正整数。要求时间复杂度为O(n),空间为O(1)
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
正整数从1开始，所以可以将数组的下标序号与此一一对应。
比如说4,3,6,1,5的数组，第一个数为4,，则与第四个数交换 -> 1,3,6,4,5. 此时第一个数为1，不再交换进行下一轮。
第二个数为3，则与第三个数交换 -> 1,6,3,4,5.此时第2个数为6，没有与序号对应需要再次交换，但此时6已经超过数组的长度所以跳过进入下一轮。
第三个数为3，与序号相等,下一轮...
直到完全交换完成，再次遍历整个数组，找出第一个没有对应的序号则是我们要求的数，这个例子则是为第二个数，所以返回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
题目：给出一组数字代表柱高，求能够容量的雨水体积。
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
rain water
与 ContainerWithMostWater 的思路类似，也是采取从两边向中间遍历的方法。我们使用两个指针，一个从左向右遍历，一个从右向左遍历。从左向右遍历时，记录下上次左边的峰值，如果右边一直没有比这个峰值高的，就已经加上这些差值。从右向左遍历时，记录下上次右边的峰值，如果左边一直没有比这个峰值高的，就加上这些差值。难点在于，当两个指针遍历到相邻的峰时，我们要选取较小的那个峰值来计算差值。所以，我们在遍历左指针或者右指针之前，要先判断左右两个峰值的大小。
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
题目：输入两个由数字组成的字符串，求他们的乘积。两个字符串的长度小于110，且都是有0-9组成，没有包含前置0，不能用 BigInteger 或者直接将字符串转化成数字来进行计算。
大数的乘法计算，我采取的是最传统的做法：挨个相乘并做大数的加法，最后得到解，算法并不算是最优解。
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;
}
}
最优的解法是
设两个数长度为m,n,然后定义一个数组a[m+n-1]，其各位乘积的规律为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了，后面用的是暴力解法，当遇到 '*' 号时做上标记，当后续无法继续匹配下去时回到 '*' 的位置开始匹配
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
题目：跳棋。给出一组数据，里面的值表示为可跳的最大范围，求从第一个数可以跳到最后一个数最小的步数。
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.)
动态规范，每一步都取 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;
}
}
网友评论