A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
Example:
Input: low = "50", high = "100" Output: 3 Explanation: 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.
就是找到所有长度为从1 到 high.length() 的string, 然后比较就可以了。
(这里, C++ string,是可以直接比较的)
class Solution { public: int strobogrammaticInRange(string low, string high) { while(low.length()<high.length()){ low = "0"+low; } while(high.length()<low.length()){ // in case high < low high = "0"+high; } int count = 0; for(int i =1;i<=high.length();i++){ for(auto str : getAll(i,i)){ while(str.length() < high.length()){ // first make same length str = "0"+str; } if(str >= low && str <= high) count++; } } return count; } private: vector<string> getAll(int n, const int N){// current n, total N if(n==0) return vector<string>{""}; if(n==1){ return vector<string>{"0","1","8"}; } vector<string> res; for(auto ss : getAll(n-2, N)){ if(n != N){ res.push_back("0"+ss+"0"); } res.push_back("1"+ss+"1"); res.push_back("8"+ss+"8"); res.push_back("6"+ss+"9"); res.push_back("9"+ss+"6"); } return res; } };
Mistakes:
这里,比较蛋疼的,就是 给的参数, high < low 。 这个得都变成string,再判断
No comments:
Post a Comment