无标题

作者: Lyapunov_ | 来源:发表于2017-09-13 11:29 被阅读0次

Manacher

解决最长回文子串问题

引入两个辅助变量 id, mx
先预处理插入#,再分两种情况:

  • 回文串 p[2*id-i] (记 p[j])包含在大子串内部, p[i]直接等于p[j]
  • p[j]部分包含在大子串内,这一部分p[i]等于p[j],后续接着扩展
//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) 
{
    p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) 
        p[i]++;
    if (i + p[i] > mx) 
    {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的

Maximum Gap

找出排序后相邻元素的最大差值,要求 O(n)
如 [9, 3, 1, 10] 返回 6

利用桶排序的思想,且每个桶会记录存放的最大值和最小值。
不妨用 N-1 个桶放置,这样每个桶的间距gap(max-min)/(N-1)注:桶的数量和间距有待进一步考证
然后扫一遍把每个数num放入第(num-min)/gap个桶中(实际上应该再加一个桶
最后找到间隔连续空桶最多的两个桶即可

相关文章

  • 无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章 无标题文章无标题文章无标题文章无...

  • 无标题文章

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章

  • 无标题文章

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标...

  • 无标题文章

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标...

  • fasfsdfdf

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标...

  • 无标题文章

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标...

  • 无标题文章

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标...

  • 无标题文章

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标...

  • 无标题文章

    无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章无标题文章

  • 无标题文章

    无标题文章 无标题文章 无标题文章无标题文章 无标题文章 无标题文章

网友评论

      本文标题:无标题

      本文链接:https://www.haomeiwen.com/subject/ihuksxtx.html