第一章 数组与字符串

1.1 检查字符串中字符是否唯一？是否可以不使用额外的数据结构？

Trick

题目中并没有说明字符串中的字符范围，因此字符可能是：

1. 26个字母
2. ASCII字符（128个字符）
3. ASCII扩展字符（256个字符）
4. Unicode字符

对于前三种情况，可以用思路一。第四种情况可以使用思路二。

参考ASCII表

思路

1. 创建一个int或者bool的哈希表。哈希表的大小可以根据前三种情况而定，分别为26，128，256。每个字符可以根据其hash值映射到哈希表中。每循环一个字符先检查哈希表中的值是否为0或者false，如果是的话标明该字符第一次出现，因此修改其值为1或者true。如果循环到下一个字符时，其对应的哈希表中的值为1或者true，说明该字符在之前出现过，返回false。
2. 如果允许修改字符串，则对字符串进行排序。然后比较相邻两个字符。如果相邻字符相同，返回false。

1.2 检查两个字符串是否包含相同不同顺序的相同字符？

例子

// a,b字符串不相同，但是所包含的字符完全一样，只是顺序不同
String a = "abcd";
String b = "dcda";

思路

1. 创建两个个默认值为0的哈希表。假设字符为ASCII字符，哈希表长度等于128。分别循环a，b两个字符串。每次循环到一个字符，就在其对应的哈希表值上加1。然后比较两个哈希表中的值是否一样。
2. 与思路一类似，但是只使用一个哈希表。先对字符串a进行循环，然后根据a中出现的字符次数修改哈希表。然后循环字符串b，每循环到一个字符便在其对应的哈希表位置中减1。如果出现负数，返回false。最后循环整个哈希表，如果存在不为0的值，返回false。
3. 将两个字符串进行排序，然后同时循环比较两个字符串，如果在相同位置出现不同的字符，则返回false。

1.3 将字符串中的空格全部替换成"%20"。假设字符串尾部有足够空间储存新增字符，且已知字符串真实长度。

例子

// 输入原字符串及其长度
"Mr John Smith    ", 13
// 输出
"Mr%20John%20Smith"

Trick

1. 字符串末尾是包含空格的。是为了储存"%20"预留的长度单位。但是真实长度并不包含这些空格。同时我们并不知道预留长度有多长。
2. 如果从头循环字符串，并对空格进行替换会非常难以操作。因为要保证空格之后的字符不被替换的字符所覆盖，所以需要向右移动空格后的字符。
3. 需要提前得知替换完成后字符串的长度，不然可能会出现索引边界问题。

思路

替换字符串中的空格需要两次循环：

1. 第一次循环记录字符串中空格的数量。空格数 x 2 + 真实长度可以得到替换完成后的字符串的长度。
2. 第二次循环开始替换字符串中的空格。从头循环字符串会覆盖原有字符，而尾部有多余的预留长度，不必担心覆盖原有的字符。所以应该从尾部循环字符串。

1.4 检查一个字符串的全排列是否有回文字符串

例子

// 回文字符串(palindrome): 一个正反一样的字符串被称之为回文字符串
String a = "abcba";
String reverse_a = "abcba";

// 全排列(permutation): 一个字符串中字符可以出现的所有顺序
String b = "abc";
String[] permutation_b = {"abc", "acb", "bac", "bca", "cab", "cba"};

// 全排列回文字符串(palindrome permutation)
String example = "tactcoa";
String[] palindrome_permutations = {"tacocat", "atcocta"};

Trick

1. 因为回文字符串正反读都一样，那么除了中间的字符其他字符都应出现偶数次。
2. 如果没有中间字符，即，字符串长度为偶数，那么所有字符都应出现偶数次。

思路

创建一个默认值为0的哈希表。循环字符串，如果其对应哈希表值为0，则增加为1。如果为1，则减少为0。最后检查整个哈希表中的值，如果有大于一个以上的元素的值为1，返回false。

1.5 字符串上可以进行三种操作，分别为插入、删除、替换一个字符。判断是否可以只进行最多一次以上一种操作，使两个字符串中的一个字符串和另一个字符串相等？

例子

