Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time

Each intermediate word must exist in the word list

For example,

Given:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Return

[

[“hit”,”hot”,”dot”,”dog”,”cog”],

[“hit”,”hot”,”lot”,”log”,”cog”]

]

Note:

All words have the same length.

All words contain only lowercase alphabetic characters.

从beginWord开始经过wordList到endWord结束。一次只能变一个字母。注意：wordList所有的字母都相同的长度，都是小写。 这是一个无向图。[“hot”,”dot”,”dog”,”lot”,”log”] 先来个邻接矩阵

     hit hot dot dog lot log cog
hit   0   1   0   0   0   0   0
hot   1   0   1   0   1   0   0
dot   0   1   0   1   1   0   0
dog   0   0   1   0   0   1   1
lot   0   1   1   0   0   1   0
log   0   0   0   1   1   0   1
cog   0   0   0   1   0   1   0


        var findLadders = function(beginWord, endWord, wordList) {
            Array.prototype.indexOf = function(val) {    //数组处理
                for (var i = 0; i < this.length; i++) {
                    if (this[i] == val) return i;
                }
                return -1;
            };
            function compare(a,b){
                var s=0;
                for(var i=0;i< a.length;i++){
                   if(a.charAt(i) !=b.charAt(i)) {
                       s++;
                   }
                }
                if(s>1){
                    return false;
                }
                return true;
            }
            var arr=[];
            wordList.unshift(beginWord);
            wordList.push(endWord);
            for(var x in wordList){
                arr[x]=[];
            }
            for(var i=0;i<wordList.length;i++){
                arr[i][i]=0;
                for(var j=i+1;j<wordList.length;j++){
                    if(compare(wordList[i],wordList[j])){
                        arr[i][j]=1;
                        arr[j][i]=1;   //利用无向图对称性
                    }else{
                        arr[i][j]=0;
                        arr[j][i]=0;    //利用无向图对称性
                    }
                }
            }
            var open=[];
            var results=[]

            function to(a){
                if(a==wordList.length-1){
                    var res=[]
                    for(var i=0;i<open.length;i++){                    
                        res.push(wordList[open[i]])
                    }
                    res.push(wordList[wordList.length-1])
                    results.push(res);
                    open.pop();
                    return;
                }
                for(var x in arr[a]){
                    if(arr[a][x]==1&&open.indexOf(x)<0){
                        open.push(a)
                      //      open.push(x)   //
                        to(x);
                    }
                }
                open.pop();
            }
            to(0);
           console.log(results)
            return results
        };
        findLadders("hit","cog",["hot","dot","dog","lot","log"])
//主意leetcode给的wordList是set数据结构，不是Array。还有，这里求的是所有的解。不是最短的。但是可以在最后只留下最短的路径。用的DFS。

上面那个肯定是不行的。回报超时的错误。权值一样，下面的换了BFS+剪枝的思想。因为是求最短路径，把已经遍历的直接删除。没用邻接矩阵，必要时再计算。

           var findLadders = function(beginWord, endWord, wordList) {
            function compare(a, b) {
                var s = 0;
                for (var i = 0; i < a.length; i++) {
                    if (a.charAt(i) != b.charAt(i)) {
                        s++;
                    }
                }
                if (s > 1) {
                    return false;
                }
                return true;
            }
            wordList.add(beginWord)
            wordList.add(endWord)
///////////////////////////////////////////////////////
            var results = [];
            function to(p) {
                for(var value in p){
                    wordList.delete(p[value])
                }
                var param= new Set();
                var temps=[];

                for (var q in p){
                    var  a=p[q];
                    if (a == endWord) {
                        return;
                    }
                    wordList.forEach(function(j) {
                            if (compare(a, j)) {
                                for (var i in results) {
                                    if (results[i][results[i].length - 1] == a) {
                                        var temp = results[i].concat(j)
                                        temps.push(temp)
                                    }
                                }
                                param.add(j)
                            }
                    })
                    }
                results=temps;
                if(param.size==0){return false}
                param=Array.from(param);
                to(param);
            }
            results.push([beginWord])
            to([beginWord]);
            var tempResults=[]
            for(var h in results){
                if(results[h][results[h].length-1]==endWord){
                    tempResults.push(results[h])
                }
            }
           console.log(tempResults)
            return tempResults;
        };
    //   findLadders("hit","cog",["hot","dot","dog","lot","log"])


        findLadders("sand","acne",["slit",````(2853???),"lame"])

这个是修改版的，输入规模到了2855个时，还是会超时。虽然解如图。最少11步，一共11个解。用Chrome控制台运行要3秒多，出结果。

发现记录路径那里还是慢，因为从beginWord记录，用的数组+遍历。换成hash（js中的hash是ES6的Map，但是，这里用Object，Object（key为string，value为Array））记录反向的关系。从beginWord开始，由图生成树，然后，从endWord开始，反向遍历树，只要最短的路径。

var findLadders = function(beginWord, endWord, wordList) {
          var solve={};
          solve.$set=function(property,value){
              if( this[property]==undefined){
                  this[property]=value;
              }else{
                  Array.prototype.push.apply(this[property], value);
              }
          }
          function compare(a, b) {
              var s = false;
              for (var i = 0; i < a.length; i++) {
                  if (a.charAt(i) != b.charAt(i)) {
                      if(s){return false}
                      s=true;
                  }
              }
              return true;
          }
          wordList.add(beginWord)
          wordList.add(endWord)
          function to(p) {
              for(var value in p){
                  wordList.delete(p[value])
              }
              var param= new Set();
              var temps=[];
              for (var q in p){
                  var child=[];
                  var  a=p[q];
                  if (a == endWord) {
                      return;
                  }
                  wordList.forEach(function(j) {
                          if (compare(a, j)) {
                              solve.$set(j,[a]);
                              param.add(j)
                          }
                  })
              }
              if(param.size==0){return 0}
              param=Array.from(param);
              to(param);
          }
          if(to([beginWord])==0){
              return [];
          };
          var lu=[[endWord]]
          function change(endWords){
              var param= new Set();
              var  temps=[];
              for(var p in endWords){
                  var endWord=endWords[p]
                  if(solve[endWord]!=undefined) {
                          for(var x in solve[endWord]){
                              for (var i in lu) {
                                  if (lu[i][0] === endWord) {
                                      var temp = [solve[endWord][x]].concat(lu[i])
                                      temps.push(temp)
                                  }
                              }
                              param.add(solve[endWord][x])
                          }
                  }

              }
              if(param.size==0){
                  return lu;
              }
              lu=temps;
            return  change(Array.from(param))
          }
          return  change([endWord])
      };//终于通过了。但还是很慢。leetcode用了1800+ms，不知道别人用js只花了300ms是怎么写的，和c++差不多速度了。以后再优化。用双BFS试试

一个简化的watch.js代码。

var a={name:'ad',age:18};
var stu={stuName:a};



