文章目录
剑指 Offer 58 - I. 翻转单词顺序
思路：先翻转整体，再翻转局部，边界条件什么的比较麻烦，需要多多注意
class Solution02 {
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int end = s.length() - 1;
int start = end;
StringBuilder sb = new StringBuilder();
while (start >= 0) {
// 搜索首个空格
while (start >= 0 && s.charAt(start) != ' ' ) {
start--;
}
// 添加单词
String word = s.substring(start + 1, end + 1);
if (start < 0) {
sb.append(word);
} else {
sb.append(word + " ");
}
// 跳过单词间空格或其他字符
while (start >= 0 && s.charAt(start) == ' ' ) {
start--;
}
end = start;
}
return sb.toString();
}
}
- 时间：O(n)
- 空间：O(n)
最长回文子串
思路一： 暴力循环，判断
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int beginIndex = 0;
int maxLen = 1;
// 时间复杂度：O(n^3)
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
// 长度判定是：（ j - i + 1 ）
if (isPalindrome(s, i, j) && (j - i + 1) > maxLen) {
beginIndex = i;
maxLen = j - i + 1;
}
}
}
return s.substring(beginIndex, beginIndex + maxLen);
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
- 空间：O(1)
- 时间：O(n^3)
思路二： 在判断是否是回文的时候，通过从中心点开始去判断。
//（2） 中心扩散
class Solution02 {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int beginIndex = 0;
int maxLen = 1;
// 时间复杂度：O(n^2 * logN)
for (int i = 0; i < len; i++) {
// 奇数
int oddLen = expandAroundCenter(s, i, i);
// 偶数
int evenLen = expandAroundCenter(s, i, i + 1);
int tmpLen = Math.max(oddLen, evenLen);
if (tmpLen > maxLen) {
maxLen = tmpLen;
// 记下这种格式
beginIndex = i - (tmpLen - 1) / 2;
}
}
return s.substring(beginIndex, beginIndex + maxLen);
}
private int expandAroundCenter(String s, int i, int i1) {
// 注意 len 应该初始化为0，而不是 1，因为 偶数的时候，不是从1 开始的
int len = 0;
int left, right;
if (i == i1) {
left = i - 1;
right = i + 1;
len = 1;
} else {
left = i;
right = i1;
}
// 中心扩散即可
while (left >= 0 && right <= s.length() - 1) {
if (s.charAt(left) != s.charAt(right)) {
return len;
}
len += 2;
left--;
right++;
}
return len;
}
}
- 时间：On^2)
- 空间：O(1)
思路三： 动态规划
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
int beginIndex = 0;
int maxLen = 1;
// 时间复杂度：O(n^2)
char[] charArray = s.toCharArray();
// 按列填写
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
// 不相等，直接就表示不是回文
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
// 相等 且 长度小于 3 就是 true
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && (j - i + 1) > maxLen) {
maxLen = j - i + 1;
beginIndex = i;
}
}
}
return s.substring(beginIndex, beginIndex + maxLen);
}
}
- 时间：O(n^2)
- 空间：O(n^2)
求两个字符串的最大公共子串(一看到两个字符串的“最值”问题，一般想到二维dp)
https://leetcode-cn.com/problems/qJnOS7/
思路一：两层for循环，如果有相同的字符，就继续往下进行比较，直到字符不同。然后得出最大公共子串
public class Solution {
/**
* longest common substring
*
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String LCS(String str1, String str2) {
if (str1 == null || "".equals(str1) || str2 == null || "".equals(str2)) {
return "";
}
char[] charArr1 = str1.toCharArray();
char[] charArr2 = str2.toCharArray();
int maxLen = 0;
int maxLenEndIndex = 0;
for (int i = 0; i < charArr1.length; i++) {
for (int j = 0; j < charArr2.length; j++) {
if (charArr1[i] == charArr2[j]) {
int tempIndex1 = i;
int tempIndex2 = j;
int tempMax = 0;
while (tempIndex1 < charArr1.length && tempIndex2 < charArr2.length
&& charArr1[tempIndex1] == charArr2[tempIndex2]) {
tempIndex1++;
tempIndex2++;
tempMax++;
}
if (tempMax > maxLen) {
maxLen = tempMax;
maxLenEndIndex = tempIndex1;
}
}
}
}
return str1.substring(maxLenEndIndex - maxLen, maxLenEndIndex);
}
}
- 时间：两层循环，设定m、n分别是字符串长度的话，最大长度maxLenth，时间复杂度为
O(m * n * maxLength) - 空间：O(1)
思路二：(代码略)
对于str1中每个元素，都循环一次str2中所有元素有点浪费。
- 可以用str2的元素集合构建一个map，key是元素值，value是元素的index。
- 考虑到可能多个index同样的值，value可以设置为多个index用逗号分隔的字符串。
- 这样以str1元素为驱动元素的话，只需要在map中找是否有对应的元素，有的话取出他们在str2中的索引列表。
- 这样好处就可以通过map直接定位元素在str2中位置，不必循环比较str2中元素。
思路三：
定义 dp[i][j] 表示字符串 str1 中第 i 个字符和 str2 种第 j 个字符为最后一个元素所构成的最长公共子串。如果要求 dp[i][j]，也就是 str1 的第 i 个字符和 str2 的第 j 个字符为最后一个元素所构成的最长公共子串，我们首先需要判断这两个字符是否相等。
-
如果不相等，那么他们就不能构成公共子串，也就是
dp[i][j]=0; -
如果相等，我们还需要计算前面相等字符的个数，其实就是dp[i-1][j-1]，所以
dp[i][j]=dp[i-1][j-1]+1;
public class Solution {
public String LCS(String str1, String str2) {
if (str1 == null || "".equals(str1) || str2 == null || "".equals(str2)) {
return "";
}
int[][] dp = new int[str1.length() + 1][str2.length() + 1];
int maxLen = 0;
int maxLenEndIndex = 0;
// 初始化第一行，第一列都为0，以便后续使用
for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
if (str1.charAt(i) == str2.charAt(j)) {
// DP 方程
dp[i + 1][j + 1] = dp[i][j] + 1;
if (dp[i + 1][j + 1] > maxLen) {
maxLen = dp[i + 1][j + 1];
maxLenEndIndex = i;
}
} else {
//递推公式，两个字符不相等的情况
dp[i + 1][j + 1] = 0;
}
}
}
return str1.substring(maxLenEndIndex - maxLen + 1, maxLenEndIndex + 1);
}
}
- 时间：O(m*n)
- 空间：O(m*n)
剑指 Offer II 095. 最长公共子序列（类似的最长子序列等等都是DP的经典解法）
https://leetcode-cn.com/problems/qJnOS7/
思路见：https://www.bilibili.com/video/BV14A411v7mP?spm_id_from=333.337.search-card.all.click
class Solution {
public int longestCommonSubsequence(String str1, String str2) {
if (str1 == null || "".equals(str1) || str2 == null || "".equals(str2)) {
return 0;
}
int[][] dp = new int[str1.length() + 1][str2.length() + 1];
int maxLen = 0;
for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
if (str1.charAt(i) != str2.charAt(j)) {
dp[i + 1][j + 1] = Math.max(dp[i][j+1], dp[i+1][j]);
} else {
dp[i + 1][j + 1] = dp[i][j] + 1;
}
maxLen = Math.max(maxLen, dp[i + 1][j + 1]);
}
}
return maxLen;
}
}
- 时间：O(m*n)
- 空间：O(m*n)
剑指 Offer II 063. 替换单词
https://leetcode-cn.com/problems/UhWRSj/
思路：
剑指 Offer 45. 把数组排成最小的数
思路：排序方法使用快排即可
class Solution {
public String minNumber(int[] nums) {
if (nums == null) {
return null;
}
quick_sort(nums, 0, nums.length - 1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < nums.length; i++) {
sb.append(nums[i]);
}
return sb.toString();
}
void quick_sort(int[] nums, int l, int r) {
if (l >= r)
return;
int q = partition(nums, l, r);
quick_sort(nums, l, q - 1);
quick_sort(nums, q + 1, r);
}
int partition(int[] nums, int l, int r) {
// 选择最后一个元素为 基准点
int k = l, pivot = nums[r];
for (int i = l; i < r; i++) {
// 小于 基准点 pivot
if (compareFun(nums[i], pivot)) {
swap(nums, i, k++);
}
}
swap(nums, k, r);
return k;
}
boolean compareFun(int x, int y) {
String xY = new StringBuilder().append(x).append(y).toString();
String yX = new StringBuilder().append(y).append(x).toString();
return xY.compareTo(yX) < 0;
}
void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
}
滑动窗口模板与思路
//模板
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray())
need.put(c,need.getOrDefault(c,0)+1);
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
System.out.println("window: ["+left+","+ right+")");
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
76. 最小覆盖子串
https://leetcode-cn.com/problems/minimum-window-substring/
class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null) {
return "";
}
int sLen = s.length();
int tLen = t.length();
if (sLen == 0 || tLen == 0 || sLen < tLen) {
return "";
}
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
// 词频数组
int[] winFreq = new int[128];
int[] tFreq = new int[128];
for (char ch : tChars) {
tFreq[ch]++;
}
int left = 0;
int right = 0;
// 表示：滑动窗口内部包含了 T 中字符的个数，而不是滑动窗口的长度。
// 窗口中单个字符个数等于 T 中对应的字符个数的时候就不再增加。
int distance = 0;
int begin = 0;
int minLen = sLen + 1;
while (right < sLen) {
//如果右边的字符在 t 中没有出现
if (tFreq[sChars[right]] == 0) {
right++;
continue;
}
// @TODO 核心
if (winFreq[sChars[right]] < tFreq[sChars[right]]) {
distance++;
}
// 第一次在 t 中出现
winFreq[sChars[right]]++;
right++;
//已经包含了 t 中所有的字符了
while (distance == tLen) {
if (right - left < minLen) {
minLen = right - left;
begin = left;
}
//如果左边的字符在 t 中没有出现
if (tFreq[sChars[left]] == 0) {
left++;
continue;
}
// @TODO 核心
if (winFreq[sChars[left]] == tFreq[sChars[left]]) {
distance--;
}
// 词频数组减少
winFreq[sChars[left]]--;
left++;
}
}
if (minLen == sLen + 1) {
return "";
}
return s.substring(begin, begin + minLen);
}
}
- 时间：O( s+t)
- 空间：O(s+t)
剑指 Offer II 016. 不含重复字符的最长子串（里面有滑动窗口的具体实现）
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
思路：
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
if (n <= 1) return n;
int maxLen = 1;
// l 表示最左 r 表示最右，实现一个滑动窗口
int left = 0, right = 0;
// 字符：下标位置
Map<Character, Integer> window = new HashMap<>();
while (right < n) {
char rightChar = s.charAt(right);
// 想想 abba 的情况。 left 必须取大值
// 当在整个窗口内部存在重复元素时，需要将left移动到重复字符的后面
if (window.containsKey(Character.valueOf(rightChar))) {
left = Math.max(window.get(rightChar) + 1, left);
}
maxLen = Math.max(maxLen, right - left + 1);
window.put(rightChar, right);
right++;
}
return maxLen;
}
}
- 时间：O(n)
- 空间：O(n)
剑指 Offer II 018. 有效的回文
思路：
- 先遍历一遍将所有的非字母数字，以及大写转换为小写，然后顺序逆序进行比较即可
- 双指针思路：见代码
class Solution {
boolean isRange(char ch) {
return ch <= 'z' && ch >= 'a';
}
boolean isRange02(char ch) {
return ch <= 'Z' && ch >= 'A';
}
boolean isRange03(char ch) {
return ch <= '9' && ch >= '0';
}
public boolean isPalindrome(String s) {
if (s == null) {
return false;
}
int len = s.length();
if (len == 1) {
return true;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!isRange(ch) && !isRange02(ch) && !isRange03(ch)) {
continue;
} else {
if (isRange02(ch)) {
ch = (char) (ch + 32);
// ch = (char) (ch + ('a' - 'A'));
}
sb.append(ch);
}
}
//直接将 s 进行转换
s = sb.toString();
for (int i = 0, j = s.length()-1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}
// 2. 双指针
class Solution {
public boolean isPalindrome(String s) {
if (s == null) {
return false;
}
int len = s.length();
if (len == 1) {
return true;
}
// 双指针思路代码结构一般都是这样(三个 while )，以后可参考~
int left = 0;
int right = len - 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 || Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
//注意指针需要变化
left++;
right--;
}
return true;
}
}