一、题目
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
二、示例
2.1> 示例：
【输入】 10
【输出】 4
【解释】 在[1, 10]中有四个好数： 2, 5, 6, 9。注意 1 和 10 不是好数, 因为他们在旋转之后不变。
提示：
- N 的取值范围是
[1, 10000]。
三、解题思路
根据题目描述，我们可以知道数字从0~9有如下三种集合划分：
- 好数：[2, 5, 6, 9]
- 旋转后仍然是它们自己：[0, 1, 8]
- 旋转后不再是有效数字：[3, 4, 7]
了解到了上面的划分之后，我们最容易想到的解题方式就是暴力破解。遍历从0~n的所有数字，针对每一个数字，我们要查看它每一位，如果发现是3、4、7中的任意1个数，则说明整体翻转后，肯定不是一个有效数字。如果是2、5、6、9中任意1个数，则具备了翻转后成为“好数”的条件。如果是0、1、8中任意1个数，则即无法确定不是有效数组，也不能作为翻转后成为“好数”的条件。具体实现，请参照：4.1> 暴力破解
除了暴力破解之外，我们其实还可以试图在有效范围n之内，拼装“好数”，即：[0, 1, 8]与[2, 5, 6, 9]进行拼装。具体实现，请参照：4.2> 拼装符合条件的好数
四、代码实现
4.1> 暴力破解
class Solution {
public int rotatedDigits(int n) {
int result = 0;
for (int i = 0; i <=n ; i++) {
boolean goodNum = false;
int num = i;
while (num > 0) {
int remainder = num % 10;
if (remainder == 3 || remainder == 4 || remainder == 7) {
goodNum = false;
break; // [3,4,7] 无效数字
}
if (remainder == 2 || remainder == 5 || remainder == 6 || remainder == 9) goodNum = true; // [2,5,6,9] 好数
num = num / 10;
}
if (goodNum) {
result++;
}
}
return result;
}
}
4.2> 拼装符合条件的好数
class Solution {
int result = 0, n = 0;
int[] sames = new int[]{0, 1, 8}, diffs = new int[]{2, 5, 6, 9};
public int rotatedDigits(int n) {
this.n = n;
for(int i = 1; i < 3; i++) dfs(sames[i], false);
for(int diff : diffs) dfs(diff, true);
return result;
}
public void dfs(int cur, boolean flag) {
if(cur > n) return;
if(flag) result++;
for(int same : sames) dfs(cur * 10 + same, flag);
for(int diff : diffs) dfs(cur * 10 + diff, true);
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」