这个寒假时间有点长，每天找一道面试题做做，做完再做个总结。
给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，是否能变成另一个字符串。要求：时间复杂度为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;
}
}
};