编程之法----面试和算法心得

第1章 字符串

1.1 字符串的旋转

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

#include <stdio.h>void ReverseString(char *s, int from, int to);int main(int argc, const char * argv[]) {// insert code here...char s[] = "I am a student.";printf("%s\n", s);　　 // I am a student.int from = 0;int to = 0;for (int i = 0; i < sizeof(s); i ++) {if (s[i] == ' ' || s[i] == '\0') {to = i - 1;ReverseString(s, from, to);from = i + 1;}}printf("%s\n", s);　　// I ma a .tneduts
    ReverseString(s, 0, sizeof(s) - 2);printf("%s\n", s); 　　// student. a am Ireturn 0;
}void ReverseString(char *s, int from, int to) {while (from < to) {char t = s[from];s[from] = s[to];s[to] = t;from ++;to --;}
}

1.2 字符串的包含

给定一长字符串a和一短字符串b。请问，如何最快地判断出短字符串b中的所有字符是否都在长字符串a中？

为简单起见，假设输入的字符串只包含大写英文字母。下面举几个例子。

（1）如果字符串a是“ABCD”，字符串b是“BAD”，答案是true，因为字符串b中的字母都在字符串a中，或者说b是a的真子集。

（2）如果字符串a是“ABCD”，字符串b是“BAE”，答案是false，因为字符串b中的字母E不再字符串a中。

（3）如果字符串a是“ABCD”，字符串b是“AA”，答案是true，因为字符串b中的字母都在字符串a中。

#include <stdio.h>
#include <stdbool.h>bool StringContain(char *a, char *b);
int length(char *a);int main(int argc, const char * argv[]) {// insert code here...char a[] = "ABCDEFG";char b[] = "BGN";bool t = StringContain(a, b);printf("%d\n", t);return 0;
}int length(char *c) {int l = 0;while (c[l] != '\0') {l ++;}return l;
}bool StringContain(char *a, char *b) {int hash = 0;int alength = length(a);for (int i = 0; i < alength; i ++) {hash |= 1 << (a[i] - 'A');}int blength = length(b);for (int i = 0; i < blength; i++) {if ((hash & (1 << (b[i] - 'A'))) == 0) {return false;}}return true;
}