目录
十九、堆
121. 数组中的第K个最大元素 ②
122. IPO ③
123. 查找和最小的K对数字 ② ×
124. 数据流的中位数 ③
二十、位运算
125. 二进制求和 ①
126. 颠倒二进制位 ①
127. 位1的个数 ①
128. 只出现一次的数字 ①
129. 只出现一次的数字 II ②
130. 数字范围按位与 ②
二十一、数学
131. 回文数 ①
132. 加一 ①
133. 阶乘后的零 ② √-
134. x的平方根 ①
135. Pow(x,n) ② ×
十九、堆
121. 数组中的第K个最大元素 ②
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
方法1： 简单方法用时少，第二个方法有的案例超时
public static int findKthLargest(int[] nums, int k) {
// 方法1：
// Arrays.sort(nums);
// System.out.println(nums[nums.length - k]);
// 方法2：超时
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
for (int num : nums) {
if (stack.size() == 0 || num > stack.peek()){
stack.push(num);
}else {
while (stack.size() > 0 && num < stack.peek()){
list.add(stack.pop());
}
stack.push(num);
int index = list.size() - 1;
while (index >= 0){
stack.push(list.get(index--));
if (index == -1){
list.clear();
}
}
}
}
int index = 0;
while (true){
if (index == k - 1){
break;
}
index++;
stack.pop();
}
return stack.peek();
}方法2：
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
return b - a;
});
for (int i : nums) {
queue.add(i);
}
int result = 0;
for (int i = 0; i < k; i++) {
result = queue.poll();
}
return result;
}122. IPO ③
123. 查找和最小的K对数字 ② ×
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。
示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 输出: [1,1],[1,1] 解释: 返回序列中的前 2 对数： [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
提示:
1 <= nums1.length, nums2.length <= 105-109 <= nums1[i], nums2[i] <= 109nums1和nums2均为 升序排列1 <= k <= 104k <= nums1.length * nums2.length
解题思路：. - 力扣（LeetCode）
方法2：（14ms） 多路归并
class Solution {
int[] nums1, nums2;
int n, m;
public List<List<Integer>> kSmallestPairs(int[] n1, int[] n2, int k) {
nums1 = n1; nums2 = n2;
n = nums1.length; m = nums2.length;
List<List<Integer>> ans = new ArrayList<>();
int l = nums1[0] + nums2[0], r = nums1[n - 1] + nums2[m - 1];
while (l < r) {
int mid = (int)(0L + l + r >> 1);
if (check(mid, k)) r = mid;
else l = mid + 1;
}
int x = r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (nums1[i] + nums2[j] < x) {
List<Integer> temp = new ArrayList<>();
temp.add(nums1[i]); temp.add(nums2[j]);
ans.add(temp);
} else break;
}
}
for (int i = 0; i < n && ans.size() < k; i++) {
int a = nums1[i], b = x - a;
int c = -1, d = -1;
l = 0; r = m - 1;
while (l < r) {
int mid = (int)(0L + l + r >> 1);
if (nums2[mid] >= b) r = mid;
else l = mid + 1;
}
if (nums2[r] != b) continue;
c = r;
l = 0; r = m - 1;
while (l < r) {
int mid = (int)(0L + l + r + 1) >> 1;
if (nums2[mid] <= b) l = mid;
else r = mid - 1;
}
d = r;
for (int p = c; p <= d && ans.size() < k; p++) {
List<Integer> temp = new ArrayList<>();
temp.add(a); temp.add(b);
ans.add(temp);
}
}
return ans;
}
boolean check(int x, int k) {
int ans = 0;
for (int i = 0; i < n && ans < k; i++) {
for (int j = 0; j < m && ans < k; j++) {
if (nums1[i] + nums2[j] <= x) ans++;
else break;
}
}
return ans >= k;
}
}
作者：宫水三叶
链接：https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/solutions/1209848/gong-shui-san-xie-duo-lu-gui-bing-yun-yo-pgw5/
方法3：（15ms） 二分法
class Solution {
int[] nums1, nums2;
int n, m;
public List<List<Integer>> kSmallestPairs(int[] n1, int[] n2, int k) {
nums1 = n1; nums2 = n2;
n = nums1.length; m = nums2.length;
List<List<Integer>> ans = new ArrayList<>();
int l = nums1[0] + nums2[0], r = nums1[n - 1] + nums2[m - 1];
while (l < r) {
int mid = (int)(0L + l + r >> 1);
if (check(mid, k)) r = mid;
else l = mid + 1;
}
int x = r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (nums1[i] + nums2[j] < x) {
List<Integer> temp = new ArrayList<>();
temp.add(nums1[i]); temp.add(nums2[j]);
ans.add(temp);
} else break;
}
}
for (int i = 0; i < n && ans.size() < k; i++) {
int a = nums1[i], b = x - a;
int c = -1, d = -1;
l = 0; r = m - 1;
while (l < r) {
int mid = (int)(0L + l + r >> 1);
if (nums2[mid] >= b) r = mid;
else l = mid + 1;
}
if (nums2[r] != b) continue;
c = r;
l = 0; r = m - 1;
while (l < r) {
int mid = (int)(0L + l + r + 1) >> 1;
if (nums2[mid] <= b) l = mid;
else r = mid - 1;
}
d = r;
for (int p = c; p <= d && ans.size() < k; p++) {
List<Integer> temp = new ArrayList<>();
temp.add(a); temp.add(b);
ans.add(temp);
}
}
return ans;
}
boolean check(int x, int k) {
int ans = 0;
for (int i = 0; i < n && ans < k; i++) {
for (int j = 0; j < m && ans < k; j++) {
if (nums1[i] + nums2[j] <= x) ans++;
else break;
}
}
return ans >= k;
}
}
作者：宫水三叶
链接：https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/solutions/1209848/gong-shui-san-xie-duo-lu-gui-bing-yun-yo-pgw5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。124. 数据流的中位数 ③
二十、位运算
125. 二进制求和 ①
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
提示：
1 <= a.length, b.length <= 104a和b仅由字符'0'或'1'组成- 字符串如果不是
"0"，就不含前导零
力扣题解：. - 力扣（LeetCode）
方法2：（0ms）
public String addBinary(String a, String b) {//测试提交时间
if (a.length() < b.length()) {
return addBinary(b, a);
}
char[] sum = new char[a.length() + 1];
int indexA = a.length() - 1, diffLen = a.length() - b.length();
char carry = '0';
while (indexA > -1) {
char bitB = indexA - diffLen > -1 ? b.charAt(indexA - diffLen) : '0';
if (a.charAt(indexA) == bitB) {
sum[indexA-- + 1] = carry;
carry = bitB;
} else {
sum[indexA-- + 1] = carry == '0' ? '1' : '0';
}
}
sum[0] = carry;
return carry == '1' ? new String(sum, 0, a.length() + 1) : new String(sum, 1, a.length());
}方法3：（1ms）
public String addBinary(String a, String b) {
StringBuilder ans = new StringBuilder();
int ca = 0;
for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
int sum = ca;
sum += i >= 0 ? a.charAt(i) - '0' : 0;
sum += j >= 0 ? b.charAt(j) - '0' : 0;
ans.append(sum % 2);
ca = sum / 2;
}
ans.append(ca == 1 ? ca : "");
return ans.reverse().toString();
}方法4：（2ms）
public String addBinary(String a, String b) {
Deque<Character> stack1 = new ArrayDeque<>();
Deque<Character> stack2 = new ArrayDeque<>();
for (char c : a.toCharArray()) {
stack1.push(c);
}
for (char c1 : b.toCharArray()) {
stack2.push(c1);
}
StringBuffer sb = new StringBuffer();
int carry = 0, sum = 0;
while (stack1.size() > 0 || stack2.size() > 0) {
int a1 = stack1.size() == 0 ? 0 : stack1.pop() - '0';
int a2 = stack2.size() == 0 ? 0 : stack2.pop() - '0';
sum = a1 + a2 + carry;
int mod = sum % 2;
carry = sum / 2;
sb.append(mod);
}
if (carry == 1) sb.append(1);
return sb.reverse().toString();
}126. 颠倒二进制位 ①
颠倒给定的 32 位无符号整数的二进制位。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数
-3，输出表示有符号整数-1073741825。
示例 1：
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：n = 11111111111111111111111111111101 输出：3221225471 (10111111111111111111111111111111) 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：
- 输入是一个长度为
32的二进制字符串
进阶: 如果多次调用这个函数，你将如何优化你的算法？
力扣题解：. - 力扣（LeetCode）
方法2：
int ans = 0;
for (int i = 0; i < 32; i++) {
int t = (n >> i) & 1;
if (t == 1) {
ans |= (1 << (31 - i));
}
}
return ans;
}
作者：宫水三叶
链接：https://leetcode.cn/problems/reverse-bits/solutions/686465/yi-ti-san-jie-dui-cheng-wei-zhu-wei-fen-ub1hi/
方法3：
public int reverseBits(int n) {
int ans = 0;
int cnt = 32;
while (cnt-- > 0) {
ans <<= 1;
ans += (n & 1);
n >>= 1;
}
return ans;
}
作者：宫水三叶
链接：https://leetcode.cn/problems/reverse-bits/solutions/686465/yi-ti-san-jie-dui-cheng-wei-zhu-wei-fen-ub1hi/
方法4：
public int reverseBits(int n) {
n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16);
return n;
}
作者：宫水三叶
链接：https://leetcode.cn/problems/reverse-bits/solutions/686465/yi-ti-san-jie-dui-cheng-wei-zhu-wei-fen-ub1hi/
127. 位1的个数 ①
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数
-3。
示例 1：
输入：n = 00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n = 11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为
32的 二进制串 。
进阶：
- 如果多次调用这个函数，你将如何优化你的算法？
方法2：
public static int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
count += n & 1;
n >>= 1;
}
return count;
}128. 只出现一次的数字 ①
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1] 输出：1
示例 2 ：
输入：nums = [4,1,2,1,2] 输出：4
示例 3 ：
输入：nums = [1] 输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
力扣题解：. - 力扣（LeetCode）
方法1：（12ms）
int res = 0;
if (nums.length == 1){
res = nums[0];
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
for (Map.Entry<Integer, Integer> entry : entries) {
if (entry.getValue() == 1){
res = entry.getKey();
}
}
return res;方法2：（0ms）
异或的方法：（除了某个元素只出现一次以外，其余每个元素均出现两次）
异或：两个相同的数字做异或会抵消。
public int singleNumber(int[] nums) {
int ans = nums[0];
int n = nums.length;
for (int i = 1; i < n;i++){
ans ^= nums[i];
}
return ans;
}129. 只出现一次的数字 II ②
130. 数字范围按位与 ②
二十一、数学
131. 回文数 ①
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121 输出：true
示例 2：
输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。
提示：
-231 <= x <= 231 - 1
方法1：
public boolean isPalindrome(int x) {
int left = 0;
String y = x + "";
int right = y.length() - 1;
while (true){
if (left >= right){
break;
}
if (y.charAt(left) == y.charAt(right)){
left++;
right--;
continue;
}else {
return false;
}
}
return true;
}方法2：
public boolean isPalindrome(int x) {
if (x < 0 || (x != 0 && x % 10 == 0)) {
return false;
}
int reversed = 0;
int original = x;
while (x > reversed) {
reversed = reversed * 10 + x % 10;
x /= 10;
}
return (x == reversed) || (x == reversed / 10);
}132. 加一 ①
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0] 输出：[1]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9
方法1：（0ms）
public int[] plusOne(int[] digits) {
if (digits[digits.length - 1] != 9){
digits[digits.length - 1] += 1;
}else {
int index = digits.length - 1;
while (index >= 0){
if (digits[index] < 9){
digits[index] += 1;
break;
}
digits[index] = 0;
index--;
}
if (digits[0] == 0){
digits = new int[digits.length + 1];
digits[0] = 1;
}
}
return digits;
}方法2：（0ms 简洁）
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0) return digits;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
} public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] == 9) {
digits[i] = 0;
} else {
digits[i] += 1;
return digits;
}
}
//如果所有位都是进位，则长度+1
digits= new int[digits.length + 1];
digits[0] = 1;
return digits;
}133. 阶乘后的零 ② √-
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3 输出：0 解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5 输出：1 解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0 输出：0
提示：
0 <= n <= 104
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
方法1：（33ms）
public static int trailingZeroes(int n) {
if (n <= 0){
return 0;
}
int count = 0;
int countTwo = 0;
int countFive = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num % 10 == 0){
count++;
num /= 10;
}
while (num % 2 == 0 && num % 5 != 0){
countTwo++;
num /= 2;
}
while (num % 2 != 0 && num % 5 == 0){
countFive++;
num /= 5;
}
}
return count + Math.min(countTwo, countFive);
}
方法2：（7ms）
public int trailingZeroes(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int N = i;
while (N > 0) {
if (N % 5 == 0) {
count++;
N /= 5;
} else {
break;
}
}
}
return count;
}
作者：windliang
链接：https://leetcode.cn/problems/factorial-trailing-zeroes/solutions/47030/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/
方法3：（0ms）
public int trailingZeroes(int n) {
int count = 0;
while (n > 0) {
count += n / 5;
n = n / 5;
}
return count;
}
作者：windliang
链接：https://leetcode.cn/problems/factorial-trailing-zeroes/solutions/47030/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/
134. x的平方根 ①
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
方法2：
public int mySqrt(int x) {
// 特殊值判断
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
int left = 1;
int right = x / 2;
// 在区间 [left..right] 查找目标元素
while (left < right) {
int mid = left + (right - left + 1) / 2;
// 注意：这里为了避免乘法溢出，改用除法
if (mid > x / mid) {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
} else {
// 下一轮搜索区间是 [mid..right]
left = mid;
}
}
return left;
}
作者：liweiwei1419
链接：https://leetcode.cn/problems/sqrtx/solutions/7866/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/
方法3：
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = (int) Math.exp(0.5 * Math.log(x));
return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}135. Pow(x,n) ② ×
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1n是一个整数- 要么
x不为零，要么n > 0。 -104 <= xn <= 104
方法1：（291/306）
public double myPow(double x, int n) {
if (x == 0){
return 0;
}
int m = n;
if (n < 0){
m = -n;
}
double res = 1;
int count = 1;
while (count <= m){
res = res * x;
count++;
}
return n < 0? 1 / res : res;
}方法2：（0ms）
解题思路：. - 力扣（LeetCode）
class Solution {
public double myPow(double x, int n) {
if(x == 0.0f) return 0.0d;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
}
作者：Krahets
链接：https://leetcode.cn/problems/powx-n/solutions/241471/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/
