刷题日常(找到字符串中所有字母异位词, 和为 K 的子数组, 滑动窗口最大值,全排列)
刷题日常(找到字符串中所有字母异位词, 和为 K 的子数组, 滑动窗口最大值,全排列)
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
题目分析：
1.将p里面的字符先丢进一个hash1中，只需要在S字符里面找到多少个和他相同的hash2即可 2.使用R遍历整个字符S，L记录匹配成功的第一个位置，用于返回最终结果在ret数据中 3.使用滑动窗口 窗口大小只需要跟p的大小一样即可 4.进窗口 使用R去遍历这个字符， 5.出窗口 当出现窗口大小 >p的个数的时候 ，此时将L上的元素移除hash2 然后L++ 6.更新结果 当窗口大小 = p的个数 并且 hash1和hash2相等的时候 记录此时的L加入最终结果
细节1：窗口大小能不能直接用hash2的size（）记录？ 答案是不行 因为可能漏 ，会出现重复字符
里面有3个元素 ，而hash.size（）却为2 所有肯定会出错 细节2：当窗口大小大于 p的个数时候 ，能不能直接移除L上的位置 答案也是不行 因为会出现重复元素 比如上图中的 b 为 2个，只需要出掉一个b ，你却结果直接把b元素都在hash移除，肯定是错误的
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ret = new ArrayList<>();
int m = p.length(), n = s.length();
HashMap<Character, Integer> hash1 = new HashMap<>();
for (int i = 0; i < m; i++) {
char ch = p.charAt(i);
hash1.put(ch, hash1.getOrDefault(ch, 0) + 1);
}
HashMap<Character, Integer> hash2 = new HashMap<>();
int left = 0;
for (int right = 0; right < n; right++) {
char ch = s.charAt(right);
// 进窗口
hash2.put(ch, hash2.getOrDefault(ch, 0) + 1);
// 判断
while (right - left + 1 > m) {
char ch1 = s.charAt(left);
int count = hash2.get(ch1) - 1;
if (count == 0) {
hash2.remove(s.charAt(left));
} else {
hash2.put(ch1, count);
}
left++;
}
// 出窗口 更新结果
if (hash2.equals(hash1)) {
ret.add(left);
}
}
return ret;
}
}和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
使用前缀和思想+哈希表 寻找某个区间之和为K dp就是前缀和数组，可以快速得到某一区间的和。 hash表第一个变量定义为前缀和，第二个变量定义为出现的次数 使用一个哈希表记录前缀和出现的数字，以及它的个数 只需要看哈希表是否有（当前数字的前缀和-K ） 如果有，返回它对应的个数，如果没有，进哈希表
细节处理：哈希表中开始前，应当把0这个数字放进去，此时为1次 防止第一个数就是我们要找到的K
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> hash = new HashMap<>();
int n = nums.length, count = 0;
int preSum = 0;
hash.put(0, 1);
for (int i = 0; i < n; i++) {
preSum += nums[i];
if (hash.containsKey(preSum - k)) {
count += hash.getOrDefault(preSum - k, 0);
}
hash.put(preSum, hash.getOrDefault(preSum, 0) + 1);
}
return count;
}
}滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
- 遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；
- 当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。
- 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int[] ret = new int[nums.length - k + 1];
int left = 0;
for(int right = 0 ;right < nums.length; right++) {
//判断队列不为空的情况下是否队列的尾巴元素要小于加入的元素
//小于的话 得不断弹出
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[right]) {
deque.pollLast();
}
//添加下标元素，为了更好的比较left
deque.addLast(right);
if(deque.peekFirst() < left) {
deque.pollFirst();
}
//判断窗口是否成型 加入到最终结果
if(right + 1 >= k) {
ret[left++] = nums[deque.peekFirst()];
}
}
return ret;
}
}全排列
题目分析：
在有重复元素中的数组中，需要考虑如何剪枝，才能使最终的结果不出现相同的结果 如图中， 1.一个数字只能使用一次在整个过程，当进入下一层中，使用一个记录boolean数组记录上一层使用的状态，如果为true，意味着我们已经使用过此元素，那么我们就跳过这个索引，避免重复使用同一个元素。 2.本题难点，当在同一层中，如何剪枝？ 例如第一个数字有4中选法，可以选择1 1 1 2，那么将肯定 3个1里面只能选择一次，不然必将会出现重复，所有此时得将后面出现的俩次1不选，才可以得出没有重复的结果 这个很简单，多加一次判断呗，当nums[i]跟nums[i-1]的位置进行比较 看看是否相同 为了避免乱序，我们开始前就得将数组进行排序，这样数组将是一个有序状态，才能比较
只考虑不合法的情况 当遇见不合法的情况下，直接continue，跳过此次循环
class Solution {
List<List<Integer>> ret;
List<Integer> path;
boolean[] check;
public List<List<Integer>> permuteUnique(int[] nums) {
check = new boolean[nums.length];
path = new ArrayList<>();
ret = new ArrayList<>();
Arrays.sort(nums);
dfs(nums);
return ret;
}
public void dfs(int[] nums) {
if (path.size() == nums.length) {
ret.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 设置不合法区别
if (check[i] == true || (i != 0 && nums[i - 1] == nums[i] && check[i - 1] == false)) {
continue;
}
path.add(nums[i]);
check[i] = true;
dfs(nums);
path.remove(path.size() - 1);
check[i] = false;
}
}
}1.
check[i] == true条件 首先，check[i] == true的条件是用来检查当前索引i是否已经被使用过。如果check[i]为true，意味着nums[i]已经在当前排列路径path中被使用过了，那么我们就跳过这个索引，避免重复使用同一个元素。 2.(i != 0 && nums[i - 1] == nums[i] && check[i - 1] == false)条件 这个条件是避免重复排列产生的关键。为了理解这个条件，我们需要知道它的作用：
-
nums[i - 1] == nums[i]：这个条件判断当前元素nums[i]是否和前一个元素nums[i - 1]相等。如果相等，说明这两个元素是相同的。 -
check[i - 1] == false：这个条件确保前一个元素nums[i - 1]在当前排列路径中没有被使用过。也就是说，只有当前一个元素还没有被使用时，才允许使用当前的重复元素。
只考虑合法的情况
class Solution {
List<List<Integer>> ret;
List<Integer> path;
boolean[] check;
public List<List<Integer>> permuteUnique(int[] nums) {
check = new boolean[nums.length];
path = new ArrayList<>();
ret = new ArrayList<>();
Arrays.sort(nums);
dfs(nums);
return ret;
}
public void dfs(int[] nums) {
if (path.size() == nums.length) {
ret.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 合法区间
if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {
path.add(nums[i]);
check[i] = true;
dfs(nums);
path.remove(path.size() - 1);
check[i] = false;
}
}
}
}腾讯云开发者