function Watch(x,prop,callback){
    Array.prototype.indexOf = function (val) {
    for (var i = 0; i < this.length; i++) {
        if (this[i] == val) {
            return i;
        }
    }
    return -1;
};
Array.prototype.remove = function (val) {
    var index = this.indexOf(val);
    if (index > -1) {
        this.splice(index, 1);
    }
};

    function removeFrom(x,arr){
        for(var j in arr){
            if(arr[j]==x){
                arr.splice(j, 1);
            }
        }
    }
    var value=x[prop];
    if(x.watchers==null){
        x.watchers={};
    }

    if(x.watchers[prop]==null){
        x.watchers[prop]=[];
    }
    x.watchers[prop].push(callback)
    if(value instanceof  Object){
        for(var i in value){
            if(i!='watchers'){
                Watch(value,i,callback);
            }
        }
    }

    Object.defineProperty( x, prop, {
        enumerable: true,
        configurable: true,
        get: function() {
            return value;
        },
        set: function(v){setter(v)}
    });
    x.__defineGetter__(prop, function() {
        return value;
    })
    x.__defineSetter__(prop,function(v){setter(v)})
    var setter=function(v){

            if(value instanceof  Object){
                for(var j in value['watchers']) {
                    //    value['watchers'][j].remove(callback)
                    removeFrom(callback,value['watchers'][j]);
                }
            }
            for(var i in x.watchers[prop]){
                x.watchers[prop][i](v,value);
            }
            value = v;
            if(v instanceof  Object){
                for(var j in v) {
                    Watch(v,j,callback);
                }
            }
            //    callback(v);
            //     callbacks.push(callback(v));
        }

}


Watch(a,'name',function(newValue){alert("a我被改变了"+newValue )});
Watch(stu,'stuName',function(newValue,oldValue){alert("stu我被改变了"+newValue+","+ oldValue)});

a.name='ap';

Validate if a given string is numeric.

Some examples:

“0” => true

“ 0.1 “ => true

“abc” => false

“1 a” => false

“2e10” => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

符合规则的 [".1","01","1."  ,"-.1","+.8","46.e3",".2e81","1.431352e7"," 005047e+6","32.e-80123"]
不符合["e9","2e"," . " ," "]

正则表达式的解：

var isNumber = function(s) {
   return  !!s.match(/^\s*-?\d+\s*$|^\s*-?\d+\.\d*\s*$|^\s*-?\.\d+\s*$|^\s*-?\d*\.?\d+e-?\+?\d+\s*$|^\s*-?\d+\.?e-?\+?\d+\s*$|^\s*\+\d+\s*$|^\s*\+\d+\.\d*\s*$|^\s*\+\.\d+\s*$|^\s*\+\d*\.?\d+e-?\+?\d+\s*$|^\s*\+\d+\.?e-?\+?\d+\s*$/)
};//Runtime: 182 ms??????94.12%

LeetCode-Valid Number - 有限状态机

var isNumber = function(s) {
          var state={
              value:0,
              "0":[0,1,2,3],    //0 space start 开始的空白，后面可以接[0,1,2,3]种字符。开始的空白、正负、点前面的数字、点 
              "1":[2,3],        //1 +-          正负
              "2":[2,3,5,8],    //2 shuzi dot   点前面的数字
              "3":[4,5,8],      //3 dian        点
              "4":[4,5,8],      //4 dot shuzi   点后面的数字
              "5":[6,7],        //5 e           e
              "6":[7],          //6 e +-        e后面的正负
              "7":[7,8],        //7 e shuzi     e后面的数字
              "8":[8],          //8 space end   结尾的空白
              change:function(x){
                  for(var i in this[this.value]){
                      if(this[this.value][i]==x){
                          this.value=x;
                          return true;
                      }
                  }
                  return false;
              }
          };
          var isDian=false;
          var isE=false;
          var isStart=false;
          var   Num=0;
         for(var i=0;i< s.length;i++){
             if(s.charAt(i)==" "){
                 if(!isStart){
                     if(state.change(0)){continue}else{return false};
                 }else{
                     if(state.change(8)){continue}else{return false};
                 }
             }
             isStart=true;
             if(!!s.charAt(i).match(/\+|-/)){
                 if(isE){
                     if(state.change(6)){continue}else{return false};
                 }
                 if(state.change(1)){continue}else{return false};
             }
             if(!!s.charAt(i).match(/[0-9]{1}/)){
                 if(isE){
                     if(state.change(7)){continue}else{return false};
                 }
                 if(isDian){
                     Num++;
                     if(state.change(4)){continue}else{return false};
                 }
                 Num++;
                 if(state.change(2)){continue}else{return false};
             }
             if(s.charAt(i)=="."){
                 isDian=true;
                 if(state.change(3)){continue}else{return false};
             }
             if(s.charAt(i)=="e"){
                 isE=true;
                 if(state.change(5)){continue}else{return false};
             }else{
                 return false;
             }
         }
          if(Num<1){return false;}
         if( state[state.value][state[state.value].length-1]==8){
             return true;
         }
          else{return false;}
      };   //Runtime: 216 ms 76.47%

突然记起来一个js中自带的方法

var isNumber = function(s) {  
    if(s.match(/^\s*$/)){ return false;}
        return  !isNaN(s);
};   //Runtime: 180 ms超过94.12%

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
就是求子集。子集中的元素，从小到大。

分析nums=[1,2,2]：递归树

第一步 选择还是不选nums[0]:               [][1]
第二步 选择还是不选nums[1]:       [][2]          [1][1,2]
第三步 选择还是不选nums[2] : [][2]  [2][2,2]  [1][1,2]    [1,2][1,2,2] 
最后最后一共2^3=8个解，[2][1,2]重复。6个解，

发现第二步和第三步产生了，重复分枝；
         [][2]
    [][2]    [2][2,2] 
可以在这个时候合并。变成[] [2] [2,2]
最后:[][1]  +  [] [2] [2,2]
[][2][2,2]    [1][1,2][1,2,2]
在出现大量重复相同元素，可以明显缩小运算规模。
由于，leetcode要求排序。排序方法采用快排。

