955. Delete Columns to Make Sorted II

LeetCode medium original: C# #array #csharp #graph #leetcode #medium #sort #string

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

Вам дан array из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

НаEsempio, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный array после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный array имеет elementы в лексикоgrafoическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). returns минимально возможное значение answer.length.

Esempio:

Input: strs = ["ca","bb","ac"]

Output: 1

C# soluzione

abbinato/originale

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++ soluzione

bozza automatica, rivedere prima dell'invio

#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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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.

Создать array delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

Итеративно проверить каждую пару соседних строк для всех столбцов.

Если для данной пары строк обнаружено нарушение лексикоgrafoического порядка, отметить соответствующий столбец для удаления.

Повторять процесс до тех пор, пока array строк не станет лексикоgrafoически отсортированным.

Вернуть количество удаленных столбцов.

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.