[LeetCode] 248. Strobogrammatic Number III 对称数之三
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 lowand high numbers are represented as string.
这道题是之前那两道 Strobogrammatic Number II 和 Strobogrammatic Number 的拓展,又增加了难度,让找给定范围内的对称数的个数,我们当然不能一个一个的判断是不是对称数,也不能直接每个长度调用第二道中的方法,保存所有的对称数,然后再统计个数,这样 OJ 会提示内存超过允许的范围,所以这里的解法是基于第二道的基础上,不保存所有的结果,而是在递归中直接计数,根据之前的分析,需要初始化 n=0 和 n=1 的情况,然后在其基础上进行递归,递归的长度 len 从 low 到 high 之间遍历,然后看当前单词长度有没有达到 len,如果达到了,首先要去掉开头是0的多位数,然后去掉长度和 low 相同但小于 low 的数,和长度和 high 相同但大于 high 的数,然后结果自增1,然后分别给当前单词左右加上那五对对称数,继续递归调用,参见代码如下:
解法一:
class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int res = ;
for (int i = low.size(); i <= high.size(); ++i) {
find(low, high, "", i, res);
find(low, high, "", i, res);
find(low, high, "", i, res);
find(low, high, "", i, res);
}
return res;
}
void find(string low, string high, string path, int len, int &res) {
if (path.size() >= len) {
if (path.size() != len || (len != && path[] == '')) return;
if ((len == low.size() && path.compare(low) < ) || (len == high.size() && path.compare(high) > )) {
return;
}
++res;
}
find(low, high, "" + path + "", len, res);
find(low, high, "" + path + "", len, res);
find(low, high, "" + path + "", len, res);
find(low, high, "" + path + "", len, res);
find(low, high, "" + path + "", len, res);
}
};
上述代码可以稍微优化一下,得到如下的代码:
解法二:
class Solution {
public:
int strobogrammaticInRange(string low, string high) {
int res = ;
find(low, high, "", res);
find(low, high, "", res);
find(low, high, "", res);
find(low, high, "", res);
return res;
}
void find(string low, string high, string w, int &res) {
if (w.size() >= low.size() && w.size() <= high.size()) {
if (w.size() == high.size() && w.compare(high) > ) {
return;
}
if (!(w.size() > && w[] == '') && !(w.size() == low.size() && w.compare(low) < )) {
++res;
}
}
if (w.size() + > high.size()) return;
find(low, high, "" + w + "", res);
find(low, high, "" + w + "", res);
find(low, high, "" + w + "", res);
find(low, high, "" + w + "", res);
find(low, high, "" + w + "", res);
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/248
类似题目:
参考资料:
https://leetcode.com/problems/strobogrammatic-number-iii/
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- linux常用查看硬件设备信息命令
- JAVA 线程中的异常捕获
- JMeter基础之--元件的作用域与执行顺序
- python 语料处理(从文件夹中读取文件夹中文件,分词,去停用词,去单个字)
- mybatis 相关总结
- cloudera安装报错 socket.gaierror: [Errno -2] Name or service not known
- JAVA toString方法
- /usr/lib/libstdc++.so.6: version `GLIBCXX_3.4.15&#39; not found错误的解决
- Radar Installation(POJ 1328 区间贪心)
- c语言,数据类型转换
- Math 对象 识记
- Django REST framework 中 3 种类视图的对比
- 嘿嘿嘿,开始自学mysql
- mysql一列相同另一列相加
- 获取子元素节点(children,childNodes)
- java 反射原理写了一个赋值和取值通用类
- Java 常用对象-Date类和Calender类
- Win窗口坐标二维坐标与OpenGl的世界坐标系的之间的相互转换
- Oil Skimming---hdu4185(最大匹配)
- 使用.sig签名验证文件
热门文章
- 运维相关指标数据采集并ES入仓 - 运维笔记
- [Node.js] TypeScript 实现 sleep 函数
- gitea/gogs在push操作时报RPC failed的问题
- DevExpress的TreeList实现节点上添加自定义右键菜单并实现删除节点功能
- 使用jq操作脚本生成元素的事件
- H3C路由器设置NAT回环、端口回流
- 如何在浏览器中运行 VS Code?
- ZooKeeper之服务器动态上下线案例
- 使用 PXE+Kickstart 实现无人值守批量部署系统
- Ubuntu 18.04通过命令禁用/开启触控板