Класс решения, который хранит все значения узлов в массиве и возвращает случайное значение из массива.

Введение

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

Постановка задачи

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

Реализуйте класс Solution:

  • Solution(ListNode head): инициализирует объект заголовком односвязного списка.
  • int getRandom(): случайным образом выбирает узел из списка и возвращает его значение. Все узлы списка должны быть выбраны с равной вероятностью.

Задача требует, чтобы мы возвращали значение случайного узла из односвязного списка. Для этого мы можем сначала сохранить все значения узлов в массиве, а затем вернуть случайное значение из массива.

Решение Объяснение

Класс Solution имеет два метода:

  • constructor(head: ListNode | null): Инициализирует объект с заголовком односвязного списка. В этом методе мы просматриваем связанный список и сохраняем все его значения в массиве this.vals.
  • getRandom(): number: случайным образом выбирает узел из списка и возвращает его значение. Все узлы списка должны быть выбраны с равной вероятностью. В этом методе мы возвращаем случайное значение из массива this.vals, используя метод Math.random().

Давайте посмотрим на код построчно.

class Solution {
    vals: number[];

    constructor(head: ListNode | null) {
        this.vals = [];
        while (head != null) {
            this.vals.push(head.val);
            head = head.next;
        }
    }

    getRandom(): number {
        // Get a random number between 0 and the length of the list
        const rand = Math.floor(Math.random() * this.vals.length);
        // Return the value at the random index
        return this.vals[rand];
    }
}

Линия 1

class Solution {

Ключевое слово class используется для определения класса в TypeScript. Здесь мы определяем класс Solution.

Линия 2

vals: number[];

Свойство vals представляет собой массив для хранения значений связанного списка.

Строки 4–10

constructor(head: ListNode | null) {
        this.vals = [];
        while (head != null) {
            this.vals.push(head.val);
            head = head.next;
        }
    }

Метод constructor используется для инициализации объекта заголовком односвязного списка. В этом методе мы сначала инициализируем массив this.vals. Затем мы проходим по связанному списку, используя цикл while, и помещаем значение каждого узла в массив this.vals.

Строки 12–16

getRandom(): number {
        return this.vals[Math.floor(Math.random() * this.vals.length)];
    }

Метод getRandom случайным образом выбирает узел из списка и возвращает его значение. Все узлы списка должны быть выбраны с равной вероятностью. В этом методе мы возвращаем случайное значение из массива this.vals, используя метод Math.random(). Math.random() возвращает случайное число от 0 (включительно) до 1 (не включая). Мы умножаем это значение на длину массива this.vals, а затем округляем его до ближайшего целого числа методом Math.floor(). Наконец, мы возвращаем значение результирующего индекса массива this.vals.

Последующие вопросы

Задача также задает два дополнительных вопроса:

  • Что делать, если связанный список очень велик и его длина вам неизвестна?
  • Не могли бы вы решить эту проблему эффективно, не используя дополнительное пространство?

Что делать, если связанный список очень велик и его длина вам неизвестна?

Если связанный список очень большой и его длина нам неизвестна, мы не можем хранить все значения узлов в массиве, так как это потребует много памяти. Одним из способов решения этой проблемы является использование метода, называемого отбором проб из резервуара. Резервуарная выборка — это алгоритм, используемый для случайной выборки k элементов из списка без замены, когда длина списка неизвестна или слишком велика для хранения в памяти.

Не могли бы вы решить эту проблему эффективно, не используя дополнительное пространство?

Текущее решение требует дополнительного места для хранения всех значений узлов в массиве. Чтобы решить эту проблему, не занимая дополнительное пространство, мы можем использовать технику под названием Reservoir Sampling. Этот алгоритм позволяет нам случайным образом выбирать k элементов из списка без замены, когда длина списка неизвестна или слишком велика для хранения в памяти.

Рекомендации