本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
125. 验证回文串
本题来自LeetCode：125. 验证回文串[1]
题目描述
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
题目分析
本题采用双指针，比较简单。
题目解答
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
int left = 0;
int right = s.length() - 1;
while(left right) {
// 左边的字母或数字字符
while(left right && !Character.isLetterOrDigit(s.charAt(left))) {
left ++;
}
// 右边的字母或数字字符
while(left right && !Character.isLetterOrDigit(s.charAt(right))) {
right --;
}
// 越界或者中间字符
if(left = right) {
break;
}
// 比较是否相等
if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left ++;
right --;
}
return true;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
680. 验证回文字符串 Ⅱ
本题来自LeetCode：680. 验证回文字符串 Ⅱ[2]
题目描述
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
题目分析
本题采用双指针，若遇到第一对不相等的字符时，跳过左边或者右边的字符，判断区间
[left + 1, right]或者
[left, right - 1]是否为回文字符串。
题目解答
class Solution {
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while(left right) {
if(s.charAt(left) == s.charAt(right)) {
left ++;
right --;
} else {
// 删除左边的字符或者右边的字符
return validPalindrome(s, left + 1, right) || validPalindrome(s, left, right - 1);
}
}
return true;
}
// 判断区间[left, right]是否为回文字符串
public boolean validPalindrome(String s, int left, int right) {
while(left right) {
if(s.charAt(left ++ ) != s.charAt(right --)) {
return false;
}
}
return true;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
387. 字符串中的第一个唯一字符
本题来自LeetCode：387. 字符串中的第一个唯一字符[3]
题目描述
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
注意事项：您可以假定该字符串只包含小写字母。
题目分析
由于字符串只包含小写字母，可以用一个长度为26的数组来存储字母出现的位置，可能存在以下三种情况：
题目解答
class Solution {
// 表示该字母没有出现
public static final int MISSING = -2;
// 表示该字母出现两次及以上
public static final int DUPLICATED = -1;
public int firstUniqChar(String s) {
int[] index = new int[26];
// 初始化
for(int i = 0; i 26; i ++) {
index[i] = MISSING;
}
for(int i = 0; i s.length(); i ++) {
int offset = s.charAt(i) - 'a';
if(index[offset] == MISSING) { // 未出现过
index[offset] = i;
} else if(index[offset] = 0) { // 已出现过一次
index[offset] = DUPLICATED;
}
}
int min = Integer.MAX_VALUE;
boolean found = false;
for(int i = 0; i 26; i ++) {
// 只出现过一次
if(index[i] = 0) {
found = true;
// 找到最小下标
min = Math.min(min, index[i]);
}
}
return found ? min : -1;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
451. 根据字符出现频率排序
本题来自LeetCode：451. 根据字符出现频率排序[4]
题目描述
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
"Aabb"
输出:
"bbAa"
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
解法一
题目分析
本题先统计出每个字符出现的频率，然后采用堆排序来解答，堆排序的具体知识请查看文章
题目解答
class Solution {
public String frequencySort(String s) {
MapCharacter, Integer map = new HashMap();
// 统计每个字符出现的频率
for(int i = 0; i s.length(); i ++) {
Integer count = map.getOrDefault(s.charAt(i), 0);
map.put(s.charAt(i), ++ count);
}
Map.EntryCharacter, Integer[] heap = new Map.Entry[map.size()];
int i = 0;
for(Map.EntryCharacter, Integer entry : map.entrySet()) {
heap[i ++] = entry;
}
// 小根堆排序
heapSort(heap);
// 输出结果
StringBuilder sb = new StringBuilder();
for(int j = 0; j heap.length; j ++) {
int count = heap[j].getValue();
char c = heap[j].getKey();
while(count--!= 0) {
sb.append(c);
}
}
return sb.toString();
}
public void heapSort(Map.EntryCharacter, Integer[] heap) {
// 建堆
for(int i = heap.length 1; i = 0; i --) {
adjust(heap, heap.length, i);
}
// 排序调整
for(int i = 1; i = heap.length; i ++) {
swap(heap, 0, heap.length - i);
adjust(heap, heap.length - i, 0);
}
}
public void adjust(Map.EntryCharacter, Integer[] heap, int length, int parent) {
int left = (parent 1) + 1;
int right = (parent 1) + 2;
int min = parent;
if(left length && heap[min].getValue() heap[left].getValue()) {
min = left;
}
if(right length && heap[min].getValue() heap[right].getValue()) {
min = right;
}
if(min != parent) {
swap(heap, min, parent);
adjust(heap, length, min);
}
}
public void swap(Map.EntryCharacter, Integer[] heap, int i, int j) {
Map.EntryCharacter, Integer temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
复杂度分析：
时间复杂度：
O(max(length, nlog(n)))，其中
length为字符串的长度，
n为字符的个数。
空间复杂度：
O(n)
解法二
题目解答
class Solution {
public String frequencySort(String s) {
// 出现相同频率的字符组成的字符串，比如aabbcc
MapInteger, StringBuilder countAndStringTable = new TreeMap();
// 记录字符出现的频率
MapCharacter, Integer charAndCountTable = new HashMap();
// 统计每个字符出现的频率
for(int i = 0; i s.length(); i ++) {
Integer count = charAndCountTable.getOrDefault(s.charAt(i), 0);
charAndCountTable.put(s.charAt(i), ++ count);
}
// 将相同频率的字符组装成字符串
for(Map.EntryCharacter, Integer entry : charAndCountTable.entrySet()) {
int count = entry.getValue();
char c = entry.getKey();
StringBuilder sb = countAndStringTable.get(count);
if(sb == null) {
sb = new StringBuilder();
countAndStringTable.put(count, sb);
}
while(count-- != 0) {
sb.append(c);
}
}
StringBuilder sb = new StringBuilder();
for(Map.EntryInteger, StringBuilder entry : countAndStringTable.entrySet()) {
sb.append(entry.getValue());
}
return sb.reverse().toString();
}
}
复杂度分析：
时间复杂度：
O(length)，其中
length为字符串的长度，
n为字符的个数。
空间复杂度：
O(n)
参考资料
验证回文字符串 Ⅱ: https://leetcode-cn.com/problems/valid-palindrome-ii
字符串中的第一个唯一字符: https://leetcode-cn.com/problems/first-unique-character-in-a-string
根据字符出现频率排序: https://leetcode-cn.com/problems/sort-characters-by-frequency
原文始发于微信公众号（xiaogan的技术博客）：
