Java动态规划之丑数问题实例讲解

问题描述：

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

注： 1也是丑数

思路：

我们来分析一下丑数如何得到，肯定是由前面的丑数乘2，乘3或者乘5得到，因此这是一道动态规划题。

  1. 使用 dp[i] 记录第i个丑数， 初始值dp[0] = 1，返回 dp[n-1]
  2. 使用 a，b，c 记录以及 2，3，5 分别乘到了第几个丑数
  3. 动态规划方程为：

dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5);

如何更新a，b，c：

  • 若当前丑数（上述最小值）为dp[a]*2，则 a++
  • 若当前丑数（上述最小值）为dp[b]*3，则 b++
  • 若当前丑数（上述最小值）为dp[c]*5，则 c++

图解：

代码：

class Solution {
    public int nthUglyNumber(int n) {
        int a=0, b=0, c=0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i=1; i<n; i++){
            int n1 = dp[a]*2;
            int n2 = dp[b]*3;
            int n3 = dp[c]*5;
            dp[i] = Math.min(Math.min(n1, n2), n3);
            if(dp[i] == n1){ a++; }
            if(dp[i] == n2){ b++; }
            if(dp[i] == n3){ c++; }
        }
        return dp[n-1];
    }
}

变式题

题目描述：

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

思路

本题和前面的题一样，只要把 2，3，5 改成 3，5，7即可 代码

class Solution {
    public int getKthMagicNumber(int k) {
        int a=0, b=0, c=0;
        int[] dp = new int[k];
        dp[0] = 1;
        for(int i=1; i<k; i++){
            int n1 = dp[a]*3;
            int n2 = dp[b]*5;
            int n3 = dp[c]*7;
            dp[i] = Math.min(Math.min(n1, n2), n3);
            if(dp[i] == n1){ a++; }
            if(dp[i] == n2){ b++; }
            if(dp[i] == n3){ c++; }
        }
        return dp[k-1];
    }
}

