当前在线人数14861
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:Re: [转载] CS Interview question
[同主题阅读] [版面: 葵花宝典] [作者:Pront] , 2004年12月09日03:26:17
Pront
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: Pront (阿呆), 信区: Programming
标  题: Re: [转载] CS Interview question
发信站: Unknown Space - 未名空间 (Thu Dec  9 03:45:15 2004) WWW-POST

我的程序和你的很象,不过我是这么想的:
对一个字符串,从左到右,分别以某个字符(或两个字符的中间)为轴,
然后向两边找对应字符,看看最远能走多少。加起来就是了。

如 “222"

2|2 2
2|2|2
2 2|2

#ifdef WIN32
#pragma warning(disable:4786 4101)
#define min _MIN
#define max _MAX
#endif
#include <vector>
#include <string>
#include <iostream>
using namespace std;

int maxPalindrome(string s)
{
    int i, j, k;
    int count = 0;
    for(i = 0; i < s.size(); i++)
        for(k = 0; k < 2; k++)
            for(j = 1; ; j++)
            {
                int x1 = i + k + j;
                int x2 = i - j + 1;
                if (x2 < 0 || x1 >= (int)s.size()
                    || s[x1] != s[x2])
                {
                    count += j-1;
                    break;
                }
            }
    return count;
}

int main()
{
    cout << maxPalindrome("aa") << endl;
    cout << maxPalindrome("aabb") << endl;
    cout << maxPalindrome("222") << endl;
    cout << maxPalindrome("baaab3") << endl;
    cout << maxPalindrome("aabbaa") << endl;
    return 0;
}



【 在 babbage (tm) 的大作中提到: 】
: Let's say that the input string is S, S[1]..S[N] are the chars.
:
: The question is to find all pairs (i,j) such that:
: 1) i<j, and
: 2) S[i+k] == S[j-k] for all k=0 to j-i. (actually to (j-i)/2 is sufficient.)
: -- this is the same as saying S[i..j] is a palindrome.
:
: Let us use boolean array A[i][j] to store if S[i..j] is a palin, then
: we have:
:
: 1) A[i][i]=true, and
: 2) A[i][i+1]=true iff S[i]=S[i+1], and
: 3) A[i][j]=true iff A[i+1][j-1] is true && S[i]==S[j]
:
: So we can use 1) and 2) to initialize all, A[i][i] and A[i][i+1]
: and use 3) as the dynamic programming step when j>=i+2:
:
: /* 1 */ for k=2 to N-1   // k is (j-i)
: /* 2 */   for i=1 to N-k
: /* 3 */     A[i][i+k] = A[i+1][i+k-1] && (S[i]==S[j])
:
: Now we know if S[i..j] is a palindrome! It takes O(N^2) time.
:
: This is probably optimal. Because there are strings that contains O(N^2)
: palindromes, for example, S= "ABABABABAB...."   (N repetitions of AB,
: where every odd-length substring is a palindrome.
:
:
:
:
:
:
:
:
:
:
: 【 在 lhict (至少还有我) 的大作中提到: 】
:
: : Create a function findPalin() that takes a string of characters as
argument
: : and returns the number of palindromes (a string in which the sequence of
cha
: : racters is the same forwards and backwards) in that string. There is no
spec
: : ial character. This function should be as fast as possible.
: : Ex:
: : "aa" returns 1
: : "aabb" returns 2
: : "222" returns 3
: : "baaab3" returns 4
:
:






--
※ 修改:·Pront 於 Dec  9 03:45:15 修改本文·[FROM: 24.16.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 24.16.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996