【leetcode】944. Delete Columns to Make Sorted
2024-08-26 17:39:01
题目如下:
We are given an array
A
ofN
lowercase letter strings, all of the same length.Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have a string
"
abcdef
"
and deletion indices{0, 2, 3}
, then the final string after deletion is"
bef
"
.Suppose we chose a set of deletion indices
D
such that after deletions, each remaining column in A is in non-decreasing sorted order.Formally, the
c
-th column is[A[0][c], A[1][c], ..., A[A.length-1][c]]
Return the minimum possible value of
D.length
.Example 1:
Input: ["cba","daf","ghi"]
Output: 1Example 2:
Input: ["a","b"]
Output: 0Example 3:
Input: ["zyx","wvu","tsr"]
Output: 3Note:
1 <= A.length <= 100
1 <= A[i].length <= 1000
解题思路:如果不考虑时间复杂度,那么这题的级别应该是Easy,而不是Medium。O(n^2)的方法也很简单,遍历每一组序列,如果不满足递增则要删除这一组。
代码如下:
class Solution(object):
def minDeletionSize(self, A):
"""
:type A: List[str]
:rtype: int
"""
for i in range(len(A)):
A[i] += '{'
res = 0
for j in range(len(A[0])):
for i in range(len(A)-1):
if A[i][j] > A[i+1][j]:
res += 1
break
return res
最新文章
- 手动部署servlet
- jzoj[1224]
- synchronized同步锁+单利模式
- Android开发之 Android应用程序详细解析
- Photoshop:通过图片理解通道原理
- 在myeclipse中使用Java语言进行spark Standalone模式应用程序开发
- linux指令tips
- ORACLE/MYSQL/DB2等不同数据库取前几条记录
- 说说JSON和JSONP,浅析JSONP解决AJAX跨域问题
- 开源 &; 在线免费使用:升讯威 周报系统
- Circular view path [home]: would dispatch back to the current handler URL [/home] again. Check your ViewResolver setup!
- 作为开发人员,这四类Code Review方法你都知道吗?
- MySQL-count(*)和count(1)的查询区别
- 重启虚拟机后dhclient进程未运行解决办法
- Winform 时间
- C++标准库和标准模板库(转)
- C语言之Bit-wise Operation和Logical Operation
- SELECT中常用的子查询操作
- 分布式事务之——tcc-transaction分布式TCC型事务框架搭建与实战案例(基于Dubbo/Dubbox)
- Vue 之axios获取Http响应头