博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode] Strobogrammatic Number II 对称数之二
阅读量:6173 次
发布时间:2019-06-21

本文共 2384 字,大约阅读时间需要 7 分钟。

 

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"].

Hint:

  1. Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

 

这道题是之前那道的拓展,那道题让我们判断一个数是否是对称数,而这道题让我们找出长度为n的所有的对称数,我们肯定不能一个数一个数的来判断,那样太不高效了,而且OJ肯定也不会答应。题目中给了提示说可以用递归来做,而且提示了递归调用n-2,而不是n-1。我们先来列举一下n为0,1,2,3,4的情况:

n = 0:   none

n = 1:   0, 1, 8

n = 2:   11, 69, 88, 96

n = 3:   101, 609, 808, 906, 111, 619, 818, 916, 181, 689, 888, 986

n = 4:   1001, 6009, 8008, 9006, 1111, 6119, 8118, 9116, 1691, 6699, 8698, 9696, 1881, 6889, 8888, 9886, 1961, 6969, 8968, 9966

我们注意观察n=0和n=2,可以发现后者是在前者的基础上,每个数字的左右增加了[1 1], [6 9], [8 8], [9 6],看n=1和n=3更加明显,在0的左右增加[1 1],变成了101, 在0的左右增加[6 9],变成了609, 在0的左右增加[8 8],变成了808, 在0的左右增加[9 6],变成了906, 然后在分别在1和8的左右两边加那四组数,我们实际上是从m=0层开始,一层一层往上加的,需要注意的是当加到了n层的时候,左右两边不能加[0 0],因为0不能出现在两位数及多位数的开头,在中间递归的过程中,需要有在数字左右两边各加上0的那种情况,参见代码如下:  

 

解法一:

class Solution {public:    vector
findStrobogrammatic(int n) { return find(n, n); } vector
find(int m, int n) { if (m == 0) return {
""}; if (m == 1) return {
"0", "1", "8"}; vector
t = find(m - 2, n), res; for (auto a : t) { if (m != n) res.push_back("0" + a + "0"); res.push_back("1" + a + "1"); res.push_back("6" + a + "9"); res.push_back("8" + a + "8"); res.push_back("9" + a + "6"); } return res; }};

 

这道题还有迭代的解法,感觉也相当的巧妙,需要从奇偶来考虑,奇数赋为0,1,8,偶数赋为空,如果是奇数,就从i=3开始搭建,因为计算i=3需要i=1,而我们已经初始化了i=1的情况,如果是偶数,我们从i=2开始搭建,我们也已经初始化了i=0的情况,所以我们可以用for循环来搭建到i=n的情况,思路和递归一样,写法不同而已,参见代码如下:

 

解法二:

class Solution {public:    vector
findStrobogrammatic(int n) { vector
one{
"0", "1", "8"}, two{
""}, res = two; if (n % 2 == 1) res = one; for (int i = (n % 2) + 2; i <= n; i += 2) { vector
t; for (auto a : res) { if (i != n) t.push_back("0" + a + "0"); t.push_back("1" + a + "1"); t.push_back("6" + a + "9"); t.push_back("8" + a + "8"); t.push_back("9" + a + "6"); } res = t; } return res; }};

 

类似题目:

 

参考资料:

 

转载地址:http://fptba.baihongyu.com/

你可能感兴趣的文章
性能测试培训总结-spotlight on mysql
查看>>
关于putty的ftp功能
查看>>
MySQL数据库常见的误解,居然连大牛都犯错误
查看>>
debugging requires the debug connect session system privilege.
查看>>
nginx 官方手册
查看>>
XP修复任务栏程序最小化丢失
查看>>
ambari 2.6.0.0开发环境配置
查看>>
C# 保证数据长度相同
查看>>
随机生成 字体大小--转
查看>>
JS中常用到的数组工具方法
查看>>
[20190510]快速建立执行脚本.txt
查看>>
自动为DEV GridView控件添加SizeChanged事件
查看>>
ASP.NET 中得到网站绝对路径的几种方法
查看>>
第四周作业
查看>>
Spring 注解概览
查看>>
快速排序法
查看>>
Swiper
查看>>
HDU Problem 1875 畅通工程再续 【最小生成树Prim】
查看>>
关于C语言中内存的3个问题
查看>>
Cesium中级教程6 - 3D Models 三维模型
查看>>