[LeetCode] 944. Delete Columns to Make Sorted 删除列使其有序
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 = ["abcdef","uvwxyz"]
and deletion indices {0, 2, 3}
, then the final array after deletions is ["bef", "vyz"]
, and the remaining columns of A
are ["b","v"]
, ["e","y"]
, and ["f","z"]
. (Formally, the c
-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]
).
Suppose we chose a set of deletion indices D
such that after deletions, each remaining column in A is in non-decreasing sorted order.
Return the minimum possible value of D.length
.
Example 1:
Input: A = ["cba","daf","ghi"]
Output: 1
Explanation:
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.
Example 2:
Input: A = ["a","b"]
Output: 0
Explanation: D = {}
Example 3:
Input: A = ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}
Constraints:
1 <= A.length <= 100
1 <= A[i].length <= 1000
这道题给了一个字符串数组,里面的字符串长度均相同,这样如果将每个字符串看作一个字符数组的话,于是就可以看作的一个二维数组,题目要求所有列上的字符是非递减顺序的,问最少需要删掉多少列。这道题唯一的难点就是读懂晦涩的题意,估计是出自非母语之手的,其他的并没有太大的难度,就是一个按列来遍历二维数组的操作,若当前位置的字符小于等于下一行同列上的字符,则跳过继续比较下一行和下下一行上的字符。否则说明需要删掉该列,结果 res 自增1,且 break 掉当前列即可,参见代码如下:
class Solution {
public:
int minDeletionSize(vector<string>& A) {
int n = A.size(), len = A[0].size(), res = 0;
for (int j = 0; j < len; ++j) {
for (int i = 0; i < n - 1; ++i) {
if (A[i][j] <= A[i + 1][j]) continue;
++res;
break;
}
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/944
参考资料:
https://leetcode.com/problems/delete-columns-to-make-sorted/
相关文章
- Leetcode: Subtree of Another Tree
- Leetcode: Sliding Window Maximum
- Leetcode: Palindrome Linked List
- leetCode 41.First Missing Positive (第一个丢失的正数) 解题思路和方法
- [LeetCode] String to Integer (atoi)
- [LeetCode] Flatten Binary Tree to Linked List
- 【leetcode】日积月累,每日一题--206. 反转链表(DayDayUp 13)
- 【LeetCode】109. Convert Sorted List to Binary Search Tree
- LeetCode Best Time to Buy and Sell Stock I II III
- LeetCode——Convert Sorted Array to Binary Search Tree
- 【Leetcode】2:两数相加(Python)
- [LeetCode] 1318. Minimum Flips to Make a OR b Equal to c 或运算的最小翻转次数
- [LeetCode] 982. Triples with Bitwise AND Equal To Zero 按位与为零的三元组
- [LeetCode] 964. Least Operators to Express Number 表示数字的最少运算符
- [LeetCode] 960. Delete Columns to Make Sorted III 删除列使其有序之三
- [LeetCode] Lonely Pixel II 孤独的像素之二
- [LeetCode] 538. Convert BST to Greater Tree 将二叉搜索树BST转为较大树
- [LeetCode] 453. Minimum Moves to Equal Array Elements 最少移动次数使数组元素相等
- [LeetCode] 273. Integer to English Words 整数转为英文单词
- [LeetCode] 25. Reverse Nodes in k-Group 每k个一组翻转链表
- [LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树
- [LeetCode] 8. String to Integer (atoi) 字符串转为整数
- leetcode 241. Different Ways to Add Parentheses 为运算表达式设计优先级(中等)
- leetcode 310. Minimum Height Trees 最小高度树(中等)