【每日算法Day 77】LeetCode 第 181 场周赛题解

classSolution {
public: 
vector<int>createTargetArray(vector<int>&nums, vector<int>&index) {     
intn=nums.size();  
vector<int>target;    
for (inti=0; i<n; ++i) {    
target.insert(target.begin()+index[i], nums[i]);      
        }        returntarget;  
    }
};

classSolution {
public:
intsumFourDivisors(vector<int>&nums) {   
intres=0;     
for (autox : nums) {      
intcnt=0, sum=0;  
for (inti=1; i*i<=x; ++i) {   
if (i*i==x) {       
cnt++;        
break;      
                }       
if (x%i==0) {   
cnt+=2;      
sum+=i+x/i; 
                }           
if (cnt>4) break;  
            }         
if (cnt==4) res+=sum;
        }     
returnres; 
    }
};

classSolution {
public:   
intlink(inta, intb, intd) {  
if (d==1||d==3) {     
d--;    
swap(a, b);  
        }     
if (d==0) return (a==1||a==4||a==6)&&(b==1||b==3||b==5); 
if (d==2) return (a==2||a==3||a==4)&&(b==2||b==5||b==6); 
returnfalse; 
    }     
boolhasValidPath(vector<vector<int>>&grid) {  
intn=grid.size(), m=grid[0].size();
intdx[4] = {0, 0, 1, -1}; 
intdy[4] = {1, -1, 0, 0};   
vector<vector<int>>vis(n, vector<int>(m, 0)); 
queue<pair<int, int>>Q;    
Q.push({0, 0});    
vis[0][0] =1;   
while (!Q.empty()) {     
pair<int, int>p=Q.front();  
Q.pop();       
intx=p.first, y=p.second;   
if (x==n-1&&y==m-1) returntrue; 
for (inti=0; i<4; ++i) {      
intnx=x+dx[i], ny=y+dy[i]; 
if (0<=nx&&nx<n&&0<=ny&&ny<m&&!vis[nx][ny] &&link(grid[x][y], grid[nx][ny], 
i)) {    
vis[nx][ny] =1;    
Q.push({nx, ny});  
                }        
            }      
        }      
returnfalse; 
    }
};

classSolution {
public: 
voidgetNext(strings, vector<int>&next) {    
intn=s.size();     
next[0] =0;    
for (intq=1, k=0; q<n; ++q) { 
while (k>0&&s[q] !=s[k])    
k=next[k-1];      
if (s[q] ==s[k]) k++;            next[q] =k;     
        }   
    }  
stringlongestPrefix(strings) {   
intn=s.size();     
vector<int>next(n);     
getNext(s, next);    
returns.substr(0, next[n-1]); 
    }
};