数组与字符串
数组与字符串是最基础的数据结构，面试中经常考察对字符串的遍历、比较、转换等操作，以及对矩阵的变换处理。
面试题 01.01. 判定字符是否唯一
题目描述
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
输入: s = "leetcode"
输出: false
示例 2：
输入: s = "abc"
输出: true
限制：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果不使用额外的数据结构，会很加分。
解题思路
方法一：使用位运算（推荐）
由于题目说明字符串只包含小写字母，最多26个不同字符，可以使用一个 int 类型的变量作为位图来记录出现过的字符。每个比特位对应一个字母。
方法二：使用Set集合
遍历字符串，使用Set记录出现过的字符，如果遇到重复字符则返回false。
Java 代码实现
位运算解法：
class Solution {
public boolean isUnique(String astr) {
int mask = 0;
for (int i = 0; i < astr.length(); i++) {
int bit = astr.charAt(i) - 'a';
if ((mask & (1 << bit)) != 0) {
return false;
}
mask |= (1 << bit);
}
return true;
}
}
Set解法：
class Solution {
public boolean isUnique(String astr) {
Set<Character> set = new HashSet<>();
for (char c : astr.toCharArray()) {
if (!set.add(c)) {
return false;
}
}
return true;
}
}
面试题 01.02. 判定是否互为字符重排
题目描述
给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
示例 1：
输入: s1 = "abc", s2 = "bca"
输出: true
示例 2：
输入: s1 = "abc", s2 = "bad"
输出: false
说明：
0 <= len(s1) <= 1000 <= len(s2) <= 100
解题思路
两个字符串互为字符重排，意味着它们包含相同的字符，且每个字符的出现次数相同。
方法一：排序比较
将两个字符串排序后比较是否相等。
方法二：计数法（推荐）
使用数组统计每个字符出现的次数，比较两个字符串的字符计数是否相同。
Java 代码实现
计数法：
class Solution {
public boolean CheckPermutation(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
int[] count = new int[26];
for (int i = 0; i < s1.length(); i++) {
count[s1.charAt(i) - 'a']++;
count[s2.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) {
return false;
}
}
return true;
}
}
排序法：
class Solution {
public boolean CheckPermutation(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
return Arrays.equals(c1, c2);
}
}
面试题 01.03. URL化
题目描述
URL化。编写一种方法，将字符串中的空格全部替换为 %20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的"真实"长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
示例 1：
输入："Mr John Smith ", 13
输出："Mr%20John%20Smith"
示例 2：
输入：" ", 5
输出："%20%20%20%20%20"
提示：
- 字符串长度在
[0, 500000]范围内。
解题思路
由于空格替换为 %20 后长度增加2，可以先统计空格数量，计算新字符串长度，然后从后向前填充字符。这样可以避免从前往后移动字符的开销。
Java 代码实现
class Solution {
public String replaceSpaces(String S, int length) {
char[] chars = S.toCharArray();
int spaceCount = 0;
for (int i = 0; i < length; i++) {
if (chars[i] == ' ') {
spaceCount++;
}
}
int newLength = length + spaceCount * 2;
int j = newLength - 1;
for (int i = length - 1; i >= 0; i--) {
if (chars[i] == ' ') {
chars[j--] = '0';
chars[j--] = '2';
chars[j--] = '%';
} else {
chars[j--] = chars[i];
}
}
return new String(chars, 0, newLength);
}
}
面试题 01.04. 回文排列
题目描述
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。回文串不一定是字典当中的单词。
示例 1：
输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）
解题思路
一个字符串能够排列成回文串的条件是：最多只有一个字符出现奇数次。可以使用位运算或计数数组来统计字符出现次数的奇偶性。
Java 代码实现
位运算解法：
class Solution {
public boolean canPermutePalindrome(String s) {
int mask = 0;
for (char c : s.toCharArray()) {
mask ^= (1 << (c - 'a'));
}
return mask == 0 || (mask & (mask - 1)) == 0;
}
}
计数解法：
class Solution {
public boolean canPermutePalindrome(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
int oddCount = 0;
for (int c : count) {
if (c % 2 == 1) {
oddCount++;
}
}
return oddCount <= 1;
}
}
面试题 01.05. 一次编辑
题目描述
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1：
输入:
first = "pale"
second = "ple"
输出: True
示例 2：
输入:
first = "pales"
second = "pal"
输出: False
解题思路
首先判断两个字符串的长度差，如果超过1则直接返回false。然后使用双指针遍历两个字符串：
- 如果长度相等，只能进行替换操作
- 如果长度差1，可以进行插入或删除操作
Java 代码实现
class Solution {
public boolean oneEditAway(String first, String second) {
int m = first.length(), n = second.length();
if (Math.abs(m - n) > 1) {
return false;
}
int i = 0, j = 0;
int count = 0;
while (i < m && j < n) {
if (first.charAt(i) == second.charAt(j)) {
i++;
j++;
} else {
if (count == 1) {
return false;
}
count++;
if (m > n) {
i++;
} else if (m < n) {
j++;
} else {
i++;
j++;
}
}
}
return true;
}
}
面试题 01.06. 字符串压缩
题目描述
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串 aabcccccaaa 会变为 a2b1c5a3。若"压缩"后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
示例 1：
输入："aabcccccaaa"
输出："a2b1c5a3"
示例 2：
输入："abbccd"
输出："abbccd"
解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
解题思路
遍历字符串，统计连续相同字符的个数，将字符和计数拼接成新字符串。最后比较压缩后的字符串长度与原字符串长度，返回较短的那个。
Java 代码实现
class Solution {
public String compressString(String S) {
if (S == null || S.length() == 0) {
return S;
}
StringBuilder sb = new StringBuilder();
int count = 1;
char prev = S.charAt(0);
for (int i = 1; i < S.length(); i++) {
if (S.charAt(i) == prev) {
count++;
} else {
sb.append(prev).append(count);
prev = S.charAt(i);
count = 1;
}
}
sb.append(prev).append(count);
return sb.length() < S.length() ? sb.toString() : S;
}
}
面试题 01.07. 旋转矩阵
题目描述
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。不占用额外内存空间能否做到？
示例 1：
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
解题思路
方法一：两次翻转
先沿对角线翻转，再沿垂直中线翻转。
方法二：四角交换
对于矩阵中的每个位置 (i, j)，旋转后变为 (j, n-1-i)。可以四个角为一组进行交换。
Java 代码实现
两次翻转：
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
}
四角交换：
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - 1 - i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = temp;
}
}
}
}
面试题 01.08. 零矩阵
题目描述
编写一种算法，若 M × N 矩阵中某个元素为 0，则将其所在的行与列清零。
示例 1：
输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]
解题思路
使用两个标记数组分别记录哪些行和哪些列需要被清零。首先遍历矩阵，记录所有0的位置，然后根据记录清零对应的行和列。
可以使用矩阵的第一行和第一列作为标记数组来节省空间。
Java 代码实现
使用额外空间：
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}
O(1)空间：
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (firstRowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (firstColZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}
面试题 01.09. 字符串轮转
题目描述
字符串轮转。给定两个字符串 s1 和 s2，请编写代码检查 s2 是否为 s1 旋转而成（比如，waterbottle 是 erbottlewat 旋转后的字符串）。
示例 1：
输入：s1 = "waterbottle", s2 = "erbottlewat"
输出：True
示例 2：
输入：s1 = "aa", s2 = "aba"
输出：False
解题思路
如果 s2 是 s1 的旋转字符串，那么 s2 一定是 s1 + s1 的子串。例如 s1 = "waterbottle"，s1 + s1 = "waterbottlewaterbottle"，s2 = "erbottlewat" 是其子串。
Java 代码实现
class Solution {
public boolean isFlipedString(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
return (s1 + s1).contains(s2);
}
}