40分钟刷完4题，打破自己的最高纪录 第一题
代码语言：javascript复制class Solution {
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
vector<int> ans;
for(int i=0;i<nums.size();i )
{
int pos = index[i];
ans.push_back(-1);
for(int j=ans.size()-1;j>=pos 1;j--)
{
ans[j]=ans[j-1];
}
ans[pos]=nums[i];
}
return ans;
}
};第二题
遍历除数的时候从1到sqrt(nums[i]) 10000*sqrt(100000) 是不会超时的
代码语言：javascript复制class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int ans=0;
for(int i=0;i<nums.size();i )
{
int res=0;
int tag=0;
for(int j=1;j*j<=nums[i];j )
{
if(nums[i]%j==0)
{
if(j!=nums[i]/j)
{
res =j;
res =nums[i]/j;
tag =2;
}
else
{
tag ;
res =j;
}
}
}
if(tag==4)
ans =res;
}
return ans;
}
};第三题
广搜，深搜都可以。
代码语言：javascript复制struct Node
{
int x;
int y;
Node(){}
Node(int x,int y)
{
this->x = x;
this->y = y;
}
};
class Solution {
public:
int vis[500][500];
int dir[6][2][2]={{{0,-1},{0,1}},{{-1,0},{1,0}},{{0,-1},{1,0}},{{0,1},{1,0}},{{0,-1},{-1,0}},{{0,1},{-1,0}}};
bool hasValidPath(vector<vector<int>>& grid) {
queue<Node> q;
q.push(Node(0,0));
vis[0][0]=1;
int n=grid.size();
int m=grid[0].size();
while(!q.empty())
{
Node term = q.front();
q.pop();
if(term.x==n-1&&term.y==m-1)
return true;
int x = grid[term.x][term.y];
for(int i=0;i<2;i )
{
int xx = term.x dir[x-1][i][0];
int yy = term.y dir[x-1][i][1];
if(xx<0||xx>=n||yy<0||yy>=m)
continue;
if(vis[xx][yy]==1)
continue;
if(!judge(x,i,grid[xx][yy]))
continue;
vis[xx][yy]=1;
q.push(Node(xx,yy));
}
}
return false;
}
bool judge(int x,int z,int y)
{
if(x==1&&z==0&&(y==1||y==4||y==6))
return true;
if(x==1&&z==1&&(y==1||y==3||y==5))
return true;
if(x==2&&z==0&&(y==2||y==3||y==4))
return true;
if(x==2&&z==1&&(y==2||y==5||y==6))
return true;
if(x==3&&z==0&&(y==1||y==4||y==6))
return true;
if(x==3&&z==1&&(y==2||y==3||y==5))
return true;
if(x==4&&z==0&&(y==1||y==3||y==5))
return true;
if(x==4&&z==1&&(y==2||y==5||y==6))
return true;
if(x==5&&z==0&&(y==1||y==4||y==6))
return true;
if(x==5&&z==1&&(y==2||y==3||y==4))
return true;
if(x==6&&z==0&&(y==1||y==3||y==5))
return true;
if(x==6&&z==1&&(y==2||y==3||y==4))
return true;
return false;
}
};第四题
KMP 的求最长公共前后缀的部分，就是Next的部分
代码语言：javascript复制class Solution {
public:
int next[100005];
string longestPrefix(string s) {
getNext(s);
int len = next[s.length()-1];
string ans="";
for(int i=0;i<len;i )
{
ans =s[i];
}
return ans;
}
void getNext(string str)
{
next[0]=0;
for(int i=1;i<str.length();i )
{
int k=next[i-1];
while(k!=0&&str[i]!=str[k])
{
k=next[k-1];
}
if(str[i]==str[k])
next[i]=k 1;
else
next[i]=0;
}
}
};
