3月21日
376. Wiggle Subsequence
分析：这个题要做到复杂度O(N)，可以考虑用dp。up[i]表示当前位置是上升的最大长度，down[i]表示当前位置为下降的最大长度。如果当前是个下降的位置，根据摆动排序的性质，则一定是从上一个上升的位置转移过来。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int len=nums.size();
if(len==0) return 0;
int up[len+10],down[len+10];
memset(up,0,sizeof(up));
memset(down,0,sizeof(down));
up[0]=1,down[0]=1;
for(int i=1;i<len;i++){
if(nums[i]>nums[i-1]){
up[i]=down[i-1]+1;
down[i]=down[i-1];
}else if(nums[i]<nums[i-1]){
down[i]=up[i-1]+1;
up[i]=up[i-1];
}else{
down[i]=down[i-1];
up[i]=up[i-1];
}
}
return max(up[len-1],down[len-1]);
}
};
3月22日
670. Maximum Swap
分析：这个题暴力做是很简单的，但是在这里，我们需要做到O(N)。我们要尽量找到最靠后的最大的数对应的位置，和前面第一个比它小的数对应的位置，然后交换二者即可。
class Solution {
public:
int maximumSwap(int num) {
string res=to_string(num);
int len=res.length();
int dig[len+10],mp[len+10],mx=0;
memset(dig,0,sizeof(dig));
memset(mp,0,sizeof(mp));
for(int i=len-1;i>=0;i--){
int tmp=res[i]-'0';
if(tmp>mx){
mp[i]=tmp;
dig[i]=i;
mx=tmp;
}else{
mp[i]=mx;
dig[i]=dig[i+1];
}
}
for(int i=0;i<len-1;i++){
int tmp=res[i]-'0';
if(tmp<mp[i+1]){
swap(res[i],res[dig[i]]);
break;
}
}
int sum=0;
for(int i=0;i<len;i++){
sum*=10;
sum+=res[i]-'0';
}
return sum;
}
};
3月23日
708. Insert into a Cyclic Sorted List
分析：首先应该考虑为空的，应该自己连向自己，形成一个闭环。然后对于其他情况，如果存在一个在前后二者之间的位置，应该插入；如果存在比最小元素小，或者比最大元素大，则插入；如果所有元素都一样，则插入。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node() {}
Node(int _val, Node* _next) {
val = _val;
next = _next;
}
};
*/
class Solution {
public:
Node* insert(Node* head, int insertVal) {
if(head==NULL){
Node *res=new Node(insertVal);
res->next=res;
return res;
}
Node *pre=NULL;
Node *cur=head;
while(cur){
pre=cur;
cur=cur->next;
if(pre->val<=insertVal&&insertVal<=cur->val) break;
if(pre->val>cur->val&&(pre->val<insertVal||cur->val>insertVal)) break;
if(cur==head) break;
}
Node *tmp=new Node(insertVal);
pre->next=tmp;
tmp->next=cur;
return head;
}
};
3月25日
959. Regions Cut By Slashes
分析：这个题开始第一思路就是连通块DFS。但是如何判连通块成为了大问题。后来看了题解之后学到了一种很有趣的做法。对于每一个方格，我们可以把它分成4份，按下图方式进行编号
1.png
这样我们就可以考虑并查集来求解了，首先当前这个的1部分一定可以和右边的3部分相连，当前部分的2一定可以和下面部分的0相连。如果当前位置是" "，则块内0和3连，1和2连，0和1连；如果当前位置是/，则块内0和3连，1和2连；如果当前位置是\，则块内0和1连，3和2连。
class Solution {
public:
vector<int>par,rankl;
void init(int n){
for(int i=0;i<n;i++){
par[i]=i;
rankl[i]=0;
}
}
int findl(int x){
if(x==par[x]) return x;
else return par[x]=findl(par[x]);
}
void Union(int x,int y){
x=findl(x);
y=findl(y);
if(x==y) return;
if(rankl[x]<rankl[y]){
par[x]=y;
}else{
par[y]=x;
if(rankl[x]==rankl[y]) rankl[x]++;
}
}
int regionsBySlashes(vector<string>& grid) {
int n=grid.size();
if(n==0) return 0;
par=vector<int>(4*n*n);
rankl=vector<int>(4*n*n);
init(4*n*n);
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
int x=4*(i*n+j)+1,y=4*(i*n+j+1)+3;
Union(x,y);
}
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n;j++){
int x=4*(i*n+j)+2,y=4*((i+1)*n+j);
Union(x,y);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x=4*(i*n+j);
if(grid[i][j]==' '){
Union(x,x+3);
Union(x+1,x+2);
Union(x,x+1);
}else if(grid[i][j]=='/'){
Union(x,x+3);
Union(x+1,x+2);
}else{
Union(x,x+1);
Union(x+2,x+3);
}
}
}
int cnt=0;
for(int i=0;i<4*n*n;i++){
if(par[i]==i) cnt++;
}
return cnt;
}
};
386. Lexicographical Numbers
分析：这个题原来遇到过，做法就是我们从高位到低位按照从小到大枚举每一位。如果遇到产生进位的情况，就从低到高找到第一个非零位加1，继续枚举。
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int>res;
res.push_back(1);
while(res.size()<n){
int len=res.size();
int tmp=res[len-1];
tmp*=10;
while(tmp>n){
tmp/=10;
tmp+=1;
while(tmp%10==0) tmp/=10;
}
res.push_back(tmp);
}
return res;
}
};
3月26日
1015. Numbers With Repeated Digits
分析：数位DP的经典题，dp[pos][state]表示第pos位，以及前面的状态，状态用二进制来记录，非常棒的题目。
class Solution {
public:
int a[20],dp[20][1025];
int dfs(int pos,int state,bool lead,bool limit){
if(pos==-1) return 1;
if(!lead&&!limit&&dp[pos][state]!=-1) return dp[pos][state];
int up=limit?a[pos]:9;
int ans=0;
for(int i=0;i<=up;i++){
if(state&(1<<i)) continue;
if(i==0&&lead) ans+=dfs(pos-1,state,lead,limit&&i==up);
else ans+=dfs(pos-1,state|1<<i,lead&&i==0,limit&&i==up);
}
if(!limit&&!lead) dp[pos][state]=ans;
return ans;
}
int numDupDigitsAtMostN(int N) {
memset(dp,-1,sizeof(dp));
int pos=0;
int x=N;
while(x){
a[pos++]=x%10;
x/=10;
}
return N+1-dfs(pos-1,0,true,true);
}
};
4月1日
847. Shortest Path Visiting All Nodes
分析：这个题目需要BFS+状态压缩DP，dp[i][state]表示当前第i个，状态为state的情况，转移到它可以到达的结点以及对应的状态，同时BFS维护最小值
typedef pair<int,int>P;
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
int n=graph.size();
int dp[n+10][(1<<n)+10];
memset(dp,0,sizeof(dp));
int num=1<<n;
for(int i=0;i<n;i++){
for(int j=0;j<num;j++) dp[i][j]=INT_MAX/2;
}
for(int i=0;i<n;i++) dp[i][1<<i]=0;
queue<P>que;
for(int i=0;i<n;i++){
que.push(P(i,1<<i));
}
while(!que.empty()){
P tmp=que.front(); que.pop();
int u=tmp.first;
int state=tmp.second;
for(auto v:graph[u]){
int res=state|1<<v;
if(dp[v][res]>dp[u][state]+1){
dp[v][res]=dp[u][state]+1;
que.push(P(v,res));
}
}
}
int mi=INT_MAX;
for(int i=0;i<n;i++) mi=min(mi,dp[i][num-1]);
return mi;
}
};
4月3日
121. Best Time to Buy and Sell Stock
分析：本质就是要找序列中后面减去前面的最大值
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
int minx=prices[0],mx=0;
for(int i=1;i<len;i++){
if(prices[i]-minx>mx){
mx=prices[i]-minx;
}
if(prices[i]<minx) minx=prices[i];
}
return mx;
}
};
4月11日 (背包问题)
474. Ones and Zeroes
分析：这个题就是个二维的01背包，需要滚动数组压缩一下空间，否则会爆内存。这里背包要求的是装到容积V，最多需要多少个。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len=strs.size();
int dp[m+10][n+10];
memset(dp,0,sizeof(dp));
vector<pair<int,int>>res;
for(auto v:strs){
int num=0;
for(int i=0;i<v.length();i++){
if(v[i]=='0') num++;
}
pair<int,int>p={num,v.length()-num};
res.push_back(p);
}
for(int i=1;i<=len;i++){
int l=res[i-1].first,r=res[i-1].second;
for(int j=m;j>=l;j--){
for(int k=n;k>=r;k--){
dp[j][k]=max(dp[j][k],dp[j-l][k-r]+1);
}
}
}
return dp[m][n];
}
};
416. Partition Equal Subset Sum
分析：一个数组，能不能分成和相等的2部分，可以无序。可以背包，看看一半能否被装满。这里背包求的是，不超过容积V，最多能装多少。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int len=nums.size();
int sum=0;
for(int i=0;i<nums.size();i++) sum+=nums[i];
if(sum%2==1) return false;
sum/=2;
int dp[sum+1];
memset(dp,0,sizeof(dp));
for(int i=0;i<len;i++){
for(int j=sum;j>=nums[i];j--)
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
}
return dp[sum]==sum;
}
};
494. Target Sum
分析：按照枚举子集的方法进行DFS即可，注意用vector做DFS会T
int cnt;
typedef long long LL;
class Solution {
public:
void dfs(int t[],LL S,int pos,int len){
if(pos==len){
if(S==0) cnt++;
return;
}else{
dfs(t,S-t[pos],pos+1,len);
dfs(t,S+t[pos],pos+1,len);
}
}
int findTargetSumWays(vector<int>& nums, int S) {
cnt=0;
int len=nums.size();
int t[len+10];
memset(t,0,sizeof(t));
for(int i=0;i<nums.size();i++) t[i]=nums[i];
dfs(t,S,0,len);
return cnt;
}
};
4月12日
879. Profitable Schemes
分析：这是一个带限制的二维背包。要求一维不超过G，一维不少于P。不超过G好办，而对于不少于P，我们同样可以采用类似的方法，只不过当放入物品i后，总价值如果已经大于k，这时候用0代替。
const int mod=1e9+7;
class Solution {
public:
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
int n=group.size();
int dp[G+10][P+10];
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=0;i<n;i++){
for(int j=G;j>=group[i];j--){
for(int k=P;k>=0;k--){
dp[j][k]=(dp[j][k]+dp[j-group[i]][max(0,k-profit[i])])%mod;
}
}
}
int sum=0;
for(int i=0;i<=G;i++){
sum+=dp[i][P];
sum%=mod;
}
return sum;
}
};
网友评论