剑指offer 60与61


剑指offer 60与61

1.面试题60. n个骰子的点数

method1:递归

class Solution {
public:
    vector<double> twoSum(int n) {
        //f(n,s) = f(n-1,s-1) + ... f(n-6,s-6);
        vector<double> res;
        for(int i=n;i<=n*6;i++) {
            res.push_back(recursion(n,i));
        }
        return res;
    }
    double recursion(int n,int s) {
        if(n==0 || s<0) return 0;
        if(n==1 && s>0 && s<7) return 1/6.0;
        double res = 0;
        for(int i=1;i<=6;i++) {
            res += recursion(n-1,s-i);
        }
        return res/6.0;
    }
};

method2:记忆化搜索

class Solution {
private:
    vector<vector<double>> memo;
public:
    vector<double> twoSum(int n) {
        //f(n,s) = f(n-1,s-1) + ... f(n-6,s-6);
        memo = vector<vector<double>>(n+1,vector<double>(n*6+1,-1.0));
        vector<double> res;
        for(int i=n;i<=n*6;i++) {
            res.push_back(recursion(n,i));
        }
        return res;
    }
    double recursion(int n,int s) {
        if(n==0 || s<0) return 0;

        if(memo[n][s]!=-1.0) return memo[n][s]; 
        if(n==1 && s>0 && s<7) {
            memo[n][s] = 1/6.0;
            return memo[n][s];
        }

        double res = 0;
        for(int i=1;i<=6;i++) {
            res += recursion(n-1,s-i);
        }
        memo[n][s] = res / 6.0;
        return memo[n][s];
    }
};

method3:动态规划法

class Solution {
private:
    vector<vector<double>> dp;
public:
    vector<double> twoSum(int n) {
        // f(n,s) = f(n-1,s-1) + ... f(n-6,s-6);
        dp = vector<vector<double>>(n+1,vector<double>(n*6+1,0));
        vector<double> res;
        double sum=0;

        // 求概率的分母,表示总可能
        int all = pow(6,n);

        // dp[i][j] 表示有1个筛子的时候出现的可能dp[1][j]
        // i=1,每个结果都是一种
        for(int i=1;i<=6;i++) {
            dp[1][i] = 1;

        }
        // 现在要求n个骰子的时候,从2个骰子到n个骰子依次填充
        for(int i=2;i<=n;i++) {
            // 有多少个骰子,可能结果就是[i,6*i]
            for(int s=i;s<=i*6;s++) {
                // 计算每种可能出现的次数
                // . . . (3,4) 1 1 2 投掷完 i 枚骰子后点数 j 出现的次数,可以由投掷完 i-1 枚骰子后,对应点数 j-1出现的次数与...等之和转化过来。
                // dp[i][s]=dp[i-1][s-1]+dp[i-2][s-2]+dp[i-6][s-6]
                for(int cur=1;cur<=6;cur++) {
                    // s-cur 表示每一枚骰子点数,范围为[1,6],所以必须保证其从1开始
                    if(s-cur<=0) break;
                    dp[i][s] += dp[i-1][s-cur];
                }
            }
        }

        // 对[n,6*n]种可能求概率
        for(int i=n;i<=6*n;i++) {
            res.push_back(dp[n][i]*1.0 / all); 
        }

        return res;
    }
};

2.面试题61. 扑克牌中的顺子

method1:排序。

首先对拿到手的牌从小到大排序,统计大小王的个数。对于不是大小王的牌,看是否和下一位的牌连续((1)如果和下一张牌相等 return false;(2)如果和下一张牌连续则continue;如果不相等且不连续,统计中间空缺的牌的个数。最后将空缺的牌(lose)的个数和大小王(king)的个数比较:king>=lose return ture;否则 return false;

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        if(nums.size()==0) return true;
        // 大王.小王.1 2 3 4 5 ... 10 J Q K
        // 统计大王与小王的个数
        // 先排序
        sort(nums.begin(),nums.end());
        int i = 0;
        // 统计大小王的个数
        while(i<nums.size() && nums[i]==0) {
            i++;
        }
        int gap = 0;
        // 开始遍历,判断当前元素是否跟后一个连续,不连续求出间隔多少个
        for(int j=i;j<nums.size()-1;j++) {
            if(nums[j]==nums[j+1]) return false;
            if(nums[j]+1==nums[j+1]) continue;
            int tmp = nums[j+1] - nums[j] - 1;
            gap += tmp;
        }
        return gap<=i ? true : false;
    }
};

method2:不排序,找出最大值与最小值即可,再判断一下中间元素是否重复。

例如:[0,0,1,2,6] 不连续,[0,0,1,2,5]连续。

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        unordered_map<int,int> m;
        if(nums.size()==0) return true;
        int max_res = INT_MIN;
        int min_res = INT_MAX;
        for(auto num : nums) {
            m[num]++;
            if(num == 0) continue;
            if(m[num]>=2) return false;
            max_res = max(max_res,num);
            min_res = min(min_res,num);
        }
        return (max_res - min_res) >=5 ? false : true;
    }
};

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录