讨论/题目交流/🏆 第 178 场力扣周赛/
🏆 第 178 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 有多少小于当前数字的数字
4 分 - 通过投票对团队排名
5 分 - 二叉树中的列表
7 分 - 使网格图至少有一条有效路径的最小代价

展开讨论

第三题:
第三题我dfs遍历整个树,然后在叶子节点对当前路径做kmp匹配,dfs之前先对链表序列做kmp预处理
/**

  • Definition for singly-linked list.

  • struct ListNode {

  • int val;
    
  • ListNode *next;
    
  • ListNode(int x) : val(x), next(NULL) {}
    
  • };
    /
    /
    *

  • 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
    {
    private:
    vector<int> next;
    int pattern[200];
    int patternlength;
    int treestr[3000];

    void kmp_prepare()
    {
    int *str = pattern;
    int length = patternlength;
    int i,j;
    next = vector<int>(length);
    next[0] = 0;

     for(i = 1,j = 0;(i < length) && (j < length);)
     {
         if(str[i] == str[j])
         {
             next[i] = j + 1;
             i++;
             j++;
         }
         else if(j == 0)
         {
             next[i] = 0;
             j = 0;
             i++;
         }
         else
         {
             j = next[j - 1];
         }
     }
    

    }

    bool kmp(int *str,int length)
    {
    int i,j;

     for(i = 0,j = 0;(i < length && (j < patternlength));)
     {
         if(str[i] == pattern[j])
         {
             i++;
             j++;
         }
         else if(j == 0)
         {
             j = 0;
             i++;
         }
         else
         {
             j = next[j - 1];
         }
     }
    
     if(j < patternlength)
     {
         return false;
     }
     else
     {
         return true;
     }
    

    }

    bool dfs(TreeNode *curnode,int length)
    {
    treestr[length] = curnode -> val;

     if((curnode -> left == NULL) && (curnode -> right == NULL))
     {
         return kmp(treestr,length + 1);
     }
     
     if(curnode -> left != NULL)
     {
         if(dfs(curnode -> left,length + 1))
         {
             return true;
         }
     }
     
     if(curnode -> right != NULL)
     {
         if(dfs(curnode -> right,length + 1))
         {
             return true;
         }
     }
     
     return false;
    

    }

public:
bool isSubPath(ListNode* head, TreeNode* root)
{
patternlength = 0;

    while(head)
    {
        pattern[patternlength++] = head -> val;
        head = head -> next;
    }
    
    kmp_prepare();
    return dfs(root,0);
}

};

展开全部 21 讨论