LeetCode题解(0788):进制转换的奇技淫巧

题目

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后,我们仍可以得到一个有效的,且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字, 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己;2 和 5 可以互相旋转成对方(在这种情况下,它们以不同的方向旋转,换句话说,2 和 5 互为镜像);6 和 9 同理,除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数?

示例:

输入: 10
输出: 4
解释: 
在[1, 10]中有四个好数: 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

提示:

  • N 的取值范围是 [1, 10000]。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/rotated-digits

解法

在这里插入图片描述

首先,看到这道题,最容易想到的方法,就是遍历从1到N的所有数,并判断他们是不是好数。在这种思路下, 无论我们怎么优化,最后的效率都不会超过O(NlogN),其中log的底数为10,log10即数字的位数。

但是,通过观察我们可以发现,数字中如果包含3、4、7,则会因为这些数字翻转后不再是数字而被剔除;而数字如果只包含0、1、8,则会因为这些数字翻转后数值不变,而被剔除。

在前100个正整数中,不包含3、4、7的数一共有49个,正好是七进制下的100对应的十进制数;而仅包含0、1、8的数一共有9个,也正好是三进制下的100对应的十进制数。(通过动态规划的方法也可以得到类似的思路)

由此,我们想到使用进制来计算。


简单来说,我们将十进制的数当做七进制和三进制,转换成十进制,即将100视作七进制的100,转换为十进制的49。并将七进制转换的数减去三进制转换的数,直接得到好数的数量。

在具体的操作上,在计算七进制时,七进制的0、1、2、5、6、8、9分别映射七进制的0、1、2、3、4、5、6;在计算三进制时,三进制的0、1、8分别映射三进制的0、1、2。如果出现了不存在于上述映射表中的数n,则取小于n的最大的数的映射,例如三进制的5,则取1的映射1

例如:

10 —— 作为七进制的10,转换为十进制的7;作为三进制的10,转换为十进制的3;最终结果:7 - 3 = 4
12 —— 作为七进制的12,转换为十进制为9;作为三进制的11,转换为十进制的4;最终结果:9 - 4 = 5

但是,在这种朴素的对应方式下,会出现如下问题:

10 -- 作为三进制的10,转换为3
12 -- 作为三进制的11,转换为4
18 -- 作为三进制的12,转换为5
20 -- 作为三进制的10,转换为3(这显然是错误的)

为了纠正这个问题,我们在转换时做出如下调整:

如果在高位上出现了不存在于映射表中的数,则低位直接取最大值。例如,130在转换为三进制时,因为十位的3不存在于映射表中,所以个位直接取最大值2,即112。


具体的Python实现如下:

def rotatedDigits(self, N: int) -> int:
    d7 = {
        "0": "0",
        "1": "1",
        "2": "2",
        "3": "2",
        "4": "2",
        "5": "3",
        "6": "4",
        "7": "4",
        "8": "5",
        "9": "6"
    }
    o7 = {"3", "4", "7"}
    d3 = {
        "0": "0",
        "1": "1",
        "2": "1",
        "3": "1",
        "4": "1",
        "5": "1",
        "6": "1",
        "7": "1",
        "8": "2",
        "9": "2"
    }
    o3 = {"2", "3", "4", "5", "6", "7", "9"}

    S = str(N)
    S7 = S3 = ""
    off = False
    for s in S:
        if off:
            S3 += "2"
        else:
            off = s in o3
            S3 += d3[s]

    off = False
    for s in S:
        if off:
            S7 += "6"
        else:
            off = s in o7
            S7 += d7[s]

    return int(S7, base=7) - int(S3, base=3)

热门文章

暂无图片
编程学习 ·

都说Python容易自学,那如何系统的学习Python

做Python开发十年,给大家详细分析一下这个问题 首先告诉你的是,零基础学习开始系统学习Python肯定难,Python的专业程度本身就不简单,学习这事本来就是一件非常煎熬的事情,人都不愿意学习,可是没办法,为了生存掌握一个技能,你必须学,如果你认真的对待,你就找不到高薪水…
暂无图片
编程学习 ·

文献管理之 Citavi & Latex

文章目录为什么选择Citavi安装地址使用指南不足之处官方文档 为什么选择Citavi 比较好的文献管理软件主要有Citavi、Endnote、Mendeley、Zotero,根据Citavi、Endnote、Mendeley 功能大比拼!到底哪一款才是众望所归的终极文献管理软件?总结,Citavi不仅是个免费的软件,而且功…
暂无图片
编程学习 ·

