[21/10/28-29 KATA NINJA]BFS DFS Stack Queueの復習
試験問題なので、簡単に概念を復習したいです.
最後のクラック止め溝の最短経路を求めればよい.すべてのノードのDFSをチェックするのではなく、BFSを使用するのに適しています.
典型的なスタック問題
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++;
}
}
Reference
この問題について([21/10/28-29 KATA NINJA]BFS DFS Stack Queueの復習), 我々は、より多くの情報をここで見つけました https://velog.io/@rat8397/211028-KATA-NINJA-BFS-DFS-Stack-Queue-복습テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol