【算法300题】：双指针

双指针板块

925. 长按键入

leetcode链接

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

思路

这道题目只要是末尾的边界条件比较恶心一点

class Solution {
public:bool isLongPressedName(string name, string typed) {int cur = 0;if(name[0] != typed[0]) return false;for(auto ch : name){if(ch == typed[cur]){// 匹配成功++cur;}else {// 匹配失败// 可能上一个字符多键入了auto prev_chr = typed[cur - 1];while(cur < typed.size() && typed[cur] == prev_chr) cur++;if(cur < typed.size() && typed[cur] == ch) {cur++;}else return false; }}// 找找还有没有词auto prev_chr = typed[cur - 1];while(cur < typed.size() && typed[cur] == prev_chr) cur++;if(cur < typed.size()) return false;return true;}
};

532. 数组中的 k-diff 数对

leetcode链接

给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：

0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
注意，|val| 表示 val 的绝对值。

示例 1：

输入：nums = [3, 1, 4, 1, 5], k = 2
输出：2
解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个 1 ，但我们只应返回不同的数对的数量。
示例 2：

输入：nums = [1, 2, 3, 4, 5], k = 1
输出：4
解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5) 。
示例 3：

输入：nums = [1, 3, 1, 5, 4], k = 0
输出：1
解释：数组中只有一个 0-diff 数对，(1, 1)

思路

第一版的思路就是直接查找, 但是k == 0单独讨论一下, 不然确实不好处理

class Solution {
public:int getPrevDiffNum(vector<int>& num,int pos){int res = pos - 1;while(res >= 0 && num[res] == num[pos]) res--;return res;// -1}int getNextDiffNum(vector<int>& num,int pos){int res = pos + 1;while(res < num.size() && num[res] == num[pos]) res++;return res;}int findPairs(vector<int>& nums, int k) {// 暴力算法// 单独处理k == 0sort(nums.begin(), nums.end());if(k == 0){int count = 0;for(int i = 0;i < nums.size();i = getNextDiffNum(nums,i))if(i + 1 < nums.size() && nums[i] == nums[i + 1]) count++;return count;}int n = nums.size();int count = 0;for(int i = 0;i < n;i = getNextDiffNum(nums,i)){auto prev_diff_pos = i;while(prev_diff_pos != -1){if(nums[i] - nums[prev_diff_pos] >= k) break;prev_diff_pos = getPrevDiffNum(nums, prev_diff_pos);}if(prev_diff_pos != -1 && nums[i] - nums[prev_diff_pos] == k) {count++;}}return count;}
};

思路

我们在查找的时候可以使用二分进行速度的优化。确实快了一些

class Solution {
public:int getPrevDiffNum(vector<int>& num,int pos){int res = pos - 1;while(res >= 0 && num[res] == num[pos]) res--;return res;// -1}int getNextDiffNum(vector<int>& num,int pos){int res = pos + 1;while(res < num.size() && num[res] == num[pos]) res++;return res;}int findPairs(vector<int>& nums, int k) {// 暴力算法// 单独处理k == 0sort(nums.begin(), nums.end());if(k == 0){int count = 0;for(int i = 0;i < nums.size();i = getNextDiffNum(nums,i))if(i + 1 < nums.size() && nums[i] == nums[i + 1]) count++;return count;}// 如果k != 0, 首先进行去重// 通过二分查找进行优化之前的逻辑int count = 0;for(int i = getNextDiffNum(nums,0);i < nums.size();i = getNextDiffNum(nums,i)){int left = 0, right = i - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[i] - nums[mid] > k) left = mid + 1;else right = mid;}if(nums[i] - nums[left] == k) count++;}return count;}
};

56. 合并区间

leetcode

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Cmp
{
public:// we must guarentee vector.size() == 2bool operator()(const vector<int>& l,const vector<int>& r){return l[0] < r[0];}
};class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> ret;std::sort(intervals.begin(),intervals.end(),Cmp());int prev_end = intervals[0][0];int prev_begin = intervals[0][0];intervals.push_back({INT32_MAX,INT32_MAX});for(auto& area : intervals){int begin = area[0], end = area[1];if(prev_end < begin){// 更新区间ret.push_back({prev_begin,prev_end});prev_begin = begin, prev_end = end;}else if(begin <= prev_end){// 出现交叉// 合并prev_end = std::max(prev_end,end);}}    return ret;}
};

75. 颜色分类

leetcode

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

class Solution {
public: // 通过快排void sortColors(vector<int>& nums) {int left = -1, right = nums.size();int cur = 0;while(cur < right){if(nums[cur] == 0) std::swap(nums[cur++], nums[++left]);else if(nums[cur] == 1) cur++;else std::swap(nums[cur], nums[--right]);}    }
};

80. 删除有序数组中的重复项 II

leetcode

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1.

class Solution {
public:int removeDuplicates(vector<int>& nums) {// 很简单的双指针的算法// count表示当前位置前面需要删除的个数int symbol = INT32_MAX;int symbol_count = 0;int offset = 0;for(int i = 0;i < nums.size();i++){if(nums[i] == symbol) {symbol_count++;if(symbol_count > 2)offset++;else{nums[i - offset] = nums[i]; }      }else {symbol = nums[i];symbol_count = 1;nums[i - offset] = nums[i];}}auto res = nums.size() - offset;nums.resize(res);return res;}
};

485. 最大连续 1 的个数

leetcode

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

class Solution {
public:int findMaxConsecutiveOnes(vector<int>& nums) {int res = 0;int count = 0;for(auto i : nums) {if(i == 0){count = 0;}else {count++;res = std::max(res,count);}}    return res;}
};

524. 通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出：“apple”
示例 2：

输入：s = “abpcplea”, dictionary = [“a”,“b”,“c”]
输出：“a”

class Solution {
public:Solution() : _hash(26){}void initHashTable(const std::string& str){for(int i = 0;i < str.size();i++)_hash[str[i] - 'a'].push_back(i);}bool isFitChildString(const std::string& src){int cur = -1; for(auto ch : src){// 判断ch是否在(cur, end]中存在, 若存在找到最近的一个// 通过二分查找进行优化auto& posSet = _hash[ch - 'a'];if(posSet.empty()) return false;else{int left = 0, right = posSet.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(posSet[mid] <= cur) left = mid + 1;else right = mid;}if(posSet[left] <= cur) return false;else cur = posSet[left];}}return true;}// 这道题目的本质就是判断dictionary中是否存在s的子序列, 对于大量判断, 通过hash来解决string findLongestWord(string s, vector<string>& dictionary) {initHashTable(s);string res;for(auto& dict : dictionary){if(isFitChildString(dict)){if(dict.size() > res.size()) res = dict;else if(dict.size() == res.size() && dict < res) res = dict;}}return res; }
// 通过hash + 二分进行优化private:vector<vector<int>> _hash;
};

986. 区间列表的交集

leetcode

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

示例 1：

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
示例 2：

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]
示例 3：

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]
示例 4：

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

class Solution {
public:struct InterArea{InterArea(int left = -1,int right = -1) : _left(left), _right(right){}operator bool(){return _left != -1;} int _left;int _right;};// 判断两个区间是否存在公共部分InterArea isHasInterSection(vector<int>& l, vector<int>& r){if(l[0] > r[1] || l[1] < r[0]) return {-1, -1 };else return InterArea((int)std::max(l[0],r[0]), (int)std::min(l[1], r[1]));}vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {vector<vector<int>> res;int start = 0;for(auto& List : secondList){while(start < firstList.size() && firstList[start][1] < List[0]) start++;auto cur = start;// 计算区间while(cur < firstList.size() && firstList[cur][0] <= List[1]){auto inter = isHasInterSection(firstList[cur], List);res.push_back({inter._left, inter._right});cur++;}}return res;}
};