Strobogrammatic Number
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string.
For example, the numbers "69", "88", and "818" are all strobogrammatic.
分析：
找出中心对称的阿拉伯数字串，解释型题目，其中0，1，8本身是中心对称的，69互相中心对称
代码：
bool isStrobogrammatic(string num) {
int i = , j = int(num.length()) - ;
while(i < j) {
if((num[i] == '' && num[j] == '') || (num[i] == '' && num[j] == '') || (num[i] == num[j] && (num[i] == '' || num[i] == '' || num[i] == ''))) {
i++;
j--;
}
else
return false;
}
//如果i大于j，则为偶数串，直接return true；i等与j，则判断num[i]本身是否是中心对称
return i > j ? true : (num[i] == '' || num[i] == '' || num[i] == '');
}
Strobogrammatic Number II
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n.
For example, given n = 2, return ["11","69","88","96"].
分析：
跟I类似，主要问题还是在与代码解释，由于要列出所有可能的答案，递归的复杂度是至少的，所以就用递归吧，DFS, BFS都行
代码：
void dfs(vector<string> &result, string str, int i, int j) {
if(i == -) {
result.push_back(str);
return;
}
if(i == j) {
i--;
j++;
dfs(result, str + '', i, j);
dfs(result, str + '', i, j);
dfs(result, str + '', i, j);
}
else {
i--;
j++;
if(i != -)
dfs(result, '' + str + '', i, j);
dfs(result, '' + str + '', i, j);
dfs(result, '' + str + '', i, j);
dfs(result, '' + str + '', i, j);
dfs(result, '' + str + '', i, j);
}
return;
}
vector<string> findCertainStrobogrammatic(int num) {
vector<string> result;
dfs(result, "", (num - )/, num/);
return result;
}
Strobogrammatic Number III
The idea is similar to Strobogrammatic Number II: generate all those in-range strobogrammatic numbers and count.
分析：
与两个边界中任何一个等长的字符串要进行逐个验证满足要求。最初的想法为了减少时间复杂度，长度n(n > 1)介于两者之间的直接用个数函数计算：n为偶数时，count(n) = 4 * 5^(n/2 -1)；n为奇数时，count(n) = 12 * 5^(n/2 - 1)。但问题在于，n足够大时，O(n * 5^n)与O(5^n)基本没差别，所以如果采用逐个验证的方法，也就不必在乎小于n时的计算量了。