leetcode 788. Rotated Digits
leetcode 788. Rotated Digitsleetcode 788. Rotated Digits题目描述解答思路代码题目描述X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is diff...
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:
- 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) O ( N ) ,因为要遍历一次。
解法二:计算法
1.我们考虑一位数中(0-9),good数字的个数为4个记为 S1 S 1 ,([2,5,6,9])。而两位数中(0-99)则有第一位为[0,1,2,5,6,8,9],后面为 S1 S 1 ,还要加上第一位为[2,5,6,9],第二位可以为[0,1,8]的情况。
所以有 S2=7∗S1+4∗3(2−1) S 2 = 7 ∗ S 1 + 4 ∗ 3 ( 2 − 1 ) 。
可以推广到 n n 位数的情况,即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)····。每次就需要加上 Sn,n表示未固定的位数 S n , n 表 示 未 固 定 的 位 数 ,还有就是如果最后一个固定的数为[2,5,6,9],还需要剩下位数为[0,1,8]组合的情况。
3.复杂度估计 O(log(N)) O ( l o g ( N ) ) (不是很确定,感觉自己写的像 O(log2(N)) O ( l o g 2 ( N ) ) )
代码
解法一,
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)准备在仔细看遍。
更多推荐
所有评论(0)