题解链接
class Solution {
public:
vector maxInWindows(const vector& num, unsigned int size) {
int n=num.size();
int low=1-size, high=0;//滑窗头，滑窗尾
deque dq;
vector res;
while(high=1 && num[low-1]==dq[0]) dq.pop_front();
while(!dq.empty() && dq[0] < num[high]) dq.pop_front();//先处理high，也就是右边更新
while(!dq.empty() && dq[dq.size()-1]=0) res.push_back(dq[0]);
low++;
high++;
}
return res;
}
};
面试题60
题解链接
时间O(n^2)
空间O(n^2)
class Solution {
public:
vector dicesProbability(int n) {
int dp[n+1][n*6+1];
memset(dp, 0, sizeof(dp));
for(int i=1; i<=6; ++i){
dp[1][i]=1;
}
for(int i=2; i<=n; ++i){
for(int j=i*1; j<=i*6; ++j){//j是i个骰子点数和，i*1 to i*6
for(int k=1; k<=6; ++k){//k是第i个骰子的点数
if(j-k <= 0){
break;//跳出当前循环
}
dp[i][j]+=dp[i-1][j-k];
}
}
}
int all=pow(6,n);//所有可能结果的数量
vector ret;
for(int i=n; i<=6*n; ++i){
ret.push_back(dp[n][i] * 1.0/all);
}
return ret;
}
};
空间优化
class Solution {
public:
vector dicesProbability(int n) {
//空间优化，dp是n个骰子掷出各个点数的出现次数，按i更新整个dp表
int dp[n*6+1];
memset(dp, 0, sizeof(dp));
for(int i=1; i<=6; ++i){
dp[i]=1;
}
for(int i=2; i<=n; ++i){
for(int j=i*6; j>=i*1; --j){//后往前更新
dp[j]=0;
for(int k=1; k<=6; ++k){//k是第i个骰子的点数
if(j-k < i-1){//前i-1个骰子的点数是j-k
break;//跳出当前循环
}
dp[j]+=dp[j-k];
}
}
}
int all=pow(6,n);//所有可能结果的数量
vector ret;
for(int i=n; i<=6*n; ++i){
ret.push_back(dp[i] * 1.0/all);
}
return ret;
}
};
面试题61
思路：set存遇到的非0数，遍历如果有重复，就false，否则，维护一个最大最小，最大-最小<5的话就是true，否则false，注意最大可以初始化为0，但最小不能初始化为0
时间O(n)，空间O(n)，其实就5个，时间空间可以忽略不计。
class Solution {
public:
bool isStraight(vector& nums) {
unordered_set st;
int maxNum=nums[0],minNum=nums[0];
for(int i=0; i
面试题62
题解链接
递归
class Solution {
public:
int LastRemaining_Solution(int n, int m) {
if(n==1) return 0;
return (LastRemaining_Solution(n-1, m)+m)%n;
}
};
迭代，先写递归，再优化成迭代
class Solution {
public:
int LastRemaining_Solution(int n, int m) {
if(n==1) return 0;
int f=0;
for(int i=2;i<=n; ++i){
f=(f+m)%i;//注意这个i，容易写成n
}
return f;
}
};
面试题63
class Solution {
public:
int maxProfit(vector& prices) {
// write code here
if(prices.size()==0) return 0;
int buyMin=prices[0];
int ans=0;
for(int i=0; i
面试题64
题解链接
class Solution {
public:
int Sum_Solution(int n) {
bool x = n > 1 && (n += Sum_Solution(n-1)); // bool x只是为了不报错
return n;
}
};
面试题65
题解链接
class Solution {
public:
int Add(int num1, int num2) {
while(num2!=0){
int c=(unsigned int)(num1&num2)<<1;
//要先unsigned int再左移
num1^=num2;
num2=c;
}
return num1;
}
};
面试题66
题解链接
class Solution {
public:
vector multiply(const vector& A) {
//迭代就行了
int n=A.size();
if(n==0) return {};
vector B(A.size(),1);
int tmp=1;
//下三角
for(int i=1; i=0; --i){
tmp*=A[i+1];
B[i]*=tmp;
}
return B;
}
};
面试题67
题解链接
class Solution {
public:
int StrToInt(string s) {
// write code here
int border=INT_MAX/10;
int i=0;
//空格
while(iborder || (ans==border && s[j]>'7'))
return sign?INT_MIN:INT_MAX;
ans=ans*10+(s[j]-'0');
}
}
return sign?ans*-1:ans;
}
};
面试题68
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
if(p==root->val || q==root->val) return root->val;
if((pval && q>root->val)||(p>root->val && qval))
return root->val;
//否则在同一侧
if(pval){//左侧
return lowestCommonAncestor(root->left, p, q);
}
else{
return lowestCommonAncestor(root->right, p, q);
}
}
};
知识
deque，pop_back(),pop_front(),可直接访问,deque[0]这种
