Add some tastes of binary search


  • 0
    F

    The general idea is the same, but when I do comparison, I used binary search, to eliminate some of them.

     var bSearch=function(s,e,w,max,t){
            if(s>e){
                return false;
            }
            var mid=parseInt((s+e)/2);
            if(w[t][0]&w[mid][0]){
                if(!bSearch(mid+1,e,w,max,t)){
                    bSearch(s,mid-1,w,max,t);
                }
            }
            else{
            	max[0]<w[t][1]*w[mid][1] ? max[0]=w[t][1]*w[mid][1] : null;
            	bSearch(mid+1,e,w,max,t);
            	return true;
            }
            return false;
        }
        var maxProduct = function(words) {
            var len=words.length,len1,w=[],mark,max=[0],t='00000000000000000000000000',b='a';
            for(var i=0;i<len;i++){
            	w.push(t.split(''));
            	len1=words[i].length;
            	for(var k=0;k<len1;k++){
            		w[i][words[i][k].charCodeAt(0)-b.charCodeAt(0)]='1';
            	}
            	w[i]=[parseInt(w[i].join(''),2),len1];
            }
            w.sort(function(a,b){
                return a[1]-b[1];
            });
            for(i=0;i<len;i++){
            	bSearch(i+1,len-1,w,max,i);
            }
            return max[0];
        };

Log in to reply
 

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