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. 剪繩子(中等)

直接放棄并開始看題解，還用上了“算術幾何均值不等式”。

方法一 數學的方法

//① 當所有繩段長度相等時，乘積最大。② 最優(yōu)的繩段長度為 3，次優(yōu)為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;
        /*
        *  創(chuàng)建動態(tài)規(guī)劃數組，所有元素初始化為0
        *  dp[i]表示剪長度為i的繩子所能得到的最大乘積，dp[n]表示長度為n的繩子
        *  所以數組的長度要為n+1
        */
        vector<int> dp(n + 1, 0);
        /*
        *  上面分析過長度小于等于3時存在的特殊情況，
        *  所以當繩子剪過之后，有一段長度小于等于3時，就不應該繼續(xù)剪，否則乘積就會變小
        *  則在動態(tài)規(guī)劃數組中，小于等于3的索引所指的元素應該等于其索引的值
        *  代表剪過的繩子到這長度就不要繼續(xù)剪了
        */
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        /* 
        *  外層循環(huán)i表示每一段要剪的繩子，去掉特殊情況從4開始
        *  內層循環(huán)j表示將繩子剪成長度為j和i-j的兩段
        *  這樣雙層循環(huán)就相當于從下向上完成了剪繩子的逆過程
        *  （剪繩子本來是將大段的繩子剪成小段，然后再在每小段上繼續(xù)剪）
        *  雙層循環(huán)中外層循環(huán)從4開始一直到原始繩子長度n，每一段都到內層循環(huán)進行剪繩子
        *  這樣就得到長度在[4, n]區(qū)間內的每段繩子剪過之后的最大乘積
        *  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
    }
};