这是悦乐书的第 316 次更新, 第 337 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 185 题(顺位题号是 788). 如果一个数字经过 180 度旋转后, 变成了一个与原数字不同的数, 这样的数被称为好数字. 数字中的每一位都必须经过旋转. 旋转的规则是: 0,1,8 这三个数旋转后还是自身, 2 旋转后变为 5,5 旋转后变为 2,6 旋转后变为 9,9 旋转后变为 6, 剩下的 3,4,7 旋转后并不能转成其他数字, 是无效的. 现在给出正数 N, 从 1 到 N 的好数字一共有多少个? 例如:
输入: 10
输出: 4
说明: 在 [1,10] 范围内有四个好的数字: 2,5,6,9. 请注意, 1 和 10 不是好数字, 因为它们在旋转后保持不变.
注意: N 将在 [1,10000] 范围内.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
题目的意思很明确, 根据旋转规则来判断数字中的每一位数即可. 将正整数转为字符数组, 然后判断每一个字符是否符合要求. 我们借助一个布尔类型的标志来判断, 整个数字是否符合要求, 对于 3,4,7 三个数, 因为是无效数字, 可以直接将标志改为 false, 并且终止循环判断, 进入下一个数. 对于 2,5,6,9 四个数, 是有效数字, 可以转换成其他的数, 碰到其中任意一个, 都将标志改为 true. 剩下的 0,1,8 因为转换后还是自身, 虽然也是有效数字, 但是可以直接忽略.
- public int rotatedDigits(int N) {
- int count = 0;
- for (int i=0; i<= N; i++) {
- String s = i+"";
- boolean flag = false;
- for (char ch : s.toCharArray()) {
- if (ch == '3' || ch == '4' || ch == '7') {
- flag = false;
- break;
- }
- if (ch == '2' || ch == '5' || ch == '6' || ch == '9') {
- flag = true;
- }
- }
- if (flag) {
- count++;
- }
- }
- return count;
- }
03 第二种解法
因为判断是按照从小到大的顺序进行的, 所以可以先将前面部分的判断结果存起来, 在遇到更大的数时, 可以节省判断步骤.
使用一个数组, 长度为 N+1, 初始元素值都为 0, 现在定义数组元素三种值类型: 为 0 时, 表示无效数字; 为 1 时, 表示有效数字, 但是转换后不变; 为 2 时, 表示有效数字, 且转换后变成了新数字.
在 N 小于 10 的时候, 根据旋转规则, 直接将部分元素的值给定; 当 N 大于 10 的时候, 只需要判断两部分即可, 一是个位数之前的数, 二是个位数. 比如: 当判断 11 的时候, 先判断十位数 1, 再判断个位数 1, 因为还是自身, 所以 dp[11]=1; 当判断 112 的时候, 112 除以 10 等于 11, 而 dp[11]=1, 再判断个位数 2,dp[2]=2,2 会转成 5, 因此旋转后变成 115, 符合要求是个好数, 因此 dp[112]=2. 以此类推, 再 112 的基础上再增加一位时, 就只需要判断 112 和增加的个位数了, 而不必像第一种解法那样, 整数上的每一位都要判断一遍.
- public int rotatedDigits2(int N) {
- int count = 0;
- int[] dp = new int[N+1];
- for (int i=0; i<= N; i++) {
- if (i <10) {
- if (i == 0 || i == 1 || i == 8) {
- dp[i] = 1;
- } else if (i == 2 || i == 5 || i == 6 || i == 9) {
- dp[i] = 2;
- count++;
- }
- } else {
- // 判断前面的几位数和个位数
- int a = dp[i/10], b = dp[i%10];
- if (a == 1 && b == 1) {
- dp[i] = 1;
- } else if (a>= 1 && b>= 1) {
- dp[i] = 2;
- count++;
- }
- }
- }
- return count;
- }
04 小结
算法专题目前已日更超过五个月, 算法题文章 185 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/e612c000245a