Day15 n个骰子的点数 + 剪绳子 + 数组中出现次数超过一

TODO:

1. 重做 n个骰子的点数，仔细理清楚思路
2. 重做剪绳子
3. 理解并记忆摩尔投票法

剑指 Offer 60. n个骰子的点数(中等)

不会做，但是还挺有趣的。
每增加一个骰子，增益1~6。并且一共有n个骰子的时候，总点数的范围为(n，6n)，故设数组大小为6n-n + 1,即5n+1。

class Solution {
public:
    vector<double> dicesProbability(int n) {
        if(n <= 0) return {};
        vector<double> dp(6,1/6.0);
        for(int i = 2; i <= n; i++){
            vector<double> temp(5*i+1,0);
                for(int k = 0; k <dp.size(); k++){
                    for(int j = 0; j < 6; j++ ){
                        temp[j+k] += dp[k]*1/6;
                    
                    }
                }
             dp = temp;
            
        }
        return dp;
    }
};

题解

剑指 Offer 14- I. 剪绳子(中等)

直接放弃并开始看题解，还用上了“算术几何均值不等式”。

方法一 数学的方法

//① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 3，次优为2，最差为1 。
class Solution {
public:
    int cuttingRope(int n) {
        if(n <=3) return n-1;
        int a = n/3, b = n%3;
        if(b == 0) return pow(3,a);
        else if(b == 1) return pow(3,a-1)*4;
        else return pow(3,a)*2;
        
    }
};

方法二 贪心

正常很难想到效率高的纯数学方法，于是又看了贪心实现的题解

class Solution {
public:
    int cuttingRope(int n) {
        /*
        *  三种特殊情况：
        *  1、长度为1时，没法剪，最大乘积为0
        *  2、长度为2时，最大乘积为1 × 1 = 1
        *  3、长度为3时，最大乘积为1 × 2 = 2
        */
        if (n <= 3) return n - 1;
        /*
        *  创建动态规划数组，所有元素初始化为0
        *  dp[i]表示剪长度为i的绳子所能得到的最大乘积，dp[n]表示长度为n的绳子
        *  所以数组的长度要为n+1
        */
        vector<int> dp(n + 1, 0);
        /*
        *  上面分析过长度小于等于3时存在的特殊情况，
        *  所以当绳子剪过之后，有一段长度小于等于3时，就不应该继续剪，否则乘积就会变小
        *  则在动态规划数组中，小于等于3的索引所指的元素应该等于其索引的值
        *  代表剪过的绳子到这长度就不要继续剪了
        */
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        /* 
        *  外层循环i表示每一段要剪的绳子，去掉特殊情况从4开始
        *  内层循环j表示将绳子剪成长度为j和i-j的两段
        *  这样双层循环就相当于从下向上完成了剪绳子的逆过程
        *  （剪绳子本来是将大段的绳子剪成小段，然后再在每小段上继续剪）
        *  双层循环中外层循环从4开始一直到原始绳子长度n，每一段都到内层循环进行剪绳子
        *  这样就得到长度在[4, n]区间内的每段绳子剪过之后的最大乘积
        *  dp[i]记录当前长度绳子剪过之后的最大乘积
        */
        for (int i = 4; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], dp[j] * dp[i - j]);
            }
        }
        /* 返回剪绳子的最大乘积 */
        return dp[n];
    }
};

剑指 Offer 39. 数组中出现次数超过一半的数字(简单)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        int count = 1,last = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(nums[i]  == last) count++;
            else{
                count--;
                if(count < 0) { //❓小于0和等于0都会，因为不用处理恰好一半的数字吗
                    last = nums[i];
                    count = 1;
                }
            }
        }
        return last;
    }
};

题解种竟然有三种还不错的方法，我用的原来是摩尔投票法。

1. 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N) 。
2. 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
3. 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)和 O(1) ，为本题的最佳解法。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0, count = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        // ⭐如果题目中没有说是否一定有众数，则需验证 x 是否为众数 
        for(int num : nums)
            if(num == x) count++;
        return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0
    }
};