プログラマ#6


DFS/BFS-ネットワーク


グラフィックDFSの問題を思い出して解決した
解題方法を知っていたからか、3級だとは思わなかった.
function aux(computers, rowIdx, isVisited){
    computers[rowIdx].map((el, colIdx) => {
        if(!isVisited[colIdx] && el === 1){
            isVisited[colIdx] = true;
            return aux(computers, colIdx, isVisited);
        }
    })
}

function solution(n, computers) {
    const isVisited = Array(n).fill(false);
    let count = 0;
    
    for(let i = 0 ; i < n ; i++){
        if(!isVisited[i]){
            isVisited[i] = true;
            count++
            aux(computers, i, isVisited);
        }
    }
    
    return count;
}

完全ナビゲーション-シミュレーション試験


休憩と同時に徹底的な探索を行った.
他の人の解答を見て、いくつかの方法が減らすことができます.
これは簡単な問題だと思いますが、どれだけ簡単かが重要だと思いますか?
function solution(answers) {
    const p1 = [1, 2, 3, 4, 5];
    const p2 = [2, 1, 2, 3, 2, 4, 2, 5];
    const p3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    
    let idx1 = 0;
    let idx2 = 0;
    let idx3 = 0;
    
    const answerCount = [0,0,0];
    
    const isOverflow = (idx, arr) => {
        idx++;
        if(idx >= arr.length) idx = 0;
        
        return idx;        
    }
    
    for(let i = 0 ; i < answers.length ; i++){
        if(p1[idx1] === answers[i]) answerCount[0]++;
        if(p2[idx2] === answers[i]) answerCount[1]++;
        if(p3[idx3] === answers[i]) answerCount[2]++;
        
        idx1 = isOverflow(idx1, p1);
        idx2 = isOverflow(idx2, p2);
        idx3 = isOverflow(idx3, p3);   
    }
    
    let max = Math.max(...answerCount);
    
    return answerCount.map((el, idx)=>{
        if(el === max){
            return idx+1;
        }
    }).filter((el)=>{
        return !!el;
    })
}

完全ナビゲーション-小数点以下を検索


与えられた数字のすべての場合の数字が小数であることを決定する必要があります.
DFSによるリリース
function isPrime(num){    
    if (num === 1) return false;
    if (num === 2) return true;
    if (num % 2 === 0) return false;
    let sqrt = parseInt(Math.sqrt(num));
    
    for (let divider = 3; divider <= sqrt; divider += 2) {
      if (num % divider === 0) {
        return false;
      }
    }
    return true;    
}

function DFS(num, numbers, idx, count, isVisited, isPicked){
    const N = numbers.length;
    
    if(idx > N) return count;
    
    isPicked[idx] = true;
    num = num + numbers[idx];
    num = Number(num);
    
    if(!isVisited[num]){
        isVisited[num] = true;
        if(isPrime(num)) count++;        
    }
    num = String(num);
    
    for(let i = 0; i < N; i++){
        if(!isPicked[i]){
            count = DFS(num, numbers, i, count, isVisited, [...isPicked]);
        }
    }
    
    return count;
}

function solution(numbers) {
    const N = numbers.length;
    const isVisited = new Array(Math.pow(10,N)).fill(false);
    const isPicked = new Array(N).fill(false);
    let count = 0;
    
    for(let i = 0 ; i < numbers.length ; i++){
        count += DFS('', numbers, i, 0, isVisited, [...isPicked]);
    }
    
    return count;
}