自己写的，递归树加剪枝。一步步合并相同的分枝。[0,1,1,1,1]这种。

   var subsetsWithDup = function(nums) {
    var  results=[];
    Array.prototype.quickSort=function(f){
        var fn=f;;
        if(f==null){
            fn=function(a,b){return a-b;}
        }//快排
        var arr=this;
        if (arr.length <= 1) { return arr; }
        var index= Math.floor(arr.length/2);
        //   var pivot = arr.splice(index,1)[0];
        var pivot = arr[index];
        var left=[];
        var right=[];
        for(var i=0;i<arr.length;i++){
            if(i==index){continue;}
            if(fn(arr[i],pivot)>0){right.push(arr[i])}
            else{left.push(arr[i])}
        }
        return left.quickSort(fn).concat([pivot], right.quickSort(fn));
    };
    function isSame(a,b){
        try{
            if(a.length!=b.length){return false;}
            for(var i=0;i< a.length;i++){
                if(a[i].constructor==Array){
                    if(isSame(a[i],b[i])){continue;}
                    else{return false;}
                }
                if(a[i]==b[i]){continue;}
                else{return false;}
            }
            return true;
        }catch(e){
            return false;
        }
    }
    function he(a,b){
        var temp=[];var same;
        for(var i=0;i< a.length;i++){
            if(isSame(same,a[i])){continue;}
            same=a[i];
            for(var j=0;j< b.length;j++){
                temp.push(a[i].concat(b[j]));
            }
        }
        //             console.log(temp);
        return temp;
    }
    for(var i=0;i<nums.length;i++){
        if(nums.length==0){break;}
        var temp = []
        var Num=nums.splice(i,1);
        i--;
        temp.push([[],Num]);
        for(var j=0;j<nums.length;j++){
            if(Num==nums[j]){
                temp.push([[],nums.splice(j,1)]);
                j--;
            }
        }
        //         console.log(temp);
        for(var k=0;k<temp.length;k++){
            if(k>0){
                temp[k]= he(temp[k-1],temp[k]);
            }
        }
        var same;
        var rsult=temp[temp.length-1]
        for(var p=0;p<rsult.length;p++){
            if(isSame(same,rsult[p])){ rsult.splice(p,1);p--;}
            same=rsult[p];
        }
        //        console.log(rsult);
        results.push(rsult)
    }
  results=  results.quickSort(function(a,b){return a[1]-b[1];})
    for(var z=0;z<results.length;z++){
        if(z>0) {
            results[z] = he(results[z - 1], results[z])
        }
    }
    console.log(results[results.length-1]);
    return results[results.length-1]
};//Runtime:216 ms

只用递归树的。到最后合并相同的解2^n。看了下leetcode上面的输入规模小，不用剪枝更快。只有在大量相同的元素时，才会大量产生相同分枝，需要剪枝。

   var subsetsWithDup = function(nums) {
       var  results=[];
       Array.prototype.quickSort=function(f){
           var fn=f;;
           if(f==null){
               fn=function(a,b){return a-b;}
           }//快排
           var arr=this;
           if (arr.length <= 1) { return arr; }
           var index= Math.floor(arr.length/2);
           //   var pivot = arr.splice(index,1)[0];
           var pivot = arr[index];
           var left=[];
           var right=[];
           for(var i=0;i<arr.length;i++){
               if(i==index){continue;}
               if(fn(arr[i],pivot)>0){right.push(arr[i])}
               else{left.push(arr[i])}
           }
           return left.quickSort(fn).concat([pivot], right.quickSort(fn));
       };
       function isSame(a,b){
           try{
               if(a.length!=b.length){return false;}
               for(var i=0;i< a.length;i++){
                   if(a[i].constructor==Array){
                       if(isSame(a[i],b[i])){continue;}
                       else{return false;}
                   }
                   if(a[i]==b[i]){continue;}
                   else{return false;}
               }
               return true;
           }catch(e){
               return false;
           }
       }
       function he(a,b){
           var temp=[];var same;

           for(var i=0;i< a.length;i++){
               if(isSame(same,a[i])){continue;}
               same=a[i];
               for(var j=0;j< b.length;j++){
                   temp.push(a[i].concat(b[j]));
               }
           }
           //             console.log(temp);
           return temp;
       }
       nums=nums.quickSort();
       var temp = [];
       for(var i=0;i<nums.length;i++){
           if(nums.length==0){break;}
           var Num=nums.slice(i,i+1);
           temp.push([[],Num]);
           if(i>0) {
               temp[i] = he(temp[i - 1], temp[i])
           }
       }
//      console.log(temp[temp.length-1])
       var same;
       var rsult=temp[temp.length-1]
       for(var p=0;p<rsult.length;p++){
           if(isSame(same,rsult[p])){ rsult.splice(p,1);p--;}
           same=rsult[p];
       }
   //    console.log(rsult)
       return rsult;

   };//Runtime: 112 ms 超过100%的javascript代码。好假

用WebWorker做测试。

var w1 =new Worker("Subsets1.js");
var w2 =new Worker("Subsets2.js");

w1.onmessage =function(evt){
    //接收worker传过来的数据函数
    console.log(evt.data);
    //输出worker发送来的数据
}

w2.onmessage =function(evt){
    //接收worker传过来的数据函数
    console.log(evt.data);
}

• 输入[4,1,0]时。2先完成
  
• 输入[4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,1,0]时。1先完成
  

证明只有在大量相同的元素时，剪枝还是有点用的。。。。

ES5之前：

var pp = {  
        _name : "jeapedu",
        set name(v){
                this._name = v;
        },
        get name(){
                return this._name;
        }
}
pp.name = "China";  
console.log(pp.name);  
/////////////////////////////////或
Object.prototype.__defineGetter__.call(obj, propName, getter);  
Object.prototype.__defineSetter__.call(obj, propName, setter);  
这样写也行
pp.__defineGetter__('name', function(){return this._name});  
pp.__defineSetter__('name', function(x){this._name=x});

ES5:

Object.defineProperty( obj, "value", {
    // value: true,
    // writable: false,
    enumerable: true,
    configurable: true,
    get: function() {
        return value;
    },
    set: function(v) {
        value = v;
    }
});

• configurable：默认false，表示此属性是否可用delete删除
• enumerable: 默认为false，表示此属性是否可被for…in、Object.keys遍历到
• value：默认undefined，此属性的值，可以是任何JavaScript类型
• writable：默认为false，此属性是否可被改写(为false时，不能和set在一起,有set时，默认为true。)
• get：默认undefined，指定一个函数，当属性被调用时，此函数也被调用，默认为返回属性值
• set：默认undefined，指定一个函数，当属性被赋值时，此函数也被调用，仅接受一个参数，参数为属性被赋的值

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:

Could you do it without any loop/recursion in O(1) runtime?

有一个非负整数num，重复这样的操作：对它的各位数字求和，……直到这结果只有一个数字。

例如：num=38，3+8=11,1+1=2。因为2小于10，因此返回2。

要求时间复杂度为O(1)

先写个简单的：

var addDigits = function(num) {  
    var numStr = num.toString();
    var result=0;
    for(var i=0;i<numStr.length;i++){
        result+=Number(numStr.charAt(i));//注意Number比parseInt快（我的测试快 10+ms，一个90+ms，一个100+ms）。
    }
    if(result<10){
        return result;
    }else{
        return addDigits(result);
    }
};

O（1）:

38=3*10+8;  
38=(3+8)+3*9   (由这个3*(1+9)+8推出)  
38=(11)+3*9  
38=((1+1)+1*9)+3*9  
除（1+1）都能被9整除=>  result=num-9*n。即result=n/9;但是当n=99时，result=0；实际为9。
因为99=((0+1*9)+1*9)+9*9。

var addDigits = function(num) {  
   if(num===0){return 0;}
   var result=num%9;
   if(result===0){result=9}
   return result;
};

最完美的:

function addDigits(num) {  
        return 1 + (num-1)%9;  //return 2+(num-2)%9
    }  

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

博弈论中极为经典的尼姆游戏。有总数为n的石头，每个人可以拿1~3(m)个石头，两个人交替拿，拿到最后一个的人获胜。究竟是先手有利，还是后手有利？

function Nim(n){    //对于先手来说。  
   if(n%4===0){return "输";}
   else{return "赢";}
}

先手有利。只有n被4整除时，才会输。

