力扣热题6-pow位运算

---

按照leetcode刷一遍：leetcode hot

50. Pow(x, n)

边界条件的人处理，Integer.MIN_VALUE和*2操作。

递归

class Solution {
    public double myPow(double x, int n) {
        System.out.println(n);
        if(n==0) return 1;
        if(n<0) {
            if(n==Integer.MIN_VALUE) return 1/(x*myPow(x,Integer.MAX_VALUE));
            return 1/myPow(x,-n); 
        }
        int idx = 1;
        double tmpx = x;
        while(idx<n/2) {
            tmpx = tmpx*tmpx;
            idx*=2;
        }
        return tmpx*myPow(x,n-idx);
    }
}

位运算

class Solution {
    public double myPow(double x, int n) {
        //System.out.println(n);
        if(n==0) return 1;
        if(n<0) {
            if(n==Integer.MIN_VALUE) return 1/(x*myPow(x,Integer.MAX_VALUE));
            return 1/myPow(x,-n); 
        }
        int curBit = n&1;
        double tmpx = x;
        double result = curBit==0?1.0f:x;
        for(int i=1;i<=31;i++) {
            curBit = n&(1<<i);
            tmpx *= tmpx;
            if(curBit==0) {
                continue;
            }
            result *= tmpx;
        }
        return result;
    }
}

53. 最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int cur = 0;
        for(int i=0;i<nums.length;i++) {
            cur+=nums[i];
            result = Math.max(result,cur);
            if(cur<0) {
                cur=0;
            } 
        }
        return result;
    }
}

进阶

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

复杂度nlogn，也不太好想，略过。

54. 螺旋矩阵

纯模拟

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int i=0;
        int j=0;
        int layer = 0;
        for(layer=0;layer<Math.min(m+1,n+1)/2;layer++) {
            i=layer;
            j=layer;
            while(result.size()<m*n&&j!=n-1-layer) {
                result.add(matrix[i][j]);
                j++;
            }
            while(result.size()<m*n&&i!=m-1-layer) {
                result.add(matrix[i][j]);
                i++;
            }
            while(result.size()<m*n&&j!=layer) {
                result.add(matrix[i][j]);
                j--;
            }
            while(result.size()<m*n&&i!=layer) {
                result.add(matrix[i][j]);
                i--;
            }
        }
        if(m==n&&m%2==1) {
            result.add(matrix[m/2][n/2]);
        }
        return result;
    }
}

55. 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        // dp 每个位置记录最远的距离
        if(nums.length<=1) return true;
        int maxLen = 0;
        for(int i=0;i<nums.length-1;i++) {
            if(maxLen<i) return false;
            maxLen = Math.max(maxLen,i+nums[i]);
            if(maxLen>=nums.length-1) return true;
        }
        return false;
    }
}

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] result = new int[intervals.length][intervals[0].length];
        for(int i=0;i<intervals.length;i++) {
            for(int j=0;j<intervals[0].length;j++) {
                result[i][j] = intervals[i][j];
            }
        }
        Arrays.sort(result,(o1,o2)->{
            if(o1[0]!=o2[0]) {
                return o1[0]-o2[0];
            }
            return o1[1]-o2[1];
        });
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{result[0][0],result[0][1]});
        for(int i=1;i<intervals.length;i++) {
            if(result[i][0]<=list.get(list.size()-1)[1]) {
                list.get(list.size()-1)[1] = Math.max(list.get(list.size()-1)[1],result[i][1]);
            } else {
                list.add(new int[]{result[i][0],result[i][1]});
            }
        }
        return list.toArray(new int[0][2]);
    }
}

62. 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++) dp[i][0]=1;
        for(int j=0;j<n;j++) dp[0][j]=1;

        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

简化dp复杂度

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp,1);

        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[j]=dp[j]+dp[j-1];
            }
        }
        return dp[n-1];
    }
}