专栏首页算法修养LeetCode Contest 181

LeetCode Contest 181

40分钟刷完4题,打破自己的最高纪录 第一题

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) 是不会超时的

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;
        
    }
};

第三题

广搜,深搜都可以。

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的部分

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;
            
        }
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 201. Bitwise AND of Numbers Range(位运算)

    题意:给你两个数n,m 0<= n<=m <=2^31-1 ,让你计算从n到m的每个数依次位与的结果。

    ShenduCC
  • HDU 5157 Harry and magic string(回文树)

    Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

    ShenduCC
  • 2016天梯模拟赛 进阶题解

    L2-005 集合相似度 题目链接: https://www.patest.cn/contests/gplt/L2-005 题目的意思是要求两个集合的交集中...

    ShenduCC
  • HDU-2588-GCD

    ACM模版 描述 ? 题解 image.png 代码 #include <stdio.h> #include <math.h> int Euler(int n...

    f_zyj
  • C++二分图代码实现

    #include <iostream> #include <cstdio> #include <vector> using namespace std; #d...

    kalifa_lau
  • 经典算法学习之回溯法

    回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

    用户1215536
  • LWC 53:694. Number of Distinct Islands

    LWC 53:694. Number of Distinct Islands 传送门:694. Number of Distinct Islands Probl...

    用户1147447
  • NYOJ 123 士兵杀敌(四) (线段树+树状数组)

    题目连接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=123

    Ch_Zaqdt
  • LeetCode 201. Bitwise AND of Numbers Range(位运算)

    题意:给你两个数n,m 0<= n<=m <=2^31-1 ,让你计算从n到m的每个数依次位与的结果。

    ShenduCC
  • 暑假(补)-5

    DFS全称Deep First Search,是一种遍历或搜索树或图的算法。在解决问题上,利用递归调用自身函数(这种说法好像不正确,领悟思想就好了)来实现搜索的...

    AngelNH

扫码关注云+社区

领取腾讯云代金券