TODO:
- 重做 n个骰子的点数，仔细理清楚思路
- 重做剪绳子
- 理解并记忆摩尔投票法
剑指 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;
}
};
题解种竟然有三种还不错的方法，我用的原来是摩尔投票法。
- 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N) 。
- 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
- 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 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
}
};
