双指针

1.验证回文串

1.答案

package com.sunxiansheng.classic150.g1;/*** Description: 125. 验证回文串** @Author sun* @Create 2024/12/19 15:03* @Version 1.0*/
public class t125 {public static boolean isPalindrome(String s) {// 直接双指针int left = 0;int right = s.length() - 1;while (left < right) {// 获取左右字符char leftChar = s.charAt(left);char rightChar = s.charAt(right);// 如果不是数字和字母，就直接下一位if (!Character.isDigit(leftChar) && !Character.isLetter(leftChar)) {left++;continue;}if (!Character.isDigit(rightChar) && !Character.isLetter(rightChar)) {right--;continue;}// 大写转换小写leftChar = Character.isUpperCase(leftChar) ? Character.toLowerCase(leftChar) : leftChar;rightChar = Character.isUpperCase(rightChar) ? Character.toLowerCase(rightChar) : rightChar;// 到这里左右都是数字字母字符了，可以直接比较if (leftChar != rightChar) {return false;}left++;right--;}return true;}public static void main(String[] args) {System.out.println("isPalindrome(\"A man, a plan, a canal: Panama\") = " + isPalindrome("A man, a plan, a canal: Panama"));}
}

2.思路

就是直接使用双指针，如果不是数字和字母，就直接下一位，大写转换小写，然后比较即可

2.判断子序列

1.动态规划解法

package com.sunxiansheng.classic150.g1;/*** Description: 392. 判断子序列** @Author sun* @Create 2024/12/21 09:36* @Version 1.0*/
public class t392 {public boolean isSubsequence(String s, String t) {// dp[i][j]:以i-1，j-1为结尾的最长公共子序列的长度// 状态转移公式：相同时 dp[i][j] = dp[i - 1][j - 1] + 1 不同时 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])// 初始化int m = s.length();int n = t.length();int[][] dp = new int[m + 1][n + 1];int max = 0;// 填充dp数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}max = Math.max(max, dp[i][j]);}}return max ==  s.length();}
}

2.双指针

package com.sunxiansheng.classic150.g1;/*** Description: 392. 判断子序列** @Author sun* @Create 2024/12/21 09:36* @Version 1.0*/
public class t392 {public static boolean isSubsequence(String s, String t) {// 双指针int left = 0;for (int right = 0; right < t.length(); right++) {// 如果左数组已经遍历完了就提前退出if (left >= s.length()) {break;}// 当右指针遇到了左指针指向的元素，左指针++if (t.charAt(right) == s.charAt(left)) {left++;}}return left >= s.length();}
}

3.两数之和 II - 输入有序数组

1.答案

package com.sunxiansheng.classic150.g1;/*** Description: 167. 两数之和 II - 输入有序数组** @Author sun* @Create 2024/12/21 10:08* @Version 1.0*/
public class t167 {public int[] twoSum(int[] numbers, int target) {// 两个指针从两边往中间移动int left = 0;int right = numbers.length - 1;while (left < right) {// 求和int sum = numbers[left] + numbers[right];// 如果大于target，就右指针移动，小于target就左指针移动if (sum > target) {right--;} else if (sum < target) {left++;} else {return new int[]{left + 1, right + 1};}}return null;}
}

2.思路

这里用的是贪心双指针，就是两个指针从两边往中间移动，和如果大于target，就右指针移动，小于target就左指针移动

4.盛最多水的容器

1.答案

package com.sunxiansheng.classic150.g1;/*** Description: 11. 盛最多水的容器** @Author sun* @Create 2024/12/21 10:42* @Version 1.0*/
public class t11 {public static int maxArea(int[] height) {int max = 0;int left = 0, right = height.length - 1;while (left < right) {// 求水量int water = Math.min(height[left], height[right]) * (right - left);// 更新最大值max = Math.max(max, water);// 哪边低移动哪边的指针if (height[left] < height[right]) {left++;} else {right--;}}return max;}
}

2.思路

使用贪心双指针解决

5.三数之和

1.答案

package com.sunxiansheng.classic150.g1;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** Description: 15. 三数之和** @Author sun* @Create 2024/12/21 10:50* @Version 1.0*/
public class t15 {public static List<List<Integer>> threeSum(int[] nums) {// 使用遍历+贪心双指针来解决List<List<Integer>> res = new ArrayList<>();// 如果数组长度小于3，直接返回空结果if (nums == null || nums.length < 3) {return res;}// 首先排序Arrays.sort(nums);// 遍历for (int i = 0; i < nums.length - 2; i++) {// 关键点：当前的元素跟前一个元素是相同的情况下不必考虑if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 贪心双指针int left = i + 1;int right = nums.length - 1;while (left < right) {// 求结果int sum = nums[left] + nums[right] + nums[i];// 根据结果来贪心的调整状态if (sum > 0) {right--;} else if (sum < 0) {left++;} else {res.add(Arrays.asList(nums[i], nums[left], nums[right]));// 关键点：当左右指针指向的下一个元素跟当前元素是相同的也不用考虑while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;}}}return res;}
}

2.思路

使用遍历+贪心双指针来解决，注意两个关键点一个是在遍历时，遇到重复元素就跳过，另一个是在左右指针移动时，遇到重复元素也跳过

滑动窗口

1.长度最小的子数组

1.答案

package com.sunxiansheng.classic150.g1;/*** Description: 209. 长度最小的子数组** @Author sun* @Create 2024/12/21 11:20* @Version 1.0*/
public class t209 {public static int minSubArrayLen(int target, int[] nums) {// 滑动窗口定义：窗口内的元素要小于targetint left = 0;int res = Integer.MAX_VALUE;int sum = 0;for (int right = 0; right < nums.length; right++) {// 加入窗口sum += nums[right];// 只要窗口内的元素是大于target的，就进行处理while (sum >= target) {// 计算结果res = Math.min(res, right - left + 1);// 滑动窗口sum -= nums[left++];}}return res == Integer.MAX_VALUE ? 0 : res;}
}

2.思路

先进行滑动窗口的定义窗口内的元素要小于target，那么只要窗口内的元素是大于target的，就进行处理，就可以计算结果了

2.无重复字符的最长子串

1.答案

package com.sunxiansheng.classic150.g1;import java.util.HashSet;
import java.util.Set;/*** Description: 3. 无重复字符的最长子串** @Author sun* @Create 2024/12/21 11:28* @Version 1.0*/
public class t3 {public static int lengthOfLongestSubstring(String s) {// 滑动窗口定义：窗口内的元素不能重复int left = 0;int res = 0;Set<Character> set = new HashSet<>();for (int right = 0; right < s.length(); right++) {// 获取set的长度int before = set.size();// 加入窗口set.add(s.charAt(right));res = Math.max(res, set.size());// 当窗口内的元素重复时if (set.size() == before) {while (s.charAt(left) != s.charAt(right)) {// 滑动窗口set.remove(s.charAt(left));left++;}// 到这里就说明当前left指向了那个重复元素，继续滑动窗口，不过不需要移动setleft++;}}return res;}
}

2.思路

这里面比较复杂一点，十分考察对滑动窗口算法的理解，加入窗口前先要获取一下加入set之前的长度，如果加入窗口后长度不变，那么就一定是元素重复了，需要滑动窗口直到不重复。计算结果则是在加入窗口的时候

3.最小覆盖子串

1.答案

package com.sunxiansheng.classic150.g1;import java.util.HashMap;
import java.util.Map;/*** Description: 76. 最小覆盖子串** @Author sun* @Create 2024/12/21 14:19* @Version 1.0*/
public class t76 {public static String minWindow(String s, String t) {// 滑动窗口定义：窗口内元素不能全部包含t的所有元素// 使用map来记录t的词频Map<Character, Integer> tMap = new HashMap<>();for (int i = 0; i < t.length(); i++) {tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);}// 所有的字符数（当满足条件的字符数为n时，表明该子串就是覆盖子串了）int n = t.length();// 满足条件的字符数int satisfy = 0;// s的词频Map<Character, Integer> sMap = new HashMap<>();// 最小覆盖子串的长度int minSonLength = Integer.MAX_VALUE;// 最小覆盖子串String minSon = "";int left = 0;for (int right = 0; right < s.length(); right++) {// 获取到目标字符char c = s.charAt(right);// 只考虑是t的元素的情况if (tMap.containsKey(c)) {// 加入窗口sMap.put(c, sMap.getOrDefault(c, 0) + 1);// 如果目标字符的出现次数是小于t中的频率，就可以增加满足条件的字符数if (sMap.get(c) <= tMap.get(c)) {satisfy++;}}// 只要目前是覆盖子串，就需要滑动窗口while (satisfy == n) {// 更新最小覆盖子串if ((right - left + 1) < minSonLength) {minSon = s.substring(left, right + 1);minSonLength = right - left + 1;}// 滑动窗口// 当是t的元素时if (tMap.containsKey(s.charAt(left))) {// 更新词频和满足的字符数sMap.put(s.charAt(left), sMap.get(s.charAt(left)) - 1);// 只有当窗口中的元素减少后，确实比t中的词频少了，才会减少满足的字符数if (sMap.get(s.charAt(left)) < tMap.get(s.charAt(left))) {satisfy--;}}// 不是t的元素就直接滑动即可left++;}}return minSon;}public static void main(String[] args) {minWindow("ADOBECODEBANC", "ABC");}
}

2.思路

核心就是使用Map来记录两个字符串的词频，然后当满足条件的字符数量为t的个数时就是覆盖子串

​