这是悦乐书的第362次更新,第389篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第224题(顺位题号是944)。我们给出了一个N个小写字母串的数组A,它们的长度都相同。

现在,我们可以选择任何一组删除索引,对于每个字符串,我们删除这些索引中的所有字符。

例如,如果我们有一个数组A = [“abcdef”,“uvwxyz”]和删除索引{0,2,3},那么删除后的数组变成了[“bef”,“vyz”],纵向上看,每一列是[“b”,“v”][“e”,“y”][“f”,“z”]。(形式上,第c列是[A[0][c]A[1][c],...,A[A.length-1][c]]。)

假设我们选择了一组删除索引D,使得在删除之后,A中的每个剩余列都处于递增排序顺序。返回D.length的最小可能值。例如:

输入:[“cba”,“daf”,“ghi”]
输出:1
说明:在选择D = {1}之后,每列[“c”,“d”,“g”][“a”,“f”,“i”]处于递增的排序顺序。如果我们选择D = {},则列[“b”,“a”,“h”]将不是递增排序顺序。

输入:[“a”,“b”]
输出:0
说明:D = {}

输入:[“zyx”,“wvu”,“tsr”]
输出:3
说明:D = {0,1,2}

注意

  • 1 <= A.length <= 100

  • 1 <= A[i].length <= 1000

02 第一种解法

题目的意思是A中包含了许多长度一样的字符串元素,从纵向来看,单个字符串中的每一列字符大小关系需要是递增的,如果不是,则需要删除,问需要删除多少列字符,才能保证所有列的字符大小关系都是递增的。结合给的示例来看,[“cba”,“daf”,“ghi”],纵向来看就变成了下面这样:

cba -->  c b a
daf -->  d a f
ghi -->  g h i

第一列为cdg,是递增的,不用删除,第二列为bah,不是递增,需要删除,第三列是afi,是递增的,不用删除,所以最后需要删除中间那列的字符,就能保证所有列的字符大小关系都是递增的,所以返回1。

思路:根据上面我们的分析,直接上两层循环就行,外层控制列数,内层控制行数,注意下标不能越界。

此解法的时间复杂度为O(A)A为数组A中所有字符的个数,空间复杂度为O(1)

public int minDeletionSize(String[] A) {
    int n = A[0].length(), len = A.length;
    int count = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<len-1; j++) {
            if (A[j].charAt(i) > A[j+1].charAt(i)) {
                count++;
                break;
            }
        }
    }
    return count;
}


03 第二种解法

我们还可以使用二维数组来解题。

在第一种解法中,通过纵向观察,可以将A中的所有字符看成是一个二维数组,行是A中元素个数,列是A中单个字符串的长度,先将字符初始化进二维数组中,然后遍历二维数组,比较列上前后字符的大小关系,需要删除(前后不是递增顺序)就计数加1,最后返回累加的count

此解法的时间复杂度时O(A)A为数组A中所有字符的个数,空间复杂度为O(N*M)N为数组A的长度,MA中单个元素的长度。

public int minDeletionSize2(String[] A) {
    int row = A.length, col = A[0].length();
    char[][] arr = new char[row][col];
    for (int i=0; i<A.length; i++) {
        arr[i] = A[i].toCharArray();
    }
    int count = 0;
    for (int i=0; i<col; i++) {
        for (int j=0; j<row-1; j++) {
            if (arr[j][i] > arr[j+1][i]) {
                count++;
                break;
            }
        }
    }
    return count;
}


04 小结

算法专题目前已连续日更超过七个月,算法题文章230+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!