数组与字符串
目前处理子串的方法有：
（1）双指针；
（2）dp；
（3）分治；
1.1 实现一个算法，确定一个字符串的所有字符是否全都不同。假使不允许使用额外的数 据结构，又该如何处理？（第 46 页）
字符串是
- ASCII字符串
- 还是Unicode字符串
Solution:
布尔值的数组
位向量（bit vector)
将字符串中的每一个字符与其余字符进行比较。这种方法的时间复杂度为O(n 2 )，空间复 杂度为O(1)。
若允许修改输入字符串，可以在O(n log(n))时间里对字符串排序
1.3 给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另 一个字符串。（第 46 页）
Make Sure:
- 弄清楚变位词（anagram）
- 是否区分大小写
- 是否要考虑空白 字符
- 核实一下字符集的大小
Solution
- 解法 1：排序字符串
- 解法 2：检查两个字符串的各字符数是否相同
1.4 编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串尾部有足够的 空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组 实现，以便直接在数组上操作。）（第 46 页）
处理字符串操作问题时，常见做法是从字符串尾部开始编辑，从后往前反向操作。这种做法 很有用，因为字符串尾部有额外的缓冲，可以直接修改，不必担心会覆写原有数据。
进行两次扫描。第一次扫描先数出字符串中有多少空格， 从而算出最终的字符串有多长。第二次扫描才真正开始反向编辑字符串。检测到空格则将%20复 制到下一个位置，若不是空白，就复制原先的字符。
1.5 利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符 串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。（第 46 页）
- StringBuilder vs Direct Concat（o n^2）
1.6 给定一幅由N×N矩阵表示的图像，其中每个像素的大小为 4 字节，编写一个方法，将 图像旋转 90 度。不占用额外内存空间能否做到？（第 47 页）
要将矩阵旋转90度，最简单的做法就是一层一层进行旋转。对每一层执行环状旋转（circular rotation），将上边移到右边、右边移到下边、下边移到左边、左边移到上边。
那么，该如何交换这四条边？一种做法是把上面复制到一个数组中，然后将左边移到上边、 下边移到左边，等等。这需要占用O(N)内存空间，实际上没有必要。 更好的做法是按索引一个一个进行交换
1.7 编写一个算法，若M×N矩阵中某个元素为 0，则将其所在的行与列清零。（第 47 页）
乍一看，这个问题似乎很简单：直接遍历整个矩阵，只要发现值为零的元素，就将其所在的 行与列清零。不过这种方法有个陷阱：在读取被清零的行或列时，读到的尽是零，于是所在行与 列都得变成零。很快，整个矩阵的所有元素都会变为零。
避开这个陷阱的方法之一，是新建一个矩阵标记零元素位置。然后，在第二次遍历矩阵时将 零元素所在行与列清零。这种做法的空间复杂度为O(MN)。
真的需要占用O(MN)空间吗？不是的。既然打算将整行和整列清为零，因此并不需要准确记 录它是cell[2][4]（行2、列4），只需知道行2有个元素为零，列4有个元素为零。不管怎样，整 行和整列都要清为零，又何必要记录零元素的确切位置？
这里用两个数组分别记录包含零元素的所有行和列。然后，在 第二次遍历矩阵时，若所在行或列标记为零，则将元素清为零。
提高空间利用率，我们可以选用位向量替代布尔数组
1.8 假定有一个方法isSubstring，可检查一个单词是否为其他字符串的子串。给定两个字 符串s1 和s2，请编写代码检查s2 是否为s1 旋转而成，要求只能调用一次isSubstring。（比如， waterbottle是erbottlewat旋转后的字符串。）（第 47 页）
假定s2由s1旋转而成，那么，我们可以找出旋转点在哪。例如，若以wat对waterbottle旋 转，就会得到erbottlewat。在旋转字符串时，我们会把s1切分为两部分：x和y，并将它们重新 组合成s2。
s1 = xy = waterbottle
x = wat
y = erbottle
s2 = yx = erbottlewat
因此，我们需要确认有没有办法将s1切分为x和y，以满足xy = s1和yx = s2。不论x和y之 间的分割点在何处，我们会发现yx肯定是xyxy的子串。也即，s2总是s1s1的子串。