到此这篇关于Java动态规划之丑数问题实例讲解的文章就介绍到这了,更多相关Java丑数问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java动态规划方式解决不同的二叉搜索树

    Java动态规划方式解决不同的二叉搜索树

    目录 一.题目描述 二.思路 三.代码 一.题目描述 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数. 来源:https://leetcode.cn/problems/unique-binary-search-trees/ 二.思路 本题可以使用动态规划的方式解决,我们先来看一下大题思路.以 n = 3 为例,n = 3 时的不同的二叉搜索树数目,可以通过分别 以 1 为根节点,以 2 为根节点,以 3 为根节点

  • Java使用动态规划算法思想解决背包问题

    Java使用动态规划算法思想解决背包问题

    目录 动态规划算法 动态规划算法的思想 最优性原理 动态规划算法的三大特点 动态规划算法中的0/1背包问题 动态规划算法的优点 小结 动态规划算法 动态规划算法的思想 动态规划算法处理的对象是多阶段复杂决策问题,动态规划算法和分治算法类似,其基本思想也是将待求解问题分解成若干个子问题(阶段),然后分别求解各个子问题(阶段),最后将子问题的解组合起来得到原问题的解,但是与分治算法不同的是,子问题往往不是相互独立的,而是相互联系又相互区别的 动态规划算法问题求解的目标是获取导致问题最优解的最优决策序

  • Java数据结构超详细分析二叉搜索树

    Java数据结构超详细分析二叉搜索树

    目录 1.搜索树的概念 2.二叉搜索树的简单实现 2.1查找 2.2插入 2.3删除 2.4修改 3.二叉搜索树的性能 1.搜索树的概念 二叉搜索树是一种特殊的二叉树,又称二叉查找树,二叉排序树,它有几个特点: 如果左子树存在,则左子树每个结点的值均小于根结点的值. 如果右子树存在,则右子树每个结点的值均大于根结点的值. 中序遍历二叉搜索树,得到的序列是依次递增的. 二叉搜索树的左右子树均为二叉搜索树. 二叉搜索树的结点的值不能发生重复. 2.二叉搜索树的简单实现 我们来简单实现以下搜索树,就不

  • Java数据结构之二叉搜索树详解

    Java数据结构之二叉搜索树详解

    目录 前言 性质 实现 节点结构 初始化 插入节点 查找节点 删除节点 最后 前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的,题目要求删除指定值的节点,并且需要保证二叉搜索树性质不变,做完之后,我觉得这道题将二叉搜索树特性凸显的很好,首先需要查找指定节点,然后删除节点并且保持二叉搜索树性质不变,就想利用这个题目讲讲二叉搜索树. 二叉搜索树作为一个经典的数据结构,具有链表的快速插入与删除的特点,同时查询效率也很优秀,所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数

  • Java通过动态规划设计股票买卖最佳时机

    Java通过动态规划设计股票买卖最佳时机

    目录 买卖股票的最佳时机 动态规划 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格.你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票.设计一个算法来计算你所能获取的最大利润.返回你可以从这笔交易中获取的最大利润.如果你不能获取任何利润,返回 0 . 示例: 链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock 动态规划

  • Java动态规划之硬币找零问题实现示例

    目录 问题描述: 问题分析: 具体的过程如下: 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的

  • 在Java中实现二叉搜索树的全过程记录

    在Java中实现二叉搜索树的全过程记录

    目录 二叉搜索树 有序符号表的 API 实现二叉搜索树 二叉搜索树类 查找 插入 最小/大的键 小于等于 key 的最大键/大于等于 key 的最小键 根据排名获得键 根据键获取排名 删除 总结 二叉搜索树 二叉搜索树结合了无序链表插入便捷和有序数组二分查找快速的特点,较为高效地实现了有序符号表.下图显示了二叉搜索树的结构特点(图片来自<算法第四版>): 可以看到每个父节点下都可以连着两个子节点,键写在节点上,其中左边的子节点的键小于父节点的键,右节点的键大于父节点的键.每个父节点及其后代节点

  • Java动态规划之丑数问题实例讲解

    Java动态规划之丑数问题实例讲解

    问题描述: 我们把只包含质因子 2.3 和 5 的数称作丑数(Ugly Number).求按从小到大的顺序的第 n 个丑数. 注: 1也是丑数 思路: 我们来分析一下丑数如何得到,肯定是由前面的丑数乘2,乘3或者乘5得到,因此这是一道动态规划题. 使用 dp[i] 记录第i个丑数, 初始值dp[0] = 1,返回 dp[n-1] 使用 a,b,c 记录以及 2,3,5 分别乘到了第几个丑数 动态规划方程为: dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3),

  • java 中动态代理机制的实例讲解

    java 中动态代理机制的实例讲解 在学习Spring的时候,我们知道Spring主要有两大思想,一个是IoC,另一个就是AOP,对于IoC,依赖注入就不用多说了,而对于Spring的核心AOP来说,我们不但要知道怎么通过AOP来满足的我们的功能,我们更需要学习的是其底层是怎么样的一个原理,而AOP的原理就是java的动态代理机制,所以本篇随笔就是对java的动态机制进行一个回顾. 在java的动态代理机制中,有两个重要的类或接口,一个是 InvocationHandler(Interface)

  • Java异常 Exception类及其子类(实例讲解)

    C语言时用if...else...来控制异常,Java语言所有的异常都可以用一个类来表示,不同类型的异常对应不同的子类异常,每个异常都对应一个异常类的对象. Java异常处理通过5个关键字try.catch.finally.throw.throws进行管理.基本过程是用try包住要监视的语句,如果在try内出现异常,则异常会被抛出,catch中捕获抛出的异常并做处理,finally一定会完成未尽事宜. 练习: package com.swift; public class Exception1

  • java创建多级目录文件的实例讲解

    实例如下所示: /** * 创建多级目录文件 * * @param path 文件路径 * @throws IOException */ private void createFile(String path) throws IOException { if (StringUtils.isNotEmpty(path)) { File file = new File(path); if (!file.getParentFile().exists()) { file.getParentFile().

  • 基于Java中UDP的广播形式(实例讲解)

    UDP---用户数据报协议,是一个简单的面向数据报的运输层协议.UDP不提供可靠性,它只是把应用程序传给IP层的数据报发送出去,但是并不能保证它们能到达目的地 ,也不能保证数据包到达的顺序.由于UDP在传输数据报前不用在客户和服务器之间建立一个连接,且没有超时重发等机制,故而传输速度很快. 在Java中UDP的实现: * UDP: * 客户端: * 1.创建用于UDP通信的socket对象---DatagramSocket(用于UDP数据的发送和接收)---数据报套接字 * 2.准备数据,封装包

  • Java获取json数组对象的实例讲解

    如下所示: JSONArray jsonArray1 = jsonObject.getJSONArray("result"); for (int i = 0; i < jsonArray1.length(); i++) { JSONObject temp = (JSONObject) jsonArray1.get(i); String x = temp.getString("x"); String y = temp.getString("y"

  • java中list的用法和实例讲解

    目录: list中添加,获取,删除元素: list中是否包含某个元素: list中根据索引将元素数值改变(替换): list中查看(判断)元素的索引: 根据元素索引位置进行的判断: 利用list中索引位置重新生成一个新的list(截取集合): 对比两个list中的所有元素: 判断list是否为空: 返回Iterator集合对象: 将集合转换为字符串: 将集合转换为数组: 集合类型转换: 去重复: 备注:内容中代码具有关联性. 1.list中添加,获取,删除元素: 添加方法是:.add(e): 获

  • python爬虫中抓取指数的实例讲解

    python爬虫中抓取指数的实例讲解

    有一些数据我们是没法直观的查看的,需要通过抓取去获得.听到指数这个词,有的小伙伴们觉得很复杂,似乎只在股票的时候才听说的,比如一些数据的涨跌分析都是比较棘手的问题.不过指数对于我们的数据分析还是很有帮助的,今天小编就python爬虫中抓取指数得方法给大家带来讲解. 刚好这几天需要用到这个爬虫,结果发现baidu指数的请求有点变化,所以就改了改: import requests import sys import time word_url = 'http://index.baidu.com/ap

  • java中使用map排序的实例讲解

    对列表进行排序也是我们经常遇到的问题,这里缩小一下范围,使用map来对列表排序.相信大家都有过TreeMap排序的经历,不过Map.Entry能按值进行排序,在用法上略胜一筹.下面我们会对这两种map排序的方法分别进行介绍,着重讲解Map.Entry排序的方法. 1.Map.Entry方法 把Map.Entry放进list,再用Comparator对list进行排序 List list = new ArrayList(map.entrySet()); Collections.sort(list,

  • java使用IO流对数组排序实例讲解

    在学会了java中io流的使用后,我们对于数组的排序,又多了一种使用方法.大家知道流处理数据的效率是比较理想的,那么在具体操作数组排序上,很多人对于排序的方法还没有明确.下面我们先java使用流对数组排序的思路为大家进行梳理,然后带来对应的实例代码方法. 1.排序思路 (1)从字符输入流中读取文本,缓冲各个字符,从而实现字符.数组和行的高效读取 (2)询问用户需要多少位数的数组 (3)转换为数字类型 (4)将用户输入数字存入数组 (5)把数组按排序需求并打印出来 2.实例 public stat

随机推荐