string题目

发表于   |   分类于

Index

1
2
3
4
5
计算器
旋转字符串(rotate string) // 来自[July](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md)
字符串转换成整数
palindrome
最长回文

Notes

  1. string类里面可以用append(), push_back(), += 来追加字符，push_back()参数为char, length增加1; append和 +=可以增加string和char.
  2. 可以用to_string()转换numerical类型到string类型, return是一个representation而不是copy，反过来可以用atoi，但是只return一个value.
  3. string转换相应数字可以用”number” - “0”，利用ASCII码转化.

1. 实现一个计算器

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.

Some examples:
“3+2*2” = 7
“ 3/2 “ = 1
“ 3+5 / 2 “ = 5
Note: Do not use the eval built-in library function.

思路：这题有乘除，那么就牵扯到了运算优先级的问题，但是这题没有括号，估计再出一道的话就该加上括号了(记得再写一道带括号的)。不管那么多，这道题先按木有有括号来处理，由于存在运算优先级，我们采取的措施是使用一个栈保存数字，如果该数字之前的符号是加或减，那么把当前数字压入栈中，注意如果是减号，则加入当前数字的相反数，因为减法相当于加上一个相反数。如果之前的符号是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中，那么完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了。代码如下：

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
class Solution {
public:
    int calculate(string s) {
        int res = 0, d = 0;
        char sign = '+';
        stack<int> nums;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] >= '0'){               // 注意这个条件
                d = d * 10 + s[i] - '0';   //从左边读入数据, d为读入数据，如果数据为INT_MAX，则会溢出，要不要用long?
            }
            if((s[i] < '0' && s[i] != ' ') || i == s.size() - 1){
                if(sign == '+') nums.push(d);
                if(sign == '-') nums.push(-d);
                if(sign == '*' || sign == '/'){
                    int tmp = sign == '*' ? nums.top() * d : nums.top() / d;
                    nums.pop();
                    nums.push(tmp);
                } 
                sign = s[i];               //使得数据读取进行下去
                d = 0;
            }
        }
        while(!nums.empty()){
            res += nums.top();
            nums.pop();
        }
        return res;
    }
};

1. 旋转字符串

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

1. brute force

初看此题，可能最先想到的方法是按照题目所要求的，把需要移动的字符一个一个地移动到字符串的尾部，如此我们可以实现一个函数LeftShiftOne(char* s, int n) ，以完成移动一个字符到字符串尾部的功能，代码如下所示：
(思考，如果是反着旋转呢？)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void LeftShiftOne(char* s, int n)
{
    char temp = s[0];          //save the first element
    for(int i = 0; i < n; i++){
        s[i + 1] = s[i];
    }
    s[n - 1] = temp;
}
void LeftRotateString(char* s, int m)
{
    while(m--){
        LeftShiftOne(s, n);
   }
}

针对长度为n的字符串来说，假设需要移动m个字符到字符串的尾部，那么总共需要 mn 次操作，同时设立一个变量保存第一个字符，如此，时间复杂度为O(m n)，空间复杂度为O(1)，空间复杂度符合题目要求，但时间复杂度不符合，所以，我们得需要寻找其他更好的办法来降低时间复杂度。

2. 三步反转法

对于这个问题，换一个角度思考一下。
将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X=”abc”，那么X^T=”cba”），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。
例如，字符串 abcdef ，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可：
首先将原字符串分为两个部分，即X:abc，Y:def；
将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。
反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ReverseString(char* s, int from, int to)
{
    while(from < to){
        char temp = s[from];
        s[from++] = s[to];
        s[to--] = t; 
        /*或者
        swap(s[from++], s[to--]); */
    }
}
void LeftRotateString(char* s, int n, int m)
{
    m %= n;  //左移大于n位，和%n是等价的
    ReverseString(s, 0, m - 1); //反转［0, m - 1］
    ReverseString(s, m, n - 1); //反转 [m, n - 1]
    ReverseString(s, 0, n - 1); //反转 [0, n - 1]
}

举一反三

1、链表翻转。给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。

2、编写程序，在原字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。

3、单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”。

2. 字符串包含

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？
为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B)
比如，如果是下面两个字符串：
String 1：ABCD
String 2：BAD
答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。
如果是下面两个字符串：
String 1：ABCD
String 2：BCE
答案是false，因为字符串String2里的E字母不在字符串String1里。
同时，如果string1：ABCD，string 2：AA，同样返回true。

字符串转换整数 ‘string’ - ‘0’，因为’0’对应的ASCII为48，整数字符串减去48得到相应的整数。另外

大小写字母的转换：先看ASCII码：a~z是97~122的二进制，而A~Z是65~90的二进制编码，于是我们就得出：大写字母=小写字母-32 ；这个公式了。当然这里的32我也可以这么写‘Z’=‘z’-‘空格’。因为空格的ASCII码是32对应的二进制编码。

比如

字符串转换成整数

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

1
2
3
4
5
6
7
8
9
10
11
int StrToInt(const char *str)
{
    int n = 0;
    while (*str != 0)
    {
        int c = *str - '0';
        n = n * 10 + c;
        ++str;
    }
    return n;
}

显然，上述代码忽略了以下细节：

空指针输入：输入的是指针，在访问空指针时程序会崩溃，因此在使用指针之前需要先判断指针是否为空。
正负符号：整数不仅包含数字，还有可能是以’+’或’-‘开头表示正负整数，因此如果第一个字符是’-‘号，则要把得到的整数转换成负整数。
非法字符：输入的字符串中可能含有不是数字的字符。因此，每当碰到这些非法的字符，程序应停止转换。
整型溢出：输入的数字是以字符串的形式输入，因此输入一个很长的字符串将可能导致溢出。

