常見演算法技巧之——雙指標思想
? 雙指標思想是指設定兩個指標解決一些演算法問題，一般用的比較多的就是去解決陣列、鏈表類的問題，還有很耳熟能詳的二分查找問題，本文將根據自己平時做題的總結以及在網上看到的其他大佬的總結講解來討論一下雙指標的使用技巧，本文會根據我平時做題實時更新，
快慢指標
? 雙指標的快慢指標用法是我最開始理解的第一種用法，快慢指標一般用來解決鏈表的問題多一些，設定一快一慢兩個指標fast和slow，初始化指向鏈表表頭，
1、計算鏈表的中點
? 給定一個鏈表，要求回傳該鏈表的中點節點，
? 設定兩個快慢指標，都從頭節點開始，快指標每次前進兩個節點，慢指標每次前進一個節點，當快指標到達鏈表末尾的時候，慢指標剛好到達中點的節點，
? 下圖中藍色指標表示快指標，橙色指標表示慢指標，
//函式中最后的判斷return有問題，直接return slow即可，這樣寫是為了區分奇偶不同的區別
public LinkedList mid (LinkedList head) {
LinkedList fast = head;
LinkedList slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast == null) { //說明有偶數個節點，此時慢指標指向的是中點靠右的節點
return slow;
} else { //fast.next == null，說明有奇數個節點，此時慢指標指的恰好是中點
return slow;
}
}
2、判斷鏈表中是否有環
? 如果已知一個單鏈表的表頭，判斷該鏈表中是否含有一個環，通常單鏈表都是一個節點只指向下一個節點這樣的鏈式結構，如果只有一個指標，從頭節點開始一路next，如果碰到null則表示有環，但如果沒有環則會一直在環里打轉，所以單指標很難解決這樣的問題，
? 設定雙指標，兩個指標一快一慢，按照不同的速度從頭節點開始往下遍歷，如果最后兩個指標相遇則表示有環，如果沒有相遇，而是快指標先到了null則表示沒有環，
public boolean hasCycle (LinkedList head) {
LinkedList fast = head;
LinkedList slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { //最后兩指標相遇，表示有環
return true;
}
}
return false; //若兩指標不相等，則說明快指標到了null
}
3、如果鏈表中有環，回傳環的起始位置
? 如果已知一個鏈表中含有環，要找出環的位置，回傳環的起始節點，
? 按照2中所說兩個指標相遇的時候說明這個鏈表中有環，那么既然快指標速度是慢指標速度的二倍，那么假設兩個指標第一次相遇的時候慢指標走了k步，則快指標就走了2k步，那么快指標的路程減去慢指標的路程就是環的長度，即為k，
? 那此時假設環的起點距離兩指標的相遇點的距離為m，則從開始相遇點繼續往下走，直到再次達到環起點，一共走了k-m步，而之前假設慢指標走了k步，從開始到第一次相遇，慢指標是從鏈表表頭到第一次相遇點，走了k步，那么慢指標從表頭到環的起點位置的距離也應該是k-m步（因為環起點距離相遇點是m步），因此當兩指標第一次相遇的時候，將一個指標重新置到頭節點，然后兩個步調一致，同樣速度，每次前進一步，當再次相遇的時候，相遇位置就是環的起點，
4、求鏈表中環的長度
? 這個很簡單，當兩個指標第一次相遇的時候，保持快指標不動，讓慢指標繼續跑，兩指標再次相遇的時候慢指標跑的距離就是環的長度，
5、求鏈表倒數第k個節點
? 先讓某個指標走k步，然后兩個指標同時走，當前面的指標走到末尾的時候，后面的指標呢恰好走到倒數第k個節點，
leetcode中的例題
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
while (k > 0) {
--k;
fast = fast.next;
}
while (fast!=null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
左右指標
? 也有叫做碰撞指標的，通常需要一個有序的陣列，左右兩個指標其實就是指示陣列的下標，通常一個初始化在開頭，一個初始化在結尾，
1、二分查找
? 這個是很經典的例子，在有序的陣列中查找某個數（記為x），回傳下標，
? 剛開始兩個指標一前一后，判斷兩指標最中間的元素是否為查找的元素x，若是直接回傳，如果不是且小于x，則將左指標移動到中間位置+1，即(l+r)/2 + 1，若大于x，則將右指標移動到中間位置-1，
public int BinarySearch (int[] nums, int target) {
int l = 0, r = nums.length-1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1; //表示未找到
}
2、n數之和的問題
? 這里以leetcode上的一個兩數之和的題為例為例，如果是三數之和可以轉化為一個數與兩數之和的和的問題，
兩數之和
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍，
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
? 先對陣列排序，設定頭尾兩個指標，判斷相加之后與目標數的大小，如果相加之后大于目標，則移動右指標，讓右指標往左滑動，使得和更小，反之則讓左指標向右滑動，直到等于target，
? 但需要注意這道題給的并不一定是有序陣列，所以并不能使用這個方法，但可以作為一個引例來啟發我們，假設陣列是有序的，
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Arrays.sort(nums);
int l = 0, r = nums.length - 1;
while (l < r) {
if (nums[l] + nums[r] == target) {
return new int[] {l,r};
} else if (nums[l] + nums[r] < target) {
l = l + 1;
} else {
r = r - 1;
}
}
return new int[] {-1,-1};
}
三數之和
給你一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組，
注意：答案中不可以包含重復的三元組，
示例：
給定陣列 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/3sum
? 正如前文所說，可以將三數之和轉化為兩數與一個數之和，因為要三數之和為0，先給定一個數，則另外兩個數之和就得等于這個數的相反數，則可以將這兩個數的和轉化為上述的兩數之和問題，
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//剪枝，如果這個數和前一個數相等，那么由此得到的答案必和前面重復
if (i > 0 && nums[i] == nums[i-1])
continue;
int target = -nums[i]; //b+c = target
int k = nums.length-1;
for (int j = i+1; j < nums.length; j++) {
if (j > i+1 && nums[j] == nums[j-1]) //j > i+1 保證了j指標至少挪動了一次
continue;
while (j < k && nums[j] + nums[k] > target) {
k--;
}
if (j == k) { //j和k的指標重合后，沒有一個k可以滿足a+b+c=0 && j<k
break;
}
if (nums[j] + nums[k] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
res.add(list);
}
}
}
return res;
}
}
四數之和
給定一個包含 n 個整數的陣列 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復的四元組，
注意：
答案中不可以包含重復的四元組，
示例：
給定陣列 nums = [1, 0, -1, 0, -2, 2]，和 target = 0，
滿足要求的四元組集合為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/4sum
? 繼續類比前面的三數之和，不過是多了層回圈而已，利用雙回圈先確定兩個數，然后剩下的兩個數就又變成了兩數之和的問題，但這類問題因為有重復的元素所以要注意剪枝去掉重復的答案，還有就是陣列必需有序，
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i <= nums.length-4; i++) {
if (i>0 && nums[i] == nums[i-1])
continue;
for (int j = i+1; j <= nums.length-3; j++) {
int tar = target - nums[i] - nums[j];
if (j>i+1 && nums[j] == nums[j-1])
continue;
for (int l = j+1; l <= nums.length-2; l++) {
if (l>j+1 && nums[l] == nums[l-1])
continue;
int r = nums.length-1;
while (r > l && nums[l] + nums[r] > tar)
r--;
if (r == l) {
break;
}
if (nums[l] + nums[r] == tar) {
List<Integer> res = new ArrayList<>();
res.add(nums[i]);
res.add(nums[j]);
res.add(nums[l]);
res.add(nums[r]);
result.add(new ArrayList<>(res));
}
}
}
}
return result;
}
}
3、反轉陣列
? 將一個陣列進行反轉，只需要設定好前后兩個指標，一個初始化指頭，另一個初始化指尾，然后交換兩個指標指向的內容，然后前面的指標+1，后面的指標-1，直到兩指標相遇（陣列大小為奇數），或者兩指標相差1（陣列大小為偶數），
public void reverse (int[] nums) {
int l = 0, r = nums.length-1;
while (l < r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
}
滑動視窗
? 其實滑動視窗應該也是左右指標中的一種，但因為它相對來說難以理解，所以單獨拎出來做一討論，
? 滑動視窗大概理解起來很簡單，但就是自己動手寫的時候會遇到很多問題，正所謂熟能生巧，筆者也才開始練這些演算法題，希望記錄下學習的程序，
1、無重復字符的最長子串
? 滑動視窗就是維護一個視窗，然后根據題目和新遇到的情況不斷更新這個視窗，不斷優化可能的解，舉個例子，比如leetcode上的無重復字符的最長子串問題，
給定一個字串，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
? 利用滑動視窗可以完美的解決這個問題，用左指標指示視窗的最左端，右指標指示視窗的最右端，初始左指標指示第0個元素，右指標指示-1，定義一個set集合存盤當前解（即當前視窗中包含的字符），然后開始一直移動右指標，使其向右移動，直到碰到一個已經添加到當前解中的字符，這時記錄下當前的set的大小為當前最優解，然后將左指標向右移動一個，并在當前解set中移出視窗最左邊的字符，之后就是繼續移動右指標，更新當前解，每次右指標碰到當前解中已存在的字符時，判斷一下當前解的大小，如果比之前的最優解更優，則更新，反之不更新，繼續移出視窗中最左邊的字符，然后繼續重復上述操作，直到右指標到達字串末尾，
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> ss = new HashSet();
//定義右指標
int res = 0, r = -1;
for(int i = 0; i < s.length(); i++) {
if (i != 0) {
ss.remove(s.charAt(i-1)); //去掉上次最左邊的元素
}
while (r+1 < s.length() && !ss.contains(s.charAt(r+1))) {
ss.add(s.charAt(r+1));
++r; //移動右指標
}
res = Math.max(res,r-i+1); //上次的最優和這次的最優進行對比，每次子串的開頭不一樣
if (r == s.length()-1) {
//r右指標已經到了最右邊，所以直接break出來，因為后面不會再有向當前解中增加元素，只會慢慢彈出當前解的元素，所以不必再繼續
break;
}
}
return res;
}
}
2、最小覆寫子串
給你一個字串 S、一個字串 T ，請你設計一種演算法，可以在 O(n) 的時間復雜度內，從字串 S 里面找出：包含 T 所有字符的最小子串，
示例：
輸入：S = "ADOBECODEBANC", T = "ABC"
輸出："BANC"
提示：
如果 S 中不存這樣的子串，則回傳空字串 ""，
如果 S 中存在這樣的子串，我們保證它是唯一的答案，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-window-substring
? 1. 這道題利用滑動視窗也可以很優雅的解決，還是先初始化兩個指標l = 0, r = 0指向字串S，開始先向右移動右指標使得視窗增大，而右指標停止移動的條件是當前左指標到右指標，即視窗內已經包含了字串T，接著開始向右移動左指標，使得視窗盡可能的小，但要確保視窗中始終是包含字串T的，等到左指標移動到不能再移動的時候，也就是若左指標再移動一次，則視窗中將不能包含字串T的所有字符，這時的視窗是當前解，也就是當前最優解，
? 2. 將其保存下來，之后向右移動一下左指標，使得視窗中不再包含T的所有字符，也就是移出去了一個T中的字符，繼續向右移動右指標使其擴張，直到視窗再次包含了字串T，然后繼續移動左指標直到視窗最小，比較當前解和前面的最優解，保存下更優的，
? 3. 接下來就是重復操作2，直到右指標到最后一個字符后，再移動左指標，得到視窗最小的時候的解，并繼續比較之前的最優解，保存更優的，
? 上面大概寫完滑動的程序，再來說說針對這個題，實作的時候的一些細節，
- 維護一個needs陣列，保存T字串每個字符出現的次數，再維護一個window陣列，保存當前視窗中各個字符的數量，后面可以根據這兩個陣列判斷當前視窗是否包含了字串T
- 使用一個count變數，如果當前字符屬于T，而且視窗中還沒有足夠多的這個字符就說明這個字符目前對于視窗來說是必要的，那么把這個字符加入視窗后給count++，如果視窗中已經有了足夠的這個字符，那將其加入視窗后無需給count++，而當將一個字符移出視窗時，如果移出了這個字符，視窗不再包含T的所有字符，就說明這個字符目前對于視窗來說也是必要的，那移出后給
count--，如果不是必需的則不需要減小count，這樣維護下來的一個count可以指示當前視窗是否完整包含了字串T，如果count的大小等于T的長度就說明此時的視窗完整的包含了T，這樣就可以快速判斷視窗是否包含T，節省了程式執行時間，
//給出的示例題解中用curr代替了window，curr記為current，表示當前的視窗
class Solution {
public String minWindow(String s, String t) {
if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
return "";
}
int l = 0, r = 0; //定義左右指標
int size = Integer.MAX_VALUE; //視窗大小
int ans_l = 0; //最優情況下左邊的指標
int count = 0;
//下面needs和curr的下標是字符的ASCII碼值
int[] needs = new int[255]; //需要的
int[] curr = new int[255]; //現有的
for (int i = 0; i < t.length(); i++) { //初始化needs
needs[t.charAt(i)]++;
}
while (r < s.length()) {
char c = s.charAt(r); //當前右指標指的字符
if (needs[c] != 0) { //需要這個字符
if (curr[c] < needs[c]) { //這個字符對于目前視窗是必需的
count++;
}
curr[c]++;
}
r++;
while (count == t.length() && l < r) {
if (size > r-l) {
ans_l = l;
size = r-l;
}
char c1 = s.charAt(l);
if (needs[c1] > 0) {
if (curr[c1] == needs[c1]) { //這個字符對于目前視窗來說是必需的
count--;
}
curr[c1]--;
}
l++;
}
}
return size==Integer.MAX_VALUE?"": s.substring(ans_l,ans_l+size);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/132244.html
標籤：其他