练习题--字符串

这个寒假时间有点长，每天找一道面试题做做，做完再做个总结。

给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，是否能变成另一个字符串。要求：时间复杂度为O(n)。

思路：将两个字符串中的字符出现次数分别统计出来，再将26个字母出现的次数进行比较（这里为了简便，只考虑26个小写字母）。如果次数完全相同，则能转换；否则不能。
还有一种思路是先将两个字符串按ASCII码大小进行排序，将排序的结果进行比较即可，但由于使用了排序算法，时间复杂度至少为O(nlogn)。

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

bool isAnagram(string first, string second) {
    int* freqFirst = new int[26];
    // memset(freqFirst, 0, 26 * sizeof(int));
    for (int i = 0; i < 26; ++i) {
        freqFirst[i] = 0;
    }

    int* freqSecond = new int[26];
    memset(freqSecond, 0, 26 * sizeof(int));

    for (int i = 0; i < first.size(); ++i) {
        freqFirst[first[i] - 'a']++;
    }
    for (int i = 0; i < second.size(); ++i) {
        freqSecond[second[i] - 'a']++;
    }

    for (int i = 0; i < 26; ++i) {
        if (freqFirst[i] != freqSecond[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    string first, second;
    cin >> first >> second;

    if (isAnagram(first, second)) {
        cout << "The letters of them is the same!" << endl;
    } else {
        cout << "They don't have the same letters!" << endl;
    }

    return 0;
}

实现一个算法，确定一个字符串的所有字符是否全都不同。要求：时间复杂度为O(n)。

思路：首先我们假设这个字符串中全都是ASCII字符（如果不是需要另外讨论了），而ASCII字符集中总共有256个字符，所以如果长度大于256，则直接返回false。定义一个bool型大小为256的数组array，初始值均为false。遍历字符串中的字符，如果这个字符是第一次出现，那么令array[indexOfChar]等于true，如果这个字符出现过了，就返回false。当字符串遍历结束后，如果没有返回false，说明字符串中没有重复的字符，则返回true。

#include <iostream>
#include<string>
using namespace std;

bool isDiff(string str) {
    if (str.length() > 256) {
        return false;
    }

    bool array[256];
    for (int i = 0; i < 256; ++i) {
        array[i] = false;
    }

    for (int i = 0; i < str.length(); i++) {
        int indexOfChar = str[i];

        if (array[indexOfChar]) {
            return false;
        }
        array[indexOfChar] = true;
    }

    return true;
}

int main() {
    string s;
    getline(cin, s);
    cout << isDiff(s) << endl;

    return 0;
}

反转一个字符串。要求：不允许使用库函数

思路：将第一个字符与最后一个字符交换，将第二个字符与倒数第二个字符交换，...，到len / 2时结束。

#include <iostream>
#include <string>
using namespace std;

void swap(char& c1, char& c2) {
    char t = c1;
    c1 = c2;
    c2 = t;
}

string reverseStr(string s) {
    unsigned long len = s.length();
    for (int i = 0; i < len / 2; ++i) {
        swap(s[i], s[len - 1 - i]);
    }

    return s;
}

int main() {
    string s;
    getline(cin, s);
    cout << reverseStr(s) << endl;

    return 0;
}

给出一个长度不超过1000的字符串，判断它是不是回文(顺读，逆读均相同)的。

思路：判断第n个与倒数第n个字符是否相同，这里使用了一个tip，即不相同时直接返回false,循环结束时没有返回，说明是回文，则返回true。
（如果循环里面的判断语句是判断是否相同，则需要一个变量存储状态的改变，相对麻烦）

#include <iostream>
using namespace std;

bool isPalindrome(string s) {
  unsigned long len = s.length();

  for (int i = 0; i < len / 2; i++) {
      if (s[i] != s[len - 1 - i]) {
          return false;
      }
  }

  return true;
}

int main() {
  string s;
  while (cin >> s) {
      if (isPalindrome(s)) {
          cout << "Yes!" << endl;
      } else {
          cout << "No!" << endl;
      }
  }

  return 0;
}

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：

class Solution {
public:
    void replaceSpace(char *str, int length) {
        if (str == NULL || length < 0) return;
        
        int count = 0;
        for (int i = 0; i < length; ++i) {
            if (*(str + i) == ' ') {
                ++count;
            }
        }
        
        char *p1 = str + length - 1;
        char *p2 = str + length + 2 * count - 1;
        
        while (p1 != p2) {
            if (*p1 == ' ') {
                *p2-- = '0';
                *p2-- = '2';
                *p2-- = '%';
            } else {
                *p2-- = *p1;
            }
            --p1;
        }
    }
};