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