Showing posts with label Random. Show all posts
Showing posts with label Random. Show all posts

Thursday, October 12, 2017

384. Shuffle an Array

https://leetcode.com/problems/shuffle-an-array/description/
class Solution {
    vector<int> nums;
public:
    Solution(vector<int> nums) {
        this->nums = nums;
    }
 
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return nums;
    }
 
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int N = nums.size();
        vector<int> res(nums);
        for(int i=0; i<N; i++) {
            int j = rand() % (N-i);
            swap(res[i], res[i+j]);
        }
        return res;
    }
};

382. Linked List Random Node

https://leetcode.com/problems/linked-list-random-node/description/
Solution 1. Reservoir sampling
class Solution {
    ListNode* head;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
    }
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* node = head;
        int res = node->val;
        node = node->next;
        int k=1, kpi=2;
        while(node) {
            if(rand()%kpi == 0) res = node->val;
            kpi++;
            node = node->next;
        }
        return res;
    }
};
Solution 2.
class Solution {
    int N;
    int len = 1000;
    ListNode* hd;
    vector<ListNode*> vl;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        hd = head;
        ListNode* p=head;
        N = 0;
        while(p) {
            if(N%len == 0) vl.push_back(p);
            N++;
            p = p->next;
        }
    }
    /** Returns a random node's value. */
    int getRandom() {
        random_device rd;
        uniform_int_distribution<int> dist(0, N-1);
        int n = dist(rd);
        ListNode*p = vl[n/len];
        n = n%len;
        while(n) {
            p = p->next;
            n--;
        }
        return p->val;
    }
};

Wednesday, October 11, 2017

Random

http://en.cppreference.com/w/cpp/numeric/random/rand
#include <cstdlib>
#include <iostream>
#include <ctime>
 
int main() 
{
    std::srand(std::time(0)); // use current time as seed for random generator
    int random_variable = std::rand();
    std::cout << "Random value on [0 " << RAND_MAX << "]: " 
              << random_variable << '\n';
}


#include <random>
    std::random_device rd;
    std::uniform_int_distribution<int> dist(0, 9);
    for (int n = 0; n < 10; ++n) {
        std::cout<<dist(rd)<<"\n";

http://en.cppreference.com/w/cpp/header/random

http://en.cppreference.com/w/cpp/numeric/random/random_device

http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution