[数据结构与算法]专题复习：双指针(1) 滑动窗口(前提是：有序数组)

leetcode?1423. 可获得的最大点数

?

思路：由于必须包含数组的首元素或者尾部元素。可以采用在数组的两端来滑动。

?代码如下，首先，sum为数组中前k个元素之和，然后，窗右边往左划，tempsum - 出窗的元素，窗左边往左滑，到数组的末尾，tempSum + 进窗的元素，一直到窗中不包含首位元素或者末尾元素。

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int sum = 0;
        int size = cardPoints.size();
        for(int i = 0; i < k; i++)
        {
            sum += cardPoints[i];
        }
        int tempSum = sum;
        for(int i = k - 1; i >= 0; i--)
        {
            tempSum -= cardPoints[i];
            tempSum += cardPoints[size - (k - i)];
            sum = max(sum, tempSum);
        }
        return sum;

    }
};

leetcode26. 删除有序数组中的重复项

注意：不要使用额外的数组空间，你必须在?原地?修改输入数组?并在使用 O(1) 额外空间的条件下完成。

思路：将数组中出现的元素按顺序放在数组的首部，效果如下：

原数组 nums = [0,0,1,1,1,2,2,3,3,4]

效果后：nums =[0,1,2,3,4,2,2,3,3,4]?

双指针：left = 0， right = 1，如果nums[right] != nums[left]? ? { left++； nums[left] = nums[right];}

如果?nums[right] == nums[left]? right++； 最后，return left+1；

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0;
        int left = 0, right = 1;
        for(right = 1; right < size; right++)
        {
            if(nums[right] != nums[left])
            {
                nums[++left] = nums[right];
            }
        }
        return left+1;
        
    }
};

剑指 Offer 57 - II. 和为s的连续正数序列

利用滑窗， left和right 表示连续数组的范围

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        if(target == 1) return {{1}};
        vector<vector<int>> res;
        if(target == 2) return res;
        int left = 1, right = 2;
        int sum = left + right;
        while(left <= target/2)
        {
            if(sum == target)
            {
                vector<int> temp;
                for(int i = left; i <= right; i++) 
                {
                    temp.push_back(i);
                }
                res.push_back(temp);
            }
            if(sum >= target)
            {
                sum -= left;
                left++;
            }
            else
            {
                right++;
                sum += right;
            }
        }
        return res;

    }
};

leetcode?349. 两个数组的交集

跟下一题一致，只不过 做了去重复操作

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size(), size2 = nums2.size();
        vector<int> res;
        if(size1 == 0 || size2 == 0)  return res;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int left = 0, right = 0;
        while(left < size1 && right < size2)
        {
            if(nums1[left] < nums2[right]) left++;
            else if(nums1[left] > nums2[right]) right++;
            else
            {
                res.push_back(nums1[left]);
                left++;
                while(left < size1 && nums1[left] == nums1[left-1]) left++;
                right++;
                while(right < size2 && nums2[right] == nums2[right-1]) right++;
            }
        }
        return res;
    }
};

leetcode350. 两个数组的交集 II

首先，将两个数组排序，然后，利用双指针，分别遍历两个数组。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> res;
        int size1 = nums1.size();
        int size2 = nums2.size();
        if(size1 == 0 || size2 == 0) return res;
        int i = 0, j =0;//用i作为索引遍历nums1 用j作为索引遍历nums2
        while(i < size1 && j < size2)
        {
            if(nums1[i] > nums2[j]) j++;
            else if(nums1[i] < nums2[j]) i++;
            else
            {
                res.push_back(nums1[i]);
                i++;
                j++;
            }
        }
        return res;
    }
};

?leetcode?424. 替换后的最长重复字符

比较难想到，利用map记录出现次数最多的字符及次数

class Solution {
public:
    int characterReplacement(string s, int k) {
        int size = s.length();
        if(size <= 1) return size;

        unordered_map<char ,int> a;
        int maxSameCount = 0;
        int maxWindow = 0;
        int left = 0, right = 1;
        a[s[left]]++;
        for(;right < size; right++)
        {
            a[s[right]]++;
            maxSameCount = max(maxSameCount, a[s[right]]);
            if(maxSameCount + k < right - left + 1)
            {
                a[s[left]]--;
                left++;
            }
            else
            {
                maxWindow = max(maxWindow, right -left + 1);
            }
        }
        return maxWindow;

    }
};

leetcode125. 验证回文串

大写字符转换为小写字符 调用函数tolower? ?小写字符转换为大写字符 调用函数toupper

class Solution {
    bool isValid(char a)
    {
        if( a >='0'&& a <= '9' || a >= 'a'&& a <= 'z' || a >= 'A'&&a <= 'Z' )
        {
            return true;
        }
        return false;
    }
public:
    bool isPalindrome(string s) {
        int len = s.length();
        if(len <= 1) return true;

        int left = 0; int right = len - 1;
        while(left <= right)
        {
            if( isValid(s[left]) && isValid(s[right]))
            {

                if( tolower(s[left]) == tolower(s[right]))
                {
                    left++;
                    right--;
                }
                else
                {
                    return false;
                }
            }
            else if(!isValid(s[left]) && isValid(s[right])) left++;
            else if(isValid(s[left]) && !isValid(s[right])) right--;
            else
            {
                left++;
                right--;
            }
        }
        return true;
    }
};

leetcode109. 有序链表转换二叉搜索树

思路：将链表从中间分隔成两段，然后利用递归

利用快慢指针，找到链表中间节点

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return nullptr;
        if(!head->next) return new TreeNode(head->val);
        ListNode* slow = head, *fast = head, *pre = nullptr;
        //这里通过快慢指针找到链表的中间结点slow，pre就是中间
       //结点slow的前一个结点
        while(fast && fast->next)
        {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;//将链表分隔为两部分
        //slow是链表的中间节点
        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        return root;
    }
};

leetcode61. 旋转链表

思路：先把链表整成环， 另外，由于k可能大于链表的长度，因此有必要计算出链表的长度。

当k > len时，即相当于往右移动k%len个位置。最后，需要将之前的环形链表截断。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return head;
        ListNode *fast = head, *slow = head;
        int len = 1;
        //计算链表的长度
        while(fast->next)
        {
            len++;
            fast = fast->next;
        }
        fast->next = head;//将链表构成环

        //还需要将环形链表截断
        int step = k%len; //当k大于len时，实际上相当于向右移动k%len个位置
        //向右移step个位置，即需要在链表的第len - step个节点之前截断，因此，需要找到
        // 第len - step - 1个节点
        int k1 = len - step - 1;
        while((k1--)>0)
        {
            slow = slow->next;
        }
        ListNode *newHead = slow->next;
        slow->next =nullptr;
        return newHead;
    }
};

leetcode?3. 无重复字符的最长子串

思路：利用set set.insert(3)? ?erase(3)? ? ?set.find(3) != set.end()

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        if(len <= 1) return len;
        int maxLen = 0;
        set<char> a;
        int left = 0;
        a.insert(s[left]);
        for(int i = 1; i < len; i++)
        {
            while(a.find(s[i]) != a.end())
            {
                a.erase(s[left]);
                left++;
            }
            a.insert(s[i]);
            maxLen= max(maxLen, i - left + 1);
        }
        return maxLen;
    }
};

方法二：直接利用数组m 记录一个字母如果后面出现重复时，left 应该调整到的新位置

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> m(128,0);//m 记录一个字母如果后面出现重复时，left 应该调整到的新位置
        int left = 0;
        int maxLen = 0;
        for(int right = 0; right < s.length();right++)
        {
            if(m[s[right]] > 0)
            {
                left = max(left, m[s[right]]);//注意，此时要取最大的left 
                                              //比如"abba" 当取到第二个a时，此时的left是为2 不应该是 m[a]即1
            }
            m[s[right]] = right + 1; 
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

leetcode11:?11. 盛最多水的容器

左指针left为0 右指针left为len -1

遍历方式：nums[left] < nums[right] left++; 否则，right++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int len = height.size();
        int left = 0, right = len - 1;
        int maxArea = 0;
        while(left < right)
        {
            int areaTemp = (right - left)*min(height[right] , height[left]);
            maxArea = max(maxArea, areaTemp);
            if(height[left] < height[right]) left++;
            else right--;
        }
        return maxArea;
    }
};

??