382. Linked List Random Node

LeetCode medium оригинал: C# #array #csharp #design #leetcode #linked-list #medium

LeetCode Static

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

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

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.

int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input

["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]

[[[1, 2, 3]], [], [], [], [], []]

Output

[null, 1, 3, 2, 2, 3]

Explanation

Solution solution = new Solution([1, 2, 3]);

solution.getRandom(); // return 1

solution.getRandom(); // return 3

solution.getRandom(); // return 2

solution.getRandom(); // return 3

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
public class Solution {
    private List<int> range = new List<int>();
    private Random random = new Random();
    public Solution(ListNode head) {
        while (head != null) {
            range.Add(head.val);
            head = head.next;
        }
    }
    public int GetRandom() {
        int pick = random.Next(range.Count);
        return range[pick];
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
public:
    private List<int> range = new List<int>();
    private Random random = new Random();
    public Solution(ListNode head) {
        while (head != null) {
            range.push_back(head.val);
            head = head.next;
        }
    }
    public int GetRandom() {
        int pick = random.Next(range.size());
        return range[pick];
    }
}

Java решение

сопоставлено/оригинал

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private List<Integer> range = new ArrayList<>();
    private Random random = new Random();

    public Solution(ListNode head) {
        while (head != null) {
            range.add(head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        int pick = random.nextInt(range.size());
        return range.get(pick);
    }
}

JavaScript решение

сопоставлено/оригинал

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class Solution {
  constructor(head) {
    this.range = [];
    while (head !== null) {
      this.range.push(head.val);
      head = head.next;
    }
  }

  getRandom() {
    const pick = Math.floor(Math.random() * this.range.length);
    return this.range[pick];
  }
}

Python решение

сопоставлено/оригинал

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:

    def __init__(self, head: ListNode):
        self.range = []
        while head:
            self.range.append(head.val)
            head = head.next

    def getRandom(self) -> int:
        pick = int(random.random() * len(self.range))
        return self.range[pick]

Go решение

сопоставлено/оригинал

package main

import (
  "math/rand"
  "time"
)

type ListNode struct {
  Val  int
  Next *ListNode
}

type Solution struct {
  rangeVals []int
}

func Constructor(head *ListNode) Solution {
  var rangeVals []int
  for head != nil {
    rangeVals = append(rangeVals, head.Val)
    head = head.Next
  }
  rand.Seed(time.Now().UnixNano())
  return Solution{rangeVals: rangeVals}
}

func (this *Solution) GetRandom() int {
  pick := rand.Intn(len(this.rangeVals))
  return this.rangeVals[pick]
}

Algorithm

Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

Реализуйте функцию getRandom(), которая будет выбирать случайный элемент из массива, созданного на первом этапе.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.