剑指offer计划29(动态规划困难)java

作者: 程序员khaos

1.1、题目1

剑指 Offer 19. 正则表达式匹配

1.2、解法

动态规划后面再研究

1.3、代码

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length() + 1, n = p.length() + 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = p.charAt(j - 1) == '*' ?
                    dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') :
                    dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));
            }
        }
        return dp[m - 1][n - 1];
    }
}

2.1、题目2

剑指 Offer 49. 丑数

2.2、解法

这题看题解才做出来的,不太懂动态规划,最近研究以下。

2.3、代码

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++)
        {
            dp[i]=Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
            if(dp[i]==dp[a]*2) a++;
            if(dp[i]==dp[b]*3) b++;
            if(dp[i]==dp[c]*5) c++;
        }
        return dp[n-1];
    }
}

3.1、题目3

剑指 Offer 60. n个骰子的点数

3.2、解法

3.3、代码

class Solution {
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

原文创作:程序员khaos

原文链接:https://www.cnblogs.com/urmkhaos/p/15353127.html

更多推荐

更多
  • Ansible2安全自动化-十、编写安全测试的 Ansible 模块 开始使用 hello world Ansible 模块,密码,建立开发环境,计划和要记住的内容,OWASP ZAP 模块,使用 Docker 创建 ZAP,创建易受攻击的应用,Ansible 模块模板,[计]元数据,记录模块,源代码模板
    Apache CN

  • Ansible2安全自动化-十一、可靠的安全最佳实践、参考和进一步阅读 十一、可靠的安全最佳实践、参考和进一步使用 Ansible 的保管库,如何对变量和文件使用 Ansible Vault,Ansible Vault 单一加密变量,Ansible 拱顶在 Ansible 塔中的应用,设置和使用可扫描集群,
    Apache CN

  • Ansible2安全自动化-九、用于取证收集和恶意软件分析的自动化实验室设置 为隔离环境的实验室创建可行的行动手册,收集文件和域恶意软件识别和分类,病毒总应用编程接口工具设置,病毒总应用编程接口扫描恶意软件样本,设置布谷鸟沙盒环境,设置布谷鸟主机,设置布谷鸟客人,使用 Ansible 行动手册提交样品和报告,使用
    Apache CN

  • Ansible2安全自动化-八、Docker 容器的持续安全扫描 理解连续安全概念,使用 Ansible 自动化 Docker 容器的漏洞评估,安全 Docker 工作台,克莱尔,为了 Docker 安全,使用 Ansible Tower 进行计划扫描,锚,锚定的引擎服务设置,锚定 cli 扫描仪,使
    Apache CN

  • Ansible2安全自动化-四、日志监控和无服务器自动防御(AWS 中的弹性栈) 四、日志监控和无服务器自动防御AWS 中的弹性栈弹性叠层介绍,弹性搜索,logstash(日志记录),马纳人,搜索,我们为什么要使用弹性栈进行安全监控和警报?,设置弹性栈的先决条件,设置弹性栈,Logstash 集成,马纳人,弹性纤维,
    Apache CN

  • Ansible2安全自动化-五、使用 OWASP ZAP 实现网络应用安全测试自动化 安装 OWASP ZAP,安装 Docker 运行时,OWASP ZAP 坞站容器设置,处理容器的专用工具——Ansible 容器,配置 ZAP 基线扫描,运行易受攻击的应用容器,运行 OWASP 扫描程序基线扫描,针对网络应用和网站的
    Apache CN

  • Ansible2安全自动化-六、利用 Nessus 进行漏洞扫描 尼斯介绍,安装 Nessus 进行漏洞评估,配置 Nessus 进行漏洞扫描,对网络执行扫描,基本网络扫描,使用自动扫描运行扫描,设置自动用户,使用自动扫描运行扫描,列出当前可用的扫描和标识,使用扫描标识启动指定的扫描,存储结果,安装
    Apache CN

  • Ansible2安全自动化-七、应用和网络的安全强化 使用 CIS、STIGs 和 NIST 等基准强化安全性,使用 Ansible 行动手册强化基线操作系统,STIGs 在 Linux 主机自动安全强化方面的可替代角色,使用 Ansible Tower 对 OpenSCAP 进行持续的安
    Apache CN

  • Ansible2安全自动化-三、使用加密自动备份设置加固 WordPress WordPress 命令行界面,为什么要为这种设置负责?,一个完整的 WordPress 安装步骤,正在设置 nginx web 服务器,设置先决条件,建立 MySQL 数据库,为 WordPress 安装程序安装 PHP,使用命令行界
    Apache CN

  • Ansible2安全自动化-二、Ansible Tower、Jenkins 和其他自动化工具 调度工具支持自动化的下一个抽象,起床跑步,设置可平移的塔,设置 Jenkins,设置运行平台,安全自动化用例,添加行动手册,Ansible 的塔式配置,Jenkins Ansible 集成配置,运行平台配置,认证和数据安全,RBAC 代
    Apache CN

  • 近期文章

    更多
    文章目录

      推荐作者

      更多