leetcode 944. 删列造序

1

题目描述

944. 删列造序

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = ["abc", "bce", "cae"] 可以排列为：

abc bce cae 你需要找出并删除 不是按字典序升序排列的 列。在上面的例子（下标从 0 开始）中，列 0（'a', 'b', 'c'）和列 2（'c', 'e', 'e'）都是按升序排列的，而列 1（'b', 'c', 'a'）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：

输入：strs = ["cba","daf","ghi"] 输出：1 解释：网格示意如下： cba daf ghi 列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。 示例 2：

输入：strs = ["a","b"] 输出：0 解释：网格示意如下： a b 只有列 0 这一列，且已经按升序排列，所以不用删除任何列。 示例 3：

输入：strs = ["zyx","wvu","tsr"] 输出：3 解释：网格示意如下： zyx wvu tsr 所有 3 列都是非升序排列的，所以都要删除。

提示：

n == strs.length 1 <= n <= 100 1 <= strs[i].length <= 1000 strs[i] 由小写英文字母组成

解题思路

法1

方法1:模拟遍历

1. 分别判断每一列是否为增序列,即后面不小于前面的字母

2. 记录不是增序列的个数

3. 输出结果

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

比较字符串数组strs中相邻字符串的对应字符，如果发现有列不是按字典序升序排列的，则计数器count加1。最后返回count的值，即需要删除的列数。

首先，我们获取字符串数组strs的第一个字符串的长度，记为n，因为题目中说明每个字符串长度相等。

然后，我们使用两层循环，外层循环控制列的索引，从0到n-1。内层循环从索引1开始，逐个比较当前列的字符和上一列的字符。如果发现当前列的字符小于上一列的字符，说明这一列不是按字典序升序排列的，需要删除，此时计数器count加1，并跳出内层循环。

最后，返回count的值，即需要删除的列数。

func minDeletionSize(strs []string) int {
    count := 0
    n := len(strs[0])

    for i := 0; i < n; i++ {
        for j := 1; j < len(strs); j++ {
            if strs[j][i] < strs[j-1][i] {
                count++
                break
            }
        }
    }

    return count
}

1

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 8 ms , 在所有 Go 提交中击败了 80.56% 的用户 内存消耗： 6.4 MB , 在所有 Go 提交中击败了 50.00% 的用户 通过测试用例： 86 / 86 炫耀一下:

1

1