刷题日记 24.5.4

lc502. IPO（HD）

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

• 1 <= k <= 10^5
• 0 <= w <= 10^9
• n == profits.length
• n == capital.length
• 1 <= n <= 10^5
• 0 <= profits[i] <= 10^4
• 0 <= capital[i] <= 10^9

---

如果不限制次数下我们可以获取的最大利润，我们应该如何处理？我们只需将所有的项目按照资本的大小进行排序，依次购入项目$i$ ，同时手中持有的资本增加$profits[i]$，直到手中的持有的资本无法启动当前的项目为止。

• 如果初始资本$w≥max⁡(capital)$ ，我们直接返回利润中的$k$ 个最大元素的和即可

• 当前的题目中限定了可以选择的次数最多为$k$ 次，这就意味着我们应该贪心地保证选择每次投资的项目获取的利润最大，这样就能保持选择$k$ 次后获取的利润最大

• 我们首先将项目按照所需资本的从小到大进行排序，每次进行选择时，假设当前手中持有的资本为$w$，我们应该从所有投入资本小于等于$w$ 的项目中选择利润最大的项目$j$，然后此时我们更新手中持有的资本为$w+profits[j]$，同时再从所有花费资本小于等于$w+profits[j]$ 的项目中选择，我们按照上述规则不断选择$k$ 次即可

• 我们利用大根堆的特性，我们将所有能够投资的项目的利润全部压入到堆中，每次从堆中取出最大值，然后更新手中持有的资本，同时将待选的项目利润进入堆，不断重复上述操作

• 如果当前的堆为空，则此时我们应当直接返回

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int curr = 0;
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> heap = new PriorityQueue<>((x, y) -> y - x);
        for (int i = 0; i < k; i++) {
            while (curr < n && arr[curr][0] <= w) {
                heap.offer(arr[curr][1]);
                curr++;
            }
            if (!heap.isEmpty()) {
                w += heap.poll();
            } else {
                break;
            }
        }
        return w;
    }
}

---

lc373. 查找和最小的 K 对数字（MD）

给定两个以 非递减顺序排列 的整数数组 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 <= 10^5
• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1 和 nums2 均为 升序排列
• 1 <= k <= 10^4
• k <= nums1.length * nums2.length

---

两个数组都是升序排列的，所以最小数对一定是($nums_1[0], nums_2[0]$) , 最大数对一定是($nums_1[length_1 - 1], nums_2[length_2 - 1]$) 。本题要求找到最小的$k$ 个数对，最直接的办法是可以将所有的数对求出来，然后利用排序或者 TopK 解法求出最小的$k$ 个数对即可。实际求解时可以不用求出所有的数对，只需从所有符合待选的数对中选出最小的即可，假设当前已选的前$n$ 小数对的索引分别为$(a_1,b_1),(a_2,b_2),(a_3,b_3),\ldots,(a_n,b_n)$. 由于两个数组都是按照升序进行排序的，则可以推出第 n+1n+1n+1 小的数对的索引选择范围为$(a_1+1,b_1),(a_1,b_1+1),(a_2+1,b_2),(a_2,b_2+1),(a_3+1,b_3),(a_3,b_3+1),\ldots,(a_n+1,b_n),(a_n,b_n+1)$

假设我们利用堆的特性可以求出待选范围中最小数对的索引为$(a_{i},b_{i})$，同时将新的待选的数对$(a_{i}+1,b_{i}),(a_{i},b_{i}+1)$ 加入到堆中，直到我们选出$k$ 个数对即可。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>(k, (o1, o2) -> {
            return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
        });

        List<List<Integer>> ans = new ArrayList<>();
        int m = nums1.length;
        int n = nums2.length;
        for (int i = 0; i < Math.min(m, k); i++) {
            heap.offer(new int[]{i, 0});
        }
        while (k-- > 0 && !heap.isEmpty()) {
            int[] indexPair = heap.poll();
            List<Integer> list = new ArrayList<>();
            list.add(nums1[indexPair[0]]);
            list.add(nums2[indexPair[1]]);
            ans.add(list);
            if (indexPair[1] + 1 < n) {
                heap.offer(new int[]{indexPair[0], indexPair[1] + 1});
            }
        }
        return ans;
    }
}

---

lc67. 二进制求和（EZ）

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

提示：

• 1 <= a.length, b.length <= 10^4
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

---

模拟法，两个字符串从后往前倒推，然后把字符转换成对应的数字再相加，最后去余数

class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; i++) {
            carry += i < a.length() ? (a.charAt(a.length() - i - 1) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - i - 1) - '0') : 0;
            ans.append((char)(carry % 2 + '0'));
            carry /= 2;
        }
        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();
        return ans.toString();
    }
}

如果是用python的话，有更简单的做法，可以直接上位运算

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            ans = x ^ y
            carry = (x & y) << 1
            x, y = ans, carry
        return bin(x)[2:]