Leetcode 7. Reverse Integer 【Easy】
難點(diǎn)在于 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正則表達(dá)式中吭练，. 匹配除"\r\n"之外的任何單個字符析显。\. 表示匹配 . 本身。為什么是兩個 \ 呢？java的 \ 等同于其他語言的一個 \ 浑侥。
難點(diǎn)在于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循環(huán)倒序遍歷來解決构资。
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記錄數(shù)字開始的位置吐绵。遍歷。
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】
常規(guī)暴力解法己单。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;
}
}
找規(guī)律：以9為循環(huán)
class Solution {
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
}
Leetcode 67. Add Binary 【Easy】
倒序遍歷兩個數(shù)組纹笼。用while(i>=0 || j>=0)作為判斷，用remainder記錄進(jìn)位苟跪。
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循環(huán)，倒序遍歷鳞陨，每次計(jì)算兩個一位數(shù)的乘積，累加到new int[]對應(yīng)位置
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的必須是非零數(shù)
res += digit;
}
}
System.out.println(res);
return res.length() == 0? "0": res;
}
}
Leetcode 29. Divide Two Integers 【Medium】
這題考了左移的操作厦滤。用 divideHelper 測試dividend 能裝多少個divisor歼狼，用的while()循環(huán)，實(shí)際上是類似二分查找羽峰。
注意：把兩個負(fù)數(shù)傳入divideHelper添瓷，是因?yàn)?MIN_VALUE 絕對值比 MAX_VALUE 大1，如果 abs(MIN_VALUE) 會越界鳞贷。所以干脆傳兩個負(fù)數(shù)進(jìn)helper.
class Solution {
public int divide(int dividend, int divisor) {
//負(fù)數(shù)左移，也是相當(dāng)于*2,直到小于MIN_VALUE,就越界成為正數(shù)(不規(guī)則的正數(shù))
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恢復(fù)為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 可能越界，所以應(yīng)該設(shè)置mid為long迅箩。比如當(dāng)x=MAX_VALUE, 第一次計(jì)算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){ //必定的結(jié)果
// return high;
// }
// return 0;
}
}
牛頓法：
牛頓法，又名切線法饲趋。
CSDN搜索： leetcode:Sqrt(x) 牛頓迭代法求整數(shù)開方
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 ...
公式推導(dǎo)：
經(jīng)過 (xn+1,0), ( xn, f(xn) ) 且斜率為f'(xn) 的直線，直線表達(dá)式為：
( f(xn)-0 ) / (xn - xn+1) = f'(xn) , 化簡得到：
而本題 f(xn) = x^2 - n, f' = 2x. 所以，
xn+1 = xn - (x^2-n)/2x
= (x + n/x)/2.
牛頓法的Time Complexity 是unstable 不穩(wěn)定的投队，可以理解為 接近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 可能越界扒披，所以應(yīng)該設(shè)置mid為long。比如當(dāng)x=MAX_VALUE, 第一次計(jì)算mid^2就必然越界
return true;
} else if (mid * mid < num){
low = (int)mid + 1;
} else {
high = (int)mid - 1;
}
}
return false;
}
}
牛頓法：Time 是 uncertain碟案，但在這題可理解為優(yōu)于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循環(huán)鳖目，讓n降低到一半，并對x進(jìn)行平方领迈。
注意：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】
這是純數(shù)學(xué)問題。只有當(dāng)z%(x和y的最大公約數(shù))==0 時才為true扯夭。
math theory 鏈接：Bézout's identity 數(shù)學(xué)家 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;
}
//輾轉(zhuǎn)相除法，iterative方法交洗。
public int gcd(int a, int b){
while(b!=0){
int temp = b;
b = a%b;
a = temp;
}
return a;
}
}
輾轉(zhuǎn)相除法，英文是Euclidean Algorithm,歐幾里得算法构拳。【ju??kl?di?n】
最大公約數(shù)的Recursive寫法：
public int gcd(int a, int b){
if(b==0) return a;
return gcd(b,a%b);
}
Leetcode 204 Count Primes 【Easy】
構(gòu)建一個boolean[] 用來記錄每個數(shù)是否為prime置森。外層for循環(huán)遍歷數(shù)組，內(nèi)層for循環(huán), 改變 i的倍數(shù)對應(yīng)的boolean凫海，從而得到每個數(shù)是否為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】
經(jīng)典題行贪，用HashMap來記錄前面存在的值和對應(yīng)位置漾稀。for循環(huán)遍歷至某值建瘫，查詢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).
題目：已經(jīng)排序完畢殷蛇。
經(jīng)典題，參考了二分法的步驟橄浓，但這里是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).
題目沒排序贮配。要用二分法思想，需要先排序泪勒。只有在從小到大排序好的數(shù)組中宴猾，才能移動left和right叼旋，而且才能達(dá)到避免duplicate的目的。
參考Leetcode 167. 同樣是運(yùn)用了二分法的思想夫植。難點(diǎn)在于怎么把三個數(shù)之和轉(zhuǎn)化為兩個數(shù)之和。
要避免duplicate重復(fù)详民，首先需要排序。用Arrays.sort() 排序沈跨。
然后第一層for循環(huán)遍歷數(shù)組由捎，第二層while用left和right狞玛，遍歷該數(shù)右邊的子數(shù)組。
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的關(guān)鍵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循環(huán)是避免duplicate的關(guān)鍵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.
題目沒排序心肪。要用二分法思想，需要先排序硬鞍。只有在從小到大排序好的數(shù)組中，才能移動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;
}
}
