Starry

发表于 更新于 分类于 本文字数： 85 阅读时长 ≈ 1 分钟

第一个for循坏有点多余，应只判断是否全为’a’，全为则最后一位改为’b’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define f(i, a, b) for (int i = a; i <= b; i++)

char * breakPalindrome(char * palindrome){
if(strlen(palindrome)==1)
return "";
f(i,'a','z'){
    f(j,0,strlen(palindrome)/2-1){
        if(palindrome[j]>i){
            palindrome[j]=i;
            return palindrome;
        }
        else if(palindrome[j]!=i){
            palindrome[strlen(palindrome)-j-1]=i;
            return palindrome;
        }
    }
}
return "";
}

发表于 更新于 分类于 本文字数： 150 阅读时长 ≈ 1 分钟

s_new和数组p都要开大，不然爆掉😴

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define f(i, a, b) for (int i = a; i <= b; i++)
#define min(a, b) (a < b ? a : b)

char * longestPalindrome(char * s){
    char s_new[5000];
    int j = 2;
    s_new[0] = '$';
    s_new[1] = '#';
    f(i, 0, strlen(s) - 1)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }
    s_new[j++] = '^';
    s_new[j] = '\0';
    int p[20000]={0};
    int center=0, right = 0,maxlen=0,maxcenter=0;
    f(i, 2, strlen(s_new))
    {
        p[i] = i >= right ? 1 : min(right - i, p[2 * center - i]);
        while(s_new[i-p[i]]==s_new[i+p[i]]){
            p[i]++;
        }
        if(i+p[i]>right){
            right = i + p[i];
            center = i;
        }
        if(maxlen<p[i]){
            maxlen = p[i];
            maxcenter = i; 
        }
    }   
    static char res[2000];
    j = 0;   
    f(i, (maxcenter - maxlen) / 2, (maxcenter + maxlen) / 2 - 2)
        res[j++] = s[i];
    res[j] = '\0';
    return res;
}

发表于 更新于 分类于 本文字数： 207 阅读时长 ≈ 1 分钟

马拉车算法

最大回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define f(i, a, b) for (int i = a; i <= b; i++)
#define pn(x) printf("%d", x)
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define min(a, b) (a < b ? a : b)

int main()
{
    char s[] = "bdbuwahdkwjfkejsoboacaob";
    char *s_new = (char *)malloc(sizeof(char) * (2 * strlen(s) + 4));
    int j = 2;
    s_new[0] = '$';
    s_new[1] = '#';
    f(i, 0, strlen(s) - 1)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }
    s_new[j++] = '^';
    s_new[j] = '\0';
    /*形成新字符串*/
    int *p = (int *)malloc(sizeof(int) * (2 * strlen(s) + 4));
    p[1] = 0;
    int center=0, right = 0,maxlen=0,maxcenter;
    f(i, 2, strlen(s_new))
    {
        p[i] = i >= right ? 1 : min(right - i, p[2 * center - i]);
        while(s_new[i-p[i]]==s_new[i+p[i]]){
            p[i]++;
        }
        if(i+p[i]>right){
            right = i + p[i];
            center = i;
        }
        if(maxlen<p[i]){
            maxlen = p[i];
            maxcenter = i;
        }
    }
    /*输出结果*/
    pn(maxlen - 1);
    char *res = (char *)malloc(sizeof(char) * maxlen);
    j = 0;
    f(i, (maxcenter - maxlen) / 2, (maxcenter + maxlen) / 2 - 2)
        res[j++] = s[i];
    res[j] = '\0';
    printf("\n%s", res);
    return 0;
}

发表于 更新于 分类于 本文字数： 109 阅读时长 ≈ 1 分钟

四平方定理:任何一个正整数都可以表示成不超过四个整数的平方之和。

推论：满足四数平方和定理的数，必定满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int numSquares(int n)
{
    if (n % 8 == 7)
        return 4;
    for (int i = n; i % 4 == 0;)
    {
        i /= 4;
        if (i % 8 == 7)
            return 4;
    }
    if (sqr((int)sqrt(n)) == n)
        return 1;
    for (int i = 1; sqr(i) <= n; i++)
    {
        if (sqr((int)sqrt(n - sqr(i))) == n - sqr(i))
            return 2;
    }
    return 3;
}
0%