• 假设有1颗石头。 先手赢
• 假设有2颗石头。 先手赢
• 假设有3颗石头。 先手赢
• 假设有4颗石头。 后手赢
• 假设有5颗石头。 先手赢（5=1+4，先拿1个，不管别人拿13个,总会留下31个。）

得出结论，要赢就要留4个给对手选择。这样必赢。

递推：要赢就要留4*N个给对手选择。这样必赢。（不管对手选q[1-3]{1}个，自己选4-q个就行，保证留下最后4个。）

因此，先手，在4*N+1或4*N+2或4*N+3颗石头时，必赢。在4N时，输。所以，先手优势。

after argument list

一般是少了 “,’,),} 中的一个,没有成对出现,基本是没有匹配导致的错误。还有没有转义，也可以出现该错误。

Unexpected token ILLEGAL(???)

一般输入了非法的符号，一般是中文的分号，冒号。出现的错误。

在二进制条件下，计算往往是采用逻辑计算的方法实现的，而非四则方法。js源码：

var add=function(a,b){

    if(!b){return a;}

    var temp1=a^b;

    var temp2=(a&b)<<1;

    return add(temp1,temp2);

}
var c=add(1,2)

举例说明： 12 + 9 = 21

• 12的二进制数是 1100;9的二进制数是 1001
• 先1100和1001异或计算,temp1=0101;
• 逻辑与 然后 右移1位，1000 右移有一位后 temp2=10000;
• 继续异或计算， (temp1)0101与(temp2)10000的异或计算 10101
• 逻辑与运算结果是00000(不需要进位了)。
• 则计算结束。二进制10101就是最终的计算结果，即十进制的21.

Color文字

Color文字

3D文字

Format Specifier

Description

%s

Formats the value as a string.

%d or %i

Formats the value as an integer.

%f

Formats the value as a floating point value.

%o

Formats the value as an expandable DOM element (as in the Elements panel).

%O

Formats the value as an expandable JavaScript object.

%c

Formats the output string according to CSS styles you provide.

输出图片

console.log("%c", "padding:50px 300px;line-height:120px;background:url('http://www.dadigua.win:8080/show/book/img/grasslight-big.jpg') no-repeat;");

输出文字

console.log("%c3D Text"," text-shadow: 0 1px 0 #ccc,0 2px 0 #c9c9c9,0 3px 0 #bbb,0 4px 0 #b9b9b9,0 5px 0 #aaa,0 6px 1px rgba(0,0,0,.1),0 0 5px rgba(0,0,0,.1),0 1px 3px rgba(0,0,0,.3),0 3px 5px rgba(0,0,0,.2),0 5px 10px rgba(0,0,0,.25),0 10px 10px rgba(0,0,0,.2),0 20px 20px rgba(0,0,0,.15);font-size:5em")

