算法剖析-经典150（双指针、滑动窗口）
双指针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-1，j-1为结尾的最长公共子序列的长度
// 状态转移公式：相同时 dp = dp + 1 不同时 dp = Math.max(dp, dp)
// 初始化
int m = s.length();
int n = t.length();
int[][] dp = new int;
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 = dp + 1;
} else {
dp = Math.max(dp, dp);
}
max = Math.max(max, dp);
}
}
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 + numbers;
// 如果大于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, height) * (right - left);
// 更新最大值
max = Math.max(max, water);
// 哪边低移动哪边的指针
if (height < height) {
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 == nums) {
continue;
}
// 贪心双指针
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
// 求结果
int sum = nums + nums + nums;
// 根据结果来贪心的调整状态
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
res.add(Arrays.asList(nums, nums, nums));
// 关键点：当左右指针指向的下一个元素跟当前元素是相同的也不用考虑
while (left < right && nums == nums) {
left++;
}
while (left < right && nums == nums) {
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) {
// 滑动窗口定义：窗口内的元素要小于target
int left = 0;
int res = Integer.MAX_VALUE;
int sum = 0;
for (int right = 0; right < nums.length; right++) {
// 加入窗口
sum += nums;
// 只要窗口内的元素是大于target的，就进行处理
while (sum >= target) {
// 计算结果
res = Math.min(res, right - left + 1);
// 滑动窗口
sum -= nums;
}
}
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指向了那个重复元素，继续滑动窗口，不过不需要移动set
left++;
}
}
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的个数时就是覆盖子串
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]