[LeetCode] 960. Delete Columns to Make Sorted III 删除列使其有序之三
We are given an array A
of N
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 an array A = ["babca","bbazb"]
and deletion indices {0, 1, 4}
, then the final array after deletions is ["bc","az"]
.
Suppose we chose a set of deletion indices D
such that after deletions, the final array has every element (row) in lexicographic order.
For clarity, A[0]
is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]
), A[1]
is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]
), and so on.
Return the minimum possible value of D.length
.
Example 1:
Input: ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn't necessarily in lexicographic order.
Example 2:
Input: ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row won't be lexicographically sorted.
Example 3:
Input: ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.
Note:
1 <= A.length <= 100
1 <= A[i].length <= 100
这道题说是给了一个字符串数组A,其中每个字符串的长度均相同,现在需要删除一些特定位置上的字符,需要使得留下的字符是按照字母顺序排列的,问最少需要删除多少列。这道题需要借助题目中给的例子来理解,因为每个字符串长度相同,若每行放一个字符串,那么其实也可以看作是一个二维的字符数组,要删除最少的列,使得每行都是有序的。实际上最差的情况就是每行都是倒序的,就要移除 n-1 列,只留下一列,若每行只有一个字符,则一定是符合题意。最好的情况就是给定每行已经都是有序的,则一列都不用移除,所以最终的结果是在一定的范围之内的,即 [0, n-1],其中n是字符串的长度。假如只有一个字符串,为了使其有序,需要移除最小的列数,移除之后剩下的就是有序的。那么其实就是等同于找出该字符串中的最大递增序列的长度,即之前那道 Longest Increasing Subsequence 的做法,然后用总长度减去这个 LIS 长度,即为最少移除的列数。若有多行的情况,这个 LIS 必须是所有行都满足的,才符合题意。这里维护一个一维 dp 数组,其中 dp[i] 表示以 A[][i] 为结尾的最长递增子串的长度,对于每一个 A[][i],从该行第一个数再搜索到i,此时由于有多行,每一行都要判断一下,假如出现 A[][j] 大于 A[][i] 的情况,说明当前列不能组成 LIS,直接 break。只有每行都符合要求,并且 dp[j]+1 大于 d[i] 时,将 dp[i] 赋值为 dp[j]+1。当每次 dp[i] 更新了之后,用 n-dp[i] 来更新结果 res 即可,参见代码如下:
class Solution {
public:
int minDeletionSize(vector<string>& A) {
int m = A.size(), n = A[0].size(), res = n - 1, k = 0;
vector<int> dp(n, 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
for (k = 0; k < m; ++k) {
if (A[k][j] > A[k][i]) break;
}
if (k == m && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
res = min(res, n - dp[i]);
}
return res;
}
};
讨论:可能会有同学有疑问,会出现 dp[j]+1 小于 dp[i] 的情况么,其实是有的,比如 "cbbdabc",i = 6,是最后一个c,因为前面有前面出现了 bb,所以此时的 dp[6] = 3,当 j = 4 时,是中间的a,前面没有比a小的字母,所以 dp[4] = 1,此时就出现了 dp[j]+1 小于 dp[i] 的情况。
Github 同步地址:
https://github.com/grandyang/leetcode/issues/960
类似题目:
Longest Increasing Subsequence
Delete Columns to Make Sorted II
参考资料:
https://leetcode.com/problems/delete-columns-to-make-sorted-iii/
相关文章
- Leetcode: Reorder List && Summary: Reverse a LinkedList
- [LeetCode] Remove Duplicates from Sorted List II
- [LeetCode] Best Time to Buy and Sell Stock II
- [LeetCode]167. 两数之和 II - 输入有序数组
- Leetcode每日一题(9.12)最长递增序列的个数
- 【leetcode周赛记录】第78场双周赛+第293场周赛记录
- 【LeetCode】273. Integer to English Words
- [LeetCode] 1320. Minimum Distance to Type a Word Using Two Fingers 二指输入的的最小距离
- [LeetCode] 1319. Number of Operations to Make Network Connected 连通网络的操作次数
- [LeetCode] 1105. Filling Bookcase Shelves 填充书架
- [LeetCode] 1019. Next Greater Node In Linked List 链表中的下一个较大的结点
- [LeetCode] 989. Add to Array-Form of Integer 数组形式的整数加法
- [LeetCode] 965. Univalued Binary Tree 单值二叉树
- [LeetCode] 944. Delete Columns to Make Sorted 删除列使其有序
- [LeetCode] 794. Valid Tic-Tac-Toe State 验证井字棋状态
- [LeetCode] 426. Convert Binary Search Tree to Sorted Doubly Linked List 将二叉搜索树转为有序双向链表
- [LeetCode] Convert a Number to Hexadecimal 数字转为十六进制
- [LeetCode] Wiggle Subsequence 摆动子序列
- [LeetCode] Super Ugly Number 超级丑陋数
- [LeetCode] Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期
- [LeetCode] 41. First Missing Positive 首个缺失的正数
- [LeetCode] Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四
- [LeetCode] 8. String to Integer (atoi) 字符串转为整数
- leetcode 300. Longest Increasing Subsequence 最长递增子序列 (中等)