第23天--算法（Leetcode 66,69,70,73,75）
66.加一
public int[] plusOne(int[] digits) { int N = digits.length; for(int i = N - 1;i >= 0;i --) { if(digits[i] < 9) { digits[i] ++; return digits; } digits[i] = 0; } int ans[] = new int[N + 1]; ans[0] = 1; return ans; } 69.Sqrt(x) public int mySqrt(int x) { if(x == 0) { return 0; } if(x < 3) { return 1; } long L = 0; long M = 0; long R = x; long ans = -1; while(L <= R) { M = (L + R) >> 1; if(M * M <= x) { ans = M; L = M + 1; }else { R = M - 1; } } return (int)ans; } 70.爬楼梯 public int climbStairs(int n) { int dp[] = new int[n + 1]; if(n < 0) { return 0; } if(n == 0 || n == 1 || n == 2) { return n; } dp[1] = 1; dp[2] = 2; for(int i = 3;i <= n;i ++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } 73.矩阵置零 public void setZeroes(int[][] matrix) { boolean rowisZero = false; boolean colisZero = false; for(int j = 0;j < matrix[0].length;j ++) { if(matrix[0][j] == 0) { rowisZero = true; break; } } for(int i = 0;i < matrix.length;i ++) { if(matrix[i][0] == 0) { colisZero = true; break; } } for(int i = 1;i < matrix.length;i ++) { for(int j = 1;j < matrix[0].length;j ++) { if(matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for(int i = 1;i < matrix.length;i ++) { if(matrix[i][0] == 0) { for(int j = 1;j < matrix[0].length;j ++) { matrix[i][j] = 0; } } } for(int j = 1;j < matrix[0].length;j ++) { if(matrix[0][j] == 0) { for(int i = 1;i < matrix.length;i ++) { matrix[i][j] = 0; } } } if(rowisZero) { for(int j = 0;j < matrix[0].length;j ++) { matrix[0][j] = 0; } } if(colisZero) { for(int i = 0;i < matrix.length;i ++) { matrix[i][0] = 0; } } } 75.颜色分类 public void sortColors(int[] nums) { int index = 0; int less = -1; int more = nums.length; while(index < more) { if(nums[index] == 1) { index ++; }else if(nums[index] == 0) { swap(nums,index ++,++ less); }else { swap(nums,index,-- more); } } } public void swap(int arr[],int x,int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; }