leetcode day2

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

1.暴力法： 从第一个字符开始遍历，直到出现第一个重复字符，记下最大值；然后从第i个开始······，比较最大值，得到最终结果

class Solution { public: int lengthOfLongestSubstring(string s) { string tmp; int maxlen=0; for(int i=0;i<s.size();i++) { for(int j=i;j<s.size();j++) { if(tmp.find(s[j])!=-1) break; else tmp=tmp+s[j]; if(j-i+1>maxlen) maxlen=j-i+1; } tmp.clear(); } return maxlen; } };

2.滑动窗口： 当出现重复字符x时，对于第一个x之前的数，从这开始也会到第二个x处结束，必定小于当前长度，所以只需从第一个x之后开始滑动即可

class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.length(), ans = 0; map<char, int> mp; for (int end = 0, start = 0; end < n; end++) { char alpha = s[end]; if (mp.find(alpha)!=mp.end()) { start = max((mp.find(alpha))->second, start); } ans = max(ans, end - start + 1); mp.erase(s[end]); mp.insert(pair<char,int>(s[end], end + 1)); } return ans; } };

收获

1.暴力法很舒服但是时间复杂度太高 2.要观察字符串的规律，思考重复字符出现有什么影响，同时铭记用空间换时间的思想 3.要温习map的常用方法，以及迭代器的使用

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

1.合并两数组直接取中位数

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int num1=nums1.size(),num2=nums2.size(); int n=num1+num2; int i=0,j=0; double zhong; vector<int> nums3; if(num1==0) //边界情况 { nums3=nums2; } else if(num2==0) { nums3=nums1; } else if(n==2) { zhong=(nums1[0]+nums2[0])/2.0; return zhong; } else for(int k=0;k<=n/2+1;k++) { if(i==num1) { nums3.push_back(nums2[j]); j++; continue; } if(j==num2) { nums3.push_back(nums1[i]); i++; continue; } if(nums1[i]>nums2[j]) { nums3.push_back(nums2[j]); j++; } else { nums3.push_back(nums1[i]); i++; } } if(n%2) zhong=nums3[(n-1)/2]; else zhong=(double)((nums3[n/2-1]+nums3[n/2])/2.0); return zhong; } };

收获

1.对于边界情况的考虑很重要，多思考边界，特殊 2.对于两数组的归并要熟练，不能在这上面浪费时间