console.log(“%c”, “padding:300px 300px;line-height:120px;background:url(‘http://www.dadigua.win:8080/show/book/img/grasslight-big.jpg') no-repeat;”);
console.log(“%c3D Text”,” text-shadow: 0 1px 0 #ccc,0 2px 0 #c9c9c9,0 3px 0 #bbb,0 4px 0 #b9b9b9,0 5px 0 #aaa,0 6px 1px rgba(0,0,0,.1),0 0 5px rgba(0,0,0,.1),0 1px 3px rgba(0,0,0,.3),0 3px 5px rgba(0,0,0,.2),0 5px 10px rgba(0,0,0,.25),0 10px 10px rgba(0,0,0,.2),0 20px 20px rgba(0,0,0,.15);font-size:5em”)

P: Polynomial Solvable

NP: Non-determinstic Polynomial Solvable

词语解释：

• Polynomial 【数】多项式的； 由平方，立方等常数次方或者更小的运算符和+,-,*,/等构成的式子及其这种式子的和
• Non-deterministic: 非确定性的（如：时间复杂度为O(n^logn)、O(n!)、O(2^n))

Turing-machine: 图灵机; 英国数学家图灵提出的计算模型, 一个两端无限长的由小格子组 成的带子，每个格子可以存储一个数，一个可以在带子左右移动的游标或者指针或者不如叫 磁头(head), 磁头可读或修改格子里的数。 下面默认说的是确定性图灵机，和非确定性图 灵机功能上等价

• Algorithm: 算法。 给定一个问题的描述作为输入，图灵机求解的过程。 此过程有可能无 限步长，则图灵机永远不会停止，除非被外部力量终止。
• Polynomial algorithm: 多项式算法。 如果给定问题输入的长度，常量n, 则如果图灵机 解答过程需要的是时间是以n为变量的多项式，则这个解法（也是个算法）是有多项式的时 间复杂度的。
• Decision question: 判定问题。 答案是yes或者no的问题

P问题和NP问题

• P问题 (Polynomial Solvable): 如果一个判定问题是P问题，则这个问题存在一个多项式解法。 即图灵机只需要多项式时间 就可以得到答案, 既回答yes或者no。
• NP问题(Nondeterminstic Polynomial Solvable): 如果一个判定问题是NP问题， 则这个问题的一个可能的解，可以在多项式时间内被验证是 否正确。 其实这不是本来的定义。 本来的定义是，NP问题是非确定性图灵机有多项式解。 但我们可以把非确定性图灵机多项多可解转化成确定性图灵机多项式可验证解。 确定性 图灵机更好好理解，所以用那个定义。
• P问题是确定性图灵机在多项式时间内求到解，NP问题是非确定性图灵机在多项式时间内求 到解，或者说NP问题是确定性图灵机在多项式时间内验证解.
• P 属于 NP。 就是说，一个问题如果属于P， 则一定属于NP。 (这里P, NP表示符合定义的 相关问题的集合) 反过来则不一定，7大数学世纪难题之一就是问 P是否等于NP。

NPC 和 NP-hard

• NPC, 即NP完全性问题(NP-complete)。 是指NP问题中的最难的问题。 即还没有找到多项式解法，但多项式可验证。 而且只要一个NPC问题有多项式解法，其它所有NP问题都会有一个多项式解法。
• NP-hard是指所有还没有找到多项式解法的问题, 并没有限定属于NP。 所以NP-hard比 NPC范围更大，也会更难。 NPC是NP-hard和NP的交集.

• concat：合并数组(不会改变a。合并成一个新数组return的)

  var a=[1];
  var b=[2];
  var c= a.concat(b);

可以使用Array.prototype.push.apply(a,b) 这样就改变的a。

• slice(start,end):从已有的数组中返回选定的元素。不会改变原数组

• splice(index,length,item1,…..,itemX):从数组中添加/删除项目，然后返回被删除的项目。

  参数 描述
  index 必需。整数，规定添加/删除项目的位置，使用负数可从数组结尾处规定位置。
  length 必需。要删除的项目数量。如果设置为 0，则不会删除项目。
  item1, …, itemX 可选。向数组添加的新项目。

以下是w3school上面的其它的api

方法    描述
join()    把数组的所有元素放入一个字符串。元素通过指定的分隔符进行分隔。
pop()    删除并返回数组的最后一个元素
push()    向数组的末尾添加一个或更多元素，并返回新的长度。
reverse()    颠倒数组中元素的顺序。
shift()    删除并返回数组的第一个元素
sort()    对数组的元素进行排序
toString()    把数组转换为字符串，并返回结果。
toLocaleString()    把数组转换为本地数组，并返回结果。
unshift()    向数组的开头添加一个或更多元素，并返回新的长度。
valueOf()    返回数组对象的原始值


Array.from()//可以将Set，Map转Array。  

求[1, -2, 3, 5, -3, 2]的最大公共子序列

最直接的回溯

function MaxSubString1(arr,n)
 {
     var  max = Number.NEGATIVE_INFINITY;  //初始值为负无穷大
     var  sum;
     for(var i = 0; i < n; i++)
     {
         sum = 0;
         for(var j = i; j < n; j++)
         {
             sum += arr[j];
             if(sum > max)
                 max = sum;
         }
     }
     return max;
 }

动态规划的解

function MaxSubString(arr,n)
      {
          var  sum = arr[n - 1];
          var  max = arr[n - 1];
          for(var  i = n - 2; i >= 0; i--)??? //从后向前遍历，反之亦可。
          {
              sum = Math.max( arr[i], arr[i] + sum);
              max = Math.max(sum, max);
          }
          return max;?????????????????????? 
      }
      MaxSubString([1, -2, 3, 5, -3, 2],6)

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2(K)    -3       3
 -5     -10     1
 10      30    -5 (P)

Notes:

The knight’s health has no upper bound.

Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

题目大意： 有一个2D方格，每个方格有个数字，要求从左上角走到右下角，没次走的方向只能是右边和下面，如果格子的数字大于0，表示可以在这个格子加hp，如果小于0就要减掉相应数字的hp.如果到达任何一个格子时，hp为0，表示不能达到这个位置。求刚开始需要初始化多少hp才能保证走到右下角的格子。

这是一个动态规划的题。用BFS，从(2,2)到(0,0)

var calculateMinimumHP = function(dungeon) {
      var colSize=dungeon[0].length;
      var rowSize=dungeon.length;
      var dp=[];
      for(var i=0;i<rowSize;i++){
          dp.push([])
      }
      dp[rowSize-1][colSize-1] = Math.max(1 - dungeon[rowSize-1][colSize-1], 1);
       if(colSize===1&&rowSize===1){return dp[rowSize-1][colSize-1];}
      function move(arr){
          var tempArr=[];
          for(var x of arr){
              if(x[0]-1>=0){   //左移
                  if(dp[x[1]][x[0]-1]===undefined){
                      dp[x[1]][x[0]-1]=Math.max(1, dp[x[1]][x[0]]-dungeon[x[1]][x[0]-1])
                      tempArr.push([x[0]-1,x[1]])
                  }else{
                      dp[x[1]][x[0]-1]= Math.min(dp[x[1]][x[0]-1] ,Math.max(1, dp[x[1]][x[0]]-dungeon[x[1]][x[0]-1]))

                  }
              }
              if(x[1]-1>=0){   //上移
                  if(dp[x[1]-1][x[0]]===undefined){
                      dp[x[1]-1][x[0]]=Math.max(1, dp[x[1]][x[0]]-dungeon[x[1]-1][x[0]])
                      tempArr.push([x[0],x[1]-1])
                  }else{
                      dp[x[1]-1][x[0]]= Math.min(dp[x[1]-1][x[0]] ,Math.max(1, dp[x[1]][x[0]]-dungeon[x[1]-1][x[0]]))
                  }
              }
          }
          if(tempArr.length===1){
              if(tempArr[0][0]===0&&tempArr[0][1]===0){
                  return dp[0][0]
              }
          }
          return move(tempArr);
      }
      return  move([[colSize-1,rowSize-1]])
  };//Runtime: 160 ms

最优的解，用的是类似Floyd算法的思想：

var calculateMinimumHP = function(dungeon) {
    var colSize=dungeon[0].length;
    var rowSize=dungeon.length;
    function move(XY) {
        if(XY[0]==colSize-1&&XY[1]==rowSize-1){return Math.max(1,1-dungeon[rowSize-1][colSize-1]);}
        if(XY[0]>=colSize){return Infinity}
        if(XY[1]>=rowSize){return Infinity}
        var right = Math.max(1,move([XY[0]+1,XY[1]])-dungeon[XY[1]][XY[0]]);
        var down =  Math.max(1,move([XY[0],XY[1]+1])-dungeon[XY[1]][XY[0]]);
        return Math.min(right,down);
    }
    return  move([0,0])
};

?????????????????????????????Floyd??????????????????

var calculateMinimumHP = function(dungeon) {
       var m = dungeon.length;
       var n = dungeon[0].length;
       var dp=[];
       for(var i=0;i<m;i++){
           dp.push([]);
       }
       dp[m-1][n-1] = Math.max(1 - dungeon[m-1][n-1], 1);
       for(var i = m-2; i >= 0; i--){
           dp[i][n-1] = Math.max(dp[i+1][n-1] - dungeon[i][n-1], 1);
       }
       for(var i = n-2; i >= 0; i--){
           dp[m-1][i] = Math.max(dp[m-1][i+1] - dungeon[m-1][i], 1);
       }
       for(var i = m-2; i >= 0; i--){
           for(var j = n-2; j >= 0; j--){
               dp[i][j] = Math.max(Math.min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j], 1);
           }
       }
       return dp[0][0] ;
   };//Runtime: 100 ms

原生js有两种事件注册的方法

var cc= document.getElementById(‘cc’);

第一种：
    cc.onmousedown=function(){
       console.log(cc)
       alert('123')
   };
第二种：
    cc.addEventListener('mousedown',function(){
       alert('456')
    },false)

第一种会覆盖第一种的事件注册。而第二种不会覆盖。

jq的事件注册不能与原生的共存。只会注册原生的。

事件移除（不能使用匿名函数）

  原生js：
 function asd(){     
     alert('asd')
 }
  cc.addEventListener('mousedown',asd,false)
  cc.removeEventListener('mousedown',asd,false)
  JQ：
 $('#cc').click(asd)
// $('#cc').on('click',asd)
 $('#cc').unbind('click',asd)

八皇后是一道很具典型性的题目。它的基本要求是这样的：在一个8*8的矩阵上面放置8个物体，一个矩阵点只允许放置一个物体，任意两个点不能在一行上，也不能在一列上，不能在一条左斜线上，当然也不能在一条右斜线上。

准备模型,打印方法，检测方法。

  var cloneObj = function(obj){    //深拷贝
    var str, newobj = obj.constructor === Array ? [] : {};
    if(typeof obj !== 'object'){
        return;
    } else if(window.JSON){
        str = JSON.stringify(obj), //系列化对象
                newobj = JSON.parse(str); //还原
    } else {
        for(var i in obj){
            newobj[i] = typeof obj[i] === 'object' ?
                    cloneObj(obj[i]) : obj[i];
        }
    }
    return newobj;
};
var QSS=[];   //棋盘解的集合
Array.prototype.indexOf = function(val) {   //数组处理
    for (var i = 0; i < this.length; i++) {
        if (this[i] == val) return i;
    }
    return -1;
};
var nQueens = [   //棋盘
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0]
];
function printQ(queens) {  //打印棋盘
    for (var row=0; row<queens.length; row++) {
        var rowText = '';
        for (var col=0; col<queens.length; col++) {
            if (queens[row][col]===undefined||queens[row][col]==null) {
                queens[row][col] = 0;
            }
            rowText = rowText + queens[row][col] + '  ';
        }
        console.log(rowText);
    }
}
function isTrue(nQueens,row,col){   //检测该位置是否满足
    for(var i=1;i<row+1;i++){
        if(nQueens[row-i][col]==1|| nQueens[row-i][col+i]|| nQueens[row-i][col-i]){return false}
    }
    return true;
}

