【堆、位运算、数学】算法例题

 

目录

 

十九、堆

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] <= 109
• nums1 和 nums2 均为 升序排列
• 1 <= k <= 104
• k <= 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 <= 104
• a 和 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 <= 100
• 0 <= 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;}}//如果所有位都是进位，则长度+1digits= 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-1
• n 是一个整数
• 要么 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/