LeetCode刷題第二天——3Longest Substring Without repeating character 4 Median of Two Sorted Arrays...

混淆點：

　　子串 連續

　　子序列 可以不連續

知識點：

　　HashMap：

出現問題：

　　1.使用unordered_map頭文件時報錯

#error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.#end if

?

　　解決方法：

　　工程上右鍵，選擇build?options，在compiler?settings里面，有列表，選擇c++0x支持。

　　PS：這個錯誤比較詭異的就是，他直接跳到了頭文件里。所以可以知道這不是自己的錯誤，在工程里更改下編譯方式就好了。　　

　　解決代碼：

//Leetcode #3
//題目描述：給定一個字符串求最大子串個數

#include<stdio.h>
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;


class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int res=0,left=-1,n=s.size();
        unordered_map<int,int> m;
        for(int i=0;i<n;++i)
        {
            //count check whether s[i] exist
            if(m.count(s[i])&&m[s[i]]>left)
            {
                left=m[s[i]];

            }
            //update s[i]'s position
            m[s[i]]=i;
            res=max(res,i-left);

        }
        return res;
    }
};






int main()
{
    Solution s;//initializing object s
    string str1="abttybacds";
    int t=0;
    t=s.lengthOfLongestSubstring(str1);
    cout<<t<<endl;
    return 0;
}

?https://www.cnblogs.com/grandyang/p/4480780.html

這個里面還有其余幾種方法的講解

4.Median of Two Sorted Arrays兩個有序數組的中位數 Hard

?這道題是用分治法做來保證時間限制

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int k=nums1.size()+nums2.size();
        if(k%2==0)
            return (median(nums1,nums2,k/2)+median(nums1,nums2,k/2+1))/2.0;
        else return median(nums1,nums2,k/2+1);
    }

double median(vector<int>& vec1,vector<int>& vec2,int k){
        if(vec1.size()>vec2.size()) return median(vec2,vec1,k);
        if(vec1.empty()) return vec2[k-1];
        if(k==1) return min(vec1[0],vec2[0]);
        int p1=vec1.size()>k/2?k/2:vec1.size();
        int p2=k-p1;
        if(vec1[p1-1]>vec2[p2-1]){
            vector<int> vec(vec2.begin()+p2,vec2.end());
            return median(vec1,vec,k-p2);
        }
       AS else if(vec1[p1-1]<vec2[p2-1]){
            vector<int> vec(vec1.begin()+p1,vec1.end());
            return median(vec,vec2,k-p1);
        }
        else return vec1[p1-1];
    }

思路還是有點不懂，先把來源貼上，明天再研究研究