删列造序 III

难度:

标签:

题目描述

代码结果

运行时间: 75 ms, 内存: 16.1 MB

/*
 * 题目思路：
 * 使用Java Stream API，遍历每列，检查每列是否破坏字典序。
 * 如果破坏则增加删除列的计数。
 */

import java.util.Arrays;

public class Solution {
    public int minDeletionSize(String[] strs) {
        int numCols = strs[0].length(); // 字符串的长度
        int[] deletionCounts = new int[1]; // 需要删除的列数

        // 遍历每一列
        Arrays.stream(strs[0].split(""))
                .forEach(c -> {
                    if (Arrays.stream(strs, 1, strs.length)
                            .anyMatch(str -> str.charAt(Arrays.asList(strs[0].split(""))
                                    .indexOf(c)) < str.charAt(Arrays.asList(strs[0].split(""))
                                    .indexOf(c) - 1))) {
                        // 如果发现当前列打破了字典序，我们就要删除它
                        deletionCounts[0]++;
                    }
                });
        return deletionCounts[0]; // 返回需要删除的列数
    }
}

解释

方法:

此题的思路是使用动态规划找出最长的按字典序排列的子序列。我们用一个数组 dp 来记录每个位置作为子序列结束位置时的最大长度。对于每个字符位置 i，我们检查前面所有的位置 j (j < i)，并判断 strs 中的所有字符串是否在 j 到 i 位置的字符是按字典序排列的。如果是，那么我们尝试用 dp[j] + 1 更新 dp[i]。最后，由于我们需要删除的列数是总列数减去最长有序子序列的长度，因此结果为列总数减去 dp 中的最大值。

时间复杂度:

O(m^2 * n)

空间复杂度:

O(m)

代码细节讲解

🦆

动态规划数组dp的初始化为1是基于什么考虑？每个位置最小可能的有序子序列长度是否一定是1？

▷

动态规划数组 dp 的初始化为1是基于这样的考虑：即使在最不利的情况下，每个字符位置本身都可以被视为一个长度为1的有序子序列。因此，每个位置的最小可能的有序子序列长度确实是1，代表该位置字符自身成为一个子序列。这样初始化保证了在动态规划的过程中，每个字符至少能构成一个长度为1的子序列。

🦆

在解法中，如果输入的字符串数组strs为空，返回值为0。但如果数组不为空而字符串长度为0，这种情况下的返回值应该如何处理？

▷

如果输入的字符串数组 strs 不为空，但每个字符串的长度为0，意味着没有任何列存在。在这种情况下，由于没有列可供删除，因此所需删除的列数也应为0。这是因为初始问题是基于列的删除来整理顺序，没有列自然也就没有需要删除的列。

🦆

在得到dp数组的最大值后，为什么直接用字符串的长度减去这个最大值得到答案？在什么情况下这种简化是合理的？

▷

在得到 dp 数组的最大值后，直接用字符串的长度减去这个最大值得到答案是基于这样的逻辑：dp 数组的最大值代表在所有字符串中能够形成的最长有序子序列的长度。因此，要使整个数组有序，需要删除的列数即为总列数减去这个最长有序子序列的长度。这种简化是合理的，因为我们的目标是减少删除的列数，同时保持字符串数组中每个字符串的相对顺序。这种方法直接给出了达到这一目标的最少删除次数。

删列造序 III

题目描述

代码结果

解释

代码细节讲解

相关问题