回溯法。一行只能有一个棋子。从第一行第一个格子放起。放了以后。再从第二排开始第一个格子检测，如果为true，则放下。然后，下一行第一个格子检测。如果其中有一排都为false且不是最后一排。则退后一行（row=row-2）。继续上一行检测.如果上一行的最后一个为1，退后2排（row=row-3）。

function NQueens(order){
        var tempCol=0;
        rowLoop:
        for(var row=0;row<order;row++){
            for(var col=tempCol;col<order;col++){
                tempCol=0;
                if(isTrue(nQueens,row,col)){
                    nQueens[row][col]=1;
                    if(row==7){
                        QSS.push(cloneObj(nQueens));
                        var mIndex=nQueens[row].indexOf(1);
                        nQueens[row][mIndex]=0;
                        if(col==7){
                            var mIndex=nQueens[row-1].indexOf(1);
                            nQueens[row-1][mIndex]=0;
                            row= row-2;
                            tempCol=mIndex+1;
                            continue rowLoop;
                        }
                        continue;
                    }
                    continue rowLoop;

                }else{//next
                    if(col==7){
                        var mIndex=nQueens[row-1].indexOf(1);
                        nQueens[row-1][mIndex]=0;
                        if(mIndex==7){
                            if(row==1){   alert('????????????'); break rowLoop;}
                            mIndex=nQueens[row-2].indexOf(1);
                            nQueens[row-2][mIndex]=0;
                            row = row-3;
                            tempCol=mIndex+1;
                        }
                        else{
                            row= row-2;
                            tempCol=mIndex+1;
                        }
                        continue rowLoop;
                    }
                }
            }
        }
    }

    NQueens(8);

    console.log(QSS.length)
    for(var x in QSS){
        console.log('///////////////////////')
        printQ(QSS[x])
    }

结果如下

一共92个解。

该题可以利用左右对称。只需求出46个解。就可以得出92个解。在这里两种情况都要考虑到。 如果其中有一排都为false且不是最后一排。则退后一行（row=row-2）。继续上一行检测.如果上一行的最后一个为1，退后2排（row=row-3）。

function NQueens(order){
    var tempCol=0;
    rowLoop:
    for(var row=0;row<order;row++){
        for(var col=tempCol;col<order;col++){
            tempCol=0;
            if(isTrue(nQueens,row,col)){
                nQueens[row][col]=1;
                if(row==7){
                    QSS.push(cloneObj(nQueens));
                    var mIndex=nQueens[row].indexOf(1);
                    nQueens[row][mIndex]=0;
                    if(col==7){
                        var mIndex=nQueens[row-1].indexOf(1);
                        nQueens[row-2][mIndex]=0;
                        row= row-2;
                        tempCol=mIndex+1;
                        continue rowLoop;
                    }
                    continue;
                }
                continue rowLoop;

            }else{//next
                if(col==7){
                    var mIndex=nQueens[row-1].indexOf(1);
                    nQueens[row-1][mIndex]=0;
                    if(mIndex==3&&row==1){
                        alert('完成一半');  //在此跳出循环
                    }
                    if(mIndex==7){
                        if(row==1){   alert('回溯完成'); break rowLoop;}
                        mIndex=nQueens[row-2].indexOf(1);
                        nQueens[row-2][mIndex]=0;
                        if(mIndex==3&&row==2){
                            console.log(QSS.length)
                            alert('完成一半');   //在此跳出循环(真)
                        }
                        row = row-3;
                        tempCol=mIndex+1;
                    }
                    else{
                        row= row-2;
                        tempCol=mIndex+1;
                    }
                    continue rowLoop;
                }
            }
        }
    }
}

NQueens(8);

console.log(QSS.length)
for(var x in QSS){
    console.log('/////////////')
    printQ(QSS[x])
}

var Reg=new RegExp(/data-page="\d+"/g)
var arr=str.match(Reg)


在 Web 开发中经常会碰到需要动态监听输入框值变化的情况，如果使用 onkeydown、onkeypress、onkeyup 这个几个键盘事件来监测的话，监听不了右键的复制、剪贴和粘贴这些操作，处理组合快捷键也很麻烦。因此这篇文章向大家介绍一种完美的解决方案：结合 HTML5 标准事件 oninput 和 IE 专属事件 onpropertychange 事件来监听输入框值变化。

pattern接正则表达式。

1
2
3
4
5
6
7
8
9
10
11

var pp = {
        _name : "jeapedu",
        set name(v){
                this._name = v;
        },
        get name(){
                return this._name;
        }
}
pp.name = "China";
console.log(pp.name);

var comment = document.getElementsByTagName('a')[0];

if (document.all) {
 // For IE 
comment.click();
} 
else if (document.createEvent) {
   //FOR DOM2
var ev = document.createEvent('MouseEvents');
 ev.initEvent('click', false, true);
 comment.dispatchEvent(ev);
}


高度塌陷的问题 – 清除浮动 
1.直接一个<div style="clear:both;"></div>放到当作最后一个子标签放到父标签  
2.overflow + zoom方法    .fix{overflow:hidden; zoom:1;}  
3. after + zoom方法  
.fix{zoom:1;}
.fix:after{display:block; content:'clear'; clear:both; line-height:0; visibility:hidden;} 


       Array.prototype.indexOf = function(val) {
            for (var i = 0; i < this.length; i++) {
                if (this[i] == val) return i;
            }
            return -1;
        };
        Array.prototype.remove = function(val) {
            var index = this.indexOf(val);
            if (index > -1) {
                this.splice(index, 1);
            }
        };


req.headers 看请求头  
req.on(‘data’) 请求事件  
res.writeHeader() 写响应头  
res.write() 写响应体  
前端ajax的接口就是：XMLHTTPRequest的实例ajax

ajax.status 看响应码  
ajax.responseText 看响应体  
ajax.onload 响应事件  
ajax.open() 请求方法  
ajax.setRequestHeader() 请求头  
ajax.send() 请求体  


parseInt('123',10)  慢  
Number('123')  
'123'<<0            快  
注： 小心使用位操作运算符。数字会被当成 64 位值，但是位操作运算符总是返回 32 位的整数（source）。位操作处理大于 32 位的整数值时还会导致意料之外的行为。讨论。最大的 32 位整数是 2,147,483,647：
2147483647 >> 0 //=> 2147483647  
2147483648 >> 0 //=> -2147483648  
2147483649 >> 0 //=> -2147483647

