分段线性 DP 问题,以及常见空间优化手段|Java 刷题打卡

简介: 分段线性 DP 问题,以及常见空间优化手段|Java 刷题打卡

题目描述



这是 LeetCode 上的 91. 解码方法 ,难度为 中等


Tag : 「线性 DP」


一条包含字母 A-Z 的消息通过以下映射进行了 编码 :


'A' -> 1
'B' -> 2
...
'Z' -> 26
复制代码


要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为:


  • "AAJF" ,将消息分组为 (1 1 10 6)
  • "KJF" ,将消息分组为 (11 10 6)


注意,消息不能分组为  (1 11 06) ,因为 "06" 不能映射为 "F" ,这是由于 "6" 和 "06" 在映射中并不等价。


给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。


题目数据保证答案肯定是一个 32 位 的整数。


示例 1:


输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
复制代码


示例 2:


输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
复制代码


示例 3:


输入:s = "0"
输出:0
解释:没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。
复制代码


示例 4:


输入:s = "06"
输出:0
解释:"06" 不能映射到 "F" ,因为字符串含有前导 0("6" 和 "06" 在映射中并不等价)。
复制代码


提示:


  • 1 <= s.length <= 100
  • s 只包含数字,并且可能包含前导零。


基本分析



我们称一个解码内容为一个 item


为根据题意,每个 item 可以由一个数字组成,也可以由两个数字组成。


数据范围为 100,很具有迷惑性,可能会有不少同学会想使用 DFS 进行爆搜。


我们可以大致分析一下这样的做法是否可行:不失一般性的考虑字符串 s 中的任意位置 i,位置 i 既可以作为一个独立 item,也可以与上一位置组成新 item,那么相当于每个位置都有两种分割选择(先不考虑分割结果的合法性问题),这样做法的复杂度是 O(2n)O(2^n)O(2n) 的,当 n 范围是 100 时,远超我们计算机单秒运算量

10710^7107)。即使我们将「判断分割结果是否合法」的操作放到爆搜过程中做剪枝,也与我们的单秒最大运算量相差很远。


递归的方法不可行,我们需要考虑递推的解法。


动态规划



这其实是一道字符串类的动态规划题,不难发现对于字符串 s 的某个位置 i 而言,我们只关心「位置 i 自己能否形成独立 item 」和「位置 i 能够与上一位置(i-1)能否形成 item」,而不关心 i-1 之前的位置。


有了以上分析,我们可以从前往后处理字符串 s,使用一个数组记录以字符串 s 的每一位作为结尾的解码方案数。即定义 f[i]f[i]f[i] 为考虑前 iii 个字符的解码方案数。


对于字符串 s 的任意位置 i 而言,其存在三种情况:


  • 只能由位置 i 的单独作为一个 item,设为 a,转移的前提是 a 的数值范围为 [1,9][1,9][1,9],转移逻辑为 f[i]=f[i−1]f[i] = f[i - 1]f[i]=f[i1]
  • 只能由位置 i 的与前一位置(i-1)共同作为一个 item,设为 b,转移的前提是 b 的数值范围为 [10,26][10,26][10,26],转移逻辑为 f[i]=f[i−2]f[i] = f[i - 2]f[i]=f[i2]
  • 位置 i 既能作为独立 item 也能与上一位置形成 item,转移逻辑为 f[i]=f[i−1]+f[i−2]f[i] = f[i - 1] + f[i - 2]f[i]=f[i1]+f[i2]


因此,我们有如下转移方程:


{f[i]=f[i−1],1⩽a≤9f[i]=f[i−2],10⩽b⩽26f[i]=f[i−1]+f[i−2],1⩽a≤9,10⩽b⩽26\begin{cases} f[i] = f[i - 1], 1 \leqslant a \leq 9 \\ f[i] = f[i - 2], 10 \leqslant b \leqslant 26 \\ f[i] = f[i - 1] + f[i - 2], 1 \leqslant a \leq 9, 10 \leqslant b \leqslant 26 \\ \end{cases}f[i]=f[i1],1a9f[i]=f[i2],10b26f[i]=f[i1]+f[i2],1a9,10b26


其他细节:由于题目存在前导零,而前导零属于无效 item。可以进行特判,但个人习惯往字符串头部追加空格作为哨兵,追加空格既可以避免讨论前导零,也能使下标从 1 开始,简化 f[i-1] 等负数下标的判断。


代码:


class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) { 
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值,那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值,那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }
}
复制代码


  • 时间复杂度:共有 n 个状态需要被转移。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:O(n)O(n)O(n)


