[21/10/28-29 KATA NINJA]BFS DFS Stack Queueの復習


試験問題なので、簡単に概念を復習したいです.

Minimum Depth of Binary Tree


最後のクラック止め溝の最短経路を求めればよい.すべてのノードのDFSをチェックするのではなく、BFSを使用するのに適しています.
var minDepth = function(root) {
    if(!root){
        return 0;
    }
    const queue = []
    
    queue.push([root,1]);
    
    while(queue.length !== 0){
        const [node,depth] = queue.shift();
        
        if(node.left === null && node.right===null){
            return depth;
        }
        
        if(node.left)
        queue.push([node.left,depth+1]);
        if(node.right)
        queue.push([node.right,depth+1]);
        
    }
};

式の最大化


典型的なスタック問題
const useon = [['*','-','+'],['*','+','-'],['+','*','-'],['+','-','*'],['-','*','+'],['-','+','*']]
function solution(expression) {
    var answer = 0;
    
    const exp = expression.split(/([/+-/*])/gi)
    
    useon.forEach(pri =>{
        let cur = exp;
        let stack = []
        
        
        pri.forEach(operation=>{
            stack = [];
            for(let i=0;i<cur.length;i++){
                if(operation === cur[i]){
                    const first = stack.pop();
                    const second = cur[i+1];
                    const res = getComputed(first,second,operation)
                    stack.push(`${res}`);
                    i++;
                }else{
                    stack.push(cur[i])
                }
            }    
            cur = stack;
        })
        
        const [res] = stack;
        answer = Math.max(answer,Math.abs(+res));
    })    
    
    
    
    return answer;
    
    function getComputed(first,second,operation){
        
        if(operation === '*'){
            return +first * +second
        }
        if(operation === '-'){
            return +first - +second;
        }
        if(operation === '+'){
            return +first + +second;
        }
    }
}

機能開発

function solution(progresses, speeds) {
    var answer = [];
    
    
    while(progresses.length > 0){
        let count = 0;
        
        for(let i=0;i<speeds.length;i++){
            progresses[i] += speeds[i];
        }
        
        while(progresses[0] >= 100){
            progresses.shift();
            speeds.shift();
            count++;
        }
        if(count > 0){
            answer.push(count);
        }
        
    }
    
    return answer;
}

プリンタ

function solution(priorities, location) {
    let answer = 0;
    
    priorities = priorities.map((item,idx)=>({item,result : location === idx}));
    
    while(priorities.length > 0){
        const {item,result} = priorities.shift();
        
        if(priorities.some(({item:tItem})=>tItem > item)){
            priorities.push({item,result});
            continue;
        }
        
        if(result){
            return answer+1;
        }
        
        answer++;        
        
        
        
        
    }
    
    
}