每周leetcode - 06 数组专题 7~739~50~offer 62~26~189~9

leetcode - 7. 整数反转（求%+/）

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。假设环境不允许存储 64 位整数（有符号或无符号）。

class Solution {
    
    public int reverse(int x) {
    
        int res = 0;
        // x=-123
        while (x!=0){
    
            if(res> Integer.MAX_VALUE /10|| res <Integer.MIN_VALUE/10){
    
                return 0;
            }
            // -3
            // -3*10-2
            // -32*10 -1
            res = res*10 + x%10;
            x = x/10;
        }
        return res;
    }
}

leetcode - 739. 每日温度（暴力法+单调栈）

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

方法1：暴力方法

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        int[] arr = new int[temperatures.length];
        if(temperatures==null || temperatures.length==0){
    
            return arr;
        }
        // [73,74,75,71,69,72,76,73]
        // [1,1,4,2,1,1,0,0]
        for(int i=0;i<temperatures.length;i++){
    
            int current = temperatures[i];
            for(int j=i+1;j<temperatures.length;j++){
    
                if(current<temperatures[j]){
    
                    arr[i] = j-i;
                    break;
                }
            }
        }
        return arr;
    }
}

方法2：单调栈

class Solution {
    
    public int[] dailyTemperatures(int[] temperatures) {
    
        int[] arr = new int[temperatures.length];
        Deque<Integer> stack = new LinkedList<>();
        // [73,74,75,71,69,72,76,73]
        // [1,1,4,2,1,1,0,0]
        for(int i=0;i<temperatures.length;i++){
    
            // 如果当前元素大于栈顶索引处元素，弹出，并赋值
            while(!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]){
    
                Integer index = stack.pop();
                arr[index] = i-index;
            }
            // 入栈
            stack.push(i);
        }
        return arr;
    }
}

leetcode - 50. Pow(x, n) （递归）

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n ）。

class Solution {
    
    public double myPow(double x, int n) {
    
        if(n>0){
    
            return pow(x,n);
        }else{
    
            return 1/pow(x,n);
        }
    }

    private double pow(double x, int n) {
    
        if(n==0) return 1;
        double y = pow(x,n/2);
        if(n%2==0){
    
            return y*y;
        }else{
    
            return y*y*x;
        }
    }
}

剑指 Offer 62. 圆圈中最后剩下的数字（动态规划）

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

class Solution {
    
    public int lastRemaining(int n, int m) {
    
        // dp[i]代表长度为i时，最终留下元素的序号
        int[] dp = new int[n+1];
        dp[1] = 0;
        for(int i=2;i<=n;i++){
    
            dp[i] = (dp[i-1]+m)%i;
        }
        // 最终序号就是元素
        return dp[n];
    }
}

leetcode- 26. 删除有序数组中的重复项 (双指针)

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

将最终结果插入 nums 的前 k 个位置后返回 k 。不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

class Solution {
    
    public int removeDuplicates(int[] nums) {
    
        int i = 0;
        int j = 0;
        while (j<nums.length){
    
            if(nums[i]==nums[j]){
    
                j++;
            }else{
    
                i++;
                nums[i] = nums[j];
            }
        }
        return i+1;
    }
}

leetcode - 189. 轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

class Solution {
    
    public void rotate(int[] nums, int k) {
    
        if(nums==null || nums.length==0){
    
            return;
        }
        k =  k % nums.length;
        reverse(0,nums.length-1,nums);
        reverse(0,k-1,nums);
        reverse(k,nums.length-1,nums);
    }

    private void reverse(int left, int right, int[] nums) {
    
        while (left<right){
    
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }
}

leetcode - 9. 回文数（求%+/）

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

class Solution {
    
    public static void main(String[] args) {
    
        isPalindrome(121);
    }
    public static boolean isPalindrome(int x) {
    
        if(x<0){
    
            return false;
        }
        int current = x;
        int result = 0;
        while (current>0){
    
            result = result*10 + current%10;
            current = current/10;
        }
        if(result==x){
    
            return true;
        }
        return false;
    }
}