leetcode 788. Rotated Digits

题目描述

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Note:

• N will be in range [1, 10000]

Difficulty: easy
788. Rotated Digits

---

中文描述
如果一个数X，每个位置旋转180°，能够得到一个有效的数字，并且该数字与X不同，则我们称X是一个good数字（2转180°为5，6转180°为9，反之亦然。0，1，8旋转不变，其他数字旋转后不为合理数字。）。给定一个范围N，找出从1到N中good数字的个数。

---

输入格式
输入一个数字N，表示[1, N]范围。

---

Examples:

1. Input: 10
   Output: 4
   解释:
   1到10的范围内，有2，5，6，8为good数字，总计4个。

---

解答思路

• 解法一：遍历

  1.因为这题给定的范围只有[1, 10000]，所以我们可以遍历全部数字，如果数字中不包含[3,4,7]，并且至少包含一个[2,5,6,9]中的其中一个数字就是一个good数字。

  2.复杂度$O(N)$，因为要遍历一次。

• 解法二：计算法

  1.我们考虑一位数中（0-9），good数字的个数为4个记为$S_{1}$，（[2,5,6,9]）。而两位数中（0-99）则有第一位为[0,1,2,5,6,8,9]，后面为$S_{1}$，还要加上第一位为[2,5,6,9]，第二位可以为[0,1,8]的情况。
  所以有$S_{2}=7*S_{1}+4*3^\left(2-1\right)$。
  可以推广到$n$位数的情况，即$S_{n}=7*S_{n-1}+4*3^\left(n-1\right)$

  2.之后我们进行计算就可以划分区域，比如1234这个数字，我们可以化为0001-0999（固定第一位为0），1000-1099（固定第一位为1，第二位为0），1100-1199（固定第一位为1，第二位为1），1200-1209（固定第一位为1，第二位为2，第三位为0），1210-1219（固定第一位为1，第二位为2，第三位为1），1220-1229（固定第一位为1，第二位为2，第三位为2）····。每次就需要加上$S_{n}，n表示未固定的位数$，还有就是如果最后一个固定的数为[2,5,6,9]，还需要剩下位数为[0,1,8]组合的情况。

  3.复杂度估计$O\left(log\left(N\right)\right)$(不是很确定，感觉自己写的像$O\left(log^{2}\left(N\right)\right)$)

---

代码

解法一，

class Solution(object):
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        112ms
        """
        count = 0
        for i in range(1, N + 1):
            s = str(i)
            num = 0
            for char in s:
                if char in '347':
                    num = -1
                    break
                elif char in '018':
                    num += 1
            # 判断是否有效，和是否相同
            if num != len(s) and num != -1:
                count += 1
        return count

解法二，逻辑没想通， dubug了半天：

class Solution(object):
    def rotatedDigits_1(self, N):
        """
        :type N: int
        :rtype: int
        31ms
        """
        # 一位数有2，5，6，9满足条件
        start = 4
        # 记录0位，1位满足题意的good数的个数
        list_start = [0, start]
        s = str(N)
        l = len(s) - 1
        # 扩展为2位到l位
        for i in range(1, l):
            # n位可以由（n-1位 + [0,1,2,5,6,8,9] + 以[2,5,6,9]开头的个数 * 剩下位数为[0，1，8]的随即排列）
            start = 7 * start + 4 * (3 ** i)
            list_start.append(start)
        count = 0
        # 每一位考虑过去，例如234，我们就先考虑0-99，100-199，200-209，210-219，220-229，230-234这样
        for i, char in enumerate(s):
            m = int(char)
            # 比当前位置小的全部数逐个累加，
            for j in range(m):
                # 如果是[0, 1, 8]，剩下位数自身一定要为good数，用前面记录的代入
                if j in [0, 1, 8]:
                    count += list_start[l - i]
                # 如果是[2, 5, 6, 9]，则除了剩下位数自身为good数，或则由[0，1，8]的随即排列
                elif j in [2, 5, 6, 9]:
                    count += list_start[l - i] + (3 ** (l - i))
            # 如果当前位置不能翻转，说明最大到此为止，结束
            if m in [3, 4, 7]:
                return count
            # 如果当前位置为[2, 5, 6, 9]，则我们考虑剩下位置由[0, 1, 8]组成且不大于N的个数
            elif m in [2, 5, 6, 9]:
                mark = True
                # 还是逐位考虑
                for next_i in range(i + 1, len(s)):
                    cur = int(s[next_i])
                    for k in [0, 1, 8]:
                        # 比[0, 1, 8]小说明该位可以为[0, 1, 8]，之后位可以由[0, 1, 8]随意组合，也不会大于目标值
                        if k < cur:
                            count += 3 ** (l - next_i)
                    # 如果当前位置不为[0, 1, 8]，说明所有小于目标的组合已经都完成了
                    if cur not in [0, 1, 8]:
                        mark = False
                        break
                # 如果末尾为[0, 1, 8]，我们需要+1
                if mark and (s[-1] in ['0', '1', '8']):
                    count += 1
        # 如果末尾为[2, 5, 6，9]，我们需要+1
        if s[-1] in ['2', '5', '6', '9']:
            count += 1
        return count

还有大神写的简洁版的代码Easy Understood Solution and O(logN)准备在仔细看遍。

---