Leetcode-双指针法

Leetcode-双指针法

双指针法

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

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int result = 0;
        unordered_set<char> st;
        int left = 0;
        for(int right=0; right<s.size(); right++){
            while(st.find(s[right]) != st.end()){
                st.erase(s[left]);
                left++;
            }
            st.insert(s[right]);
            result = max(result, right - left + 1);
        }
        return result;
    }
};

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        bool next;
        int sign = (m + n) / 2; 
        if((m + n) % 2 == 1){
            next = false;
        } else{
            sign -= 1;
            next = true;
        }
        int res1 = 0;
        int res2 = 0;
        int globalindex = 0;
        int nums1index = 0;
        int nums2index = 0;
        while(globalindex <= sign){
            if(nums1index < m && nums2index < n){
                if(nums1[nums1index] < nums2[nums2index]){
                    res1 = nums1[nums1index];
                    nums1index += 1;
                } else{
                    res1 = nums2[nums2index];
                    nums2index += 1;
                }
            } else if (nums1index < m){
                res1 = nums1[nums1index];
                nums1index += 1;
            } else {
                res1 = nums2[nums2index];
                nums2index += 1;
            }
            globalindex += 1;
        }
        if(next == false){
            return res1;
        }
        if(nums1index < m && nums2index < n){
            if(nums1[nums1index] < nums2[nums2index]){
                res2 = nums1[nums1index];
            } else{
                res2 = nums2[nums2index];
            }
        } else if (nums1index < m){
            res2 = nums1[nums1index];
        } else {
            res2 = nums2[nums2index];
        }
        return ((double)res1 + (double)res2) / 2.0;
    }
};

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

class Solution {
public:
    string longestPalindrome(string s) {
        vector<int> result = {0,0};
        for(int i=0;i<s.size()-1;i++){
            int left = i;
            int right = i;
            while(left >= 0 && right < s.size()){
                if(s[left] == s[right]){
                    if(result[1] - result[0] < right - left){
                        result[1] = right;
                        result[0] = left;
                    }
                    right += 1;
                    left -= 1;
                } else{
                    break;
                }
            }
            left = i;
            right = i+1;
            while(left >= 0 && right < s.size()){
                if(s[left] == s[right]){
                    if(result[1] - result[0] < right - left){
                        result[1] = right;
                        result[0] = left;
                    }
                    right += 1;
                    left -= 1;
                } else{
                    break;
                }
            }
        }
        return s.substr(result[0], result[1]-result[0] + 1);
    }
};

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 例如，121 是回文，而 123 不是。

class Solution {
public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        int left = 0;
        int right = s.size() - 1;
        while(left < right){
            if(s[left] != s[right]){
                return false;
            }
            left += 1;
            right -= 1;
        }
        return true;
    }
};

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

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

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index = m + n - 1;
        m -= 1;
        n -= 1;
        while(index >= 0){
            if(m < 0){
                nums1[index] = nums2[n];
                n--;
            } else if (n < 0){
                nums1[index] = nums1[m];
                m--;
            } else{
                if(nums1[m] > nums2[n]){
                    nums1[index] = nums1[m];
                    m--;
                } else{
                    nums1[index] = nums2[n];
                    n--;
                }
            }
            index--;
        }
        return;
    }
};

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

class Solution {
public:
    ListNode* merge(vector<ListNode*>& lists, int start, int end){
        if(start > end){
            return NULL;
        }
        if(start == end){
            return lists[start];
        }
        int mid = (end - start) / 2 + start;
        ListNode* first = merge(lists, start, mid);
        ListNode* second = merge(lists, mid + 1, end);
        if(first == NULL){
            return second;
        }
        if(second == NULL){
            return first;
        }
        ListNode* head = new ListNode(0);
        ListNode* p = head;
        while(first != NULL && second != NULL){
            if(first->val < second->val){
                p->next = first;
                first = first->next;
            } else{
                p->next = second;
                second = second->next;
            }
            p = p->next;
        }
        if(first != NULL){
            p->next = first;
        } else{
            p->next = second;
        }
        return head->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size()-1);
    }
};