Сенат Dota2

Средняя
medium , string
16 February 2024

Описание задачи #

В мире Dota2 существует 2 партии Radiant и Dire. Для того чтобы внести изменение в игру Dota2 необходимо провести голосование сената, каждый член которого принадлежит одной из двух партий.

Голосование идет раундами, в каждом раунде по очереди опрашивается каждый сенатор. Сенатор может выполнить одно из двух действий:

Напишите функцию, которая будет рассчитывать результаты голосования сената.

Входные данные

Строка, описывающая последовательность голосующих сенаторов и их принадлежность к партиям.

Выходные данные

Строка с названием победившей партии (Radiant или Dire).

Ограничения #

Примеры #

  • Входные данные: RD

    Ответ: Radiant

    Пояснение: В первом раунде первый сенатор из партии Radiant лишает права голоса сенатора из Dire. На этом раунд заканчивается, так как не осталось сенаторов с правом голоса. Во втором раунде сенатор из партии Radiant объявляет победу своей партии.

  • Входные данные: RDD

    Ответ: Dire

    Пояснение: В первом раунде сентаор из Radiant лишает одного из сенаторов Dire права голоса. Второй сенатор из Dire лишает права голоса сенатора из Radiant и в следующем раунде объявляет победу своей партии.

Решение #

На первый взгляд задача может решиться простым сравнением количества сенаторов из каждой партии. На самом деле такое решение будет не верно, так как не учитывает порядок голосования.

Давайте рассмотрим на простом примере: RDRDRDRDRDDD. В данном примере 5 сенаторов в партии Radiant и 7 в Dire. Давайте разберем по шагам данный пример (символом _ будем отмечать сенаторов лишенных права голоса).

Таким образом, несмотря на количественное преимущество партии Dire, победу одержала Radiant.

На самом деле, в решении данной задачи нам поможет одна из базовых структур данных - очередь. В качестве очереди мы будем использовать массив. В данном случае можно забыть про то, что голосование проходит по раундам и представить весь процесс как непрерывный цикл.

Изначально мы помещаем всех сенаторов в очередь в соответствии с их порядком и подсчитываем общее количество представителей каждой из партий.

Далее, пока в очереди присутствуют представители обеих партий мы запускаем наш непрерывный цикл.

  • package main

func predictPartyVictory(senate string) string {
	rCount, dCount := 0, 0
	queue := make([]byte, 0, 2*len(senate))
	for i := 0; i < len(senate); i++ {
		if senate[i] == 'R' {
			rCount++
		} else {
			dCount++
		}

		queue = append(queue, senate[i])
	}

	for rCount > 0 && dCount > 0 {
		firstElem := queue[0]
		killCount := 1
		queue = append(queue, firstElem)
		queue = queue[1:]

		for killCount > 0 && rCount > 0 && dCount > 0 {
			if queue[0] == firstElem {
				queue = append(queue, queue[0])
				queue = queue[1:]
				killCount++
			} else {
				if queue[0] == 'R' {
					rCount--
				} else {
					dCount--
				}
				killCount--
				queue = queue[1:]
			}
		}
	}

	if rCount > 0 {
		return "Radiant"
	}

	return "Dire"
}

  • const moveFirst = (arr: string[]) => {
	const first = arr.shift()

	if (first) {
		arr.push(first)
	}
}

export const predictPartyVictory = (senate: string): string => {
	let rCount = 0
	let dCount = 0

	const queue: string[] = []

	for (let i = 0; i < senate.length; i++) {
		if (senate[i] === 'R') {
			rCount++
		} else {
			dCount++
		}

		queue.push(senate[i])
	}

	while (rCount > 0 && dCount > 0) {
		let firstElem = queue[0]
		let killCount = 1

		moveFirst(queue)

		while (killCount > 0 && rCount > 0 && dCount > 0) {
			if (queue[0] == firstElem) {
				moveFirst(queue)
				killCount++
			} else {
				if (queue[0] == 'R') {
					rCount--
				} else {
					dCount--
				}
				killCount--
				queue.shift()
			}
		}
	}

	if (rCount > 0) {
		return "Radiant"
	}

	return "Dire"
}

Оценка сложности #

По времени

Сложность O(n), где n — длина строки.

По памяти

Сложность O(n), так как нам пришлось создать очередь для хранения данных.

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >