双指针汇总

双指针

lc3

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

 

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:

输入: s = ""
输出: 0
 

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

需要两部分。

1.一个类似于map的机构，记录字符出现的位置。

2.双指针，移动。

如果重复的话，左指针移动到字符出现位置+1，字符出现位置更新为右指针在的位置，右指针再加1

这里判断是否出现过用asc[s[i]]>=left, 因为↑行为只更新重复字符出现位置，没有更新对应map中其它是否出现过的值，但左指针之前的已无比较价值，因此可以帮助排除。

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;
        
    }
};

环形链表快慢指针

lc141&142

1.一个快指针，一次走两步，一个慢指针，一次走一步。

如果快能追上慢，则是环形链表。

2.找到环入口。

两者相遇后，一个指针放在头，一个指针放在相遇点，每次都走一步，则再次相遇点是环的入口。

对于这种问题，也可以用map来做，即map<ListNode*,int> 一个节点遍历，第一次发现重复出现的节点，就是环的入口。

方法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 * 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) {
        //找到环的入口
        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

https://www.jianshu.com/p/f1416af4cfde

挡板类问题（lc11&lc42)

https://www.jianshu.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、内容是否一致
        //↑这样想是不对的。例子中某一个就不对。
        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.递归。
同时传入两个指针，这两个指针每次对比相反方向的值就可
↑这个一直没有转过来，一直没有想明白

/**
 * 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、内容是否一致
        //↑这样想是不对的。
        if(!root)
        return true;

        return checksym(root,root);


        


    }
};