pale, ple -> true // 插入
pales, pale -> true // 插入 或 删除
pale, bale -> true // 替换
pale, pale -> true // 无需操作
pale, bake -> false // 只进行最多一次操作无法使得字符串1和字符串2相等

Trick

1. 插入和删除会增加或者减少字符串长度1位。
2. 替换不会修改字符串长度。
3. 如果字符串1可以通过插入一个字符，使其与字符串2相等。那么在字符串2上删除一个字符，可以使二者相等。所以插入和删除其实为同一种操作。

思路

• 通过以上观察，可以分为三种情况进行判定：
  1. 两个字符串长度相等，然后判断是否可以通过替换使得两个字符串相等
     • 检查两个字符串是否最多只有一个字符不同
  2. 两个字符串长度相差1，判断是否可以通过插入/删除使得两个字符串相等
     • 从头循环两个字符串，如果相同位置的字符串不同，则比较短字符串该位置的字符和长字符串下一位置的字符是否相同。如果还是不同，返回false
  3. 两个字符串长度相差大于1，返回false

1.6 压缩字符串。将aabbcccaa这样字符串压缩成a2b2c3a2的格式，如果原字符串比压缩后的字符串短，则返回原字符串。

Trick

• 注意循环索引不要超出字符串长度

思路

循环字符串，比较当前字符和下一个字符。如果二者不同则将该字符连同计数器值写入压缩后的字符串，并重置计数器变量。如果二者相同，则计数器变量加1。

1.7 将一个NxN的矩阵旋转90°。是否可以在不使用额外空间的情况下完成该操作？

rotate_img_90.png

思路

观察根据上图可知：

// 原图 行=>列
row 0 => col 2
row 1 => col 1
row 2 => col 0

// 原图 列=>行
col 0 => row 0
col 1 => row 1
col 2 => row 2

// 具体到每个单一元素
1 = (0,0) => (0,2)
2 = (0,1) => (1,2)
3 = (0,2) => (2,2)
4 = (1,0) => (0,1)
5 = (1,1) => (1,1)
6 = (1,2) => (2,1)
7 = (2,0) => (0,0)
8 = (2,1) => (1,0)
9 = (2,2) => (2,0)

通过以上观察可知：
1. 原坐标的列等于新坐标的行
2. 原坐标的行等于新坐标的(N-1-row)列。row为原坐标的行数，N为矩阵的行数和。例如，在一个4x4的矩阵中。行2在旋转90°后，会变为4-1-2 = 1，也就是第1列。

1.8 在MxN大小的矩阵中，如果包含值为0的元素。则将该元素所在的行、列全部重置为0.

思路

这道题乍看上去很简单。我们只需要注意循环矩阵中的元素，然后将元素为0的所在行、列重置为0即可。但是，这样会使得该行的下一个元素变为0。重复以上步骤之后，很快整个矩阵都会变为0，所以这个方法行不通。

因此，我们需要先记录所有值为0的元素的位置，然后再重置矩阵中的数值。

值得注意的是，保存所有值为0元素的位置时，我们并不需要创建一个新的矩阵（额外的O(MN)的空间）。只需要用两个数组分别保存元素所在的行和列即可。

1.9 假设现在有一个函数isSubstring可以用来检查一个字符串是不是另一个字符串的子串。要求在只使用该函数一次的情况下，检查String1是不是由String2旋转而成？

例子

"erbottlewat"就是由"waterbottle"旋转而成

"waterbottle"从第三个字符开始旋转，将其后的字符依次放置于字符串的左侧

思路

通过上面的描述，可以发现一个字符串是由两个部分组成的，假设这个两个部分分别为x，y：

x = "wat";
y = "erbottle";

// 将两个部分拼接在一起
x+y = "waterbottle"; // 原有字符串
// 旋转过后，两部分位置颠倒
y+x = "erbottlewat"; // 旋转后的字符串

// 想要检查一个字符串是否是由另一个字符串旋转而成
// 实际上要检查的就是是否能将y+x转换成x+y
// 通过将旋转后的字符串前后拼接在一起，可以发现中间的部分正是x+y
y+x+y+x = "erbottlewaterbottlewat"; 

根据上面的观察，只需要将旋转后的字符串前后拼接在一起，然后查看原字符串是否是其子串，即可判断String1是否是由String2旋转而成。