九十六、雙指針和滑動窗口算法模板
「@Author：Runsen」
雙指針的算法原理，通過兩個指針在一個for循環(huán)下完成兩個for循環(huán)的工作。時間復雜度從優(yōu)化到了。
雙指針的算法模板比較簡單，突破口主要是需要找到題目中的單調(diào)性，從而加以利用。
快慢指針
快慢指針一個鏈表操作技巧，它還有一個有趣的名字，龜兔賽跑。
移除元素：
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;
}
};
環(huán)的入口位置：應用快慢指針，快指針走兩步，慢指針走一步。假使有環(huán)，兩指針遲早相遇；假使無環(huán)，快指針就會走到盡頭，退出循環(huán)。如果有環(huán)，慢指針重新開始，此時快指針是交點，同速兩指針交點必是入口。
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;
}
};
鏈表的中間結(jié)點：應用快慢指針，快指針走兩步，慢指針走一步?？熘羔樧叩奖M頭時，慢指針剛好走了一半，返回即為中間結(jié)點。
刪除鏈表的倒數(shù)第 N 個結(jié)點：快指針先走 n 步，然后快慢指針同時走，快指針走到頭時，慢指針就在倒數(shù)第 n 個位置。
反向指針
反向指針經(jīng)典題目是N sum 系列和二分變種題目。
N sum 系列的經(jīng)典題目是：三數(shù)之和
def threeSum(nums):
nums.sort()
# [-4, -1, -1, 0, 1, 2]
res_list = []
# 頭部循環(huán)查找
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]:
# 從左往右，相同數(shù)值直接跳過
l += 1
while r > l and nums[r] == nums[r + 1]:
# 從右往左，相同數(shù)值直接跳過
r -= 1
elif three_sum > 0:
# 大于零，右邊數(shù)值大，左移
r -= 1
else:
# 小于零，左邊數(shù)值小，右移
l += 1
return res_list
在四種二分變種中，根據(jù)王爭算法專欄中，寫死low = 0，high = len(list) - 1。循環(huán)條件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 猜的數(shù)字大了
elif list[mid] < target:
low = mid + 1 # 注意4 猜的數(shù)字小了
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記錄模式串的字符數(shù)量，一個window記錄窗口的字符
unordered_map<char, int> need, window;
// 初始化need
for (char c : t) need[c]++;
int left = 0, right = 0;
// 兩個unordered_map的符合條件數(shù)目
int valid = 0;
// 記錄最小覆蓋子串的起始索引及長度
int start = 0, len = INT_MAX;
while (right < s.size()) {
// c 是將移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 進行窗口內(nèi)數(shù)據(jù)的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判斷左側(cè)窗口是否要收縮
while (valid == need.size()) {
// 在這里更新最小覆蓋子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是將移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 進行窗口內(nèi)數(shù)據(jù)的一系列更新
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實現(xiàn)
評論
圖片
表情