leetcode——雙指針
-
-
- 1. 兩數之和Ⅱ-輸入有序數組（167）
- 2.合并兩個有序數組（88）
- 3.快慢指針（142）
- 4.滑動視窗（76最小覆寫子串）
- 練習
-
- 1.平方數之和（633）
- 2.驗證回文字元串（680）
- 3.通過删除字母比對到字典裡最長單詞（524）
-
1. 兩數之和Ⅱ-輸入有序數組（167）
給定一個已按照 升序排列的整數數組 numbers ，請你從數組中找出兩個數滿足相加之和等于目标數 target 。
函數應該以長度為 2 的整數數組的形式傳回這兩個數的下标值。numbers 的下标 從 1 開始計數 ，是以答案數組應當滿足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假設每個輸入隻對應唯一的答案，而且你不可以重複使用相同的元素。
示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目标數 9 。是以 index1 = 1, index2 = 2 。
示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
題解： i指向開頭，j指向結尾，周遊一遍。
vector<int> twoSum(vector<int>& numbers, int target) {
int i = 0, j = numbers.size() - 1, sum;
while(i < j){
sum = numbers[i] + numbers[j];
if(sum == target) break;
if(sum < target) i++;
else j--;
}
return vector<int>{i+1,j+1};
}
2.合并兩個有序數組（88）
給你兩個有序整數數組 nums1 和 nums2，請你将 nums2 合并到 nums1 中，使 nums1 成為一個有序數組。
初始化 nums1 和 nums2 的元素數量分别為 m 和 n 。你可以假設 nums1 的空間大小等于 m + n，這樣它就有足夠的空間儲存來自 nums2 的元素。
示例 1：
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
示例 2：
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
題解： 因為兩個數組都是有序的，直接從最後開始比較大小，然後賦給nums1。如果nums1複制完，nums2需要單獨再複制剩下的。如果nums2複制完，nums1不需要改變，因為原來就是有序的。
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int k = m + n - 1;
m--;
n--;
while(m >= 0 && n >= 0){
if(nums1[m] < nums2[n]){
nums1[k--] = nums2[n--];
}else{
nums1[k--] = nums1[m--];
}
/**
* 可改為
* nums1[k--] = nums1[m] < nums2[n] ? nums2[n--] : nums1[m--];
*
* */
}
while(n >= 0){
nums1[k--] = nums2[n--];
}
}
3.快慢指針（142）
給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。
為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。注意，pos 僅僅是用于辨別環的情況，并不會作為參數傳遞到函數中。
說明：不允許修改給定的連結清單。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：傳回索引為 1 的連結清單節點
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：傳回索引為 0 的連結清單節點
解釋：連結清單中有一個環，其尾部連接配接到第一個節點。
示例 3：
輸入：head = [1], pos = -1
輸出：傳回 null
解釋：連結清單中沒有環。
提示：
- 連結清單中節點的數目範圍在範圍 [0, 104] 内
- -105 <= Node.val <= 105
- pos 的值為 -1 或者連結清單中的一個有效索引
題解： 對于連結清單找環，通用的解法為：快慢指針（Floyd判圈法）。給定兩個指針，一快每次走兩步，一慢每次走一步，相遇則有環。
随便拿個圖，m為連結清單起點到圈起點的距離。n為環的周長。設圖中兩段紅線中間短的距離(即圈起點到相遇點的距離）為k。長的距離（即相遇點到圈起點的距離）為l。
2slow = fast;
慢的走了m+k，快的走了m + k + xn（x圈環）
則有2（m + k） = m + k + xn
即m + k = xn
得m = (x-1)n + l。
是以在相遇之後，讓快指針回到起點，并每次步伐大小改為1，慢指針繼續走。一定會在圈起點相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
do{
if(!fast || !fast->next) return NULL;
fast = fast->next->next;
slow = slow->next;
}while(fast != slow);
fast = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return fast;
}
};
4.滑動視窗（76最小覆寫子串）
給你一個字元串 s 、一個字元串 t 。傳回 s 中涵蓋 t 所有字元的最小子串。如果 s 中不存在涵蓋 t 所有字元的子串，則傳回空字元串 " " 。
注意：如果 s 中存在這樣的子串，我們保證它是唯一的答案。
示例 1：
輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”
示例 2：
輸入：s = “a”, t = “a”
輸出：“a”
提示：
- 1 <= s.length, t.length <= 105
- s 和 t 由英文字母組成
題解： 用長度128的數組來映射字元，也可用哈希表替代。其中chars表示目前每個字元缺少的數量，flag表示每個字元是否在t中存在。
string minWindow(string s, string t) {
vector<int> chars(128,0);
vector<bool> flag(128,false);
//統計t中字元的情況
for(int i = 0; i < t.size(); i++){
flag[t[i]] = true;
++chars[t[i]];
}
// 移動視窗，不斷更改統計資料
int cnt = 0, l = 0, min_l = 0, min_size = s.size() + 1;
for(int r = 0; r < s.size(); r++){
if(flag[s[r]]){
if(--chars[s[r]] >= 0){
++cnt;
}
//若目前滑動視窗已包含t中所有字元
//嘗試l右移，在不影響結果的前提下獲得最短子字元串。
while(cnt == t.size()){
if(r - l + 1 < min_size){
min_l = l;
min_size = r - l + 1;
}
if(flag[s[l]] && ++chars[s[l]] > 0){
--cnt;
}
++l;
}
}
}
return min_size > s.size() ? "" : s.substr(min_l, min_size);
}
練習
1.平方數之和（633）
給定一個非負整數 c ，你要判斷是否存在兩個整數 a 和 b，使得 a^2+ b^2 = c 。
示例 1：
輸入：c = 5
輸出：true
解釋：1 * 1 + 2 * 2 = 5
示例 2：
輸入：c = 3
輸出：false
示例 3：
輸入：c = 4
輸出：true
示例 4：
輸入：c = 2
輸出：true
示例 5：
輸入：c = 1
輸出：true
提示：
0 <= c <= 2^31 - 1
題解： 這道題比較簡單，但是要注意一點細節。因為它是a^2 + b ^ 2 = c,是以我們可以使用雙指針周遊一遍到 0 ~ sqrt（c）即可。從測試用例c=2為true可以看出，兩個數是可以重複的。
bool judgeSquareSum(int c) {
long r = sqrt(c);
long l = 0;
while(l <= r){
if((l * l + r * r) == c)
return true;
else if((l * l + r * r) < c){
l++;
}else{
r--;
}
}
return false;
}
2.驗證回文字元串（680）
給定一個非空字元串 s，最多删除一個字元。判斷是否能成為回文字元串。
示例 1:
輸入: “aba”
輸出: True
示例 2:
輸入: “abca”
輸出: True
解釋: 你可以删除c字元。
注意:
字元串隻包含從 a-z 的小寫字母。字元串的最大長度是50000。
題解： 無
bool checkPalidrome(string s, int l, int r){
for(int i = l, j = r; i < j; i++, j--){
if(s[i] != s[j])
return false;
}
return true;
}
bool validPalindrome(string s) {
int l = 0;
int r = s.length() - 1;
while(l < r){
if(s[l] == s[r]){
l++;
r--;
}
else return checkPalidrome(s,l,r-1) || checkPalidrome(s,l+1,r);
}
return true;
}
3.通過删除字母比對到字典裡最長單詞（524）
給定一個字元串和一個字元串字典，找到字典裡面最長的字元串，該字元串可以通過删除給定字元串的某些字元來得到。如果答案不止一個，傳回長度最長且字典順序最小的字元串。如果答案不存在，則傳回空字元串。
示例 1:
輸入:
s = “abpcplea”, d = [“ale”,“apple”,“monkey”,“plea”]
輸出:
“apple”
示例 2:
輸入:
s = “abpcplea”, d = [“a”,“b”,“c”]
輸出:
“a”
說明:
- 所有輸入的字元串隻包含小寫字母。
- 字典的大小不會超過 1000。
- 所有輸入的字元串長度不會超過 1000。
題解： 暴力法就是周遊比較集合裡的字元串和s了。
string findLongestWord(string s, vector<string>& d) {
string str = "";
for(string strd : d){
for(int i = 0,j = 0; i < s.length(); i++) {
if(s[i] == strd[j]) j++;
if(j == strd.length()) {
if(strd.length() > str.length() || (strd.length() == str.length() && strd.compare(str) < 0)) {
str = strd;
}
}
}
}
return str;
}