AttributeError: ‘list‘ object has no attribute ‘value‘

AttributeError: ‘list’ object has no attribute ‘value’需要注意self.session.run输出的格式,如下代码会报错 precise_summary = self.session.run([ts.precise_summary],{ts.x: xs, ts.y: ys}) writer.add_summary(precise_summary, epoch)AttributeError: ‘list’ ob…
暂无图片
编程学习 ·

四.面向对象

解释说明姓名 职位 动作张三 程序员 打卡,开会李四 前台 打卡,开会王五 财务 打卡,开会用表格表示一组数据,表结构理解为类,每一行数据对应一个对象; 姓名、职位相当于类中的属性; 动作早会相当于类中的方法; 面向过程:执行者思维,对于简单问题,比如开车步骤 按照12…
暂无图片
编程学习 ·

面试必问之 == 与 equals

== : 它的作用是判断两个对象的地址是不是相等。即,判断两个对象是不是同一个对象(基本数据类型==比较的是值,引用数据类型==比较的是内存地址)。equals() : 它的作用也是判断两个对象是否相等。但它一般有两种使用情况:情况1:类没有覆盖 equals() 方法。则通过 equals() 比…
暂无图片
编程学习 ·

如何理解numpy中的c_函数

其实,c_并不是一个函数,它只是CClass类的一个实例,而CClass是定义了切片方法__getitem__的类,所以c_就可以使用切片,仿佛就像一个函数一样。源代码是这样的#头部声明c_变量__all__ = [ravel_multi_index, unravel_index, mgrid, ogrid, r_, c_,s_, index_exp, ix_, ndenum…
暂无图片
编程学习 ·

selenium+ChromeDriver+java爬虫初探

selenium+ChromeDriver+java爬虫初探seleniumChromeDriver简单的demo selenium 自动化测试工具,可以完全模拟人的行为。我们可以用它来打开浏览器,访问指定URL,并且定位到具体的按钮,点击触发事件等等。ChromeDriver selenium和谷歌浏览器交互,需要这个驱动。下载地址(ht…
暂无图片
编程学习 ·

mongoDB采坑

mongoDB采坑 安装问题没有权限参考 https://blog.csdn.net/qq_20084101/article/details/82261195
暂无图片
编程学习 ·

Jmeter之JDBC的使用

(一)环境准备 1、下载mysql-connector-java-x.x.x.jar放到 jmeter根目录的lib目录下,重启jmeter(二)数据库配置 1、在测试计划下面,添加一个setup线程组2、在setup线程组下,添加一个配置元件JDBC Connection Configuration3、填写配置信息 Variable Name:数据库连接池的…
暂无图片
编程学习 ·

vue项目里引用 gojs 流程图

要实现的需求 流程图,支持字体图标,颜色,可连接线,点击时右侧展示相关的详细信息 调研了多种可拖拽流程图的技术,如:bpmn.js,gojs等,由于bpmn-js功能冗余,GOJS相对于更加轻量级,最终选用GOJS开发此功能 gojs 文字区块 使用TextBlock类显示文本。 设置TextBlock.text属性…
暂无图片
编程学习 ·

java枚举enum

java枚举 jdk5.0之前的 public class SessonTest {public static void main(String[] args) {Seasson spring = Seasson.Spring;System.out.println(spring);} }class Seasson{//1.private final String seassonName;private final String seassonDesc;//2.private Seasson(Str…
暂无图片
编程学习 ·

Leetcode 题解 - 双指针

双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。 有序数组的 Two Sum Leetcode :167. Two Sum II - Input array is sorted (Easy) Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2题目描述:在有序数组中找出两个数,使它们的和为…
暂无图片
编程学习 ·

公司开发规范 - 【管理岗的第二年】

由于阿里的规范太长了 本文就不赘述阿里大佬了,只是用于我带的团队书写代码严格遵循驼峰命名规范每个方法类【不包含工具类、抽象类、实体类】行数不能超过200行,可以拆解到多个类(DataOperatorService,DataLogService等)每个方法有效逻辑行数【不包含注释、静态、属性字段…
暂无图片
编程学习 ·

VMware下安装CentOS7

VMware下安装CentOS7和安装CentOS6.5是一样的,不同的就是在配置硬件时,根据自己电脑情况选择合理的需求。在这里大家可以参考我之前写的一篇博文:VMware下安装CentOS6.5Centos官方地址:https://www.centos.org/ 这个是最新版本 下载地址:https://www.centos.org/download/…