2020-07-05 刷题3 模拟

60 n个骰子的点数

动态规划，dp[n,s]表示n个骰子出现s点的次数，dp[n,s]=dp[n-1,s-1]+...+dp[n-1,s-6]，这只取决于n-1个骰子的点数。

class Solution {
public:
    vector<double> twoSum(int n) {
        double dp[12][70] = {0};
        dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = dp[1][5] = dp[1][6] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = i; j <= 6 * i; j++){
                // dp[n][s] = dp[n-1][1]+...
                for(int k = 1; k <= 6; k++){
                    if(j > k)
                        dp[i][j] += dp[i-1][j-k];
                }
            }
        }
        double total_cnt = pow(6, n);
        vector<double> probs;
        for(int i = n; i <= 6 * n; i++){
            dp[n][i] /= total_cnt;
            probs.push_back(dp[n][i]);
        }
        return probs;
    }
};

61 扑克牌中的顺子

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        // 统计0的个数
        int zero_cnt = 0, i = 0;
        while(i < 5 && nums[i]==0){
            zero_cnt++;
            i++;
        }
        if(i >= 4)
            return true;
        // 统计空的个数
        int cur = nums[i], margin_cnt = 0;
        i++;
        while(i < 5){
            // 有相同的牌，不可能是顺子
            if(nums[i] == cur)
                return false;;
            margin_cnt += nums[i] - cur - 1;
            cur = nums[i];
            i++;
        }
        if(margin_cnt > zero_cnt)
            return false;
        return true;
    }
};

63 圆圈中最后的数字

模拟解法，用环链表实现：

class Solution {
public:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int v): val(v), next(nullptr){}
    };
    int lastRemaining(int n, int m) {
        // construct list
        ListNode *cur = new ListNode(0);
        ListNode *head = cur;
        for(int i = 1; i < n; i++){
            cur -> next = new ListNode(i);
            cur = cur -> next;
        }
        cur -> next = head;
        ListNode *pre = cur;
        cur = cur -> next;
        // begin
        while(cur != cur -> next){
            for(int i = 1; i < m; i++){
                pre = cur;
                cur = cur -> next;
            }
            pre -> next = cur -> next;
            delete cur;
            cur = pre -> next;
        }
        return cur -> val;
    }
};

这个解法提交后过了26个case，然后就超时了，因此需要进一步优化时间。
用f(n, m)表示一共n个数，每次删除第m个数，最后剩下的数的下标，假设f(n,m)=y，f(n-1,m)=x就表示了一共n-1个数，每次删除第m个数最后剩下的数的下标。
如果n个数时，先删除一次，就剩下了n-1个数，此时，删除的这个数（也就是(m-1)%n）向后数x+1个数，就恰好是y，即：
f(n,m)=[(m-1)%n + x + 1]%n = [(m-1)%n+f(n-1,m)+1]%n
用到的定理：

1. (a + b) % c = ((a % c) + (b % c)% c
2. a % c % c = a % c
   最后化简得到：f(n,m) = (f(n-1,m) + m)% n
   f(1, m) = 0.
   代码：

class Solution {
public:
    int lastRemaining(int n, int m) {
        int last = 0;
        for(int i = 2; i <= n; i++)
            last = (last + m) % i;
        return last;
    }
};

真的是非常的牛皮。