面试题集-数组和字符串
哈希表
尽管哈希表不能解决所有的问题，但是面试中的大部分问题能用它解决。在面试之前一定要好好准备下哈希表的使用和实现。
数组链表
数组链表(大小可动态变化的数组)在使用中能够根据需要扩大数组的容量，并且能够提供O(1)的随机访问效率。数组链表典型的一种实现方法就是：当达到数组上限，就将数组容量扩大一倍。虽然在扩大容量时候的时间复杂度为O(n)，但是这样情况都较少发生，所以总的时间开销可近似为O(1)。
字符串
问：下面这段代码的时间复杂度？
答：O(n^2)，这里的n为字符串sentence中的字符的个数。理由如下：每次你在向字符串sentence串中才追加一个数组的时候，就需要重新复制一次sentence中的字符，每次复制都需要从头到尾遍历一次sentence。这样的话把所有的单词追加到sentence中的时间复杂度为O(n^2)。
1.1设计算法判断一个字符串中字符都是否唯一的。如果不能使用额外的数据结构呢？
解答1.1：先假设字符串中的字符均为ASCII码(如果不是的可以增大存储空间，而算法的逻辑是相同的)。“假设”在你的面试中非常的重要。
算法的时间空间复杂度均为O(n)，n为字符串的长度。
采用bit序列来代替数组可以为我们进一步节省空间。这里我们需要假设字符串中的字符为'a'-'z'。这样只要用一个int型的变量就能记录字符是否出现了。
本题还有其他的解法：
1. 检查每一个字符在字符串中的出现次数，这样的方法时间复杂度为O(n^2),但是空间复杂度为0。
2.如果字符串中的内容可以破坏的话。我们可以将字符串中的字符排序(时间复杂度为O(nlogn))，然后遍历字符串中的某个字符相邻的字符时候相同。但是要注意有些排序算法是需要额外的存储空间的。
(C语言字符串：例如“abcd”字符串为5个字符，最后一个字符为/0用来表示字符串结束。)
解答1.2：
这个是面试的常见问题。如果你说你懂的话，就马上开始写代码吧。
1.3设计一个算法移除字符串中的重复字符，算法不使用额外缓冲。并对你的算法设计测试用例。注意：一两个变量使用当是OK的，但是复制整个数组就不行了。
解答1.3：
无字符串缓冲算法
1. 对每个字符判断是否为重复字符。
2. 重复字符直接跳过，非重复字符记录。
时间复杂度为O(n^2)
测试用例：
1. 无重复字符：abcd；
2. 全重复字符：aaaa；
3. 无效字符串：null；
4. 连续重复字符串：aaaabbbb；
5. 非连续重复字符串：abcabc；
字符串缓冲算法：
1. 无重复字符：abcd；
2. 全重复字符：aaaa；
3. 无效字符串：null；
4. 空字符串：empty
5. 连续重复字符串：aaaabbbb；
6. 非连续重复字符串：abcabc；
1.4写一个函数判断两个字符串是否使用相同的字符构成。
解答1.4：
本题有两种解法
法1 排序法
法2 计数法
1.5编写代码将字符串在中的空格替换为‘ ’
解答1.5：
算法流程：
1 遍历字符串，记录下有多少个空格；
2 从字符串尾部重新解析：
1.6给出一张图片，表示为NXN的居然，每个像素点为4字节。写一个函数实现将这张图片旋转90°。
解答1.6：
图片的旋转可以将像素划分成一圈一圈，然后从最外层一圈一圈上来旋转。旋转某一圈的某个元素的时候，相当于对应的上下左右依次交换。
1.7实现算法：在一个MxN的矩阵中，如果某一元素为0，则将其所在的行和列都置为零。
解答1.7：
乍一看题目，先遍历矩阵，出现0元素，就将所在的行列置零。但是这样的方法执行下来的话整个矩阵都变成了0了。
一个变通的方法，在另外一个MxN的矩阵中记录是否出现零的情况，然后根据记录对原来的矩阵中对相应的行列进行置零。可是这样方法的空间复杂度为O(MxN)。有没有改进的空间呢？
经过观察，其实我们只需要记录哪一列和哪一行需要置零即可。那么我们新的记录方法即为:使用两个数组rows[]和col[]来记录需要置零的行列。更具这样的方法算法代码如下：
1.8假设你已经有一个函数用来 isSubstring(s1,s2)用来判断字符串s1是否是字符串s2的子串。那么现在给你一个字符串s1和s2，让你判断s1是否是s2循环位移得到的。你的算法中只能调用一次isSubstring(比如“waterbottle”循环位移就可以得到"erbottlewat")。
解答1.8：
算法描述:
1 如果length(s1)！= length(s2) 返回 false
2将是s1和本身连接，得到新字符串s1'，调用isSubstring(s2,s1')判断s2是否为s1'的字符串。