精华内容
下载资源
问答
  • 中心扩散算法--最长回文子串

    千次阅读 2020-08-20 00:07:11
    这篇看一下中心扩散算法。 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb" 代码: #include<iostream> #include<string> #include<vector>...

          这篇看一下中心扩散算法。

    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    示例 2:
     
    输入: "cbbd"
    输出: "bb"

      代码:

      

    #include<iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<utility>
    
    using namespace std;
    //最长回文子串
    
    //中心扩散算法
    class Solution {
    public:
        pair<int, int> expandAroundCenter(const string& s, int left, int right) {
            while (left >= 0 && right < s.size() && s[left] == s[right]) {
                --left;
                ++right;
            }
    		
            return {left + 1, right - 1};
        }
    
        string longestPalindrome(string s) {
            int start = 0, end = 0;
            for (int i = 0; i < s.size(); ++i) {
    			//1个边界条件
                auto [left1, right1] = expandAroundCenter(s, i, i);
    			//2个相等字母的边界条件
                auto [left2, right2] = expandAroundCenter(s, i, i + 1);
    		    cout << "left1=" << left1 << "," << "right1=" << right1 << endl;
    			cout << "left2=" << left1 << "," << "right2=" << right1 << endl;
    
    			//判断新的回文子串是否比前面的长
                if (right1 - left1 > end - start) {
                    start = left1;
                    end = right1;
                }
                if (right2 - left2 > end - start) {
                    start = left2;
                    end = right2;
                }
    			cout << "-------------------" << endl;
            }
    		cout << "start=" << start << "end=" << end << endl;
            return s.substr(start, end - start + 1);
        }
    };
    
    int main(){
    	
    	string str = "babad";
    	Solution s;
    	
    	auto ret = s.longestPalindrome(str);
        cout << ret << endl;
    
    	return 0;
    }

      运行:

    left1=0,right1=0
    left2=1,right2=0
    -------------------
    left1=0,right1=2
    left2=2,right2=1
    -------------------
    left1=1,right1=3
    left2=3,right2=2
    -------------------
    left1=3,right1=3
    left2=4,right2=3
    -------------------
    left1=4,right1=4
    left2=5,right2=4
    -------------------
    start=0end=2
    bab

    这个分为1位扩散和2位扩散

     

    代码地址:https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

    展开全文
  • 什么是中心扩散法? 中心扩散法,顾名思义就是以某一个位置为中心,向周围扩散,直到满足条件或到达边界。 Leetcode 5.最长回文子串 题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设s 的最大...

     

    什么是中心扩散法?

    中心扩散法,顾名思义就是以某一个位置为中心,向周围扩散,直到满足条件或到达边界。

    Leetcode 5.最长回文子串

    题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

    示例 1:输入: "babad",输出: "bab",注意: "aba" 也是一个有效答案。

    示例 2:输入: "cbbd",输出: "bb"

     

    解题思路:遍历s,以每个char以及两个char中点为中心,计算以此点为中心的最长回文串;

    例如: 字符串abcba 共有5(字母) + 4(两字母间) = 9个中心点;因此,长度为N的string共有2N-1个中心。我们的目标就是统计以这2N-1个点为中心的最长回文串s1,s2,..,s2N-1,并从中挑出全局最长回文串。保留最大长度回文串index,记为left和right;完成遍历后返回以left和right为边界的substring

    public class Solution {
        public static void main(String[] args) {
            Solution solution = new Solution();
            String s1 = "babad";
            System.out.println(solution.longestPalindrome(s1));
            String s2 = "cbbd";
            System.out.println(solution.longestPalindrome(s2));
            String s4 = "";
            System.out.println(solution.longestPalindrome(s4));
            String s3 = null;
            System.out.println(solution.longestPalindrome(s3));
        }
        public String longestPalindrome(String s) {
            if(null == s) {
                return null;
            }
            char[] charArray = s.toCharArray();
            int length = charArray.length;
            int left = 0, right = 0, longestLength = 0;
            String longestPalindromeStr = "";
            for(int i=0; i<length; i++) {//以单个字符为中心扩散,则有n个中心(n是输入字符串的长度)
                left = i;
                right = i;
                while(left >= 0 && right < length && charArray[left] == charArray[right]) {
                    left--;
                    right++;//cabad
                }
                if(right - left - 1 > longestLength) {
                    longestLength = right - left - 1;
                    longestPalindromeStr = s.substring(left + 1, right);
                }
            }
            for(int i=0; i<length-1; i++) {//以双字符为中心扩散,则有n-1个中心(n是输入字符串的长度)
                left = i;
                right = i+1;
                while(left >= 0 && right < length && charArray[left] == charArray[right]) {
                    left--;
                    right++;
                }
                if(right - left - 1 > longestLength) {
                    longestLength = right - left - 1;
                    longestPalindromeStr = s.substring(left + 1, right);
                }
            }
            return longestPalindromeStr;
        }
    }

     

    转载于:https://www.cnblogs.com/jiangwangxiang/p/11145976.html

    展开全文
  • 方法一:中心扩散法 class Solution { public String longestPalindrome(String s) { if(s.length()<2) return s; char[] c = s.toCharArray(); int count; int point;

    https://leetcode-cn.com/problems/longest-palindromic-substring/

    方法一:中心扩散法

    class Solution {
        public String longestPalindrome(String s) {
             if(s.length()<2) return s;
            char[] c = s.toCharArray();
            int count;
            int point;
            int maxcount=0;
            int maxpoint=0;
            int size=0;
            int L=c.length;
            boolean flagissig=true;
    
            for (int i = 0; i < L; i++) {
                point = i;
                size = Math.min(i, L - i - 1);
                count = 0;
    
                for (int j = 0; j <= size; j++) {
                    if (c[i - j] == c[i + j]) {
                        count++;
                        continue;
                    } else {
                        break;
                    }
                }
    
                if (count > maxcount) {
                    maxcount = count;
                    maxpoint = point;
                }
            }
    
    
    //回文串是偶数的情况再来一次
            for (int i = 0; i < L; i++) {
                point = i;
                size = Math.min(i, L - i - 2);
                count = 0;
                for (int j = 0; j <= size; j++) {
                    if (c[i - j] == c[i + j +1]) {
                        count++;
                        continue;
                    } else {
                        break;
                    }
                }
    
                if (count >= maxcount) {
                    flagissig=false;
                    maxcount = count;
                    maxpoint = point;
                }
            }
    
            if(flagissig)
            return s.substring(maxpoint - maxcount + 1, maxpoint + maxcount);
            else
                return s.substring(maxpoint - maxcount + 1, maxpoint + maxcount+1);
        }
    }
    

     

    方法二:移动窗口法

    public class jarvis {
    
        public static void main(String[] args) {
            System.out.println(longestPalindrome("sojrsalskjdef"));
        }
    
        public static String longestPalindrome(String s) {
            String result = null;
            char[] chars = s.toCharArray();
            for (int i = chars.length; i >= 1; i--) {
                //获取所有这个长度的char数组
                for (int a = 0; a <= chars.length - i; a++) {
                    //判断是否是回文
                    boolean flag = false;
                    for (int j = 0; j < i / 2; j++) {
                        if (chars[a + j] == chars[a + i - 1 - j]) {
    
                        } else {
                            flag = true;  //不是回文
                        }
                    }
                    if (flag == false) {
                        result = s.substring(a, a + i);
                        return result;
                    }
                }
            }
            return null;
        }
    }

     

     

     

     

    展开全文
  • 方法一:中心扩散法 我们判断一个字符串是不是回文字符串,要分两种情况,第一种就该回文字符串是奇数,当我们枚举每个字符时,就可以判断以该字符为中心对称点的回文字符串最长为多少,方法很简单就是用l,r两个指针...

    题目链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

    解题思路

    方法一:中心扩散法

    我们判断一个字符串是不是回文字符串,要分两种情况,第一种就该回文字符串是奇数,当我们枚举每个字符时,就可以判断以该字符为中心对称点的回文字符串最长为多少,方法很简单就是用l,r两个指针比较是否相同,相同则往外面扩散。偶回文字符串也一样只不过初始化l,r两个指针的时候l指向i。

    代码

    class Solution {
        public String longestPalindrome(String s){
            int len = s.length(), start = 0, end = 0;   //记录最大回文子串的起始位置和终止位置
            for(int i = 0; i < len; i++){
                int l = i - 1, r = i + 1;   //查找以i为奇数回文字符串的最大长度
                while(l >= 0 && r < len && s.charAt(l) == s.charAt(r)){
                    l--;
                    r++;
                }
                if(r - l - 1 > end - start + 1) {   //当进入这个条件时,r和l是不相等的,所以他们都要往中间靠一个位置然后再计算他们区间的长度
                    start = l + 1;  //往右移一个位置
                    end = r - 1;        //往左移一个位置
                }
                l = i;
                r = i + 1;
                while(l >= 0 && r < len && s.charAt(l) == s.charAt(r)) {//查找以i为偶数回文字符串的最大长度
                    l--;
                    r++;
                }
               if(r - l - 1 > end - start + 1) {
                    start = l + 1;  //往右移一个位置
                    end = r - 1;        //往左移一个位置
               }
            }
            return s.substring(start, end + 1); //返回答案,记住该方法不包含右边界end+1
        }
    }
    

    复杂度分析

    • 时间复杂度:O(n^2),其中n是字符串的长度。长度为1和2的回文中心分别有n和n−1个,每个回文中心最多会向外扩展O(n)次。
    • 空间复杂度:O(1)。

    方法二:马拉车算法(Manacher’s Algorithm)

    这个算法有点难度,而且很反人类,一般如果没有见过的话基本上都不可能想出这种方法。但是虽然反人类,但是这个方法的时间复杂度还是提高成线性的了。虽然空间复杂度也提高了,但是对于打ACM比赛的选手还是很有用的,因为ACM很难超出空间,最关注的就是时间复杂度。

    代码

    class Solution {
        public String longestPalindrome(String s){
            if (s.length() < 2) 
                return s;
            // 第一步:预处理,将原字符串转换为新字符串
            String t = "$";
            for (int i = 0; i < s.length(); i++) 
                t += "#" + s.charAt(i);
            // 尾部再加上字符@,变为奇数长度字符串
            t += "#@";
            // 第二步:计算数组p、起始索引、最长回文半径
            int n = t.length();
            // p数组
            int[] p = new int[n];
            int id = 0, mx = 0;
            // 最长回文子串的长度
            int maxLength = -1;
            // 最长回文子串的中心位置索引
            int index = 0;
            for (int j = 1; j < n - 1; j++) {
                // 参看前文第五部分
                p[j] = mx > j ? Math.min(p[2 * id - j], mx - j) : 1;
                // 向左右两边延伸,扩展右边界
                while (t.charAt(j + p[j]) == t.charAt(j - p[j]))
                    p[j]++;
                // 如果回文子串的右边界超过了mx,则需要更新mx和id的值
                if (mx < p[j] + j) {
                    mx = p[j] + j;
                    id = j;
                }
                // 如果回文子串的长度大于maxLength,则更新maxLength和index的值
                if (maxLength < p[j] - 1) {
                    // 参看前文第三部分
                    maxLength = p[j] - 1;
                    index = j;
                }
            }
            // 第三步:截取字符串,输出结果
            // 起始索引的计算参看前文第四部分
            int start = (index - maxLength) / 2;
            return s.substring(start, start + maxLength);
        }
    }
    

    复杂度分析

    • 时间复杂度:O(n),
    • 空间复杂度:O(n)。
    展开全文
  • 中心扩散法 时间复杂度 \(O(n^2)\) ,空间复杂度 \(O(1)\) 我们先假定以某点为中心向两端扩散,找到以该点为中心的最长回文子串 class Solution { public: int rx, ry; void helper(string &s, int i, int ...
  • 三、中心扩散法 四、Manacher 算法 求最长回文子串的方法:(子串一定是连续的,子序列不是) LeetCode题目链接:https://leetcode-cn.com/problems/longest-palindromic-substring/ 一、暴力法 枚举子串的...
  • } 中心扩散 奇数以一个字母向两边扩散 偶数以相邻两个字母向两边扩散 int cnt; public int countSubstrings(String s) { if(s == null) return 0; cnt = 0; for (int i = 0;i ();i++){ count(s,i,i);//奇数 count(s...
  • 1.中心扩散法: 枚举每一个位置(两个位置)作为中心点的情况,向两边扩散,不断更新最大长度的答案。 时间复杂度O(n^2),空间复杂度O(1)。 2.动态规划: 定义状态dp[i][j]为区间[i,j]的s的子串是否为回文。假如...
  • 2.2 中心扩散中心扩散法是另一种回文串解决方法,算法思路是从字符串的第一个字符一直遍历到最后一个字符,每次从该字符往两边扫描,如果左右两边的值相等,那么往左右两边拓展,直至左右两边的值不相等或者越界...
  • 思路与算法: 边界情况即为子串长度为 1 或 2 的情况。我们枚举每一种边界情况,并从对应的子串开始不断地向两边扩展。如果两边的字母相同,我们就可以继续扩展,例如从 P(i+1,j-1)扩展到 P(i,j);如果两边的字母...
  • https://leetcode-cn.com/problems/longest-palindromic-substring/... class Solution { public String longestPalindrome(String s) { String string="#"; int max=1,c = 0,l=0; for(int i=0;... string=string+Cha
  • 2.2 中心扩散中心扩散法是另一种回文串解决方法,算法思路是从字符串的第一个字符一直遍历到最后一个字符,每次从该字符往两边扫描,如果左右两边的值相等,那么往左右两边拓展,直至左右两边的值不相等或者越界...
  • 解答参考:动态规划、中心扩散、Manacher 算法 问题描述: 给你一个字符串s,找到s中最长的回文子串。比如给定字符串s = "babad" ,找出最长的回文子串为"bab" 算法思路: 本题可以采用暴力破解法、中心扩散法...
  • 中心扩散法的实例

    2019-11-26 15:23:30
    中心算法与暴力匹配法相比优势巨大 看一下实例 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 ...
  • 一维对流扩散问题TDMA算法

    千次阅读 2012-03-21 22:05:10
    一维对流扩散问题TDMA算法,支持中心差分,迎风,混合,指数,乘方格式,还可 以输出精确解 用法 直接编译运行,不带参数运行时会自动输出使用方法: upwind –left=(左端点处的值) –right=(右端点处的值) –...
  • 思路1:【中心扩散法】记得以前做过很多回文的变形题,现在貌似又的差不多了。言归正传,这题可以向在每个字符间插入一个自定义符号例如#等,这样可以保证一定最大的回文字符串一定是奇数的,也就是一定以某个字符...
  • )是基于中心扩散算法的一种改进。 什么叫中心扩散算法呢? 举个简单的例子,假设有字符串1234135314,我们从5开始往两边扩散,就能够,经过O(n)时间(实际上远远达不到)就可以找到这个字符串的子串 :13531。 ...
  • Day3 回文串中心扩散

    2020-07-01 21:56:27
    leetcode 算法5. 最长回文子串 class Solution { public String longestPalindrome(String s) { if(null == s || s.length() == 0){ return ""; } int size = s.length(); int start = 0; int end = 0; ...
  • 1 先介绍一下中心扩散思想: 从每一个位置,向二边扩散即可(区分奇数和偶数个数) 2 基于中心思想,利用动态规划,这里可推出具体的公式来 假设 d[i][j]表示字符串中第i个字符到第j个字符是否为回文串,则d[i-1[j+1...
  • 「力扣」第 5 题:最长回文子串(暴力解法、中心扩散、动态规划) 解释题意 大家好,这里是「力扣」视频题解第 5 题:最长回文子串。 这道题给我们一个字符串 s,让我们找出这个字符串 s 的最长回文子串,并且告诉...
  • 以下解法中「暴力算法」是基础,「动态规划」必须掌握,「中心扩散」方法要会写; 「Manacher 算法」仅用于扩宽视野,绝大多数的算法面试中,面试官都不会要求写这个方法(除非面试者是竞赛选手)。 方法一:暴力...
  • 在写manacher算法前我们先了解一下中心扩散以及动态规划。暴力匹配比较简单就不再阐述了。 中心扩散中心扩散法,顾名思义就是以某一个位置为中心,向周围扩散,直到满足条件或到达边界。中心扩散法的思路是:遍历...
  • 中心扩散的另一种形式是以一个空字符为中心向两边扩散,扩散的条件和上面的一样。所以我们需要定义一个check函数,传入开始扩散的左右起始点,一步一步向两边扩散,直到组不成回文子串位置,返回这个子串的长度。 ...
  • 考虑网络节点深层次结构对影响扩散的作用并权衡计算复杂度与准确度,定义了3-layer局部中心度,以计算节点的潜在影响力值。基于线性阈值模型,启发选择一部分种子节点:每一次都选取潜在影响力最大的节点作为种子节点...
  • Manacher 算法

    2019-11-27 10:54:17
    个人觉得Manacher 算法是基于“中心扩散法”,采用和 kmp 算法类似的思想来的。 Manacher 算法,被中国程序员戏称为“马拉车”算法。它专门用于解决“最长回文子串”问题,时间复杂度为 O(N)。 ...
  • 目前复杂网络节点重要性识别算法主要集中在...为了验证该算法的有效性,利用W-SIR传播模型在真实复杂网络上进行病毒传播仿真实验,结果表明cw-壳分解方法能够有效地对节点进行分级排序,识别出具有高扩散能力的节点。

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 190
精华内容 76
关键字:

中心扩散算法