資料結構
網路
關係資料庫管理系統 (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
廣告