gcd，哈希問題-LeetCode 357、355、365、367、380
- 2019 年 12 月 1 日
- 筆記
gcd，哈希表問題：LeetCode #357 355 365 367 380
1
編程題
【LeetCode #357】計算各個位數不同的數字個數
給定一個非負整數 n，計算各位數字都不同的數字 x 的個數，其中 0 ≤ x < 10n 。
示例: 輸入: 2 輸出: 91 解釋: 答案應為除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 區間內的所有數字。
解題思路：
n = 1時，res = 10; n = 2時，兩位數符合條件的有99,首位不能是零！然後再加上n=1時的結果 n = 3時，三位數符合條件的有99*8, 然後再加上n=2時的結果！ 注意：n>10時，必定重複，結果為零！
class Solution { public: int countNumbersWithUniqueDigits(int n) { int res = 0; if(n == 0) return 1; if(n > 10) return 0; res = 10; int tmp = 9; // 多位數的第一位不為零，因此有9種選擇 for(int i = 1; i < n; i++){ tmp *= (10-i); res += tmp; // 加上前一位數的個數 } return res; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/count-numbers-with-unique-digits
【LeetCode #355】設計推特
設計一個簡化版的推特(Twitter)，可以讓用戶實現發送推文，關注/取消關注其他用戶，能夠看見關注人（包括自己）的最近十條推文。你的設計需要支持以下的幾個功能：
postTweet(userId, tweetId): 創建一條新的推文 getNewsFeed(userId): 檢索最近的十條推文。每個推文都必須是由此用戶關注的人或者是用戶自己發出的。推文必須按照時間順序由最近的開始排序。 follow(followerId, followeeId): 關注一個用戶 unfollow(followerId, followeeId): 取消關注一個用戶
示例: Twitter twitter = new Twitter(); // 用戶1發送了一條新推文 (用戶id = 1, 推文id = 5). twitter.postTweet(1, 5); // 用戶1的獲取推文應當返回一個列表，其中包含一個id為5的推文. twitter.getNewsFeed(1); // 用戶1關注了用戶2. twitter.follow(1, 2); // 用戶2發送了一個新推文 (推文id = 6). twitter.postTweet(2, 6); // 用戶1的獲取推文應當返回一個列表，其中包含兩個推文，id分別為 -> [6, 5]. // 推文id6應當在推文id5之前，因為它是在5之後發送的. twitter.getNewsFeed(1); // 用戶1取消關注了用戶2. twitter.unfollow(1, 2); // 用戶1的獲取推文應當返回一個列表，其中包含一個id為5的推文. // 因為用戶1已經不再關注用戶2. twitter.getNewsFeed(1);
解題思路：
首先設計兩個map，一個用於儲存用戶之間的關係follows，即某用戶訂閱了那些用戶，另一個用於保存某用戶發了那些推特，由於題目中需要按照發表時間排序，因此tweets的數據類型為map<int, vector<pair>>, 由於一個人會發多篇，使用vector儲存，每個tweet都有對應時間，因此使用pair.,>,="">
主要在於getNewsFeed函數，當獲取tweet時，我們應該將自己以及該用戶訂閱的所有人的推文放到一起，按照時間排序，取出時間最大的前10個推文即可！ 有可能總推文數沒有10個，因此使用int n = min(10, (int)tmp.size());來獲取個數！
class Twitter { public: map<int, vector<pair<int, long long>>> tweets; map<int, set<int>> follows; long long times = 0; /** Initialize your data structure here. */ Twitter() { } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { tweets[userId].emplace_back(tweetId, times++); } /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */ vector<int> getNewsFeed(int userId) { vector<int> res; vector<pair<int, long long>> tmp; follows[userId].insert(userId); for(auto usr: follows[userId]){ // 該用戶訂閱了那些人 for(auto tw: tweets[usr]){ tmp.push_back(tw); } } sort(tmp.begin(), tmp.end(), [](pair<int, long long>a, pair<int, long long>b){ return a.second > b.second; }); int n = min(10, (int)tmp.size()); for(int i = 0; i < n; i++){ res.push_back(tmp[i].first); } return res; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ void follow(int followerId, int followeeId) { follows[followerId].insert(followeeId); // key為訂閱者，value為被訂閱者 } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ void unfollow(int followerId, int followeeId) { follows[followerId].erase(followeeId); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/design-twitter
【LeetCode #365】水壺問題
有兩個容量分別為 x升 和 y升 的水壺以及無限多的水。請判斷能否通過使用這兩個水壺，從而可以得到恰好 z升 的水？ 如果可以，最後請用以上水壺中的一或兩個來盛放取得的 z升 水。 你允許：
- 裝滿任意一個水壺
- 清空任意一個水壺
- 從一個水壺向另外一個水壺倒水，直到裝滿或者倒空
示例 1: (From the famous "Die Hard" example) 輸入: x = 3, y = 5, z = 4 輸出: True
解題思路：
這個是數學問題，即尋找x和y的最大公約數，然後z為其最大公約數的整數倍。 最大公約數算法也叫gcd，至於算法原理來自一個數學定理，記下好了！剩餘的就是一些邊界條件問題！
class Solution { public: int gcd(int x, int y){ if(y == 0) return x; int r = x % y; return gcd(y, r); } bool canMeasureWater(int x, int y, int z) { if(x == 0 && y == 0) return z == 0; return z == 0 || (z % gcd(x, y) == 0 && (x+y) >= z); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/water-and-jug-problem
【LeetCode #367】有效的完全平方數
給定一個正整數 num，編寫一個函數，如果 num 是一個完全平方數，則返回 True，否則返回 False。 說明：不要使用任何內置的庫函數，如 sqrt。
示例 1： 輸入：16 輸出：True
解題思路：
使用二分查找，但需要注意的是INT的最大值為2147483647，因此平方的底數最大為46340，設置這個上限即可！
class Solution { public: bool isPerfectSquare(int num) { int l = 0, r = 46340; while(l <= r){ int mid = l + (r - l) / 2; long power = mid * mid; if(power > num){ r = mid -1; } else if(power < num){ l = mid +1; } else{ return true; } } return false; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/valid-perfect-square
【LeetCode #380】常數時間插入、刪除和獲取隨機元素
設計一個支持在平均 時間複雜度 O(1) 下，執行以下操作的數據結構。
insert(val)：當元素 val 不存在時，向集合中插入該項。 remove(val)：元素 val 存在時，從集合中移除該項。 getRandom：隨機返回現有集合中的一項。每個元素應該有相同的概率被返回。
class RandomizedSet { public: /** Initialize your data structure here. */ unordered_set<int> s; RandomizedSet() {} /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ bool insert(int val) { if(s.count(val)) return false; s.insert(val); return true; } /** Removes a value from the set. Returns true if the set contained the specified element. */ bool remove(int val) { if(s.count(val) == 0) return false; s.erase(val); return true; } /** Get a random element from the set. */ int getRandom() { auto it = s.begin(); int step = rand() % s.size(); while(step--){ //it++; it = next(it); } return *it; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1
