leetcode
leetcode 551 ~ 600
奇怪的打印机

奇怪的打印机

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为何在题解中,预处理步骤是去除连续重复的字符?这个步骤对解题有什么帮助?
在题解中,预处理步骤去除连续重复的字符是因为在打印过程中,连续的相同字符可以在一次打印操作中完成。例如,字符串'aaabb'可以被看作是'ab'进行打印,因为连续的'a'和'b'在实际打印中不需要单独区分。这样预处理后,可以显著减少需要考虑的子问题数量,从而简化问题的复杂度。这个步骤有助于优化动态规划过程中的状态转移,减少不必要的冗余计算。
🦆
在动态规划的状态转移方程中,为什么当s[i] == s[j-1]时,可以直接考虑dp(i, j-1)而忽略s[j-1]?
在动态规划中,当s[i]和s[j-1]相同时,意味着第i个字符和第j-1个字符可以在同一次打印操作中被打印出来,因此s[j-1]可以被's[i...j-1]'的打印过程包含。因此,问题可以简化为求解s[i...j-2]的最小打印次数,即dp(i, j-1)。这利用了问题的重叠子问题特性,避免了重复的计算,且保证了打印次数最小化。
🦆
题解中提到使用记忆化搜索来避免重复计算,具体是如何实现的?它与普通的递归有什么区别?
记忆化搜索是动态规划的一种实现方式,它通过存储已经计算过的结果(通常是在递归过程中)来避免重复计算,从而提高效率。在Python中,这通常是通过使用装饰器如@cache来实现的。这种方法与普通递归的主要区别在于,普通递归每次调用都会重新计算结果,而记忆化搜索会先查看之前是否已经计算过相同的调用,如果是,则直接返回存储的结果,减少了计算次数。
🦆
题解中使用了数组prev来记录每个字符最后一次出现的位置,这个数组的作用是什么?
数组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