简单回溯

401. 二进制手表

回溯法 呜呜呜呜找了两天的问题

var readBinaryWatch = function(turnedOn) {
    let arr = [1,2,4,8,1,2,4,8,16,32];
    let result=[],path=[];
    let len = arr.length;
    var backtrack = function(n,k,start){
        if(path.length==k){
            result.push(path);/path.slice(); 必须复制，否则不保存，一直重复
            console.log('答',result);
            return ;
        }
        for(let i = start;i<n;i++){
            path.push(arr[i]);
            console.log(path,result);
            backtrack(n,k,i+1);//i+1不会一直加，提前写i=i+1;
            path.pop();
        }

    }
    backtrack(len,turnedOn,0);
    return result;
};

回溯法模板

全局变量

backtracking(参数，开始下标) {

    if(终止条件){加入result；return;}

    for(横向遍历i=开始下标){

        操作，加入path；

        backtracking（）；

        撤回操作； 

    }
执行backtracking();
return result;

}

var readBinaryWatch = function(turnedOn) {
    let arr = [1,2,4,8,1,2,4,8,16,32];
    let result=[],path=[0,0];
    let len = arr.length;
    var backtrack = function(turnedOn,start,path){
        if(path[0]>11||path[1]>59)return;
        if(turnedOn==0){
            let min = path[1]<10?`0${path[1]}`:path[1];
            result.push(`${path[0]}:${min}`);
            //console.log('aa',result);
            return;
        }
        for(let i = start;i<len;i++){
            console.log(start,i,arr[i]);
            if(i<4){path[0]+=arr[i];}
            else{path[1]+=arr[i];}
            //path.push(arr[i]);
            //console.log(path,'ans1',result);
            start = start+1;
            turnedOn= turnedOn-1;
            backtrack(turnedOn,start,path);
            if(i<4){path[0]-=arr[i];}
            else{path[1]-=arr[i];}
            turnedOn= turnedOn+1;
            //backtrack(turnedOn,start+1,path);
        }
    }
    backtrack(turnedOn,0,path);
    return result;
};

784. 字母大小写全排列

有问题

var letterCasePermutation = function(s) {
    let len = s.length;
    let result=[],path='';
    var backtracking=function(start,path){
        //console.log(s[start],isNaN(s[start]),/\d/.test(s[start]));
        while(/\d/.test(s[start])){
            path+=s[start];start +=1;
            }if将出现重复?why
        if(path.length==len){///if放在while后，否则出错？？？？？
            result.push(path.slice()); 
            return;
        }
        let index = start;
        start=start+1;
        backtracking(start,path+s[index].toUpperCase());
        backtracking(start,path+s[index].toLowerCase());
        
    }
    backtracking(0,path);
    return result;
};

简单排序

1122. 数组的相对排序

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function(arr1, arr2) {
    let map = new Map();
    let ans=[];
    arr1.sort();
    for(let i = 0;i<arr1.length;i++){
        if(map.has(arr1[i])){ map.set(arr1[i],map.get(arr1[i])+1);}
        else{map.set(arr1[i],1);}  
    }
    //console.log(map);
    for(let j of arr2){
        if(map.has(j)){
            let p = map.get(j);
            while(p>0){
                ans.push(j);
                p--;
            }
            map.delete(j);
        }
    }
    let res = [];
    for(let [key,value] of map){
        //console.log(key);
        let p = value;
            while(p>0){
                res.push(key);
                p--;
            }
    }
    return ans.concat(res.sort(function(a,b){return a-b;}));
};

广度优先

深度优先是递归，广度优先是迭代，层序遍历。

107. 二叉树的层序遍历 II

 

var levelOrderBottom = function(root) {
    let res=[];
    let que=[];
    if(root){que.push(root);}
    while(que.length){//后序遍历，入栈：左-右；出栈：中 -> 右 -> 左，结果左右根
        let size = que.length;//每层节点数
        let path = [];
        for(let i=0;i<size;i++){
            let node = que.shift();
            path.push(node.val);
            if(node.left){que.push(node.left);}
            if(node.right){que.push(node.right);}
        }
        res.unshift(path);
    }
    return res;
};

111. 二叉树的最小深度

var minDepth = function(root) {
    if(root==null)return 0;
    if(root.left==null&&root.right==null){return 1;}
    let min = Number.MAX_VALUE;
    if(root.left!=null){min = Math.min(minDepth(root.left),min);}
    if(root.right!=null){min = Math.min(minDepth(root.right),min);}
    return min+1;
};

var minDepth = function(root) {
    if(root ==null)return 0;
    let que = [root];
    console.log(que);
    let dep = 0;
    while(1){

        let size = que.length;
        console.log(size,que);
        dep++;
        while(size--){
            const node = que.shift();
            if(node.left==null&&node.right==null)return dep;
            if(node.left!=null){que.push(node.left);}
            if(node.right!=null){que.push(node.right);}
        }
    }
};

690. 员工的重要性

迭代

let ans=0;
var GetImportance = function(employees, id) {
   for(let i of employees){
       if(i.id==id){
           ans+=i.importance;
           for(let k of i.subordinates){GetImportance(employees,k);}
       }
   }
   return ans;
};

迭代没有终止条件，因为不新加入，会一直出栈，直到栈空，不再执行循环。

var GetImportance = function(employees, id) {
   let map = new Map();
   for(let i of employees){
       map.set(i.id,i);
   }
   //console.log(map);
   let res =0;
   let arr=[id];
    while(arr.length){
       // console.log(arr);
        const key = arr.shift();
        const em = map.get(key);
        res+=em.importance;
        arr.push(...em.subordinates);
    }

   return res;
};

这些算法还需要系统学习，接下来跟着代码随想录，将典型题 按类型再刷一遍。