378. 有序矩阵中第K小的元素

class Solution { public int kthSmallest(int[][] matrix, int k) { int rows = matrix.length, columns = matrix[0].length; int[] sorted = new int[rows * columns]; int index = 0; for (int[] row : matrix) { for (int num : row) { sorted[index++] = num; } } Arrays.sort(sorted); return sorted[k - 1]; } } class Solution { public int kthSmallest(int[][] matrix, int k) { //创建一个堆，并设置元素的排序方式 PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b) -> a[0] - b[0]); int n = matrix.length; for (int i = 0; i < n; i++) { pq.offer(new int[]{matrix[i][0], i, 0}); } for (int i = 0; i < k - 1; i++) { int[] now = pq.poll(); if (now[2] != n - 1) { pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1}); } } return pq.poll()[0]; } } class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int left = matrix[0][0]; int right = matrix[n - 1][n - 1]; while (left < right) { int mid = left + ((right - left) >> 1); if (check(matrix, mid, k, n)) { right = mid; } else { left = mid + 1; } } return left; } public boolean check(int[][] matrix, int mid, int k, int n) { int i = n - 1; int j = 0; int num = 0; while (i >= 0 && j < n) { if (matrix[i][j] <= mid) { num += i + 1; j++; } else { i--; } } return num >= k; } }

29. 两数相除

class Solution { public int divide(int dividend, int divisor) { if (dividend == 0) { return 0; } if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } boolean negative; negative = (dividend ^ divisor) < 0;//用异或来计算是否符号相异 long t = Math.abs((long) dividend); long d= Math.abs((long) divisor); int result = 0; for (int i=31; i>=0;i--) { if ((t>>i)>=d) {//找出足够大的数2^n*divisor result += 1<<i;//将结果加上2^n t -= d<<i;//将被除数减去2^n*divisor } } return negative ? -result : result;//符号相异取反 } }

371. 两整数之和

class Solution { public int getSum(int a, int b) { //两个整数a, b; a ^ b是无进位的相加； a&b得到每一位的进位；让无进位相加的结果与进位不断的异或， 直到进位为0； int sum,carry; sum = a^b; carry = (a&b)<<1; if(carry!=0){ return getSum(sum,carry); } return sum; } } class Solution { public int getSum(int a, int b) { //两个整数a, b; a ^ b是无进位的相加； a&b得到每一位的进位；让无进位相加的结果与进位不断的异或， 直到进位为0； if (a==0) return b; if (b==0) return a; int lower; int carrier; while (true) { lower = a^b; // 计算低位 carrier = a&b; // 计算进位 if (carrier==0) break; a = lower; b = carrier<<1; } return lower; } }

你知道的越多，你不知道的越多。