算法刷题记录-双指针/滑动窗口(LeetCode)

809. Expressive Words

思路

根据题目描述，我们可以知道，如果要将某个单词定义为可扩张（stretchy），需要满足如下两个条件：

所以，我们在实现的时候，可以通过两个指针p1和p2，分别指向s和word，分别统计连续的相同字符数量c1和c2，然后再通过上述的两个条件进行判断，即：如果

(c1 != c2 && c1 < 3) || (c1 < c2 && c1 >= 3)

则表示该单词不是可扩张的。

代码

class Solution {public int expressiveWords(String s, String[] words) {int result = 0;char[] sc = s.toCharArray();for (String word: words) result += stretchyWord(sc, word.toCharArray()) ? 1 : 0;return result;}private boolean stretchyWord(char[] sc, char[] wc) {if (sc.length < wc.length) return false; // word的字符串长度不允许超过s的字符串长度int cp, p1 = 0, p2 = p1;while ((cp = p1) < sc.length && p2 < wc.length) {int c1 = 0, c2 = 0;while (p1 < sc.length && sc[p1] == sc[cp]) {c1++; p1++; // 在字符串s中，遍历连续的字符sc[cp]的数量}while (p2 < wc.length && wc[p2] == sc[cp]) {c2++; p2++; // 在字符串word中，遍历连续的的字符sc[cp]的数量}if ((c1 != c2 && c1 < 3) || (c1 < c2 && c1 >= 3)) return false;}return p1 == sc.length && p2 == wc.length; // 只有sc和wc都被遍历完毕，才返回true}
}

823. Binary Trees With Factors

思路

代码

class Solution {static final long MOD = (long) 1e9 + 7;public int numFactoredBinaryTrees(int[] arr) {Arrays.sort(arr);long[] ans=new long [arr.length];ans[0]=1;for (int i=1;i<arr.length;i++){ans[i]=1;int left=0;int right=i-1;while (left<=right){while (left<=right){long prod= (long) arr[left] *arr[right];if (prod==arr[i]){break;}else if (prod<arr[i]){left++;}else{right--;}}if (left>right){break;}if (left==right){ans[i]+=ans[left]*ans[left];}else{ans[i]+=ans[left]*ans[right]*2;}left++;right--;}ans[i]%=MOD;}long final_ans=0;for (long val:ans){final_ans=final_ans+val;final_ans%=MOD;}return (int)final_ans;}
}

*828. Count Unique Characters of All Substrings of a Given String

思路 贡献法+双指针

请看下图，我们以s=“ABCD”为例，首先，可以将其拆分为10个子串（以“A”为基准的4个子串；以“B”为基准的3个子串；以“C”为基准的2个子串；以“D”为基准的1个子串；），那么由于s字符串中的字符都是彼此不重复的，所以，总结果其实就是“A”、“B”、“C”、“D”这个四个字符在所有10个子串中出现的次数之和，即：A出现4次 + B出现6次 + C出现6次 + D出现4次 = 20。

通过上面的例子，我们将问题转换为某个字符在子串中出现的个数问题了。那么，针对这个问题，其实有3种情况：

情况1：字符是“头元素”，那么出现次数可以通过：数组长度 - 元素下标位置 来计算出来。
情况2：字符是“尾元素”，那么出现次数可以通过：元素下标位置 - (-1) 来计算出来。
情况3：字符是“中间元素”，那么出现次数可以通过：(元素下标位置 - (-1)) * (数组长度 - 元素下标位置) 来计算出来。

那么前面我们是针对于字符串中字符不重复的情况来看的，下面我们再来看一下有重复字符的情况。其实，针对于这种情况，就产生了区间的概念。因为我们上面进行统计的时候，都是针对于某一区间内这个元素是唯一的，所以，如果发生了重复字符，我们就需要将其拆分为多个区间。以下图s="ABCB"为例，当我们要统计元素“B”的时候，由于发生了重复的情况，所以，我们要将其拆分为：
当B的下标=1的时候，它唯一的区间是[0,2] 当B的下标=3的时候，它唯一的区间是[2,3]
那么，由于产生了区间的概念，我们也随之创建两个指针，分别是head和tail，head指向的某区间开始位置的前一个位置；tail指向的是某区间结束为止的后一个位置。那么计算公式最终就是：(某元素下标位置 - head) * (tail - 某元素下标位置)。

我们得出了计算公式之后，就可以针对给出的字符串s中的每个字符进行遍历，在哈希表中记录一下每个元素的所在位置，key=字符，value=该字符出现的位置集合。具体实现，请参照：代码1-哈希表采用哈希表方式实现。如果需要提升执行效率，我们也可以采用数组来记录每个元素的所在位置，26个字母对应数组的坐标，然后一个数组是用来针对某个元素出现多次进行统计

解题思路我们就说完了。下面我们以s=“LEETCODE”为例，看一下具体的计算过程。由于下图中的计算细节已经在图中写出来了，所以这里的文字部分就不去赘述了。具体的计算过程，请参见下图。

代码1-哈希表

