Leetcode 7. Reverse Integer 【Easy】
难点在于 int 越界问题，用int temp暂时代替即可.
class Solution {
public int reverse(int x) {
int res = 0;
while(x != 0){
int a = x % 10;
int temp = res * 10 + a; //处理越界问题
if((temp-a)/10 != res) return 0;
res = temp;
x = x/10;
}
return res;
}
}
Leetcode 165. Compare Version Numbers.【Medium】
http://www.runoob.com/java/java-regular-expressions.html
java正则表达式中，. 匹配除"\r\n"之外的任何单个字符。\. 表示匹配 . 本身。为什么是两个 \ 呢？java的 \ 等同于其他语言的一个 \ 。
难点在于Math.max() , 和 i<v1.length 的判断。
class Solution {
public int compareVersion(String version1, String version2) {
String[] v1 = version1.split("\\.");
String[] v2 = version2.split("\\.");
for(int i=0; i<Math.max(v1.length,v2.length);i++){
int num1 = i<v1.length? Integer.valueOf(v1[i]) : 0;
int num2 = i<v2.length? Integer.valueOf(v2[i]) : 0;
if( num1 > num2 ) return 1;
if( num1 < num2 ) return -1;
}
return 0;
}
}
Leetcode 66. Plus One. 【Easy】
只分为两种情况，一是999，而是其他。
其他，就用for循环倒序遍历来解决。
class Solution {
public int[] plusOne(int[] digits) {
for(int i=digits.length-1; i>=0; i--){
if(digits[i]<9){
digits[i]++;
return digits;
} else {
digits[i] = 0;
}
}
int[] newDigits = new int[digits.length+1];
newDigits[0] = 1;
return newDigits;
}
}
Leetcode 8. String to Integer (atoi) 【Medium】
判断str.charAt(0)，用start记录数字开始的位置。遍历。
class Solution {
public int myAtoi(String str) {
str = str.trim();
if(str == null || str.length() == 0) return 0;
long res = 0;
int start = 0;
int sign = 1;
if(str.charAt(0) == '+'){
start++;
} else if (str.charAt(0) == '-'){
sign = -1;
start++;
}
for(int i = start; i< str.length();i++){
if(!Character.isDigit(str.charAt(i))){
return (int)res * sign;
}
res = res * 10 + str.charAt(i) - '0';
if(sign==1 && res>=Integer.MAX_VALUE) return Integer.MAX_VALUE;
if(sign==-1 && res>Integer.MAX_VALUE) return Integer.MIN_VALUE;
}
return (int)res * sign;
}
}
Leetcode 258. Add Digits. 【Easy】
常规暴力解法。Time: O(n), Space: O(1).
class Solution {
public int addDigits(int num) {
int sum = 0;
while(true){
sum = 0;
while(num>0){
sum += num % 10;
num /= 10;
}
num = sum;
if(sum<10) break;
}
return sum;
}
}
找规律：以9为循环
num对应的result以9为循环.jpg
class Solution {
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
}
Leetcode 67. Add Binary 【Easy】
倒序遍历两个数组。用while(i>=0 || j>=0)作为判断，用remainder记录进位。
Time: O(n), Space: O(n).
class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int remainder = 0, sum = 0;
while(i>=0 || j>=0){
sum = remainder;
if(i>=0) sum += a.charAt(i--) -'0';
if(j>=0) sum += b.charAt(j--) -'0';
sb = sb.insert(0,sum%2);
//如果用sb.append(num%2),就要在最后return sb.reverse().toString()
remainder = sum/2;
}
if(remainder != 0) sb = sb.insert(0,remainder);
return sb.toString();
}
}
Leetcode 43. Multiply Strings. 【Medium】
题目要求4: You must not use any built-in BigInteger library or convert the inputs to integer directly. 不能直接用long，int等。
两个for循环，倒序遍历，每次计算两个一位数的乘积，累加到new int[]对应位置
class Solution {
public String multiply(String num1, String num2) {
int[] digits = new int[num1.length()+num2.length()]; //想清楚这里
for(int i=num1.length()-1; i>=0; i--){
for(int j=num2.length()-1; j>=0; j--){
int product = (num1.charAt(i)-'0') * (num2.charAt(j)-'0'); //注意要 -'0'
int index1 = i + j, index2 = index1 + 1; //想清楚这里
int sum = product + digits[index2];
digits[index2] = sum % 10;
digits[index1] += sum / 10; // 注意是 +=
}
}
String res = new String(); // 用String 或 StringBuilder都行
for(int digit: digits){
if(!(res.length() == 0 && digit == 0)){ //第一个加入res的必须是非零数
res += digit;
}
}
System.out.println(res);
return res.length() == 0? "0": res;
}
}
Leetcode 29. Divide Two Integers 【Medium】
这题考了左移的操作。用 divideHelper 测试dividend 能装多少个divisor，用的while()循环，实际上是类似二分查找。
注意：把两个负数传入divideHelper，是因为 MIN_VALUE 绝对值比 MAX_VALUE 大1，如果 abs(MIN_VALUE) 会越界。所以干脆传两个负数进helper.
class Solution {
public int divide(int dividend, int divisor) {
//负数左移，也是相当于*2,直到小于MIN_VALUE,就越界成为正数(不规则的正数)
if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
boolean isSameSign = (dividend <0) == (divisor<0);
int res = divideHelper(-Math.abs(dividend),-Math.abs(divisor));
return isSameSign ? res : -res;
}
private int divideHelper(int dividend, int divisor){
int res = 0;
int currentDivisor = divisor;
while(dividend<=divisor){ // abs(divisor) <= abs(dividend)
int temp = 1;
while((currentDivisor << 1)>=dividend && (currentDivisor << 1)<0 ){ //test max temp for: temp * abs(divisor) <= abs(dividend), while temp = 2^n
temp <<=1;
currentDivisor <<=1;
}
dividend -= currentDivisor;
res += temp;
currentDivisor = divisor; //将currentDivisor恢复为divisor
}
return res;
}
}
Leetcode 69. Sqrt(x). 【Easy】
这题，需要写出两种情况：1) 二分法；2) 牛顿法。
二分法：Time: O(logn), Space: O(1).
class Solution {
public int mySqrt(int x) {
if(x<=0) return 0;
int low = 1, high = x;
while(low<=high){
long mid = (high - low)/2 + low;
if(mid * mid == x){ // mid * mid 可能越界，所以应该设置mid为long。比如当x=MAX_VALUE, 第一次计算mid^2就必然越界
return (int)mid;
} else if (mid * mid > x){
high = (int)mid - 1;
} else {
low = (int)mid + 1;
}
}
return high;
// if(high * high < x){ //必定的结果
// return high;
// }
// return 0;
}
}
牛顿法：
牛顿法，又名切线法。
CSDN搜索： leetcode:Sqrt(x) 牛顿迭代法求整数开方
https://blog.csdn.net/newfelen/article/details/23359629
draw a tangent line for function f(x), the tangent line and x axis intersects at point( xn+1, 0). So the tangent line passes both (xn, f(xn)) and (xn+1, 0). We can get the equation for the tangent line, which is ...
公式推导：
经过 (xn+1,0), ( xn, f(xn) ) 且斜率为f'(xn) 的直线，直线表达式为：
( f(xn)-0 ) / (xn - xn+1) = f'(xn) , 化简得到：
牛顿法的迭代公式.jpg
而本题 f(xn) = x^2 - n, f' = 2x. 所以，
xn+1 = xn - (x^2-n)/2x
= (x + n/x)/2.
牛顿法的Time Complexity 是unstable 不稳定的，可以理解为 接近O(logn).
public int mySqrt(int x){
long res = x;
while( res * res > x){
res = ( res + x / res ) / 2 ;
}
return (int)res;
}
Leetcode 367. Valid Perfect Square. 【Easy】
这题，需要写出两种情况：1) 二分法；2) 牛顿法。
二分法：Time: O(logn), Space: O(1).
class Solution {
public boolean isPerfectSquare(int num) {
int low = 1, high = num;
while(low<=high){
long mid = (high - low)/2 + low;
if(mid * mid == num){ // mid * mid 可能越界，所以应该设置mid为long。比如当x=MAX_VALUE, 第一次计算mid^2就必然越界
return true;
} else if (mid * mid < num){
low = (int)mid + 1;
} else {
high = (int)mid - 1;
}
}
return false;
}
}
牛顿法：Time 是 uncertain，但在这题可理解为优于O(nlogn).
class Solution {
public boolean isPerfectSquare(int num) {
long x = num;
while(x * x > num){
x = (x + num/x)/2;
}
return x * x == num;
}
}
Leetcode 50. Pow(x, n) 【Medium】
Time: O(logn), Space: O(1).
本题暴力解法就是O(n), 要提升，必然是二分法，提升到O(logn).
用Iterative方法，每次while循环，让n降低到一半，并对x进行平方。
注意：min的绝对值大于max绝对值，所以Integer.MIN_VALUE的绝对值会越界；所以要用long值记录n的绝对值。
class Solution {
public double myPow(double x, int n) {
if(n==0) return 1;
long abs = Math.abs((long)n);
double res = 1;
while(abs >0){
if(abs%2 != 0) {
res *= x;
}
x *= x;
abs /= 2;
}
if(n<0) {
return 1/res;
} else {
return res;
}
}
}
【不推荐】用Recursive方法做。
public double myPow(double x, int n) {
return n<0? 1/helper(x,-n):helper(x,n);
}
private double helper(double x, int n){
if(n==0) return 1;
double y = helper(x,n/2);
if(n%2 != 0){
return y * y * x;
} else {
return y * y;
}
}
Leetcode 365. Water and Jug Problem 【Medium】
这是纯数学问题。只有当z%(x和y的最大公约数)==0 时才为true。
math theory 链接：Bézout's identity 数学家 Mathematician 读音：/'bezu/ 贝祖
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if(x+y<z) return false;
if(x==z || y==z || x+y==z) return true;
return z % gcd(x,y) == 0;
}
//辗转相除法，iterative方法。
public int gcd(int a, int b){
while(b!=0){
int temp = b;
b = a%b;
a = temp;
}
return a;
}
}
辗转相除法，英文是Euclidean Algorithm,欧几里得算法。【juːˌklɪdiən】
最大公约数的Recursive写法：
public int gcd(int a, int b){
if(b==0) return a;
return gcd(b,a%b);
}
Leetcode 204 Count Primes 【Easy】
构建一个boolean[] 用来记录每个数是否为prime。外层for循环遍历数组，内层for循环, 改变 i的倍数对应的boolean，从而得到每个数是否为prime的信息。
class Solution {
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n+1]; //j<=n/i情况下用n+1.若是i*j<n,用n就行
int res = 0;
for(int i=2;i<n;i++){
if(notPrime[i]==false){
res++;
// System.out.println(i);
for(int j=2;j<=n/i;j++){ //或者： (int j=2,i*j<n,j++)也可
notPrime[i*j] = true;
}
}
}
return res;
}
}
Leetcode 1. Two Sum. 【Easy】
经典题，用HashMap来记录前面存在的值和对应位置。for循环遍历至某值，查询target-该值在map中是否存在。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[]{-1,-1};
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
if(map.containsKey(target-nums[i])){
res[0] = map.get(target-nums[i]);
res[1] = i;
break;
}
map.put(nums[i],i);
}
return res;
}
}
Leetcode 167. Two Sum II - Input array is sorted. 【Easy】
Time: O(n).
题目：已经排序完毕。
经典题，参考了二分法的步骤，但这里是right--或left++，每次只移动一步
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length-1;
while(left<right){
if(numbers[left]+numbers[right]==target){
return new int[]{left+1,right+1};
} else if(numbers[left]+numbers[right]>target){
right--;
} else {
left++;
}
}
return new int[]{-1,-1};
}
}
Leetcode 15. 3Sum. 【Medium】
Time: O(n2).
题目没排序。要用二分法思想，需要先排序。只有在从小到大排序好的数组中，才能移动left和right，而且才能达到避免duplicate的目的。
参考Leetcode 167. 同样是运用了二分法的思想。难点在于怎么把三个数之和转化为两个数之和。
要避免duplicate重复，首先需要排序。用Arrays.sort() 排序。
然后第一层for循环遍历数组，第二层while用left和right，遍历该数右边的子数组。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i<nums.length-2; i++){
if(i>0 && nums[i]==nums[i-1]) continue; //避免duplicate的关键1
int left = i+1, right = nums.length-1;
int sum = 0 - nums[i];
while(left<right){
if(nums[left]+nums[right]==sum){
res.add(Arrays.asList(nums[i],nums[left],nums[right])); //Arrays.asList().
//两个while循环是避免duplicate的关键2
while(left<right && nums[left+1]==nums[left]) left++; //left<right是防止越界
while(left<right && nums[right-1]==nums[right]) right--; //left<right是防止越界
left++;
right--;
} else if(nums[left]+nums[right]>sum){
right--;
} else {
left++;
}
}
}
return res;
}
}
Leetcode 16.
题目没排序。要用二分法思想，需要先排序。只有在从小到大排序好的数组中，才能移动left和right。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int res = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for(int i=0; i<nums.length-2;i++){
int left = i+1, right = nums.length-1;
while(left<right){
int sum = nums[i]+nums[left]+nums[right];
if(Math.abs(sum-target)<Math.abs(res-target)){
res = sum;
}
if(sum>target){
right--;
} else {
left++;
}
}
}
return res;
}
}
Leetcode 259. 3Sum Smaller 【Medium】
class Solution {
public int threeSumSmaller(int[] nums, int target) {
int res = 0;
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int left = i+1, right = nums.length-1;
while(left<right){
int sum = nums[i]+nums[left]+nums[right];
if(sum<target){
res += right-left; //特定的i,特定的left,right(right可以一直左移到left+1,共right-left个)
left++; //测试下一个left
} else {
right--; //right左移，直到找到符合条件的right使得sum<target
}
}
}
return res;
}
}
Leetcode 18. 4Sum. 【Medium】
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length-3;i++){
if(i>0 && nums[i]==nums[i-1]) continue;
//比3Sum多了一个for和一句continue
for(int j=i+1; j<nums.length-2;j++){
if(j>i+1 && nums[j]==nums[j-1]) continue;
int left = j+1, right = nums.length-1;
while(left<right){
int sum = nums[i]+nums[j]+nums[left]+nums[right];
if(sum==target){
list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while(left<right && nums[left+1]==nums[left]) left++;
while(left<right && nums[right-1]==nums[right]) right--;
left++;
right--;
} else if(sum<target){
left++;
} else {
right--;
}
}
}
}
return list;
}
}
网友评论