LC3: [Longest substring without repeated chars] (https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)
题目思路: 维护一个map,记录每个字母最新的位置，遍历每个字母，如果之前改字母就在当前substr范围内，则需要把之前的那个都舍弃掉。然后比较下舍弃掉后的新长度是否变大。
int longestSubstring(string s) {
int res = 0;
int ignored = -1;
vector<int> m(256, -1);
for(int i = 0; i < str.size(); i++) {
ignored = max(m[s[i]], ignored);
res = max(res, i - ignored);
m[str[i]] = i;
}
return res;
}
LC4: [Median of Two Sorted Arrays] (https://leetcode.com/problems/median-of-two-sorted-arrays/description/)
题目思路: 分制
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if((m+n)%2) return findK(nums1, m, nums2, n, (m+n)/2 + 1);
return (findK(nums1, m, nums2, n, (m+n)/2) + findK(nums1, m, nums2, n, (m+n)/2 + 1) ) / 2.0;
}
// Note: if use erase here, then don't use 引用, and K means Kth
double findK(vector<int> nums1, int len1, vector<int> nums2, int len2, int k) {
if(len1 > len2) return findK(nums2, len2, nums1, len1, k);
if(len1 == 0) return nums2[k-1];
if(k == 1) return min(nums1[0], nums2[0]);
int pa = min(k/2, len1), pb = k - pa;
if(nums1[pa-1] < nums2[pb-1]) {
nums1.erase(nums1.begin(), nums1.begin() + pa);
return findK(nums1, len1 - pa, nums2, len2, k - pa);
}
if (nums1[pa-1] > nums2[pb-1]) {
nums2.erase(nums2.begin(), nums2.begin() + pb);
return findK(nums1, len1, nums2, len2-pb, k - pb);
}
return nums1[pa-1];
}