3 模拟——788. 旋转数字 ★★
2 模拟
788. 旋转数字
我们称一个数X为好数, 如果它的每位数字逐个地被旋转180度后，我们仍可以得到一个有效的，且和X不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0、1和8被旋转后仍然是它们自己；2和5可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2和5互为镜像）；6和9同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数N，计算从1到N中有多少个数X是好数？
示例1：
输入: 10
输出: 4
解释: 在[1, 10]中有四个好数：2, 5, 6, 9。
注意：1和10不是好数, 因为他们在旋转之后不变。
算法设计
根据题目的要求，一个数是好数，当且仅当：
- 数中没有出现3、4、7；
- 数中至少出现一次2或5或6或9。
枚举[1, n]中的每一个数，解析该数的每一位上的数字，如果出现2或5或6或9，令flag=true；如果出现3、4、7，则令flag=false，并立即break跳出循环。如果flag=true，则计数器ans++。最后返回ans即可。
算法实现
//Leetcode788 旋转数字
int rotatedDigits(int n) {int ans = 0;for (int i = 1; i <= n; i++) {bool flag = false;int x = i;while (x) {int d = x % 10; //取每一位上的数字x /= 10;if (d == 2 || d == 5 || d == 6 || d == 9) flag = true;else if ( d == 3 || d == 4 || d == 7) {flag = false;break;}}if (flag) ans++;}return ans;
}
上面的程序中，判断语句过于繁琐，也可以定一个一个判定数组，出现3、4、7的位置设为-1，出现2或5或6或9的位置设为1，其它位置设为0。
const int check[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
这样只需要根据数位对应位置的值判断即可，不需要枚举那么多种情况。
算法实现
//Leetcode788 旋转数字
const int check[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
int rotatedDigits(int n) {int ans = 0;for (int i = 1; i <= n; i++) {bool flag = false;int x = i;while (x) {int d = x % 10;x /= 10;if (check[d] == 1) flag = true;else if(check[d] == -1) {flag = false;break;}}if (flag) ans++;}return ans;
}
算法分析
有n个数需要枚举，检查一个数需要遍历每个数字，n的数位为O(logn)，时间复杂度为O(nlogn)，空间复杂度为O(1)。