九十六、双指针和滑动窗口算法模板
「@Author：Runsen」
双指针的算法原理，通过两个指针在一个for循环下完成两个for循环的工作。时间复杂度从优化到了。
双指针的算法模板比较简单，突破口主要是需要找到题目中的单调性，从而加以利用。
快慢指针
快慢指针一个链表操作技巧，它还有一个有趣的名字，龟兔赛跑。
移除元素：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
环的入口位置：应用快慢指针，快指针走两步，慢指针走一步。假使有环，两指针迟早相遇；假使无环，快指针就会走到尽头，退出循环。如果有环，慢指针重新开始，此时快指针是交点，同速两指针交点必是入口。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
if (fast && fast->next){
slow = head;
while(slow!=fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
return nullptr;
}
};
链表的中间结点：应用快慢指针，快指针走两步，慢指针走一步。快指针走到尽头时，慢指针刚好走了一半，返回即为中间结点。
删除链表的倒数第 N 个结点：快指针先走 n 步，然后快慢指针同时走，快指针走到头时，慢指针就在倒数第 n 个位置。
反向指针
反向指针经典题目是N sum 系列和二分变种题目。
N sum 系列的经典题目是：三数之和
def threeSum(nums):
nums.sort()
# [-4, -1, -1, 0, 1, 2]
res_list = []
# 头部循环查找
for i in range(len(nums)):
# 必须判断 nums[i] > nums[i - 1]这个条件
if i == 0 or nums[i] > nums[i - 1]:
# 最左端
l = i + 1
# 最右端
r = len(nums) - 1
while l < r: # 正在查找
three_sum = nums[i] + nums[l] + nums[r]
if three_sum == 0:
res_list.append([nums[i], nums[l], nums[r]])
l += 1 # 右移一位
r -= 1 # 左移一位
while l < r and nums[l] == nums[l - 1]:
# 从左往右，相同数值直接跳过
l += 1
while r > l and nums[r] == nums[r + 1]:
# 从右往左，相同数值直接跳过
r -= 1
elif three_sum > 0:
# 大于零，右边数值大，左移
r -= 1
else:
# 小于零，左边数值小，右移
l += 1
return res_list
在四种二分变种中，根据王争算法专栏中，写死low = 0，high = len(list) - 1。循环条件low <= high。往左移动high = mid - 1，往右移动low = mid + 1
def binary_search(nums, target):
'''标准二分算法模板'''
low = 0
high = len(nums) - 1 # 注意1 low和high用于跟踪在其中查找的列表部分
while low <= high: # 注意2 只要还没有缩小到只有一个元素，就不停的检查
mid = (low + high) // 2
if list[mid] == target:
return mid
elif list[mid] > target:
high = mid - 1 # 注意3 猜的数字大了
elif list[mid] < target:
low = mid + 1 # 注意4 猜的数字小了
return mid
def bsearch_low(nums,target):
'''求第一个等于定值 '''
low = 0
high = len(nums) - 1
# 这里需要 <=
while low <= high:
# 这里需要注意： 就是使用((high - low) >> 1)需要双扩号
mid = low + ((high - low) >> 1)
if nums[mid] < target:
low = mid + 1
elif nums[mid] > target:
high = mid - 1
else:
if mid == 0 or nums[mid-1] != target:
return mid
else:
high = mid -1
return -1
def bsearch_high(nums,target):
'''求最后一个等于定值的'''
low = 0
higt = len(nums) -1
while low <= higt:
mid = low + ((higt- low) >>1 )
if nums[mid] > target:
higt = mid - 1
elif nums[mid] < target:
low = mid +1
else:
if mid == (len(nums) -1) or nums[mid] != nums[mid+1]:
return mid
else:
low = mid +1
return -1
'''
查找第一个大于等于给定值的元素
* 如序列：3，4，6，7，19 查找第一个大于5的元素，即为6，return 2
* 第一个大于给定值，则说明上一个小于给定值，依次判断
'''
def bsearch_low_not_less(nums,target):
low = 0
high = len(nums) -1
while(low<=high):
mid = low + ((high-low) >>1)
if nums[mid] >= target:
if mid == 0 or nums[mid - 1] < target:
return mid
else:
# 往左移动
high = mid - 1
else:
# 往右移动
low = mid +1
return -1
'''
查找第一个小于给定值的元素
* 如序列：3，4，6，7，19 查找第一个小于5的元素，即为4，返回1
* 第一个大于给定值，则说明上一个小于给定值，依次判断
'''
def bsearch_high_not_greater(nums,target):
'''求最后一个小于等于值'''
low = 0
higt = len(nums) -1
while low <= higt:
mid = low + (( higt -low ) >> 1)
if nums[mid] <= target:
if (mid == len(nums) -1) or (nums[mid + 1] > target):
return mid
else:
low = mid +1
else:
higt = mid -1
return -1
滑动窗口
原文：https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA
滑动窗口算法是双指针技巧的最高境界，主要用于两个字符串匹配的问题。
掌握了滑动窗口的解题模板可以轻松解决一系列字符串匹配的问题。
下面模板代码来源labuladong，解决LeetCode 76 题，Minimum Window Substring，求最小覆盖子串。
/* 滑动窗口算法框架 */
string minWindow(string s, string t) {
// 两个unordered_map ，一个need记录模式串的字符数量，一个window记录窗口的字符
unordered_map<char, int> need, window;
// 初始化need
for (char c : t) need[c]++;
int left = 0, right = 0;
// 两个unordered_map的符合条件数目
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = INT_MAX;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 在这里更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// 返回最小覆盖子串
return len == INT_MAX ?
"" : s.substr(start, len);
}
在python里unodered map可以用collections.defaultdict和collections.Counter实现
评论