字符串有关算法题

发表于

字符串

旋转字符串

  • 题目描述

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

  • 解答

可以先在原地进行旋转，例如ab旋转为ba，cdef旋转为fedc，此时变为bafedc，然后再旋转cdefab。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ReverseString(char* s,int from,int to)
{
    while (from < to) {
        char c = s[from];
        s[from++] = s[to];
        s[to--] = c;
    }
}

void LeftRotateString(char* s,int n,int m)
{
    m %= n;
    ReverseString(s, 0, m-1);
    ReverseString(s, m, n-1);
    ReverseString(s, 0, n-1);
}

字符串转换成整数

  • 题目描述

输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串"123"，输出整数123。 给定函数原型int StrToInt(const char *str) ，实现字符串转换成整数的功能，不能使用库函数atoi。

  • 解答

本题的关键是三个部分：防止空指针，避免无效字符，解决溢出问题

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
int StrToInt(const char* str)
{
    if (!str) return 0;
    static const int MAX_INT = (int)((unsigned)~0 >> 1);
    static const int MIN_INT = -(int)((unsigned)~0 >> 1) - 1;
    int n = 0;
    while (isspace(*str)) str++;

    int sign = 1;
    if (*str=='-'||*str=='+') {
        if (*str == '-') sign = -1;
        str++;
    }

    while (isdigit(*str))
    {
        int tmp = *str - '0';

        if (sign > 0 && (n>MAX_INT/10 || (n == MAX_INT/10 && tmp>MAX_INT%10) )) return MAX_INT;
        else if (sign < 0 && (n>(unsigned)MIN_INT/10 || (n == MIN_INT/10 && tmp>(unsigned)MIN_INT%10))) return MIN_INT;

        n = n * 10 + tmp;
        str++;
    }
    return n*sign;
}

回文判断

  • 题目描述

回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多有趣的回文诗。 那么，我们的第一个问题就是：判断一个字串是否是回文

  • 解答

用两个指针，分别指向首尾，进行遍历；或者两个指针从中间往两边遍历：

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
bool IsPalindrome1(const char *s, int n)
{
    if (!s||n<1) return false;
    const char *front, *last;

    front = s;
    last = s + n - 1;
    while (front < last) {
        if (*front != *last) return false;
        front++;
        last--;
    }
    return true;
}

bool IsPalindrome2(const char *s, int n)
{
    if (!s || n < 1) return false;
    if (s && n == 1) return true; 

    int mid = n / 2 - 1;
    const char *front, *last;

    front = s + mid;
    last = s + (n-1) - mid;

    while (front >= s) {
        if (*front != *last) return false;
        front--;
        last++;
    }

    return true;
}

字符串的全排列

  • 题目描述

输入一个字符串，打印出该字符串中字符的所有排列。 例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab 和 cba。

  • 解答

递归实现，每次固定首个字符，然后递归对后面的字符进行全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void CalcAllPermutation(char* perm, int from, int to)
{
    if (to < 1) return;
    if (from == to) {
        for (int i = 0; i <= to;i++)
            std::cout << perm[i];
        std::cout << std::endl;
    }
    else{
        for (int i = from; i<=to; i++)
        {
            std::swap(perm[i], perm[from]);
            CalcAllPermutation(perm, from+1, to);
            std::swap(perm[i], perm[from]);
        }
    }
}