1716.计算力扣银行的钱

链接：1716.计算力扣银行的钱
难度：Easy
标签：数学
简介：给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。

题解 1 - cpp

• 编辑时间：2022-01-16
• 执行用时：16ms
• 内存消耗：16.3MB
• 编程语言：cpp
• 解法介绍：随机数。

class Solution {
   public:
    vector<int> arr;
    Solution(ListNode* head) {
        srand(time(0));
        ListNode* p = head;
        while (p) {
            arr.push_back(p->val);
            p = p->next;
        }
    }
    int getRandom() { return arr[rand() % arr.size()]; }
};

题解 2 - cpp

• 编辑时间：2022-01-16
• 执行用时：24ms
• 内存消耗：16.2MB
• 编程语言：cpp
• 解法介绍：水塘抽样。

class Solution {
   public:
    ListNode *node;
    Solution(ListNode *head) {
        srand(time(0));
        node = head;
    }
    int getRandom() {
        int ans, i = 1;
        for (ListNode *p = node; p; p = p->next, i++) {
            if (rand() % i == 0) ans = p->val;
        }
        return ans;
    }
};