Use unordered set to solve this question(C++)


  • 8
    S

    Here I show the thinking process to solve this question.
    And another two method can not be accepted by the OJ .

    //事实证明,还是可以用哈希表,直接建立一个string的哈希表太大了!
    //因为string的每一位都只有四种可能,我用一个int位来代替一个10位的string,ACGT分别代表两位00 01 10 11,即
    //用一个20位的int值表示10位的string
    //再用hash来建立int的表进行查找~即可
        vector<string> findRepeatedDnaSequences(string s) {
            vector<string> res;
    		int i,foo_i;
    		string foo,bar;
    		unordered_set<int> A;
    		int size=s.length();
    		if(size<=10)
    			return res;
    		for(i=0;i+10<=size;i++){
    			foo=s.substr(i,10);
    			foo_i=str2num(foo);
    			if(A.find(foo_i)==A.end()){
    				A.insert(foo_i);
    			}
    			else{
    				if(find(res.begin(),res.end(),foo)==res.end())
    				res.push_back(foo);
    			}
    		}
    		return res; 
        }
        int str2num(string A){
        	int i,res=0;
        	for(i=0;i<10;i++){
        		if(A[i]=='A')
        			res+=0;
        		else if(A[i]=='C')
        			res+=1;
        		else if(A[i]=='T')
        			res+=2;
        		else if(A[i]=='G')
        			res+=3;
        		res=res<<2;
    		}
    		return res;
    	}
    //Time Limit method
    /*
    	vector<string> findRepeatedDnaSequences(string s) {
    		vector<string> res;
    		int i,loc;
    		string foo,bar;
    		int size=s.length();
    		if(size<=10)
    			return res;
    		for(i=0;i+10<=size;i++){
    			foo=s.substr(i,10);
                        if(find(res.begin(),res.end(),foo)!=res.end())
    			continue;
    			loc=s.find(foo,i+1);
    			if(loc>0){
    				res.push_back(foo);
    				for(;s[i+10]==s[loc+10]&&i+10<=size&&loc+10<=size;i++,loc++){
                           if(find(res.begin(),res.end(),foo)!=res.end())
    					       res.push_back(s.substr(i+1,10));
    				}
    			}
    		} 
    		return res;
    	}
    	*/
        //建立一个哈希表,结构出现 Memory Limit Exceeded的错误
        /*
        vector<string> findRepeatedDnaSequences(string s) {
            vector<string> res;
    		int i;
    		string foo,bar;
    		unordered_set<string> A;
    		int size=s.length();
    		if(size<=10)
    			return res;
    		for(i=0;i+10<=size;i++){
    			foo=s.substr(i,10);
    			
    			if(A.find(foo)==A.end()){
    				A.insert(foo);
    			}
    			else{
    				res.push_back(foo);
    			}
    		}
    		sort(res.begin(),res.end());
    		res.erase(unique(res.begin(),res.end()),res.end());
    		return res; 
        }
        */

  • 0
    H

    why is left shift 2bit,not1bit?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.