LeetCode刷题（Easy）

LeetCode刷题

Type：Easy

#7 整数翻转

注意int整数范围
-2147483638 ~ 2147483637
在翻转计算之前需要判断翻转后是否会超出范围

class Solution {
public int reverse(int x) {
    int res = 0;
    while(x != 0){
        int tmp = x % 10;
        x = x / 10;
        if((res > Integer.MAX_VALUE / 10) || (res == Integer.MAX_VALUE/10 && tmp > 7)){
            return 0;
        }
        if((res < Integer.MIN_VALUE / 10) || (res == Integer.MIN_VALUE/10 && tmp < -8)){
            return 0;
        }
        res = res * 10 + tmp;
    }
    return res;
}
}

#9 回文数

如果整数是回文数，那么后一半一定等于前一半
取一半长度的数，判等即可，要注意奇数长度的数

class Solution {
public boolean isPalindrome(int x) {
    if(x < 0 || (x % 10 == 0 && x != 0))
        return false;
    int reverse = 0;
    while(x > reverse){
        int tmp = x % 10;
        reverse = reverse * 10 + tmp;
        x = x / 10;
    }
    if(x == reverse || x == reverse / 10)
        return true;
    else
        return false;
}
}

#53 最大子序和

https://mxxt.github.io/2018/11/19/Algorithm-1/

#66 加一

一开始想的是循环数组拼成整数，加1，然后再放进数组里，问题是，数组里每个下标元素只存储一个数字，数组是不会超出范围的，但是int是有上下限的，所以不能把它转出int加1
∴ 对数组从后先前循环，最后一位加1，如果等于10，就继续循环（即相当于进位1），如果小于10，就直接加1然后break循环

class Solution {
public int[] plusOne(int[] digits) {
    int n = digits.length;
    if(n == 0){
        int[] res = new int[1];
        res[0] = 0;
        return res;
    }
    for(int i = n - 1; i >= 0; --i){
        if(digits[i] + 1 == 10){
            digits[i] = 0;
        }else{
            digits[i]++;
            break;
        }
    }
    if(digits[0] == 0){
        n++;
        int[] res = new int[n];
        res[0] = 1;
        for(int i = 1; i < n;i++){
            res[i] = digits[i-1];
        }
        return res;
    }else{
        return digits;
    }
}
}

#125 验证回文串

针对几个测试用例去修改代码

"a"    true
"....a.." true
"." true

第一种方法：
先判断字符串有没有字母或数字，只要有一个即可，如果没有的话直接返回true（即为回文串）。再从前和从后同时循环，如果 i 位置不是字母或数字，i++同时continue直接继续进行循环，同理如果 j 位置不是字母或数字，j–同时continue直接继续进行循环。如果 i 和 j 位置都是字母或数字，比较两个位置的字符，不相等就返回false

class Solution {
public boolean isPalindrome(String s) {
    String tmp = s.replace(" ","").toLowerCase();
    if(tmp.length() == 0){
        return true;
    }
    int i = 0;
    int j = tmp.length() - 1;
    boolean flag = false;
    for(i = 0; i <= j; ++i){
        if(Character.isLetterOrDigit(tmp.charAt(i))){
            flag = true;
            break;
        }
    }
    if(flag == false)
        return true;
    while(i <= j){
        if(!Character.isLetterOrDigit(tmp.charAt(i))){
            i++;
            continue;
        }
        if(!Character.isLetterOrDigit(tmp.charAt(j))){
            j--;
            continue;
        }

        if(tmp.charAt(i) != (tmp.charAt(j))){
            return false;
        }else{
            i++;
            j--;
            flag = true;
        }
    }
    return flag;
}
}

第二种方法：
使用StringBuilder来帮助计算。从头循环字符串，如果 i 位置是字母或数字，就添加到StringBuilder中，最后判断StringBuilder.toString()和StringBuilder.reverse().toString()是否相等即可

class Solution {
public boolean isPalindrome(String s) {
    s = s.toLowerCase();
    int n = s.length();
    if(n == 0){
        return true;
    }
    StringBuilder tmp = new StringBuilder();
    for(int i = 0; i < n; ++i){
        if(Character.isLetterOrDigit(s.charAt(i))){
            tmp.append(s.charAt(i));
        }
    }
    if(tmp.toString().equals(tmp.reverse().toString())){
        return true;
    }else{
        return false;
    }
}
}

#70 爬楼梯

仿Fibonacci数列，n = 1 时返回 1，n = 2 时返回 2，n = 3 时开始循环（不能用递归！递归会自动创建系统栈，对空间和时间都不友好，会超时）

class Solution {
public int climbStairs(int n) {
    if(n == 1){
        return 1;
    }
    if(n == 2){
        return 2;
    }
    int sum = 0;
    int s1 = 1;
    int s2 = 2;
    int step = 3;
    while(step <= n){
        sum = s1 + s2;
        s1 = s2;
        s2 = sum;
        ++step;
    }
    return sum;
}
}

#263 丑数

对 num 不断用 2，3，5去除，如果余数最终只有 1，2，3，5 这四种情况是就返回true，说明没有别的因数（这个因数不能用 2，3，5 表示）

class Solution {
public boolean isUgly(int num) {
    if(num <= 0){
        return false;
    }
    while(num % 2 == 0){
        num /= 2;
    }
    while(num % 3 == 0){
        num /= 3;
    }
    while(num % 5 == 0){
        num /= 5;
    }
    return (num == 1 || num == 2 || num == 3 || num == 5);
}
}

#26 删除排序数组中的重复项

用 i 来控制数组的长度，如果 j 找到下一个不同的数则记录到 i 里

class Solution {
public int removeDuplicates(int[] nums) {
    if(nums.length == 0)
        return 0;
    int i = 0;
    for(int j = 1; j < nums.length; ++j){
        if(nums[j] != nums[i]){
            nums[i+1] = nums[j];
            i++;
        }
    }
    System.out.println(i+1);
    return i+1;
}
}

#441 排列硬币

求的是 1 + 2 + 3 + … + x < n 即
(1 + x) x < 2n => x² + x - 2n < 0
△x = b² - 4ac = 1 + 8n
x = (-b ± △x^½) / 2a => x = ((1 + 8n)^½ - 1) / 2
因为 n 可能会超出int范围，所以需要转换一下类型

class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.sqrt(1 + 8 * (long)n) - 1) / 2;
    }
}