首页 > 其他分享 >LeetCode刷题记录.Day21

LeetCode刷题记录.Day21

时间:2022-11-20 23:14:50浏览次数:69  
标签:int Day21 len next 后缀 长度 size LeetCode 刷题

重复的子字符串

459. 重复的子字符串 - 力扣(LeetCode)

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = -1;
        int j = -1;
        for(int i = 1;i < s.size(); i++){
            while(j >= 0 && s[i] != s[j + 1]){
                j = next[j];
            }
            if( s[i] == s[j + 1]){
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        if(s.size() == 0){
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        //next[len - 1] 如果为-1,代表末位的回退下表不存在,也就是该前缀表的最后一位不存在相等前后缀,所以必然不符合
        //数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环
        //len % (len - next[len - 1] + 1) == 0   next[len - 1]就是最末尾前后缀的回退下标,next[len - 1] + 1 下标+1就是最长相同前后缀的长度
        //存在合法的相等前后缀,则可以判断符合
        if(next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0){
            return true;
        }
        else{
            return false;
        }
    }
};

 

算是KMP思想的应用题。主要涉及到一个找最小周期的数学运算上的东西。理解了KMP的原理(递归建立回退数组)就差不多明白这道题该怎么操作了

标签:int,Day21,len,next,后缀,长度,size,LeetCode,刷题
From: https://www.cnblogs.com/tianmaster/p/16909983.html

相关文章

  • [leetcode每日一题]11.20
    ​​799.香槟塔​​我们把玻璃杯摆成金字塔的形状,其中 第一层 有 ​​1​​ 个玻璃杯, 第二层 有 ​​2​​ 个,依次类推到第100层,每个玻璃杯(250ml)将盛有香槟......
  • leetcode343-数拆分。还需要继续琢磨
    343.整数拆分 这道题的关键点在于下面这两个式子。比如要计算dp【10】,就逐个比较1*dp【9】,2*dp【8】,3*dp【7】,还有1*9,2*8,3*7,才考虑了所有的情况如果使用dp[i]=max(d......
  • [LeetCode] 2221. Find Triangular Sum of an Array
    Youaregivena0-indexedintegerarraynums,wherenums[i]isadigitbetween0and9(inclusive).Thetriangularsumofnumsisthevalueoftheonlyelemen......
  • Leetcode 799.香槟塔:动态规划+递归
    香槟塔:动态规划+递归题目来源:Leetcode22/11/20每日一题:799.香槟塔https://leetcode.cn/problems/champagne-tower我们把玻璃杯摆成金字塔的形状,其中第一层有1个玻......
  • leetcode-1380-easy
    LuckyNumbersinaMatrixGivenanmxnmatrixofdistinctnumbers,returnallluckynumbersinthematrixinanyorder.Aluckynumberisanelementofthe......
  • leetcode-507-easy
    PerfectNumberAperfectnumberisapositiveintegerthatisequaltothesumofitspositivedivisors,excludingthenumberitself.Adivisorofanintegerx......
  • leetcode-1403-easy
    MinimumSubsequenceinNo-IncreasingOrderGiventhearraynums,obtainasubsequenceofthearraywhosesumofelementsisstrictlygreaterthanthesumofth......
  • leetcode-506-easy
    RelativeRanksYouaregivenanintegerarrayscoreofsizen,wherescore[i]isthescoreoftheithathleteinacompetition.Allthescoresareguaranteedt......
  • 代码随想录刷题营day1|704.二分查找 34. 有序数组找首位末位 35.搜索插入的位置 27.移
    一、数组理论基础数组下标都是从0开始的数组内存空间的地址是连续的数组的元素是不能删的,只能覆盖二、刷题第一题704.二分查找题目链接:https://leetcode.com/prob......
  • 代码随想录day4---LeetCode24. 两两交换链表中的节点&19.删除链表的倒数第N个节点&面
    LeetCode24.两两交换链表中的节点题目链接给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节......