5. 1201.丑數III(中等)

1201. 丑數 III - 力扣（LeetCode）

思想

1.丑數是可以被 a 或 b 或 c 整除的 正整數 。
給你四個整數：n 、a 、b 、c ，請你設計一個算法來找出第 n 個丑數。
2.此題是4. 878.第N個神奇數字的進階版，從兩個數的容斥原理變成三個數的容斥原理，同理即可

代碼

c++:

class Solution {
public:bool check(int n, int a, int b, int c, long long bei_ab, long long bei_ac,long long bei_bc, long long bei_abc, long long mid) {long long cnt = 0;cnt = mid / a + mid / b + mid / c - mid / bei_ab - mid / bei_ac -mid / bei_bc + mid / bei_abc;if (cnt >= n)return true;elsereturn false;}long long gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);}int nthUglyNumber(int n, int a, int b, int c) {long long bei_ab = 1LL * a / gcd(a, b) * b;long long bei_ac = 1LL * a / gcd(a, c) * c;long long bei_bc = 1LL * b / gcd(b, c) * c;long long bei_abc = 1LL * bei_ab / gcd(bei_ab, c) * c;long long left = min({a, b, c}), right = min({a, b, c}) * n, res = 0;while (left <= right) {long long mid = left + ((right - left) >> 1);if (check(n, a, b, c, bei_ab, bei_ac, bei_bc, bei_abc, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};

6. 373.查找和最小的K對數字(中等,學習優先隊列小頂堆)

373. 查找和最小的 K 對數字 - 力扣（LeetCode）

思想

1.給定兩個以 非遞減順序排列 的整數數組 nums1 和 nums2 , 以及一個整數 k 。
定義一對值 (u,v)，其中第一個元素來自 nums1，第二個元素來自 nums2 。
請找到和最小的 k 個數對 (u1,v1), (u2,v2) … (uk,vk) 。
2.一開始想的是二分答案和最小的第k個和，但是check函數里面雙指針不好寫判斷，所以學習優先隊列最小堆寫法
3.因為是按照和最小排序，所以最小堆比較的元素一定是和，即priority_queue的第一個元素是和，但是也要記錄下標(i,j)從而能訪問下一個元素，所以優先隊列里面元素是三元組turple<int,int,int>,而優先隊列默認是升序最大堆，且沒有三元組的降序最小堆寫法，需自己寫，為了簡單存入和的負值即可
接下來考慮入堆,目前元素為(i,j),下一個入堆元素為(i+1,j)或者(i,j+1),但是會出現一個問題,(i+1,j)入堆，然后(i+1,j+1)入堆，而如果(i,j+1)入堆，然后(i+1,j+1)又會入堆一次，導致(i+1,j+1)入堆兩次，解決辦法是先讓所有(i,0)入堆(數量小于k),然后接下來入堆的只有(i,j+1)了(即固定i更新j)

代碼

c++:

class Solution {
public:vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2,int k) {int n1 = nums1.size(), n2 = nums2.size();priority_queue<tuple<int, int, int>> pq;vector<vector<int>> res;for (int i = 0; i < min(n1, k); ++i) {pq.emplace(-nums1[i] - nums2[0], i, 0); // 先讓所有(i,0)入堆,因為是小根堆，所以放負值}while (res.size() < k && !pq.empty()) {auto t = pq.top();pq.pop();int i = get<1>(t), j = get<2>(t);res.push_back({nums1[i], nums2[j]});if (j + 1 < n2)pq.emplace(-nums1[i] - nums2[j + 1], i, j + 1); //優先隊列不是順序訪問，所以不用加back}return res;}
};

學習:
1.三元組tuple<int,int,int> t,訪問三個元素get<0/1/2>(t)
2.vector,deque,list這些順序訪問才是push_back和emplace_back,且vector<vector<int>>插入一整行要用push_back({i,j}),不能用emplace_back(i,j)
而prioriyt_queue這些非順序訪問是emplace