Given an integer n
. Each number from 1
to n
is grouped according to the sum of its digits.
Return how many groups have the largest size.
Example 1:
Input: n = 13 Output: 4 Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13: [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.
Example 2:
Input: n = 2 Output: 2 Explanation: There are 2 groups [1], [2] of size 1.
Example 3:
Input: n = 15 Output: 6
Example 4:
Input: n = 24 Output: 5
Constraints:
1 <= n <= 10^4
A:
class Solution { public: int countLargestGroup(int n) { unordered_map<int, vector<int>> M; int largestSize = 0; for(int i = 1; i<=n;++i) largestSize = max(largestSize, helper(M,i)); // get how many groups with largestSize auto iter = M.begin(); int res = 0; while(iter!= M.end()){ if(iter->second.size()==largestSize){ res++; } iter++; } return res; } private: int helper(unordered_map<int, vector<int>> & M, int i){ string str = to_string(i); int sum = 0; for(char ch : str){ sum += ch -'0'; } if(M.find(sum)==M.end()){ vector<int> tmp; M[sum] = tmp; } M[sum].push_back(i); return M[sum].size(); } };
---------------------修改后,我们发现,不需要存储 所有的i.值, 只需要记录有多少个就行
class Solution { public: int countLargestGroup(int n) { unordered_map<int, int> M; int largestSize = 0; for(int i = 1; i<=n;++i) largestSize = max(largestSize, helper(M,i)); // get how many groups with largestSize auto iter = M.begin(); int res = 0; while(iter!= M.end()){ if(iter->second==largestSize){ res++; } iter++; } return res; } private: int helper(unordered_map<int, int> & M, int i){ string str = to_string(i); int sum = 0; for(char ch : str){ sum += ch -'0'; } M[sum]++; return M[sum]; } };
No comments:
Post a Comment