力扣热题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];
}
}