~~n  都行
n<<0  
n>>0  
n|0  


 var Base64 = {
        // 转码表
        table : [
                'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
                'I', 'J', 'K', 'L', 'M', 'N', 'O' ,'P',
                'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
                'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
                'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
                'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
                'w', 'x', 'y', 'z', '0', '1', '2', '3',
                '4', '5', '6', '7', '8', '9', '+', '/'
        ],
        UTF16ToUTF8 : function(str) {
            var res = [], len = str.length;
            for (var i = 0; i < len; i++) {
                var code = str.charCodeAt(i);
                if (code > 0x0000 && code <= 0x007F) {
                    // 单字节，这里并不考虑0x0000，因为它是空字节
                    // U+00000000 – U+0000007F  0xxxxxxx
                    res.push(str.charAt(i));
                } else if (code >= 0x0080 && code <= 0x07FF) {
                    // 双字节
                    // U+00000080 – U+000007FF  110xxxxx 10xxxxxx
                    // 110xxxxx
                    var byte1 = 0xC0 | ((code >> 6) & 0x1F);
                    // 10xxxxxx
                    var byte2 = 0x80 | (code & 0x3F);
                    res.push(
                        String.fromCharCode(byte1), 
                        String.fromCharCode(byte2)
                    );
                } else if (code >= 0x0800 && code <= 0xFFFF) {
                    // 三字节
                    // U+00000800 – U+0000FFFF  1110xxxx 10xxxxxx 10xxxxxx
                    // 1110xxxx
                    var byte1 = 0xE0 | ((code >> 12) & 0x0F);
                    // 10xxxxxx
                    var byte2 = 0x80 | ((code >> 6) & 0x3F);
                    // 10xxxxxx
                    var byte3 = 0x80 | (code & 0x3F);
                    res.push(
                        String.fromCharCode(byte1), 
                        String.fromCharCode(byte2), 
                        String.fromCharCode(byte3)
                    );
                } else if (code >= 0x00010000 && code <= 0x001FFFFF) {
                    // 四字节
                    // U+00010000 – U+001FFFFF  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
                } else if (code >= 0x00200000 && code <= 0x03FFFFFF) {
                    // 五字节
                    // U+00200000 – U+03FFFFFF  111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
                } else /** if (code >= 0x04000000 && code <= 0x7FFFFFFF)*/ {
                    // 六字节
                    // U+04000000 – U+7FFFFFFF  1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
                }
            }

            return res.join('');
        },
        UTF8ToUTF16 : function(str) {
            var res = [], len = str.length;
            var i = 0;
            for (var i = 0; i < len; i++) {
                var code = str.charCodeAt(i);
                // 对第一个字节进行判断
                if (((code >> 7) & 0xFF) == 0x0) {
                    // 单字节
                    // 0xxxxxxx
                    res.push(str.charAt(i));
                } else if (((code >> 5) & 0xFF) == 0x6) {
                    // 双字节
                    // 110xxxxx 10xxxxxx
                    var code2 = str.charCodeAt(++i);
                    var byte1 = (code & 0x1F) << 6;
                    var byte2 = code2 & 0x3F;
                    var utf16 = byte1 | byte2;
                    res.push(Sting.fromCharCode(utf16));
                } else if (((code >> 4) & 0xFF) == 0xE) {
                    // 三字节
                    // 1110xxxx 10xxxxxx 10xxxxxx
                    var code2 = str.charCodeAt(++i);
                    var code3 = str.charCodeAt(++i);
                    var byte1 = (code << 4) | ((code2 >> 2) & 0x0F);
                    var byte2 = ((code2 & 0x03) << 6) | (code3 & 0x3F);
                    var utf16 = ((byte1 & 0x00FF) << 8) | byte2
                    res.push(String.fromCharCode(utf16));
                } else if (((code >> 3) & 0xFF) == 0x1E) {
                    // 四字节
                    // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
                } else if (((code >> 2) & 0xFF) == 0x3E) {
                    // 五字节
                    // 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
                } else /** if (((code >> 1) & 0xFF) == 0x7E)*/ {
                    // 六字节
                    // 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
                }
            }

            return res.join('');
        },
        encode : function(str) {
            if (!str) {
                return '';
            }
            var utf8    = this.UTF16ToUTF8(str); // 转成UTF8
            var i = 0; // 遍历索引
            var len = utf8.length;
            var res = [];
            while (i < len) {
                var c1 = utf8.charCodeAt(i++) & 0xFF;
                res.push(this.table[c1 >> 2]);
                // 需要补2个=
                if (i == len) {
                    res.push(this.table[(c1 & 0x3) << 4]);
                    res.push('==');
                    break;
                }
                var c2 = utf8.charCodeAt(i++);
                // 需要补1个=
                if (i == len) {
                    res.push(this.table[((c1 & 0x3) << 4) | ((c2 >> 4) & 0x0F)]);
                    res.push(this.table[(c2 & 0x0F) << 2]);
                    res.push('=');
                    break;
                }
                var c3 = utf8.charCodeAt(i++);
                res.push(this.table[((c1 & 0x3) << 4) | ((c2 >> 4) & 0x0F)]);
                res.push(this.table[((c2 & 0x0F) << 2) | ((c3 & 0xC0) >> 6)]);
                res.push(this.table[c3 & 0x3F]);
            }

            return res.join('');
        },
        decode : function(str) {
            if (!str) {
                return '';
            }

            var len = str.length;
            var i   = 0;
            var res = [];

            while (i < len) {
                code1 = this.table.indexOf(str.charAt(i++));
                code2 = this.table.indexOf(str.charAt(i++));
                code3 = this.table.indexOf(str.charAt(i++));
                code4 = this.table.indexOf(str.charAt(i++));

                c1 = (code1 << 2) | (code2 >> 4);
                c2 = ((code2 & 0xF) << 4) | (code3 >> 2);
                c3 = ((code3 & 0x3) << 6) | code4;

                res.push(String.fromCharCode(c1));

                if (code3 != 64) {
                    res.push(String.fromCharCode(c2));
                }
                if (code4 != 64) {
                    res.push(String.fromCharCode(c3));
                }

            }

            return this.UTF8ToUTF16(res.join(''));
        }
    };
        var css3 = function(dom) {
            this.dom = dom;
            this.css = function(option) {
                if (arguments.length === 2) {
                    var obj = {};
                    obj[arguments[0]] = arguments[1];
                    option = obj;
                }
                for (var key in option) {
                    var temp = document.createElement('temp').style;
                    if (typeof temp[key] === "undefined") {
                        var prefixes = ['Webkit', 'Moz', 'O', 'ms', 'Khtml'];
                        var keyC = key.charAt(0).toUpperCase() + key.substr(1);
                        for (var x in prefixes) {
                            prefixes[x] = prefixes[x] + keyC;
                            if (typeof temp[prefixes[x]] !== "undefined") {
                                this.dom.style[prefixes[x]] = option[key];
                                return this;
                            }
                        }
                    } else {
                        this.dom.style[key] = option[key];
                        return this;
                    }
                }
            }
            if (this === window) {
                return new css3(dom);
            }
        }


