955. Delete Columns to Make Sorted II
Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.
Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.
Пример:
Input: strs = ["ca","bb","ac"]
Output: 1
C# решение
сопоставлено/оригиналpublic class Solution {
public int MinDeletionSize(string[] strs) {
int n = strs.Length;
int m = strs[0].Length;
bool[] deleteCount = new bool[m];
bool IsSorted() {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
if (strs[i][j] > strs[i + 1][j]) return false;
if (strs[i][j] < strs[i + 1][j]) break;
}
}
return true;
}
while (!IsSorted()) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
for (int i = 0; i < n - 1; i++) {
if (strs[i][j] > strs[i + 1][j]) {
deleteCount[j] = true;
break;
}
}
if (deleteCount[j]) break;
}
}
int count = 0;
foreach (bool del in deleteCount) {
if (del) count++;
}
return count;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MinDeletionSize(vector<string> strs) {
int n = strs.size();
int m = strs[0].size();
bool[] deleteCount = new bool[m];
bool IsSorted() {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
if (strs[i][j] > strs[i + 1][j]) return false;
if (strs[i][j] < strs[i + 1][j]) break;
}
}
return true;
}
while (!IsSorted()) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
for (int i = 0; i < n - 1; i++) {
if (strs[i][j] > strs[i + 1][j]) {
deleteCount[j] = true;
break;
}
}
if (deleteCount[j]) break;
}
}
int count = 0;
foreach (bool del in deleteCount) {
if (del) count++;
}
return count;
}
}Java решение
сопоставлено/оригиналclass Solution {
public int minDeletionSize(String[] strs) {
int n = strs.length;
int m = strs[0].length();
boolean[] deleteCount = new boolean[m];
while (!isSorted(strs, deleteCount)) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
for (int i = 0; i < n - 1; i++) {
if (strs[i].charAt(j) > strs[i + 1].charAt(j)) {
deleteCount[j] = true;
break;
}
}
if (deleteCount[j]) break;
}
}
int count = 0;
for (boolean del : deleteCount) {
if (del) count++;
}
return count;
}
private boolean isSorted(String[] strs, boolean[] deleteCount) {
int n = strs.length;
int m = deleteCount.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
if (strs[i].charAt(j) > strs[i + 1].charAt(j)) return false;
if (strs[i].charAt(j) < strs[i + 1].charAt(j)) break;
}
}
return true;
}
}JavaScript решение
сопоставлено/оригиналvar minDeletionSize = function(strs) {
const n = strs.length;
const m = strs[0].length;
const deleteCount = new Array(m).fill(false);
const isSorted = () => {
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < m; j++) {
if (deleteCount[j]) continue;
if (strs[i][j] > strs[i + 1][j]) return false;
if (strs[i][j] < strs[i + 1][j]) break;
}
}
return true;
};
while (!isSorted()) {
for (let j = 0; j < m; j++) {
if (deleteCount[j]) continue;
for (let i = 0; i < n - 1; i++) {
if (strs[i][j] > strs[i + 1][j]) {
deleteCount[j] = true;
break;
}
}
if (deleteCount[j]) break;
}
}
return deleteCount.filter(Boolean).length;
};Python решение
сопоставлено/оригиналdef minDeletionSize(strs):
n = len(strs)
m = len(strs[0])
delete_count = [False] * m
def is_sorted():
for i in range(n - 1):
for j in range(m):
if delete_count[j]:
continue
if strs[i][j] > strs[i + 1][j]:
return False
if strs[i][j] < strs[i + 1][j]:
break
return True
while not is_sorted():
for j in range(m):
if delete_count[j]:
continue
for i in range(n - 1):
if strs[i][j] > strs[i + 1][j]:
delete_count[j] = True
break
if delete_count[j]:
break
return sum(delete_count)Go решение
сопоставлено/оригиналpackage main
func minDeletionSize(strs []string) int {
n := len(strs)
m := len(strs[0])
deleteCount := make([]bool, m)
isSorted := func() bool {
for i := 0; i < n-1; i++ {
for j := 0; j < m; j++ {
if deleteCount[j] {
continue
}
if strs[i][j] > strs[i+1][j] {
return false
}
if strs[i][j] < strs[i+1][j] {
break
}
}
}
return true
}
for !isSorted() {
for j := 0; j < m; j++ {
if deleteCount[j] {
continue
}
for i := 0; i < n-1; i++ {
if strs[i][j] > strs[i+1][j] {
deleteCount[j] = true
break
}
}
if deleteCount[j] {
break
}
}
}
count := 0
for _, del := range deleteCount {
if del {
count++
}
}
return count
}Algorithm
Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.
Итеративно проверить каждую пару соседних строк для всех столбцов.
Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления.
Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.