奇怪的打印机
难度:
标签:
题目描述
代码结果
运行时间: 131 ms, 内存: 18.6 MB
/*
* 题目思路:
* 使用Java Stream的API来解决这个问题。
* 可以通过将字符串转化为字符流,并使用distinct方法去重,然后计算这些不同字符的数量。
*/
import java.util.stream.IntStream;
public class StrangePrinterStream {
public int strangePrinter(String s) {
if (s == null || s.length() == 0) return 0;
return (int) IntStream.range(0, s.length() - 1)
.filter(i -> s.charAt(i) != s.charAt(i + 1))
.count() + 1; // 初始值为1,因为至少需要一次打印
}
}
解释
方法:
该题解采用了动态规划的思路。首先对原字符串进行预处理,去除连续重复的字符。然后使用记忆化搜索来求解最少打印次数。dp(i, j) 表示打印子串 s[i:j] 所需的最少次数。如果 s[i] 和 s[j-1] 相同,则可以直接忽略最后一个字符。否则,枚举 s[i:j] 中间与 s[j-1] 相同的字符作为分割点,将原问题分解为两个子问题,取各子问题的最优解,然后相加得到原问题的最优解。通过记忆化搜索避免了重复计算。
时间复杂度:
O(n^3)
空间复杂度:
O(n^2)
代码细节讲解
🦆
为何在题解中,预处理步骤是去除连续重复的字符?这个步骤对解题有什么帮助?
▷🦆
在动态规划的状态转移方程中,为什么当s[i] == s[j-1]时,可以直接考虑dp(i, j-1)而忽略s[j-1]?
▷🦆
题解中提到使用记忆化搜索来避免重复计算,具体是如何实现的?它与普通的递归有什么区别?
▷🦆
题解中使用了数组prev来记录每个字符最后一次出现的位置,这个数组的作用是什么?
▷相关问题
移除盒子
给出一些不同颜色的盒子 boxes
,盒子的颜色由不同的正数表示。
你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k
个盒子(k >= 1
),这样一轮之后你将得到 k * k
个积分。
返回 你能获得的最大积分和 。
示例 1:
输入:boxes = [1,3,2,2,2,3,4,3,1] 输出:23 解释: [1, 3, 2, 2, 2, 3, 4, 3, 1] ----> [1, 3, 3, 4, 3, 1] (3*3=9 分) ----> [1, 3, 3, 3, 1] (1*1=1 分) ----> [1, 1] (3*3=9 分) ----> [] (2*2=4 分)
示例 2:
输入:boxes = [1,1,1] 输出:9
示例 3:
输入:boxes = [1] 输出:1
提示:
1 <= boxes.length <= 100
1 <= boxes[i] <= 100