概要
本篇通过944题演示实际学习过程中正确的解题思路，以及学习方法。算法相关的程序设计力求完美，在系统环境支持的情况下，时间和空间复杂度的考虑是首要因素，实际项目中针对算法相关的业务不妨多考虑一步，正所谓失之毫厘，差之千里！做到精益求精，总归是有帮助的。本篇题解思路相对简单，重在分析针对同一思路，对细节进行优化提高算法效率。
原题
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: ["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","b"]
Output: 0
Explanation: D = {}
Example 3:
Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}
Note:
1 <= A.length <= 100
1 <= A[i].length <= 1000
944. 删除非排序列（根据题意命名）
一个大小为N数组A，数组的每个元素是都是小写字母组成的字符串，其中每个字符串长度相等。
删除操作：删除一列，从A中删除这一列的所有字符，比如，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。
加入有一个数组A = ["abcdef", "uvwxyz"]，
被删除的列为 {0, 2, 3}，删除后A成为["bef", "vyz"]， 删除后A的列分别是["b","v"], ["e","y"], ["f","z"]。
请选出一组要删掉的列D，对A执行删除操作，A剩余的每一列都是非降序排列的，最后返回D.length的最小值。
例 1：
输入：["cba", "daf", "ghi"]
输出：1
说明：
选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，为非降序排列。
若选择 D = {}（不删除），那么 A 的列 ["b","a","h"] 不是非降序排列
例 2：
输入：["a", "b"]
输出：0
说明：D = {} （无需删除）
例 3：
输入：["zyx", "wvu", "tsr"]
输出：3
说明：D = {0, 1, 2}
提示：
1 <= A.length <= 100
1 <= A[i].length <= 1000
- 本题在LeetCode上属于贪心算法分类下
题意分析
本题所属分类虽在贪心算法下，但是显然属于统计数组中需要删除的非升序排列的列数，自然容易联想到最简单的方式，直接循环统计的方式。
思路:
循环统计法，循环遍历每一列，遍历当前列的某个元素时，对比当前字符和当前列的上一个字符是否为非降序，若为非降序列，则计数加1，遍历完成后得出总的非升序总列数。
伪代码
1、声明一个计数变量count;
2、根据列数进行for循环遍历
3、循环中再针对当前列进行比较统计，若当前列当前元素和上一元素对比为非升序排列，则计数加1
普通版：
public int minDeletionSize1(String[] A) {
if (A.length == 0) return 0;
int count = 0;
for (int i = 0; i < A[0].length(); i++) {
for (int j = 1; j < A.length; j++) {
if (A[j].charAt(i) < A[j - 1].charAt(i)) {
count++;
break;
}
}
}
return count;
}
普通版执行结果
进阶版
public int minDeletionSize(String[] A) {
if (A == null) return 0;
int count = 0;
for (int i = 0; i < A[0].length(); ++i) {
if(isNoSort(A, i)) ++count;
}
return count;
}
public static boolean isNoSort(String[] A, int num) {
for (int i = 1; i < A.length; ++i) {
if (A[i].charAt(num) < A[i-1].charAt(num)) return true;
}
return false;
}
进阶版执行结果
终极版
public int minDeletionSize(String[] A) {
if (A == null) return 0;
int count = 0;
int len = A[0].length();
for (int i = 0; i < len; i++) {
if(isNoSort(A, i)) count++;
}
return count;
}
public static boolean isNoSort(String[] A, int num) {
char c = A[0].charAt(num);
for (int i = 0; i < A.length;i++) {
if (A[i].charAt(num) < c) return true;
c = A[i].charAt(num);
}
return false;
}
终极版执行结果
优化说明
可以看到经过优化后的算法，执行速度从<font color=#ff0000 size=2>击败64.42%到99.67%再到100%</font>，有一个质的飞跃。重点是这三种方法的核心算法思想都一样，只是略有细节上的区别。
- 进阶版对比普通版
明显可见的区别是，将内存循环遍历判断是否有非升序的逻辑封装成了一个单独的方法，核心逻辑没有任何变化
- 终极版对比进阶版
<font color=#ff0000 size=2>观察细节不难发现有两处明显的变化:</font>
1.外层循环长度变量从放在for循环内部变成变量len移动到循环外部，避免每次for循环都会重复调用length（）方法。
2.排序方法isNoSort里对比逻辑if条件,由两个元素分别调用charAt方法，变成一个元素调用charAt方法，前一个元素的具体char数值由一个临时变量存储，每次循环的时候赋值，这样节省了在循环内部调用charAt方法的开销。
彩蛋
进阶版对比普通版效率上有质的提高，主要是将双重for循环的内存循环拆成了独立的方法，这便是本文的彩蛋，感兴趣可以关注一波博主的微信订阅号，后续会针对文中彩蛋作统一解答_
扫一扫 关注我的微信订阅号
网友评论