网站开发运营工作总结,如何在网上做网站推广,资源专业网站优化排名,保定网站免费制作目录 十九、堆
121. 数组中的第K个最大元素 ②
122. IPO ③
123. 查找和最小的K对数字 ②
124. 数据流的中位数 ③
二十、位运算
125. 二进制求和 ①
126. 颠倒二进制位 ①
127. 位1的个数 ①
128. 只出现一次的数字 ①
129. 只出现一次的数字 II ②
130. 数字范围…
目录 十九、堆
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超时ArrayListInteger list new ArrayList();StackInteger 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) {PriorityQueueInteger 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
方法214ms 多路归并
class Solution {int[] nums1, nums2;int n, m;public ListListInteger kSmallestPairs(int[] n1, int[] n2, int k) {nums1 n1; nums2 n2;n nums1.length; m nums2.length;ListListInteger 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) {ListInteger 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) {ListInteger 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/方法315ms 二分法
class Solution {int[] nums1, nums2;int n, m;public ListListInteger kSmallestPairs(int[] n1, int[] n2, int k) {nums1 n1; nums2 n2;n nums1.length; m nums2.length;ListListInteger 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) {ListInteger 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) {ListInteger 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
方法20ms 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());}
方法31ms 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();}
方法42ms public String addBinary(String a, String b) {DequeCharacter stack1 new ArrayDeque();DequeCharacter 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
方法112ms int res 0;if (nums.length 1){res nums[0];}HashMapInteger, Integer map new HashMap();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}SetMap.EntryInteger, Integer entries map.entrySet();for (Map.EntryInteger, Integer entry : entries) {if (entry.getValue() 1){res entry.getKey();}}return res;
方法20ms
异或的方法除了某个元素只出现一次以外其余每个元素均出现两次
异或两个相同的数字做异或会抵消。 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 方法10ms 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;}
方法20ms 简洁 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 进阶你可以设计并实现对数时间复杂度的算法来解决此问题吗 方法133ms 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);}方法27ms
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/方法30ms 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
方法1291/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;}
方法20ms
解题思路. - 力扣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/