空间优化



不难发现,我们转移 f[i] 时只依赖 f[i-1]f[i-2] 两个状态。


因此我们可以采用与「滚动数组」类似的思路,只创建长度为 3 的数组,通过取余的方式来复用不再需要的下标。


代码:


class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[3];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i % 3] = 0;
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            if (1 <= a && a <= 9) f[i % 3] = f[(i - 1) % 3];
            if (10 <= b && b <= 26) f[i % 3] += f[(i - 2) % 3];
        }
        return f[n % 3];
    }
}
复制代码


  • 时间复杂度:共有 n 个状态需要被转移。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:O(1)O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.91 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
15天前
|
Java Spring
如何优化Java异步任务的性能?
本文介绍了Java中四种异步任务实现方式:基础Thread、线程池、CompletableFuture及虚拟线程。涵盖多场景代码示例,展示从简单异步到复杂流程编排的演进,适用于不同版本与业务需求,助你掌握高效并发编程实践。(239字)
125 6
|
21天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案
|
2月前
|
安全 Java 编译器
new出来的对象,不一定在堆上?聊聊Java虚拟机的优化技术:逃逸分析
逃逸分析是一种静态程序分析技术,用于判断对象的可见性与生命周期。它帮助即时编译器优化内存使用、降低同步开销。根据对象是否逃逸出方法或线程,分析结果分为未逃逸、方法逃逸和线程逃逸三种。基于分析结果,编译器可进行同步锁消除、标量替换和栈上分配等优化,从而提升程序性能。尽管逃逸分析计算复杂度较高,但其在热点代码中的应用为Java虚拟机带来了显著的优化效果。
63 4
|
2月前
|
存储 人工智能 算法
Java 大视界 -- Java 大数据在智能医疗影像数据压缩与传输优化中的技术应用(227)
本文探讨 Java 大数据在智能医疗影像压缩与传输中的关键技术应用,分析其如何解决医疗影像数据存储、传输与压缩三大难题,并结合实际案例展示技术落地效果。
Java 数据库 Spring
59 0
|
1月前
|
算法 Java
Java多线程编程:实现线程间数据共享机制
以上就是Java中几种主要处理多线程序列化资源以及协调各自独立运行但需相互配合以完成任务threads 的技术手段与策略。正确应用上述技术将大大增强你程序稳定性与效率同时也降低bug出现率因此深刻理解每项技术背后理论至关重要.
92 16
|
2月前
|
缓存 并行计算 安全
关于Java多线程详解
本文深入讲解Java多线程编程,涵盖基础概念、线程创建与管理、同步机制、并发工具类、线程池、线程安全集合、实战案例及常见问题解决方案,助你掌握高性能并发编程技巧,应对多线程开发中的挑战。
|
2月前
|
数据采集 存储 前端开发
Java爬虫性能优化:多线程抓取JSP动态数据实践
Java爬虫性能优化:多线程抓取JSP动态数据实践
|
3月前
|
Java API 调度
从阻塞到畅通:Java虚拟线程开启并发新纪元
从阻塞到畅通:Java虚拟线程开启并发新纪元
309 83
|
3月前
|
安全 算法 Java
Java 多线程:线程安全与同步控制的深度解析
本文介绍了 Java 多线程开发的关键技术,涵盖线程的创建与启动、线程安全问题及其解决方案,包括 synchronized 关键字、原子类和线程间通信机制。通过示例代码讲解了多线程编程中的常见问题与优化方法,帮助开发者提升程序性能与稳定性。
145 0

热门文章

最新文章