ShawnPei

6186

ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return NULL;
if (root==p || root==q) return root;
auto left=lowestCommonAncestor(root->left,p,q);
auto right=lowestCommonAncestor(root->right,p,q);
if (left && right) return root;
if (left) return left;
return right;

}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

class Solution {
public:
int strToInt(string str) {
long long res=0;
bool isneg=false;
int i=0,j=str.size();
while (i<j && str[i]==' ') i++;
if (str[i]=='-') i++,isneg=true;
else if (str[i]=='+') i++;
else if (!(str[i]>='0' && str[i]<='9')) return 0;
for (;i<j && str[i]>=0 && str[i]<='9';i++) {
if (isneg) res=res*10-(str[i]-'0');
else res=res*10+str[i]-'0';
}
if (res>INT_MAX) res=INT_MAX;
else if (res<INT_MIN) res=INT_MIN;
return res;
}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

将数组拆分为left和right两部分，left[i]=A[i-1]*left[i-1],right[i]=A[i+1]*right[i+1]

class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B(A.size());
vector<int> left(A.size(),1);
vector<int> right(A.size(),1);
for (int i=1;i<A.size();i++) {
left[i]=A[i-1]*left[i-1];
// cout<<left[i]<<' ';
}
for (int i=A.size()-2;i>=0;i--) {
right[i]=A[i+1]*right[i+1];
// cout<<right[i]<<' ';
}
for (int i=0;i<A.size();i++) {
B[i]=left[i]*right[i];
// cout<<B[i]<<' ';
}
return B;
}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

class Solution {
public:
int maxDiff(vector<int>& nums) {
int n=nums.size();
if (n==0) return 0;
vector<vector<int> > f(n,vector<int>(2));
for (int i=0;i<n;i++) {
if (i-1==-1) {
f[i][0]=0;
f[i][1]=-nums[i];
continue;
}
f[i][0]=max(f[i-1][0],f[i-1][1]+nums[i]);
f[i][1]=max(f[i-1][1],-nums[i]);
}
return f[n-1][0];
}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

1.排序删除0
2.判重
3.末尾和第一个非零数之间相差不超过4

class Solution {
public:
bool isContinuous( vector<int> nums ) {
if (nums.empty()) return false;
int k=0;
sort(nums.begin(),nums.end());
while (!nums[k]) k++;
for (int i=k+1;i<nums.size();i++) {
if (nums[i]==nums[i-1]) {
return false;
}
}
return nums.back()-nums[k]<=4;
}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

状态表示f（i，j）表示前i次，点数为j的方案数


class Solution {
public:
vector<int> numberOfDice(int n) {
vector<vector<int> > f(n+1, vector<int>(6*n+1));
f[0][0]=1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=6*i;j++) {
for (int k=1;k<=min(j,6);k++) {
f[i][j]+=f[i-1][j-k];
}
}
}
vector<int> res;
for (int i=n;i<=6*n;i++) res.push_back(f[n][i]);
return res;
}
};



ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1(单调队列)

利用单调队列维护一个单调递减的队列，队首元素为每个窗口的最大值

class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
int n=nums.size();
vector<int> res;
deque<int> q;
for (int i=0;i<n;i++) {
while (q.size() && q.front()<=i-k) q.pop_front();
while (q.size() && nums[q.back()]<=nums[i]) q.pop_back();
q.push_back(i);
if (i>=k-1) res.push_back(nums[q.front()]);
}
return res;
}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1

class Solution {
public:
string leftRotateString(string str, int n) {
reverse(str.begin(),str.begin()+n);
reverse(str.begin()+n,str.end());
reverse(str.begin(),str.end());
return str;
}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1(双指针)

利用双指针先对整个字符串翻转，然后，在对翻转后的字符串中的每个单词进行翻转

class Solution {
public:
string reverseWords(string s) {
for (int i=0,j=s.size()-1;i<j;i++,j--) swap(s[i],s[j]);
for (int i=0;i<s.size();i++) {
int j=i;
while (j<s.size() && s[j]!=' ') j++;
for (int a=i,b=j-1;a<b;a++,b--) swap(s[a],s[b]);
i=j;
}
return s;
}
};


ShawnPei
5个月前

### 题目描述

blablabla

#### 样例

blablabla


### 算法1(双指针)

class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> res;
for (int i=1,j=1,s=1;i<sum;i++) {
while (s<sum) s+=++j;
if (s==sum && j-i+1>1) {
vector<int> line;
for (int k=i;k<=j;k++) line.push_back(k);
res.push_back(line);
}
s-=i;
}
return res;
}
};