[leetcode] 248. Strobogrammatic Number III 解题报告

qq508618087 分享于 2016-06-21

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements

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.

For example,
Given low = "50", high = "100", return 3. Because 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.

```class Solution {
public:
void DFS(string& low, string& high, int n, string str)
{
if(n==0 && stol(str)>=stol(low) && stol(str)<=stol(high)) {Max++; return;}
if(n%2==1) for(auto val: same) DFS(low, high, n-1, val);
if(n==0 || n%2==1) return;
for(int i = (n==2?1:0); i< two.size(); i++)
DFS(low, high, n-2, two[i].first+str+two[i].second);
}

int strobogrammaticInRange(string low, string high) {
int n1 = low.size(), n2 = high.size();
for(int i = n1; i <= n2; i++) DFS(low, high, i, "");
return Max;
}
private:
int Max = 0;
vector<string> same{"0", "1", "8"};
vector<pair<char,char>> two{{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
};```

×
• 登录
• 注册

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品，请激活账号。

您的注册邮箱： 修改

如果您没有收到激活邮件，请注意检查垃圾箱。