[LeetCode] Ugly Number II
LeetCode number II
2023-09-14 09:01:04 时间
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the
The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).
int ugly = Math.min(Math.min(num[n2] * 2, num[n3] * 3), num[n5] * 5); num[i++] = ugly; if (ugly == num[n2] * 2) { n2++; if (ugly == num[n3] * 3) { n3++; if (ugly == num[n5] * 5) { n5++; return num[n - 1]; }
LeetCode 306. Additive Number 累加数是一个字符串,组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 0 - 9 的字符串,编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number.
Hint:
The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).
见题目中的提示,主要就是维持一个丑数序列,一个丑数一定是序列中比它小的丑数乘以2,3或5的结果。
int ugly = Math.min(Math.min(num[n2] * 2, num[n3] * 3), num[n5] * 5); num[i++] = ugly; if (ugly == num[n2] * 2) { n2++; if (ugly == num[n3] * 3) { n3++; if (ugly == num[n5] * 5) { n5++; return num[n - 1]; }
LeetCode 306. Additive Number 累加数是一个字符串,组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 0 - 9 的字符串,编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
相关文章
- [LeetCode] Palindrome Number & Valid Palindrome - 回文系列问题
- [LeetCode] Number of 1 Bits & Reverse Integer - 整数问题系列
- Leetcode 之Convert Sorted List to Binary Search Tree(55)
- leetcode 之Single Number(14)
- Java实现 LeetCode 823 带因子的二叉树(DP)
- Java实现 LeetCode 432 全 O(1) 的数据结构
- Java实现 LeetCode 223 矩形面积
- Java实现 LeetCode 78 子集
- 【LeetCode算法-9】Palindrome Number
- [LeetCode] Missing Number
- [LeetCode] Number of 1 Bits
- Leetcode学习计划之动态规划入门day16(64,221)
- 【LeetCode Python实现】355. 设计推特(中等)
- Leetcode 1047. 删除字符串中的所有相邻重复项
- Leetcode 1209. 删除字符串中的所有相邻重复项 II(初版本没过)
- [LeetCode] 191. Number of 1 Bits ☆(位 1 的个数)
- leetcode文章137称号-Single Number II
- leetcode 9. Palindrome Number
- leetcode 374. Guess Number Higher or Lower
- leetcode 762. Prime Number of Set Bits in Binary Representation
- 【LeetCode】合并二叉树