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)

热门文章

暂无图片
编程学习 ·

操作系统——银行家算法

银行家算法安全性检测C++实现,求安全序列 #include <bits/stdc++.h>using namespace std; const int N = 100;const int total_resources = 3; //资源总数struct process {/* data */int resources_max[total_resources]; //每种资源的总大需求量int resources_a…
暂无图片
编程学习 ·

JS 中的展开运算符你了解多少 ?

什么是展开运算符 (...)?展开运算符 :允许一个表达式在某处展开。展开运算符在多个参数(用于函数调用)或多个元素(用于数组字面量)或者多个变量(用于解构赋值)等地方可以使 用,作用就是 展开数组或字符串为一个新数组。注意 : 展开运算符不能用在对象当中,因为目前…
暂无图片
编程学习 ·

dnf强化系统实测 java代码

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;/*** dnf强化系统实测*/ public class Qianghua {public static void main(String[] args) throws IOException {//手动强化//manualQianghua();//自动强化autoQianghua(0,16);}…
暂无图片
编程学习 ·

springboot应用启动流程分析,嵌入式tomcat

之前我们分析了下springboot自动装载的原理,现在我们看看springboot应用启动的流程: 一般调用如下: // 应用代码SpringApplication.run(MiddlewareApplication.class, args); // SpringApplication.javapublic static ConfigurableApplicationContext run(Class<?> p…
暂无图片
编程学习 ·

【GNURadio RTL-SDR】双RTL-SDR信号源的FM调频广播接收机

文章目录1. 前言2. 实验过程2.1 制作流图2.2 RTL-SDR的设备参数1. 前言 两个RTL-SDR的dongle“电视棒”,芯片 RTL2832U + R820T ,淘宝50左右那种能收FM和我国DTMB频段,想都接到同一台电脑去用软件无线电(GNURadio)的方式收多个FM调频广播信号。 2. 实验过程 在谷歌搜了不少…
暂无图片
编程学习 ·

虚拟机VMware安装学习过程中遇到的几个问题

1.在安装VMware的时候刚开始因为版本不足的原因,电脑显示 Failed to initialize ploicy for cpu 后来我把它复制到百度上发现是我电脑版本过高的原因,于是又下载了VMware15.5.1版本 又查找了它的破解版。2.在安装的过程中还出现过屏幕就一个-,然后什么都不出现,于是查找资…
暂无图片
编程学习 ·

设计模式-工厂模式

关注公众号 JavaStorm 获取更多精彩工厂模式定义 工厂方法(Factory Method)模式的意义是定义一个创建产品对象的工厂接口,将实际创建工作推迟到子类当中。核心工厂类不再负责产品的创建,这样核心类成为一个抽象工厂角色,仅负责具体工厂子类必须实现的接口,这样进一步抽象化…
暂无图片
编程学习 ·

智慧RFID工地人员定位-工地人员定位系统-新导智能

随着RFID技能的逐渐老练,RFID工地人员定位系统系在施工项目中越来越多地被运用到实践当中。尤其是在工地分布范围广,现场环境恶劣的项目施行现场,为了对施工现场进行安全规范办理,在施工项目应用根据RFID工地人员定位体系,能够实时监测各个施工现场的人员状况,统一办理,…
暂无图片
编程学习 ·

Vue父组件调用子组件的方法

1.子组件使用ref,父组件直接调用(推荐)<child ref="mychild"></child>this.$refs.mychild.childMethod("嘿嘿嘿");2.子组件注册监听事件,父组件调用$emit触发this.$refs.mychild.$emit(childMethod,嘿嘿嘿) // 方法1:触发监听事件//子组件注册…
暂无图片
编程学习 ·

navigation笔记

react native存在的问题 vscode怎样打断点 _onPressButton()为什么以下划线命名 setState用法 render()用法eslint报错 不懂的地方:不懂怎么调试 不懂apk入库yarn start报错不知道怎么去解决 1 怎样让调试栏目处于最顶部 2 怎样快速找到问题的地方 3 怎么快速打断点类为什么前…
暂无图片
编程学习 ·

js动态生成多行多列复选框

本例目标: 获取后台数据集合,将集合的某个字段,比如:姓名,以复选框形式显示在HTML页面 应用场景: 获取数据库的人员姓名,将其显示在页面,供多项选择 效果如下:一、后台 查询数据库,返回List集合形式给页面 二、HTML 设置一个div,里面动态加载人员姓名 <div id=&q…
暂无图片
编程学习 ·

结构体学生信息输入

不知不觉学到第七章结构体了,这一章开始到后面的章节网上的免费课程就越来越少了。每次有不会的只能各种百度,心累。。。但还是会坚持的!!! 记录第7章课后习题第3题: 题目:编写一个函数print,打印一个学生的成绩数组,该数组中有5个学生的数据,每个学生的数据包括num(学…
暂无图片
编程学习 ·

Java继承多态面试题

1.多态的实现原理2.面向对象的特征之一——多态2.1多态的定义多态是同一个行为具有不同的表现形式或形态的能力。允许不同类的对象对同一消息做出响应,同一消息可以根据发送的对象不同采用不同的行为方式。对于面向对象,多态分为编译时多态和运行时多态,编译时多态是静态的,…
暂无图片
编程学习 ·

echarts关系图多条连线

最近用echarts做图的关系实现图数据结构连接线会重合,解决办法 import Graph from echarts/lib/data/Graph import echarts from echartsconst Edge = Graph.Edge const Node = Graph.Nodefunction generateNodeKey(id) {return _EC_ + id; }Graph.prototype.addEdge = functi…
暂无图片
编程学习 ·

05 | 消息积压了该如何处理?

1.应用场景https://blog.csdn.net/william_n/article/details/1040254082.学习/操作2.1 阅读文档这节课我们来聊一聊关于消息积压的问题。据我了解,在使用消息队列遇到的问题中,消息积压这个问题,应该是最常遇到的问题了,并且,这个问题还不太好解决。我们都知道,消息积压…
暂无图片
编程学习 ·

Spring Boot, MySQL, JPA, Hibernate Restful CRUD API Tutorial

Spring Boot MySQL JPA Hibernate Restful CRUD API TutorialSpring Boot has taken Spring framework to the next level. It has drastically reduced the configuration and setup time required for spring projects. Spring Boot将Spring框架提升到了一个新的高度。它大大…
暂无图片
编程学习 ·

哈夫曼编码

哈夫曼编码 输入一个字符串文本 #include <stdio.h> #include <stdlib.h> #include <string.h>#define cmax 0x3f3f3f3f // 宏定义一个较大的数,作为比较数据 #define cmaxsize 10000 // 宏定义数组的长度 // ---构建哈夫曼树 // ---定义哈夫曼…
暂无图片
编程学习 ·

mysql学习总结

连接数据库语句:mysql -h 服务器主机地址 -u 用户名 -p用户密码 基本的数据库操作命令: update user set password=password(‘123456’)where user=‘root’; 修改密码 flush privileges; 刷新数据库 show databases; 显示所有数据库 use dbname;打开某个数据库 show table…
暂无图片
编程学习 ·

Java数据类型

数据类型 Java属于一种强类型语言 什么是强类型语言? 即要求变量的使用需要严格符合规定,要求所有变量都必须先定义后再使用,若不按规定就会报错! Java的数据类型分为两类 基本类型(primitive type) Java语言提供了八种基本类型:六种数字类型(四个整数型,两个浮点型),…