Início / user-19979948

clearcut3000's questions

Martin Hope
clearcut3000
Asked: 2025-04-15 14:59:45 +0800 CST
  • 7

Estou tentando resolver o seguinte problema algorítmico:

Todos os dias, Bob vai trabalhar e realiza uma das 26 tarefas possíveis. As tarefas são codificadas com as letras do alfabeto inglês de A a Z. Às vezes, Bob realiza tarefas atribuídas por seu chefe e, às vezes, pode escolher qual das 26 tarefas possíveis realizará ele mesmo. Esses dias são marcados com o símbolo !. O chefe definiu o plano de trabalho de Bob para os próximos N dias. Bob realmente não gosta de realizar a mesma tarefa por vários dias seguidos e, para mostrar ao chefe como está entediado, decidiu contar o número de maneiras de escolher um segmento contínuo de pelo menos dois dias durante o qual realizará a mesma tarefa todos os dias.

Ou seja, Bob considera todos os segmentos possíveis do dia L ao dia R, onde L < R, e se ele puder escolher seu trabalho de forma que as tarefas em todos os dias desse segmento sejam as mesmas, então ele considera esse segmento chato.

Ajude Bob a determinar o número de segmentos chatos no plano de trabalho para os próximos N dias enquanto ele estiver entediado.

Formato de entrada

É inserida uma única linha, que é uma sequência de caracteres composta por letras maiúsculas do inglês e o símbolo ! — o plano de trabalho para os próximos N (1 ≤ N ≤ 1000000) dias.

Formato de saída

Produza um único número — o número de segmentos de perfuração no plano.

Exemplo 1

Entrada:a!b!c

Saída: 5

Exemplo 2

Entrada:a!

Saída: 1

Notas

Todos os segmentos possíveis no primeiro exemplo estão entre |e|

|a!|b!c
a|!b|!c
a|!b!|c
a!|b!|c
a!b|!c|

Formalizei a tarefa da seguinte forma:

Problema

Dado um plano de trabalho para N dias como uma sequência composta por letras maiúsculas (de 'a' a 'z') e pontos de exclamação ('!'), conte o número de segmentos contínuos de pelo menos dois dias (ou seja, do dia L ao dia R, onde 1 ≤ L < R ≤ N) de forma que seja possível para Bob realizar a mesma tarefa em todos os dias dentro do segmento. Um segmento é considerado "chato" se:

  • Todos os caracteres dentro do segmento são o mesmo caractere não-'!'.

  • O segmento contém pelo menos um ponto de exclamação ('!').

Entrada

Uma única sequência representando o plano de trabalho para N dias.

A sequência consistirá apenas de letras maiúsculas em inglês (de 'a' a 'z') e pontos de exclamação ('!').

O comprimento da string N estará entre 1 e 1.000.000, inclusive (1≤N≤10 6 ).

Saída

Um único inteiro representando o número total de segmentos "chatos" no plano de trabalho fornecido.

Meu Código

func solve() {
  guard let plan = readLine() else { return }
  let n = plan.count
  let planArray = Array(plan)
  var boringSegmentCount = 0
  for i in 0..<n {
    var nonWildcards = Set<Character>()
    for j in i..<n {
      if planArray[j] != "!" {
        nonWildcards.insert(planArray[j])
      }
      if j > i && nonWildcards.count <= 1 {
        boringSegmentCount += 1
      }
    }
  }
  print(boringSegmentCount)
  
}

O código Swift fornecido tem como objetivo resolver o problema iterando por todos os segmentos contínuos possíveis da string de entrada plan.

Ele usa loops aninhados para iterar por todos os segmentos contínuos possíveis da string:

  • O loop externo ( i) determina o índice inicial do segmento.
  • O loop interno ( j) determina o índice final do segmento.

Para cada segmento (do índice iaté j):

  • Ele cria uma Setchamada nonWildcardspara armazenar caracteres únicos que não são '!'.
  • Ele itera pelos caracteres dentro do segmento atual.
  • Se um caractere não for '!', ele o adiciona ao nonWildcardsconjunto.
  • Ele verifica se o comprimento do segmento é maior que 1 ( j > i) e se o número de caracteres não curinga exclusivos no segmento é no máximo 1 ( nonWildcards.count <= 1).
  • Se ambas as condições forem verdadeiras, ele incrementa o boringSegmentCount.

O principal problema com esse algoritmo é sua complexidade de tempo quadrática, O(n²), portanto, para valores grandes de n(até 1.000.000, conforme declarado no problema), esse algoritmo pode ser muito lento e levar a um erro de limite de tempo excedido.

Minha pergunta

É possível propor um algoritmo com assintóticas mais baixas para esta tarefa? Suponho que seja possível resolver este problema em tempo linear, mas, para minha vergonha, ainda não consegui encontrar uma lógica adequada.

arrays