剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

方法一：dp

class Solution {
public:int cuttingRope(int n) {vector<int> dp(n+1,1);if(n==1||n==2) return 1;else if(n==3) return 2;dp[1]=1;dp[2]=2;dp[3]=3;for(int i=4;i<=n;i++){for(int k=1;k<=i/2;k++){dp[i]=max(dp[k]*dp[i-k],dp[i]);}}return dp[n];}
};

方法二：贪心（需要证明）

长度为n的绳子切成a段
利用算数几何均值不等式，等号当且仅当切成的绳子长度相等时成立。设每段绳子长为x，则n=ax
乘积为x^a。

x^a= x^n/x
即求y=x^1/x的极值。
求导得到极大值点e。 因为x为整数，所以x可以取2或3，验证后y极大值为取3时得到。

尽可能将绳子以长度3等分为多段时，乘积最大。讨论绳子尽可能都切分为3之后的情况：

1. 留下最后一段绳子长度为1：因为2×2>3×1 所以要把一份3+1换为2+2
2. 留下最后一段绳子为2：保留即可

剑指 Offer 14- Ⅱ. 剪绳子

结果存在大数越界的情况，要求取模后输出。
因为有取模这一步…dp似乎是没法用了

class Solution {
public:int cuttingRope(int n) {if(n==1||n==2) return 1;else if(n==3) return 2;int p=1e9+7;int a=n/3; //n=3*a+b;int b=n%3;long temp=remainder2(3,a-1,p);if(b==0) return (int)(temp*3%p);else if(b==1) return (int)(temp*4%p);else return (int)(temp*6%p);}//循环求余法long remainder(int x,int a,int p){long rem=1;for(int i=0;i<a;i++){rem=(rem*x)%p;}return rem;}// 快速幂求余long remainder2(int x,int a,int p){long rem=1;while(a>0){if(a%2==1){rem=(rem*x)%p;}x=(long)x*x%p;  //不改为long 这里会溢出a/=2;}return rem;}
};

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> s;int k=0;for(int num:pushed){s.push(num);while(!s.empty()&&s.top()==popped[k]){s.pop();k++;}}if(k==pushed.size()) return true;else return false;}
};