当前位置: 首页 > news >正文

字节跳动面到这道题,有的读者一脸懵逼,有的读者笑嘻嘻

大家好,我是程序员吴师兄。

今天在逛 LeetCode 评论区的时候,发现了一道题目近期频繁出现在字节跳动的面试中,不得不感慨一句:面试官真喜欢考察 动态规划 呀!

今天就来详解这道题目,希望能帮助你在面试的时候笑嘻嘻:)

题目描述是这样子的。

题目描述

编写一个程序,找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明: 

  • 1 是丑数。

  • n 不超过1690。

题目来源:https://leetcode-cn.com/problems/ugly-number-ii/

题目解析

题目让你找出第 n 个丑数。对于丑数,题目也给出了定义,丑数是正整数,并且它的质数因子仅包含 2, 3, 5。另外,整数 1 算是一个最小的丑数。

一开始看到这道题,感觉就是一道简单的数学乘法题,一个循环不就搞定了?

但其实并不是,如果仅仅使用简单的乘法循环,你并不知道下一个数所在的序列位置

另外,暴力的深度优先搜索遍历在这道题上也不适用,因为你并不确定搜索的结束条件,到底找到哪个数才停止递归呢?

但如果进一步思考,你会发现 后面的数可以由前面的数推出来

用通俗一点的话讲就是,问题的解可以由子问题的解推出来。这句话是不是很熟悉?是的,动态规划的特点

但这里比较难想到的地方是,子问题之间的联系是什么?

比如我们定义动态规划状态,dp[i] 表示第 i 个丑数,那么这个状态怎么由前面的状态推导得出?

这里的重点是,前面的每一个数(状态)都可以乘上 2, 3, 5 来形成一个新的状态,新的状态是肯定符合丑数的定义。

但是我们的关注点是下一个状态是什么,比如第一个状态是 1,它可以乘以上面 3 个数的其中一个,结果为 2、3、5,取最小的 1 × 2 = 2 为第二个状态。

到这时,我们需要考虑第三个状态是什么。

从第一个状态 1 出发,我们得到了 2,但是从第一个状态 1 出发,我们还可以得到 3,5。另外,从第二个状态 2 出发我们可以得到  4 。

你可能会说,从第二个状态 2 出发我们还可以得到 6、10。没错,但是乘上 3、5 在 1 的时候考虑比在 2 处考虑得出的状态更小。

也就是说,第三个状态的值在 1 × 3、1 × 5、 2 × 2 三者里面进行选择。

通过上面的描述,你可能 找到规律 了:每个状态都可以乘上 2, 3, 5

但是状态乘上这些质数因子的时候,必须保证前面的状态已经乘过了对应的质数因子,因为前面会得到更小的值,我们需要的是 按序查找

由此,我们可以创建 3 个指针 p2、p3、p5,分别表示这 3 个质数因子此时应该乘上第几个状态。

补充:这里来具体解释一下 p2、p3、p5 的含义(来源于 LeetCode 题解区 zzxn)。

实际上 pi 的含义是有资格同 i 相乘的最小丑数的位置

这里资格指的是:如果一个丑数 dp[pi] 通过乘以 i 可以得到下一个丑数,那么这个丑数 dp[pi] 就永远失去了同 i 相乘的资格(没有必要再乘了),我们把 pi++ 让 dp[pi] 指向下一个丑数即可。

不懂的话举例说明:

一开始,丑数只有{1},1可以同 2 、3 、5 相乘,取最小的 1 ×  2 = 2 添加到丑数序列中。

现在丑数中有 {1,2} ,在上一步中,1 已经同 2 相乘过了,所以今后没必要再比较 1 × 2 了,我们说 1 失去了同 2 相乘的资格。

现在 1 有与 3、5 相乘的资格,2 有与 2、3、5 相乘的资格,但是 2 × 3 和 2 × 5 是没必要比较的,因为有比它更小的 1 可以同 3、5 相乘,所以我们只需要比较 1 × 3 、1 × 5 、 2 × 2 。

依此类推,每次我们都分别比较有资格同 2、3、5 相乘的最小丑数,选择最小的那个作为下一个丑数,假设选择到的这个丑数是同 i( i = 2、3、5)相乘得到的,所以它失去了同 i 相乘的资格,把对应的 pi++ ,让 pi 指向下一个丑数即可。

这样的思路可以在 O(n) 的时间完成这道题目。

参考代码

class Solution {public int nthUglyNumber(int n) {if( n < 1) return 0;int p2 = 0;int p3 = 0;int p5 = 0;int[] dp = new int[n];dp[0] = 1;for (int i = 1; i < n; i ++) {// 比较此时可能的状态,取最小的那个dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));// 更新指向// 注意这里不能只更新一个指针// 比如 6,可以由 2 * 2 * 2 形成,也可以由 2 * 3 组成if( dp[i] == dp[p2] * 2) p2++;if( dp[i] == dp[p3] * 3) p3++;if( dp[i] == dp[p5] * 5) p5++;}return dp[n - 1];}
}

---

由 五分钟学算法 原班人马打造的公众号:图解面试算法,现已正式上线!
接下来我们将会在该公众号上,为大家分享优质的算法解题思路,坚持每天一篇原创文章的输出,视频动画制作不易,感兴趣的小伙伴可以关注点赞一下哈!

http://www.taodudu.cc/news/show-8457230.html

相关文章:

  • 初学网络安全一脸懵逼?看懂直接跪下!
  • 微信小程序app.json全局配置
  • 计算机毕业设计PHP+安卓美食菜谱App(源码+程序+lw+远程调试)
  • 同城厨师上门做饭系统源码做菜预约做饭家宴代厨轰趴app源码厨师入住+厨师傅端/前端语言uniapp
  • 历书中的哥伦布
  • GPS历书(Almanac)和星历(Ephemeris)有什么区别?
  • SSM之一点一滴:Object对象使用Field反射遍历书输出
  • how many days c语言,万年历书-C精粹的万年历C语言实例解析精粹这本书的万年历程序实在是看不懂, 爱问知识人...
  • GPS星历与历书的区别
  • GPS卫星 星历与历书的区别
  • GPS星历与历书
  • Java小白——三元运算符比较两个数获得大值
  • 小程序的三元表达式
  • 三元表达式多个判断条件
  • 三元运算符 比较三个数大小 三元操作符的类型务必一致
  • 【题解】【AcWing】3874. 三元组的最小距离
  • java 三元运算符比大小
  • 三元组的最小距离问题|数据结构常见小题05
  • 三元运算符完成三个数的大小顺序排列
  • 最小三元组距离
  • 【算法】三元组求最小距离
  • 小程序三元参数判断
  • Python算法——求解最小三元组距离
  • 求解最小三元组距离
  • maven pom.xml加载不进来
  • IDEA 中导入Maven项目Jar加载不进来
  • 怎么判断微信小程序是分享进来页面
  • 解决idea pom依赖 导入jar包导入不进来
  • maven打包成第三方jar包且把pom依赖包打入进来的方法
  • okhttp3.logging.HttpLoggingInterceptor 引不进来包问题,kotlin看不了源码