Cursos Empresas Blog Live Conf Eventos Precios

0:0016:04

Programando Reorganize String con Python

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Clase 31 de 34

Clase 31 / 34

Miguel Angel Reyes Moreno

Hace 2 años

Comparto una solución distinta: import heapq

class Solution:

def reorganizeString(self, s: str) -> str:

frequency_characters = {}

s_len_half = (len(s) + 1) // 2

for char in s:

frequency_characters[char] = frequency_characters.get(char, 0) + 1

if frequency_characters[char] > s_len_half:

return ""

max_heap = []

for char, freq in frequency_characters.items():

heapq.heappush(max_heap, (-freq, char))

result = []

prev_char = None

prev_freq = 0

while max_heap:

freq, char = heapq.heappop(max_heap)

result.append(char)

if prev_freq < 0:

heapq.heappush(max_heap, (prev_freq, prev_char))

prev_char = char

prev_freq = freq + 1

return "".join(result)

Comentarios (10)10 comentarios

Pro Code

Hace 3 años

La solución de la profe solo me ejecutó si cambiaba las líneas 8 y 9 por:

    for caracter  in ocurrenciasPorCaracter:
        colaPrioridad.append((-ocurrenciasPorCaracter[caracter], caracter))

**Lo ejecuté en línea en: **

Código completo:

import heapq
from collections import defaultdict


def reorganizeString(S: str) -> str:
    ocurrenciasPorCaracter = defaultdict(int)
    for caracter in S:
        ocurrenciasPorCaracter[caracter] += 1
        if ocurrenciasPorCaracter[caracter] > (len(S)+1) / 2: return ""
    colaPrioridad = []
    for caracter  in ocurrenciasPorCaracter:
        colaPrioridad.append((-ocurrenciasPorCaracter[caracter], caracter))
    heapq.heapify(colaPrioridad)

    stringOrdenada = []
    while 2 <= len(colaPrioridad):
        ocurrencia1, caracter1 = heapq.heappop(colaPrioridad)
        ocurrencia2, caracter2 = heapq.heappop(colaPrioridad)
        stringOrdenada.append(caracter1)
        stringOrdenada.append(caracter2)
        if ocurrencia1 + 1: heapq.heappush(colaPrioridad, (ocurrencia1 +1, caracter1))
        if ocurrencia2 + 1: heapq.heappush(colaPrioridad, (ocurrencia2 +1, caracter2))

    if colaPrioridad: return "".join(stringOrdenada) + colaPrioridad[0][1]
    return "".join(stringOrdenada)
    
    
print(reorganizeString("aaaii"))

Ejecutar python 3 online: https://www.tutorialspoint.com/execute_numpy_online.php

Nicolas Guillen

Este recurso me ayudó mucho porque no lograba entener por qué la heap es tan importante y es básicamente un binary tree, entonces hay formas de insertar un nodo de forma que el árbol sigue ordenado sin necesidad de usar un sorting algorithm para re organizar la lista. Entonces cuál es el punto?

Sorting algorithms no son tan rápidos. La heap nos ayuda a evitarlos básicamente.

Creo que esa es la forma más simple de explicarlo pero por favor comenten si hace falta algo.

REYNALDO FABIAN NORIEGA ZAMBRANO

Hace 10 meses

John Eduard Meneses González

Hace un año

My solution!!

Santiago Amaya

Yojan Antonio Pardo Zabala

Hans Arias

Luis Antonio Ibarra Salgado

Luis Angel Armenta Delgadillo

Hace 4 años

A mí me quedo mi solución así. Me inventé una cola medio rara con la lista en_espera, pero creo que el objetivo era usar colas de prioridad... x3 😂😅

from typing import List

def reorganize_string(s: str) -> str:
  resultado: str = s[0]
  en_espera: List[str] = []
  
  for c in s[1:]:
    if resultado[-1] == c:
      en_espera.append(c)
    else:
      if len(en_espera) != 0:
        resultado += c
        resultado += en_espera.pop(0)
      else:
        resultado += c
  
  if len(en_espera) != 0:
    return ''
  else:
    return resultado

Emilio Sala

está muy bien la idea! pero para casos especiales no daría la respuesta esperada. como por ejemplo "caa" el caracter con más apariciones debería de estar siempre al inicio para aprovechar los inicios y finales.

Programando Reorganize String con Python

Progreso del curso

Introducción

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos