Divide and Conquer

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

两种方法都是基于二分的思想. 一种是通用的查找 kth element 的方法:

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        size_t m = nums1.size();
        size_t n = nums2.size();
        if ((m+n) & 1) return kth_element(nums1, 0, nums2, 0, (m+n)/2 + 1);
        else {
            return (kth_element(nums1, 0, nums2, 0, (m+n)/2) + kth_element(nums1, 0, nums2, 0, (m+n)/2 + 1))/ 2.0;
        }
    }

    int kth_element(vector<int>& nums1, int m, vector<int>& nums2, int n, int k) {
        if (m >= nums1.size()) return nums2[n + k - 1];
        if (n >= nums2.size()) return nums1[m + k - 1];
        if (k == 1) return min(nums1[m], nums2[n]);

        int value_a = (m + k/2 - 1) < nums1.size() ? nums1[m + k/2 - 1] : INT_MAX;
        int value_b = (n + k/2 - 1) < nums2.size() ? nums2[n + k/2 - 1] : INT_MAX;
        if (value_a < value_b) {
            return kth_element(nums1, m + k/2, nums2, n, k - k/2);
        } else {
            return kth_element(nums1, m, nums2, n + k/2, k - k/2);
        }
    }
};

另外一种就是基于median 的分析得到的: 即将数组分为两半, 左边的都比右边的小, 分为 A[i], A[i+1], B[j], B[j+1]. 找出 i 和j 的值

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        size_t m = nums1.size();
        size_t n = nums2.size();

        if (m > n) return findMedianSortedArrays(nums2, nums1);

        int minidx = 0, maxidx = m, i, j, mid = (m + n + 1) >> 1;
        int n1, n2;
        while (minidx <= maxidx) {
            i = (minidx + maxidx) >> 1;
            j = mid - i;
            if (i < m && j > 0 && nums2[j - 1] > nums1[i]) minidx = i + 1;
            else if (i > 0 && j < n && nums2[j] < nums1[i - 1]) maxidx = i - 1;
            else {
                if (i == 0) n1 = nums2[j - 1];
                else if (j == 0) n1 = nums1[i - 1];
                else n1 = max(nums1[i - 1], nums2[j - 1]);
                break;
            }
        }

        if ((m+n)&1) return n1;
        if (i == m) n2 = nums2[j];
        else if (j == n) n2 = nums1[i];
        else n2 = min(nums1[i], nums2[j]);
        return (n1 + n2) / 2.;
    }
};

14. Longest Common Prefix

这一题有好多解法, 比较精彩的两种是二分查找和分治法

Write a function to find the longest common prefix string amongst an array of strings.

二分查找:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int max_len = INT_MAX;
        string res;
        if (strs.size() == 0) return res;
        for (auto str : strs) if (max_len > str.size()) max_len = str.size();

        int start = 1;
        int end = max_len;
        int common_len = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (isCommonPrefix(strs, mid)) {
                common_len = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return strs[0].substr(0, common_len);

    }

    bool isCommonPrefix(vector<string>& strs, int len) {
        if (len < 0) return false;
        string target = strs[0].substr(0, len);
        for (auto str : strs) {
            if (str.substr(0, len) != target) return false;
        }
        return true;
    }
};

分治法:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) return "";
        return longestCommonPrefix(strs, 0, strs.size() - 1);
    }

    string longestCommonPrefix(vector<string>& strs, int start, int end) {
        if (start == end) return strs[start];
        int mid = start + (end - start) / 2;

        auto first = longestCommonPrefix(strs, start, mid);
        auto second = longestCommonPrefix(strs, mid + 1, end);
        int max_len = min(first.size(), second.size());
        for (size_t i = 0; i < first.size() && i < second.size(); ++i) {
            if (first[i] != second[i]) {
                max_len = i;
                break;
            }
        }
        return first.substr(0, max_len);
    }
};

23. Merge k Sorted Lists

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (!lists.size()) return nullptr;
        while (lists.size() > 1) {
            ListNode* l1 = lists[0];
            ListNode* l2 = lists[1];
            lists.erase(lists.begin(), lists.begin() + 2);
            lists.push_back(merge2Lists(l1, l2));
        }
        return lists[0];
        // auto cmp = [](ListNode* a, ListNode* b) {return a->val > b->val;};
        // priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        // for (auto l : lists) if (l) pq.push(l);
        // if (pq.empty()) return nullptr;
        // ListNode* head = pq.top();
        // ListNode* pre = nullptr;
        // while (!pq.empty()) {
        //     ListNode* cur = pq.top();
        //     pq.pop();
        //     if(pre) pre->next = cur;
        //     pre = cur;
        //     cur = cur->next;
        //     if (cur) pq.push(cur);
        // }
        // return head;
    }

    ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = merge2Lists(l1->next, l2);
            return l1;
        } else {
            l2->next = merge2Lists(l1, l2->next);
            return l2;
        }
    }
};

25. Reverse Nodes in k-Group

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || !head->next || k <= 1) return head;
        auto cur = head;
        ListNode* pre = nullptr;
        int cnt = 0;
        while (cur && cnt < k) {
            pre = cur;
            cur = cur->next;
            ++cnt;
        }
        if (cnt < k) return head;
        pre ->next = nullptr;
        auto next_group = cur;

        auto newHead = pre;
        cur = head;
        pre = nullptr;
        while (cur) {
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        head->next = reverseKGroup(next_group, k);
        return newHead;
    }
};

395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input: s = "aaabb", k = 3

Output: 3

The longest substring is "aaa", as 'a' is repeated 3 times. Example 2:

Input: s = "ababbc", k = 2

Output: 5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

class Solution {
public:
    int longestSubstring(string s, int k) {
        return getLen(s, 0, s.size(), k);
    }

    int getLen(const string& s, int l, int r, int k) {
        if (l >= r) return 0;
        unordered_map<char, int> ch_cnt;
        vector<size_t> neg_pos;
        for (size_t i = l; i < r; ++i) ch_cnt[s[i]]++;
        for (size_t i = l; i < r; ++i) {
            if (ch_cnt[s[i]] < k) neg_pos.push_back(i);
        }
        if (neg_pos.empty()) return r - l;
        neg_pos.push_back(r);
        int res = 0;
        for (auto pos : neg_pos) {
            res = max(res, getLen(s, l, pos, k));
            l = pos + 1;
        }
        return res;
    }
};

results matching ""

    No results matching ""