761. Special Binary String

LeetCode original: C# #bit-manipulation #csharp #graph #leetcode #prefix-sum #recursion #sort #string #tree

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

: hard

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная cadena s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. return лексикоgrafoически наибольшую результирующую строку, возможную после Applications указанных операций над строкой.

Ejemplo:

Input: s = "11011000"

Output: "11100100"

C# solución

coincidente/original

using System;
using System.Collections.Generic;
public class Solution {
    public string MakeLargestSpecial(string s) {
        int count = 0, i = 0;
        List<string> substrs = new List<string>();
        for (int j = 0; j < s.Length; j++) {
            count += s[j] == '1' ? 1 : -1;
            if (count == 0) {
                substrs.Add("1" + MakeLargestSpecial(s.Substring(i + 1, j - i - 1)) + "0");
                i = j + 1;
            }
        }
        substrs.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
        return string.Join("", substrs);
    }
}

C++ solución

borrador automático, revisar antes de enviar

#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 string MakeLargestSpecial(string s) {
        int count = 0, i = 0;
        List<string> substrs = new List<string>();
        for (int j = 0; j < s.size(); j++) {
            count += s[j] == '1' ? 1 : -1;
            if (count == 0) {
                substrs.push_back("1" + MakeLargestSpecial(s.Substring(i + 1, j - i - 1)) + "0");
                i = j + 1;
            }
        }
        substrs.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
        return string.Join("", substrs);
    }
}

Java solución

coincidente/original

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public String makeLargestSpecial(String s) {
        int count = 0, i = 0;
        List<String> substrs = new ArrayList<>();
        for (int j = 0; j < s.length(); j++) {
            count += s.charAt(j) == '1' ? 1 : -1;
            if (count == 0) {
                substrs.add("1" + makeLargestSpecial(s.substring(i + 1, j)) + "0");
                i = j + 1;
            }
        }
        Collections.sort(substrs, Collections.reverseOrder());
        return String.join("", substrs);
    }

Python solución

coincidente/original

def makeLargestSpecial(s):
    count = i = 0
    substrs = []
    for j, char in enumerate(s):
        count += 1 if char == '1' else -1
        if count == 0:
            substrs.append('1' + makeLargestSpecial(s[i + 1:j]) + '0')
            i = j + 1

Go solución

coincidente/original

package main

import (
    "sort"
    "strings"
)

func makeLargestSpecial(s string) string {
    count, i := 0, 0
    substrs := []string{}
    for j := 0; j < len(s); j++ {
        if s[j] == '1' {
            count++
        } else {
            count--
        }
        if count == 0 {
            substr := "1" + makeLargestSpecial(s[i+1:j]) + "0"
            substrs = append(substrs, substr)
            i = j + 1
        }
    }
    sort.Sort(sort.Reverse(sort.StringSlice(substrs)))
    return strings.Join(substrs, "")
}

Algorithm

Определите, что специальная двоичная cadena можно разбить на несколько специальных подстрок.

Рекурсивно примените к каждой подстроке этот Algoritmo, чтобы find лексикоgrafoически наибольшую строку.

Сортируйте полученные подстроки в лексикоgrafoическом порядке по убыванию и объединяйте их.

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.