[LeetCode] 248. Strobogrammatic Number III 对称数III
2024-10-19 19:39:29
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.
246. Strobogrammatic Number和247. Strobogrammatic Number II的拓展,求一个区间的数里有多少个对称数。有了247一题作基础,这里我们可以先用迭代方法求出所有长度满足的数,再通过与low,high的compare比较,选出最终的结果并count。
Java:
public class Solution {
public List<String> helper(int n, int max) {
if (n == 0) return new ArrayList<String>(Arrays.asList(""));
if (n == 1) return new ArrayList<String>(Arrays.asList("1", "8", "0")); List<String> list = helper(n - 2, max);
List<String> result = new ArrayList<String>();
for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
if (n != max) result.add("0" + s + "0");
result.add("1" + s + "1");
result.add("8" + s + "8");
result.add("6" + s + "9");
result.add("9" + s + "6");
}
return result;
} public int strobogrammaticInRange(String low, String high) {
int count = 0;
List<String> result = new ArrayList<String>();
for (int i = low.length(); i <= high.length(); i++) {
result.addAll(helper(i, i));
}
for (String str : result) {
if (str.length() == low.length() && str.compareTo(low) < 0 || str.length() == high.length() && str.compareTo(high) > 0) continue;
count++;
}
return count;
}
}
Java:
public class Solution {
private int count = 0;
private Map<Character, Character> map = new HashMap<>(); public int strobogrammaticInRange(String low, String high) {
if (low == null || low.length() == 0 || high == null || high.length() == 0) {
return 0;
} fillMap(); for (int n = low.length(); n <= high.length(); n++) {
char[] arr = new char[n];
getStrobogrammaticNumbers(arr, 0, n - 1, low, high);
} return count;
} private void getStrobogrammaticNumbers(char[] arr, int start, int end, String low, String high) {
if (start > end) {
String s = new String(arr);
if ((s.length() == 1 || s.charAt(0) != '0') && compare(low, s) && compare(s, high)) {
count++;
}
return;
} for (char c : map.keySet()) {
arr[start] = c;
arr[end] = map.get(c); if ((start < end) || (start == end && map.get(c) == c)) {
getStrobogrammaticNumbers(arr, start + 1, end - 1, low, high);
}
}
} // Return true if s1 <= s2
private boolean compare(String s1, String s2) {
if (s1.length() == s2.length()) {
if (s1.compareTo(s2) <= 0) {
return true;
} else {
return false;
}
} return true;
} private void fillMap() {
map.put('0', '0');
map.put('1', '1');
map.put('8', '8');
map.put('6', '9');
map.put('9', '6');
}
}
类似题目:
[LeetCode] 246. Strobogrammatic Number 对称数
[LeetCode] 247. Strobogrammatic Number II 对称数II
All LeetCode Questions List 题目汇总
最新文章
- JavaScript 自定义对象
- SQL中EXISTS的使用
- Android 图片圆角的简单方法
- C#中异常:“The type initializer to throw an exception(类型初始值设定项引发异常)”的简单分析与解决方法
- Oralce 账户被锁后的解决办法
- zk源码环境搭建
- BZOJ-1901 Zju2112 Dynamic Rankings 函数式线段树 套 树状数组+离线处理
- POJ 3258 River Hopscotch
- Js注册等待
- 20145315 《Java程序设计》实验五实验报告
- form 表单
- my Highcharts
- Ubuntu 12.04中文输入法的安装
- PowerShell中的数学计算
- iOS:图像和点击事件
- HttpWebRequest和WebClient的区别
- iOS 引导页
- 向Spring容器中注册组件的方法汇总小结
- Pandas字符串操作及实例应用
- 在Ubuntu下解决 adb devices :???????????? no permissions 方法
热门文章
- 【Calling Circles UVA - 247 】【Floyd + dfs】
- Java线程状态、线程start方法源码、多线程、Java线程池、如何停止一个线程
- .NET下各种可用的HTML解析组件
- BZOJ3028 食物 和 LOJ6261 一个人的高三楼
- shell脚本中向hive动态分区插入数据
- 浅谈C++编译原理 ------ C++编译器与链接器工作原理
- May Cook-Off 2019 解题报告
- lambda表达式格式以及应用场景?
- Pivotal Greenplum 6.0 新特性介绍
- vue+elementUI完成注册及登陆