    public int uniqueLetterString(String s) {HashMap<Character, ArrayList<Integer>> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {if (!map.containsKey(s.charAt(i))) {map.put(s.charAt(i), new ArrayList<>());}map.get(s.charAt(i)).add(i);}int ans = 0;for (var pair : map.entrySet()) {int head = -1;int tail = -1;var items = pair.getValue();for (int i = 0; i < items.size(); i++) {tail = i < (items.size() - 1) ? items.get(i + 1) : s.length();ans += (items.get(i) - head) * (tail - items.get(i));head = items.get(i);}}return ans;}

849. Maximize Distance to Closest Person

思路(双指针+贪心)

我们考虑前一个1出现的位置prev,一直向右遍历的位置i每当seats[i]为1时，i与prev相减的值即为距离，求所有可能的距离的最大值即可。注意，在实现代码中，考虑的略复杂了一些 其中while（seat[i]==0）的部分可优化为prev=-1。但是，我们一定需要当遍历结束后强制判断一次，因为可能出现类似$[1,0,0,0]$此类序列。

代码

    int maxDistToClosest(vector<int>& seats) {int prev;int i=0;while (seats[i]==0){i++;}prev=i;int max_length=i;for (i++; i < seats.size(); ++i) {if (seats[i]==0){continue;}int length=i-prev-1;max_length=max((int)ceil((double)length/2),max_length) ;prev=i;}int length=seats.size()-prev-1;if (length>max_length){max_length=length;}return max_length;}

881. Boats to Save People

思路

首先对数组进行排序，设置两个指针left，right。令每次救生艇乘坐的人重量最大。若left+right>limit，则说明位于right位置的人需要一个独立的救生艇。当左右指针相遇时，说明剩下需要一个独立的救生艇，再次＋1。

代码

class Solution {public int numRescueBoats(int[] people, int limit) {int ans=0;Arrays.sort(people);int left=0;int right=people.length-1;while (left<=right){while (right>left&&people[left]+people[right]>limit){right--;ans++;}if (left==right){ans++;break;}ans++;left++;right--;}return ans;}
}

904. Fruit Into Baskets

思路 双指针+HashMap

构建一个HashMap,令left指针标注序列开始点，right指针标注序列结束点。
每次将一个新水果fruits[right]加入序列，若map的长度大于2，则右移left指针并对map内的fruits[left]进行-1操作，若map[fruit[left]]为0，则表示已完全移除，map长度减一。从此往复，统计map内key的value和的最大值。

代码

    public int totalFruit(int[] fruits) {HashMap<Integer, Integer> map = new HashMap<>();int left = 0;int right = 0;int ans=0;while (right < fruits.length) {map.merge(fruits[right], 1, Integer::sum);while (map.size() > 2) {map.merge(fruits[left], -1, Integer::sum);if (map.get(fruits[left])==0){map.remove(fruits[left]);}left++;}int curr_ans=0;for (var key:map.keySet()){curr_ans+=map.get(key);}ans=Math.max(ans,curr_ans);right++;}return ans;}

2841. Maximum Sum of Almost Unique Subarray

思路 滑动窗口

用滑动窗口枚举长为 k 的子数组，用哈希表记录子数组中各元素出现的次数，以维护当前子数组中不同元素的个数

代码

class Solution {public long maxSum(List<Integer> nums, int m, int k) {HashMap<Integer,Integer>map=new HashMap<>();int left=0;int right=k;long ans=0;long curr_sum=0;for (int i=0;i<k;i++){curr_sum+=nums.get(i);map.merge(nums.get(i),1,Integer::sum);}if (map.size()>=m){ans=Math.max(curr_sum,ans);}while (right<nums.size()){curr_sum+= nums.get(right);curr_sum-= nums.get(left);map.merge(nums.get(right),1,Integer::sum);map.merge(nums.get(left),-1,Integer::sum);if(map.get(nums.get(left))==0){map.remove(nums.get(left));}if (map.size()>=m){ans=Math.max(curr_sum,ans);}left++;right++;}return ans;}}

2844. Minimum Operations to Make a Special Number

思路 滑动窗口

要想被25整除，末尾数字只能是00、25、50、75 。只要从最后一个数字遍历即可，若最后一位数字为5，则向前寻找2或者7、否则向前寻找0或者5。

代码

class Solution {public int minimumOperations(String _num) {char[] num=_num.toCharArray();int ans=120;boolean containsZero=false;int end=num.length-1;while (end>0){if (num[end]=='0'||num[end]=='5'){int prev=end-1;if (num[end]=='0'){containsZero=true;while (prev>=0&&(num[prev]!='5'&&num[prev]!='0')){prev--;}}else {while (prev>=0&&(num[prev]!='2'&&num[prev]!='7')){prev--;}}if (prev>=0){ans=Math.min(ans,end-prev-2+num.length-end);}}end--;}if (ans==120){return containsZero? num.length-1 :num.length ;}return ans;}
}