Day24 2023.2.6 数学（中等）
剑指Offer 14 - Ⅰ. 剪绳子
自己实现
就是简单地把给的数n尽可能平均分为m份（m是for(m=2;m<n;m++)），然后再比较每个m的乘积结果，最后再取最大值
代码如下：
class Solution {
public:
int cuttingRope(int n) {
int m=2;
if(n==2)return 1;
int max=0;
for(;m<n;m++){
int left=n%m;
int sing=n/m;
int pro_ori = pow(sing,m-left);
int pro_left=pow(sing+1,left);
int now = pro_ori*pro_left;
if(now>max)max=now;
}
return max;
}
};
代码表现
hint
- 其实这种题就相当于要先用纯数学推导一下，才能尽可能简化过程。
- 这个地方的结论就是尽量等分，并且尽可能分为3段能使乘积最大，推导过程要用到算数几何均值不等式
剑指Offer 57 - Ⅱ. 和为s的连续正数序列
自己实现
自己的思路还是想用先平均分target的方法，然后往两边扩散，但是感觉这个会很耗时间，特别是对于target比较大的时候。所以就没有继续写下去了，直接看题解了
题解
题解采用了滑动窗口，对于这种连续序列就该用滑动窗口。
设置好左边界和右边界，并实时更新滑动窗口里面的和s，当s==target时，保存当前序列，并将左边界向右移动；当s<target时，将左边界向右移动；当s>target时，将右边界向右移动
代码如下：
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
if(target==0)return res;
int i=1,j=2,s=3;
while(i<j){
if(s==target){
vector<int> ans;
for(int m=i;m<=j;m++)ans.push_back(m);
res.push_back(ans);
}
if(s>=target){
s-=i;
i++;
}
else{
j++;
s+=j;
}
}
return res;
}
};
代码表现
hint
- 这种连续序列就应该考虑滑动窗口的方式，但是要考虑好左边界和右边界的移动，一般都是向右移动
剑指Offer 62.圆圈中最后剩下的数字
自己实现
这个题目是之前程序设计专题中讲过的猴子选大王的问题（更常见的是叫做约瑟夫环问题），这个当然可以用逐个删除的方式来做，但是这个一定是最耗时的做法。之前老师讲过用极少的代码量就能实现的，直接看题解了
题解
其实就是用动态规划来做。
设n个数每隔m个进行删除的问题的最终解为f(n,m)，那么f(n,m)是可以由f(n-1,m)得到的，具体为f(n)=(f(n-1)+m)%n，那么对n进行迭代递推即可。其中f(1,m)=0
代码如下：
class Solution {
public:
int lastRemaining(int n, int m) {
int x=0;
for(int i=2;i<=n;i++){ //dp[1]就等于0, 已经处理了，然后由于dp是从1下标开始，所以要i<=n
x=(x+m)%i; //这列要注意%i而不是%n
}
return x;
}
};
代码表现
hint
- 这个题目就是动态规划的经典想法，只是可能这个
%i容易搞错