getOwnPropertyNames 方法同时返回可枚举的和不可枚举的属性和方法的名称。若要仅返回可枚举的属性和方法的名称，可使用 Object.keys 函数 (JavaScript)。  


恩 。 babel升级拆分了模块 。你需要 
npm install babel-loader babel-core babel-preset-es2015 babel-preset-react —save-dev  
然后 
loader: "babel?presets[]=react,presets[]=es2015"

就好了

本人想找前端的工作。因此，算法语言都是用的javascript。

先介绍一种人人都能写出的匹配方法。

function strMatch(a,b){
    for(var i=0;i< a.length;i++){
        if(a.substr(i,1)==b.substr(0,1)){
            for(var j=0;j< b.length;j++){
                if(a.substr(i+j,1)!=b.substr(j,1)){break;}
                if(j == b.length-1){console.log(i);}
            }
        }
    }
}

再来介绍大名鼎鼎KMP算法（Knuth-Morris-Pratt，起头的那个K就是著名科学家Donald Knuth。写过《计算机程序设计艺术》一书，当时被誉为计算机学的圣经。）：

转的字符串匹配的KMP算法知识库博客园

1.先得出《部分匹配表》

　　首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。

　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；
　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

代码：

function retunB(pre,next){
        var temp=[];
        for(var i=0;i<pre.length;i++){
            if(pre[i]==next[i]){
                temp.push(pre[i]);
            }
        }
        if(temp.length==0){return 0;}
        else{return temp[temp.length-1].length;}
    }
    function getB(b){
        var B=[];
        for(var i=1;i<b.length+1;i++){
            if(i==1){B.push(0);continue}
            var tempStr = b.substring(0,i);
            var pre=[];
            var next=[];
            for(var j=1;j<tempStr.length;j++){
                pre.push(tempStr.substring(0,j));
           next.push(tempStr.substring(tempStr.length-j,tempStr.length))
            }
            B.push( retunB(pre,next)) ;
        }
        return B;
    }

2.开始KMP匹配:

function KMP(a,b){
      var B = getB(b);
      for(var i=0;i< a.length;i++){
          if(a.substr(i,1)==b.substr(0,1)){
              for(var j=0;j< b.length;j++){
                  if(a.substr(i+j,1)!=b.substr(j,1)){
                      var y=j-B[j-1];
                      i = i+y-1;
                      break;
                  }
                  if(j == b.length-1){console.log(i);}
              }
          }
      }
  }

先写快排吧,时间复杂度为O(nlogn)，时间复杂度由渐进符号O符号表示，f(n) = O(g(n))，表示f(n)的复杂度最多与g(n)一个数量级，即小于等于。

思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

Array.prototype.quickSort=function(){    //快排  
    var arr=this;
    if (arr.length <= 1) { return arr; }
    var index= Math.floor(arr.length/2);
    //   var pivot = arr.splice(index,1)[0];
    var pivot = arr[index];
    var left=[];
    var right=[];
    for(var i=0;i<arr.length;i++){
        if(i==index){continue;}
        if(arr[i]>pivot){right.push(arr[i])}
        else{left.push(arr[i])}
    }
    return left.quickSort().concat([pivot], right.quickSort());
}

归并排序：（可以用于外排序，把几组已经排好序的集合归并到一组）

function　merge(left, right){  
    var　result=[];
    while(left.length>0 && right.length>0){
        if(left[0]<right[0]){
        /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return　result.concat(left).concat(right);
}
function　mergeSort(items){  //items数组  
    if(items.length == 1){
        return　items;
    }
    var　middle = Math.floor(items.length/2),
    left = items.slice(0, middle),
    right = items.slice(middle);
    return　merge(mergeSort(left),mergeSort(right));
}

堆排序:

Array.prototype.swap=function(i,j){   //交换元素  
    var tmp=this[i];
    this[i]=this[j];
    this[j]=tmp;
};

Array.prototype.heapSort=function(f){            //堆排序  
    var fn=f;;
    if(f==null){
        fn=function(a,b){return a-b;}
    }

    var that=this;
    buildHeap();
    for(var i=that.length-1;i>0;i--){
        that.swap(0,i);
        heapAdjust(0,i);
    }
    return that;
    function heapAdjust(i,j){
        var M=i;
        var left=i*2+1;
        var right=i*2+2;
        if(left<j&&fn(that[M],that[left])<0){
            M=left;
        }
        if(right<j&&fn(that[M],that[right])<0){
            M=right;
        }
        if(M!=i){
            that.swap(i,M);
            heapAdjust(M,j);
        }
    }
    function buildHeap(){
        for(var i=Math.floor(that.length/2)-1;i>=0;i--){
            heapAdjust(i,that.length);
        }
    }
}

递归和迭代都是循环的一种。网上很多都是用递归解决汉罗塔，。今天研究了下用迭代解决。 先贴出递归的javascript版。大家可以到chrome控制台直接调试。

var j=0;  
        function Hanoi(n,a,b,c){
            if(n>=1){
                Hanoi(n-1,a,c,b);
                j++;
                console.log('第'+j+'部从'+a+'移动到'+c);
                Hanoi(n-1,b,a,c);
            }
        }
        Hanoi(7,'A','B','C')

大多数的递归都可以改写成循环，递归从上而下。循环从下往上；递归由系统压栈，循环则要自己存储。就是，用简单的循环来代替递归的话，有时必须要手工维护一个数据结构。

循环的解法

Array.prototype.Run=function(to){
        if(to=='left'){
            for(var i=0;i<this.length;i++){
                if(this[i].from=='B'){this[i].from='C';}else{
                    if(this[i].from=='C'){this[i].from='B';}
                }
                if(this[i].to=='B'){this[i].to='C';}else{
                    if(this[i].to=='C'){this[i].to='B';}
                }
            }
        }
        if(to=='right'){
            for(var i=0;i<this.length;i++){
                if(this[i].from=='A'){this[i].from='B';}
                else{
                    if(this[i].from=='B'){this[i].from='A';}
                }

                if(this[i].to=='A'){this[i].to='B';}else{
                    if(this[i].to=='B'){this[i].to='A';}
                }

            }
        }
        return this;
    }
    function hanoi3(n){
        var a='A';
        var b='B';
        var c='C';
        var temp=1;
        for(var i=0;i<n;i++){
            temp = temp+temp+1;
            if(i==0){ s.push(new to(a,c));continue;}
            var temp =cloneObj(s);
            var temp2=cloneObj(s);
            s = temp.Run('left').concat([new to(a,c)],temp2.Run('right'));
        }

        for(var i=0;i< s.length;i++){

            console.log('第'+(i+1)+'从'+s[i].from+'移动到'+s[i].to);
        }

    }


    var cloneObj = function(obj){
        var str, newobj = obj.constructor === Array ? [] : {};
        if(typeof obj !== 'object'){
            return;
        } else if(window.JSON){
            str = JSON.stringify(obj), //系列化对象
                    newobj = JSON.parse(str); //还原
        } else {
            for(var i in obj){
                newobj[i] = typeof obj[i] === 'object' ?
                        cloneObj(obj[i]) : obj[i];
            }
        }
        return newobj;
    };

    hanoi3(7)