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
}
};
网友评论