剑指 Offer 60. n个骰子的点数

题目

代码

方法一：迭代解法

class Solution {
    
public:
    vector<double> dicesProbability(int n) {
    
        //动态规划
        int min = n, max = n * 6;
        double dp[n + 1][max + 1];
        //The number of resulting arrays has n*5-1个
        vector<double> res(n * 5 + 1);
        //base case 
        for(int j = 1; j <= 6; j++) {
    
            dp[1][j] = 1 / 6.0;
        }
        //状态转移
        for(int i = 2; i <= n;i++) {
    
            for(int j = i; j <= i * 6 ;j++) {
    
                for(int k = 1; k <= 6; k++) {
    
                    if(j - k > 0) {
    
                        //通过i-1dice tossed pointsj-k
                        dp[i][j] = dp[i][j] + dp[i - 1][j - k]/6;
                    }else {
    
                        break;
                    }
                }
            }
        }
        for(int i = 0;i <= 5*n;i++){
    
            res[i] = dp[n][n+i];
        }
        return res;
    }
};

方法二：递归解法

class Solution {
    
public:
    vector<double> dicesProbability(int n) {
    
        //初始化1An array of probabilities for the dice
        vector<double> dp(6, 1.0 / 6.0);
        for(int i = 2; i <= n; i++) {
    
            //新数组存放骰子的每个总数和出现的概率
            //骰子总数为i时,骰子可能出现的点数i~6i,长度6i-i+1
            vector<double> temp(5 * i + 1, 0);
            //The number of traversing dice is i-1的概率数组,Calculate the number of diceiprobability of time points
            for(int j = 0; j < dp.size(); j++) {
    
                for(int k = 0; k < 6; k++) {
    
                    temp[j + k] = temp[j + k] + dp[j] / 6.0;
                }
            }
            骰子总数为i的数组赋值骰子总数为i-1的数组
            dp = temp;
        }
        return dp;
    }
};

剑指 Offer 61. 扑克牌中的顺子

题目

代码

The first thing to understand about the second data use case is that big or small kings can substitute for any hand.
再遍历数组,Find the maximum and minimum values ​​of an array,Except for the big king0之外,There cannot be equal numbers in the array,如果有则返回false,If the maximum and minimum values ​​differ by more than 5也返回false.

class Solution {
    
public:
    bool isStraight(vector<int>& nums) {
    
        //Note that big and small kings can substitute for any card
        int max = 0, min = 14;
        set<int>rep;
        for(int i = 0; i < 5; i++) {
    
            if(nums[i] == 0) {
    
                continue;
            }
            max = max > nums[i] ? max : nums[i];
            min = min < nums[i] ? min : nums[i];
            if(rep.find(nums[i]) != rep.end()) {
    
                return false;
            }
            rep.insert(nums[i]);

        }
        return max - min < 5;
    }
};

剑指 Offer 62. 圆圈中最后剩下的数字

题目

I thought it would be the same“CCF201712-2 游戏”The same principle applies to this topic,But if you look closely, it's different.The question is after each elimination,重新从0start counting tomnumber to eliminate it,The latter reports have been increasing,遇到kMultiples or single digits of k则淘汰.

代码

本题是著名的 “约瑟夫环” 问题,可使用 动态规划 解决.
长度为 n 的序列会先删除第 m % n 个元素,然后剩下一个长度为 n - 1 的序列.那么,我们可以求解 f(n - 1, m)

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

剑指 Offer 63. 股票的最大利润

题目

代码

法一：
双层for循环遍历

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        //动态规划
        int n = prices.size();
        int maxvalue = 0;
        int sell = 0;
        //Looking for a buy on the outside
        for(int i = 0; i < n; i++){
    
            //Looking for sale inside
            sell = prices[i];
            for(int j = i + 1; j < n; j++) {
    
               sell = max(sell, prices[j]);
            }
             maxvalue = max(maxvalue, sell - prices[i]);
        }
        return maxvalue;
        
    }
};

法二：
动态规划（未压缩）

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int n = prices.size();
        if(n == 0) {
    
            return 0;
        }
        //dp[i][j],i表示天数,jIndicates the current holding state,0表示未持有,1表示持有
        vector<vector<int>>dp(n, vector<int>(2));
        //base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        //状态转移
        for(int i = 1; i < n; i++) {
    
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(-prices[i], dp[i - 1][1]);
        }
        return dp[n - 1][0];
    }
};

法三：
Compressed dynamic programming

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int n = prices.size();
        if(n == 0) {
    
            return 0;
        }
        //base case
        int dp_i_0 = 0, dp_i_1 = -prices[0];
        //状态转移
        for(int i = 1; i < n; i++) {
    
            // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
            // dp[i][1] = max(dp[i-1][1], -prices[i])
            dp_i_1 = max(-prices[i], dp_i_1);
        }
        return dp_i_0;
    }
};