雙指針匯總 - 簡書

雙指針

lc3

無重復(fù)字符的最長子串

給定一個字符串 s 踪栋，請你找出其中不含有重復(fù)字符的 最長子串 的長度焙格。

 

示例 1:

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3夷都。
示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"眷唉，所以其長度為 1。
示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"，所以其長度為 3冬阳。
     請注意蛤虐，你的答案必須是 子串 的長度，"pwke" 是一個子序列摩泪，不是子串笆焰。
示例 4:

輸入: s = ""
輸出: 0
 

提示：

0 <= s.length <= 5 * 104
s 由英文字母、數(shù)字见坑、符號和空格組成

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有嚷掠。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處荞驴。

需要兩部分不皆。

1.一個類似于map的機構(gòu)，記錄字符出現(xiàn)的位置熊楼。

2.雙指針霹娄，移動。

如果重復(fù)的話鲫骗，左指針移動到字符出現(xiàn)位置+1犬耻，字符出現(xiàn)位置更新為右指針在的位置，右指針再加1

這里判斷是否出現(xiàn)過用asc[s[i]]>=left, 因為↑行為只更新重復(fù)字符出現(xiàn)位置执泰，沒有更新對應(yīng)map中其它是否出現(xiàn)過的值枕磁，但左指針之前的已無比較價值，因此可以幫助排除术吝。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //字符有限制 hashset
        int ans=0;
        if(s.length()==0)
            return ans;
                int len=s.length();
        // int z[len];
        int asc[128];
        memset(asc,-1,sizeof(asc));
        // fill(z,z+s.length(),1);
        int left=0;
        int right=-1;
        for(int i=0;i<len;i++){
            if(asc[s[i]]>=left){
                left=asc[s[i]]+1;
                right+=1;

            }else{
                right+=1;

            }
                asc[s[i]]=i;
                ans=max(ans,right-left+1);
            // cout<<z[i]<<endl;
        }
        // sort(z,z+len);

        return ans;
        
    }
};

環(huán)形鏈表快慢指針

lc141&142

1.一個快指針计济，一次走兩步，一個慢指針排苍，一次走一步沦寂。

如果快能追上慢，則是環(huán)形鏈表淘衙。

2.找到環(huán)入口传藏。

兩者相遇后，一個指針放在頭幔翰，一個指針放在相遇點漩氨，每次都走一步，則再次相遇點是環(huán)的入口遗增。

對于這種問題，也可以用map來做款青，即map<ListNode*,int> 一個節(jié)點遍歷做修，第一次發(fā)現(xiàn)重復(fù)出現(xiàn)的節(jié)點，就是環(huán)的入口。

方法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) {
        //找到環(huán)的入口
        ListNode * tmp;
       if(!head||!head->next)
            return NULL;
        ListNode *fast=head->next->next;
        ListNode *slow=head->next;
        while(fast!=slow){
            slow=slow->next;
            if(fast&&fast->next)
                fast=fast->next->next;
            else
                return NULL;
        }
        if(!fast)
            return NULL;
        
        ListNode *pre=fast;
        ListNode *now=head;
        while(now!=pre){
            now=now->next;
            pre=pre->next;
        }
        return now;
            
        
    }
};

方法2：

/**
 * 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) {
        //找到環(huán)的入口
        map<ListNode*,int> res;
        ListNode* cur=head;
        if(!cur){
            return nullptr;
        }
        int index=0;
        while(cur){
            if(res.find(cur)==res.end())
                res[cur]=1;
            else{
                return cur;
            }
            index+=1;
            cur=cur->next;
        }
        return NULL;
            
        
    }
};

lc26& lc19

http://www.reibang.com/p/f1416af4cfde

擋板類問題（lc11&lc42)

http://www.reibang.com/p/14952c22473a

對稱二叉樹（lc101）

判斷二叉樹是否是對稱的

1.層次遍歷饰及，最好想蔗坯，因為每次往隊列里push left、right相反順序的值就可燎含。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        //一個右中左
        //一個左中右
        //得到兩個vector宾濒，看看是否一致。1屏箍、大小是否一致绘梦。2、內(nèi)容是否一致
        //↑這樣想是不對的赴魁。例子中某一個就不對卸奉。
        if(!root)
        return true;

        queue<TreeNode*> t1;
        queue<TreeNode*> t2;
        t1.push(root);
        t2.push(root);

        while(!t1.empty()&&!t2.empty()){
                    TreeNode* tmp1;
            TreeNode* tmp2;
            tmp1=t1.front();
            tmp2=t2.front();
            t1.pop();
            t2.pop();
            //cout<<tmp1->val<<tmp2->val<<endl;;
            if(tmp1->val!=tmp2->val)
                return false;
            if(tmp1->left&&tmp2->right){
                t1.push(tmp1->left);
                t2.push(tmp2->right);
            }else if(!(!tmp1->left&&!tmp2->right))
                return false;
            if(tmp1->right&&tmp2->left){
                t1.push(tmp1->right);
                t2.push(tmp2->left);
            }else if(!(!tmp1->right&&!tmp2->left))
                return false;        

        }
        if(!t1.empty()||!t2.empty())
            return false;
        return true;
        // return checksym(root,root);


        


    }
};

2.遞歸。
同時傳入兩個指針颖御，這兩個指針每次對比相反方向的值就可
↑這個一直沒有轉(zhuǎn)過來榄棵，一直沒有想明白

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool checksym(TreeNode* leftnode,TreeNode*rightnode){
        if(!leftnode&&!rightnode)
            return true;
        if(!leftnode||!rightnode)
            return false;
        return (leftnode->val==rightnode->val) && (checksym(leftnode->left,rightnode->right)) &&(checksym(leftnode->right,rightnode->left));
    }
    bool isSymmetric(TreeNode* root) {
        //一個右中左
        //一個左中右
        //得到兩個vector，看看是否一致潘拱。1疹鳄、大小是否一致。2芦岂、內(nèi)容是否一致
        //↑這樣想是不對的瘪弓。
        if(!root)
        return true;

        return checksym(root,root);


        


    }
};