数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++实现删除列以使数组排序 III
假设我们有一个包含N个字符串的数组A。每个字符串都由小写字母组成，并且长度相同。现在，我们可以选择任意一组删除索引，对于每个字符串，我们将删除这些索引中的所有字符。现在考虑我们已经选择了一组删除索引D，使得删除后，最终数组的每个元素都按字典顺序排列。
为了清楚起见，A[0]按字典顺序排列（因此A[0][0] <= A[0][1] <= ... <= A[0][n - 1]），A[1]按字典顺序排列（即A[1][0] <= A[1][1] <= ... <= A[1][n - 1]），依此类推。（这里n是字符串的大小）。我们必须找到D的最小可能大小。
因此，如果输入类似于["cbcdb","ccbxc"]，则输出将为3
为了解决这个问题，我们将遵循以下步骤：
ret := 0
n := A的大小
m := A[0]的大小
定义一个大小为(m + 1)的数组lis，并将其填充为1
for i := 0 to m-1 do −
for j := 0 to i-1 do −
ok := true
for k := 0 to n-1 do −
if A[k, j] > A[k, i], then
ok := false
退出循环
if ok == true, then −
lis[i] := max(lis[j] + 1, lis[i])
ret := max(ret, lis[i])
if ret == 0, then −
return m - 1
return m - ret
让我们看看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDeletionSize(vector<string>& A){
int ret = 0;
int n = A.size();
int m = A[0].size();
vector<int> lis(m + 1, 1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < i; j++) {
bool ok = true;
for (int k = 0; k < n; k++) {
if (A[k][j] > A[k][i]) {
ok = false;
break;
}
}
if (ok) {
lis[i] = max(lis[j] + 1, lis[i]);
ret = max(ret, lis[i]);
}
}
}
if (ret == 0)
return m - 1;
return m - ret;
}
};
main(){
Solution ob;
vector<string> v = {"cbcdb","ccbxc"};
cout << (ob.minDeletionSize(v));
}输入
{"cbcdb","ccbxc"}输出
3
更新于：2020年6月4日
浏览量：191
广告