雙指針和滑動(dòng)窗口算法模板
作者：小sen
雙指針的算法原理，通過(guò)兩個(gè)指針在一個(gè)for循環(huán)下完成兩個(gè)for循環(huán)的工作。雙指針的算法模板比較簡(jiǎn)單，突破口主要是需要找到題目中的單調(diào)性，從而加以利用。
雙指針的算法原理，通過(guò)兩個(gè)指針在一個(gè)for循環(huán)下完成兩個(gè)for循環(huán)的工作。時(shí)間復(fù)雜度從
優(yōu)化到了
。
雙指針的算法模板比較簡(jiǎn)單，突破口主要是需要找到題目中的單調(diào)性，從而加以利用。
快慢指針
快慢指針一個(gè)鏈表操作技巧，它還有一個(gè)有趣的名字，龜兔賽跑。
- 移除元素：
- 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)的入口位置：應(yīng)用快慢指針，快指針走兩步，慢指針走一步。假使有環(huán)，兩指針遲早相遇;假使無(wú)環(huán)，快指針就會(huì)走到盡頭，退出循環(huán)。如果有環(huán)，慢指針重新開(kāi)始，此時(shí)快指針是交點(diǎn)，同速兩指針交點(diǎ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é)點(diǎn)：應(yīng)用快慢指針，快指針走兩步，慢指針走一步?？熘羔樧叩奖M頭時(shí)，慢指針剛好走了一半，返回即為中間結(jié)點(diǎn)。
- 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)：快指針先走 n 步，然后快慢指針同時(shí)走，快指針走到頭時(shí)，慢指針就在倒數(shù)第 n 個(gè)位置。
反向指針
反向指針經(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]這個(gè)條件
- 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ù)值直接跳過(guò)
- l += 1
- while r > l and nums[r] == nums[r + 1]:
- # 從右往左，相同數(shù)值直接跳過(guò)
- r -= 1
- elif three_sum > 0:
- # 大于零，右邊數(shù)值大，左移
- r -= 1
- else:
- # 小于零，左邊數(shù)值小，右移
- l += 1
- return res_list
在四種二分變種中，根據(jù)王爭(zhēng)算法專(zhuān)欄中，寫(xiě)死low = 0，high = len(list) - 1。循環(huán)條件low <= high。往左移動(dòng)high = mid - 1，往右移動(dòng)low = mid + 1
- def binary_search(nums, target):
- '''標(biāo)準(zhǔn)二分算法模板'''
- low = 0
- high = len(nums) - 1 # 注意1 low和high用于跟蹤在其中查找的列表部分
- while low <= high: # 注意2 只要還沒(méi)有縮小到只有一個(gè)元素，就不停的檢查
- 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):
- '''求第一個(gè)等于定值 '''
- low = 0
- high = len(nums) - 1
- # 這里需要 <=
- while low <= high:
- # 這里需要注意： 就是使用((high - low) >> 1)需要雙擴(kuò)號(hào)
- 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):
- '''求最后一個(gè)等于定值的'''
- 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
- '''
- 查找第一個(gè)大于等于給定值的元素
- * 如序列：3，4，6，7，19 查找第一個(gè)大于5的元素，即為6，return 2
- * 第一個(gè)大于給定值，則說(shuō)明上一個(gè)小于給定值，依次判斷
- '''
- 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:
- # 往左移動(dòng)
- high = mid - 1
- else:
- # 往右移動(dòng)
- low = mid +1
- return -1
- '''
- 查找第一個(gè)小于給定值的元素
- * 如序列：3，4，6，7，19 查找第一個(gè)小于5的元素，即為4，返回1
- * 第一個(gè)大于給定值，則說(shuō)明上一個(gè)小于給定值，依次判斷
- '''
- def bsearch_high_not_greater(nums,target):
- '''求最后一個(gè)小于等于值'''
- 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
滑動(dòng)窗口
原文：https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA
滑動(dòng)窗口算法是雙指針技巧的最高境界，主要用于兩個(gè)字符串匹配的問(wèn)題。
掌握了滑動(dòng)窗口的解題模板可以輕松解決一系列字符串匹配的問(wèn)題。
下面模板代碼來(lái)源labuladong，解決LeetCode 76 題，Minimum Window Substring，求最小覆蓋子串。
- /* 滑動(dòng)窗口算法框架 */
- string minWindow(string s, string t) {
- // 兩個(gè)unordered_map ，一個(gè)need記錄模式串的字符數(shù)量，一個(gè)window記錄窗口的字符
- unordered_map<char, int> need, window;
- // 初始化need
- for (char c : t) need[c]++;
- int left = 0, right = 0;
- // 兩個(gè)unordered_map的符合條件數(shù)目
- int valid = 0;
- // 記錄最小覆蓋子串的起始索引及長(zhǎng)度
- int start = 0, len = INT_MAX;
- while (right < s.size()) {
- // c 是將移入窗口的字符
- char c = s[right];
- // 右移窗口
- right++;
- // 進(jìn)行窗口內(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++;
- // 進(jìn)行窗口內(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實(shí)現(xiàn)
責(zé)任編輯：姜華
來(lái)源：
Python之王