字符串转换成整数，完整的参考代码为

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
int StrToInt(const char* str)
{
    static const int MAX_INT = (int)((unsigned)~0 >> 1);
    static const int MIN_INT = -(int)((unsigned)~0 >> 1) - 1;
    unsigned int n = 0;
    //判断是否输入为空
    if (str == 0)
    {
        return 0;
    }
    //处理空格
    while (isspace(*str))
        ++str;
    //处理正负
    int sign = 1;
    if (*str == '+' || *str == '-')
    {
        if (*str == '-')
            sign = -1;
        ++str;
    }
    //确定是数字后才执行循环
    while (isdigit(*str))
    {
        //处理溢出
        int c = *str - '0';
        if (sign > 0 && (n > MAX_INT / 10 || (n == MAX_INT / 10 && c > MAX_INT % 10)))
        {
            n = MAX_INT;
            break;
        }
        else if (sign < 0 && (n >(unsigned)MIN_INT / 10 || (n == (unsigned)MIN_INT / 10 && c > (unsigned)MIN_INT % 10)))
        {
            n = MIN_INT;
            break;
        }
        //把之前得到的数字乘以10，再加上当前字符表示的数字。
        n = n * 10 + c;
        ++str;
    }
    return sign > 0 ? n : -n;

举一反三

实现string到double的转换
分析：此题虽然类似于atoi函数，但毕竟double为64位，而且支持小数，因而边界条件更加严格，写代码时需要更加注意。

回文判断

题目描述
回文，英文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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
bool IsPalindrome(const char *s, int n)
{
    // 非法输入
    if (s == NULL || n < 1)
    {
        return false;
    }
    const char* front,*back;
    // 初始化头指针和尾指针
    front = s;
    back = s+ n - 1;
    while (front < back)
    {
        if (*front != *back)
        {
            return false;
        }
        ++front;
        --back;
    }
    return true;
}
解法二
上述解法一从两头向中间扫描，那么是否还有其它办法呢？我们可以先从中间开始、然后向两边扩展查看字符是否相等。参考代码如下：
```bash
bool IsPalindrome2(const char *s, int n)
{
    if (s == NULL || n < 1)
    {
        return false;
    }
    const char* first, *second;
    // m定位到字符串的中间位置      
    int m = ((n >> 1) - 1) >= 0 ? (n >> 1) - 1 : 0; 
    first = s + m;
    second = s + n - 1 - m;
    while (first >= s)
    {
        if (*first!= *second)
        {
            return false;
        }
        --first;
        ++second;
    }
    return true;
}

最长回文

最容易想到的办法是枚举所有的子串，分别判断其是否为回文。这个思路初看起来是正确的，但却做了很多无用功，如果一个长的子串包含另一个短一些的子串，那么对子串的回文判断其实是不需要的。
解法一

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
int LongestPalindrome(const char *s, int n)
{
    int i, j, max,c;
    if (s == 0 || n < 1)
        return 0;
    max = 0;
    for (i = 0; i < n; ++i) { // i is the middle point of the palindrome  
        for (j = 0; (i - j >= 0) && (i + j < n); ++j){ // if the length of the palindrome is odd  
            if (s[i - j] != s[i + j])
                break;
            c = j * 2 + 1;
        }
        if (c > max)
            max = c;
        for (j = 0; (i - j >= 0) && (i + j + 1 < n); ++j){ // for the even case  
            if (s[i - j] != s[i + j + 1])
                break;
            c = j * 2 + 2;
        }
        if (c > max)
            max = c;
    }
    return max;
}

解法二 Manacher算法
首先通过在每个字符的两边都插入一个特殊的符号，将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。

此外，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。此外，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。
以字符串12212321为例，插入#和$这两个特殊符号，变成了 S[] = “$#1#2#2#1#2#3#2#1#”，然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左或向右扩张的长度（包括S[i]）。

比如S和P的对应关系：

S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
可以看出，P[i]-1正好是原字符串中最长回文串的总长度，为5。

接下来怎么计算P[i]呢？Manacher算法增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。得到一个很重要的结论：

如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i)

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
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);
 
  ret += "#$";
  return ret;
}
 
string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 1; i < n-1; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)
    
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
    
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;
 
    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
 
  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 1; i < n-1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;
  
  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}

另外附上九章算法的binary search模版
// Comment
public class Solution {
/**

 * @param array source array
 * @param target target to search
 * @return the first occurrence position of target 
 */
public int binarySearch(int[] A, int target) {
    if (A.length == 0) {
        return -1;
    }

    int start = 0;
    int end = A.length - 1;
    int mid;

    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
            end = mid;
        } else if (A[mid] < target) {
            start = mid;
        } else if (A[mid] > target) {
            end = mid;
        }
    }

    if (A[start] == target) {
        return start;
    }
    if (A[end] == target) {
        return end;
    }

    return -1;
}

}

Attention:
1) Why start + 1 < end?
There might be deadlock if use start < end, for example, if start = 1, end = 2, => mid = 1. Then, it will be a deadlock.(To solve this problem, mid + 1, for some problems)

  1. Related Problems

2.1 Search for Insertion Position
2.2 Search for a Range
2.3 Search in Rotated Sorted Array
写好不容易，有细节，算法性强，类似分糖果题。
用二分法的变种做，循环左移。