손으로 쓴 제목의 알고리즘 편

11136 단어 javascript 알고리즘 전단
  • 두 갈래 나무의 넓이 역력
  • 이차수층 서열 두루두루
  • 두 갈래 나무 깊이 역력: 앞차례, 중차례, 뒤차례
  • 두 갈래 나무의 최대 깊이
  • 2분 검색
  • 주어진 path, 트리를 옮겨다니며 지정한 path가 있는 노드를 찾기
  • 빠른 정렬
  • K위
  • 최장 공통 접두어
  • 중복된 문자가 없는 최장자 문자열
    • 나무가 많이 돌아다녀서 먼저 나무 구조를 정의합니다.
    //  
const tree = {
      data: 1,
      left: {
        data: 2,
        left: {
          data: 4,
          left: {
            data: 8,
          },
          right: {
            data: 9
          }
        },
        right: {
          data: 5,
          left: {
            data: 10,
          },
          right: {
            data: 11
          }
        }
      },
      right: {
        data: 3,
        left: {
          data: 6,
          left: {
            data: 12
          }
        },
        right: {
          data: 7
        }
      }
    };

    두 갈래 나무의 넓이가 두루 미치다


    광도 범람은 각 층을 범람하는 것이다. 위의tree 광도 범람 후의 결과는 [1,2,3,4,5,6,7,8,9,10,11,12]이다.실현 방식은 창고를 통해 옮겨다니는 상태를 부모 노드, 왼쪽 트리, 오른쪽 트리의 순서에 따라 창고를 압축하는 것이다.창고의 꼭대기를 꺼내서 결과 그룹에 저장하고 창고가 비어 있을 때 반복해서 끝냅니다.
    코드는 다음과 같습니다.
    //  
function bfs(tree){
    //  
    let stack = [tree];
    let result = [];
    
    while(stack.length){
        //  
        const node = stack.shift();
        
        result.push(node.data);
        //  
        if(node.left){
            stack.push(node.left);
        }
        //  
        if(node.right){
            stack.push(node.right);
        }
    }

    return result;

}

console.log(' ', bfs(tree));

    두 갈래 나무가 층층이 두루 다니다


    층차 반복은 층마다 하나의 그룹 항목에 저장됩니다.
        //  
        function levelOrder(tree){
            const output = [];

            let level = 0;

            if(level === null){
                return output;
            }

            const visitLoop = (node, level) => {
                if(!output[level]){
                    output[level] = [];
                }

                output[level].push(node.data);

                if(node.left){
                    visitLoop(node.left, level + 1);
                }

                if(node.right){
                    visitLoop(node.right, level + 1);
                }
            };

            visitLoop(tree, 0);

            return output;

        }

        console.log(' ', levelOrder(tree));

    두 갈래 나무의 앞줄이 두루 다니다


    앞의 순서가 반복되는 순서는 루트에 접근한 다음 왼쪽 트리에 접근하고 오른쪽 트리에 접근하는 것입니다.앞의 순서가 반복된 결과는 [1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 7]이다.창고의 특성을 이용하여 현재 스트리밍 상태를 저장합니다.루트 노드를 초기화하고 창고를 먼저 압수합니다.매번 순환에서 창고 꼭대기를 꺼내 결과 그룹에 저장하고, 오른쪽 나무 창고가 있으면 왼쪽 나무 창고가 있습니다.
    //  
function preOrder(tree){
    let stack = [tree];
    let result = [];
    let node;

    while(stack.length){
        let node = stack.pop();

        result.push(node.data);

        if(node.right){
            stack.push(node.right);
        }

        if(node.left){
            stack.push(node.left);
        }

    }

    return result;
}

console.log(' ', preOrder(tree));

    앞의 순서가 두루 반복되는 귀속 실현
    //  
function preOrderRcs(tree){
    let result = [];
    const visitLoop = function(node){
        result.push(node.data);

        if(node.left){
            result.concat(visitLoop(node.left));
        }

        if(node.right){
            result.concat(visitLoop(node.right));
        }
    };

    visitLoop(tree);

    return result;
}

console.log(' - ', preOrderRcs(tree));

    두 갈래 나무에 차례대로


    중간 순서는 왼쪽 트리를 먼저 방문하고, 루트를 방문하고, 마지막으로 오른쪽 트리를 방문합니다.중순 역행 결과는 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 3, 7]이다.중순 반복 비귀속 실현은 역추적 알고리즘을 사용했다.
    회소법(back tracking)(탐색과 회소법)은 우수한 것을 선택하는 검색법으로 탐색법이라고도 부른다. 우수한 조건에 따라 앞으로 검색하여 목표를 달성한다.그러나 어떤 단계를 탐색했을 때 원래 선택이 좋지 않거나 목표에 도달하지 못하면 한 걸음 물러서서 다시 선택하는 기술을 소급법이고 소급 조건을 만족시키는 어떤 상태를 소급점이라고 한다.
    반복되지 않거나 창고를 이용하여 반복되는 순서를 저장하고 현재 반복되는 노드를 변수로 저장합니다.스트리밍 조건: 창고가 비어 있지 않거나 현재 노드가 비어 있지 않으며 현재 노드가 창고에 저장됩니다. 순서대로 왼쪽 트리를 창고에 넣습니다. 왼쪽 트리가 존재하지 않을 때 창고 꼭대기에서 튀어나온 원소가 결과 그룹에 저장됩니다. 만약에 튀어나온 원소가 오른쪽 트리가 있다면 오른쪽 트리는 현재 스트리밍 노드이고 창고에 저장됩니다.
    //    
        function inOrder(tree){
            const stack = [];
            const result = [];

            //  
            let node = tree;
            
            while(stack.length || node){
                //  ， 
                if(node){
                    stack.push(node);

                    node = node.left;
                }else{
                    //  ， 
                    const current = stack.pop();
                    //  
                    result.push(current.data);
                    
                    //  ， 
                    if(current.right){
                        node = current.right;
                    }
                }
            }

            return result;

        }


        console.log(' ', inOrder(tree));
    //  
function inOrderRcs(tree){
    let result = [];
    
    const visitLoop = function(node){
        if(node.left){
            result.concat(visitLoop(node.left));
        }

        result.push(node.data);

        if(node.right){
            result.concat(visitLoop(node.right));
        }
    };

    visitLoop(tree);

    return result;
}

console.log(' - ', inOrderRcs(tree));

    두 갈래 나무 뒤에 차례대로


    먼저 왼쪽 트리를 훑어보고 오른쪽 트리를 훑어보고 마지막에 뿌리를 훑어본다.뒷순서 역행 결과는 [8, 9, 4, 10, 11, 5, 2, 12, 6, 7, 3, 1]이다.
    스트리밍 순서를 저장하는 창고와 현재 스트리밍 노드를 저장하는 것을 제외하고 모든 노드에touched 속성을 추가합니다.현재 노드에 왼쪽 트리가 있을 때 순서대로 창고를 누비고, 현재 노드 터치는left로 설정합니다.현재 노드에 오른쪽 트리가 있을 때 순서대로 창고를 누비고, 현재 터치ed는false로 설정합니다.만약 잎 노드나 좌우 나무를 모두 훑어보았다면 결과 그룹에 저장합니다.현재 역행 노드를 창고 꼭대기 요소로 설정합니다.
    //  
function postOrder(tree){
    const stack = [tree];
    const result = [];
    let node = tree;

    while(stack.length){
        //  ， 
        if(node.left && !node.touched){
            node.touched = 'left';
            node = node.left;
            stack.push(node);
            continue;

        }

        //  ， 
        if(node.right && node.touched !== 'right'){
            node.touched = 'right';
            node = node.right;
            stack.push(node);

            continue;
        }


        //  
        const current = stack.pop();
        result.push(current.data);
        
        //  
        node = stack[stack.length - 1];
    }

    return result;
}

console.log(' ', postOrder(tree))

    //  - 
function postOrderRcs(tree){
    let result = [];
    const visitLoop = function(node){

        if(node.left){
            result.concat(visitLoop(node.left));
        }

        if(node.right){
            result.concat(visitLoop(node.right));
        }

        result.push(node.data);
    };

    visitLoop(tree);

    return result;
}

console.log(' - ', postOrderRcs(tree))

    두 갈래 나무의 최대 깊이

    //  
function maxDepth(tree){

    if(tree === null){
        return 0;
    }

    let res = 0;

    const visitLoop = (node, level) => {
        if(!node){
            return 0;
        }

        if(!node.left && !node.right){
            res = Math.max(res, level);
        }


        if(node.left){
            visitLoop(node.left, level + 1);
        }

        if(node.right){
            visitLoop(node.right, level + 1);
        }
    };

    visitLoop(tree, 1);

    return res;
}

console.log(' ', maxDepth(depthTree));

    이분 검색

    function binarySearch(nums, target){

    if(!nums.length){
        return -1;
    }

    let start = 0
        let end = nums.length - 1;

        let mid;

        while(start <= end){
            let mid = Math.floor((start + end) /2);

            if(target === nums[mid]){
                return mid;
            }
            if(target < nums[mid]){
                end = mid - 1;
            }

            if(target > nums[mid]){
                start = mid + 1;
            }

        }

        return -1;
}

console.log(' ', binarySearch([-1,0,3,5,9,12], 9));

    빠른 정렬


    두 가지 절차로 나뉜다.
  • 분할:partition 함수에 따라 수조를 기준위에서 2부분으로 나누는데 기준위 이전은 그것보다 작고 이후는 그것보다 크다.정렬할 때 좌우 두 개의 바늘을 사용하고, 두루 훑어본 후, 왼쪽이 기준치보다 크고 오른쪽의 작은 값에 닿으면 두 개의 값을 교환하고, 왼쪽의 바늘로 돌아간다.
  • 귀속: 주 함수quickSortHandler가 있는데 파티션을 실행하여 왼쪽 바늘 좌표를 추출하고 이 좌표에 따라 그룹을 나누어 귀속합니다.종료 조건은 그룹 길이입니다.
    • //  
function quickSort(nums = []){

    const swap = (nums, i ,j) => {
        const temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    };


    // 
    const partition = (nums, i, j) => {
        let left = i;
        let right = j;

        let mid = Math.floor((right + left)/2);

        //  
        while(left <= right){
            
            while(nums[left] < nums[mid]){
                left++;
            }

            while(nums[right] > nums[mid]){
                right --;
            }

            if(left <= right){
                swap(nums, left, right);
                left++;
                right --;

            }
        }
        return left;
    };

    //  
    const quickSortHandler = (nums, left, right) => {

        let index;

        //  
        if(nums.length > 1){
            index = partition(nums, left, right);

            if(left < index - 1){
                quickSortHandler(nums, left, index - 1);
            }

            if(index < right){
                quickSortHandler(nums, index, right);
            }
        }

        return nums;

    };

    quickSortHandler(nums, 0, nums.length - 1);

    return nums;
}

console.log(' ', quickSort([5,1,1,2,0,0]));

    K위


    빠른 정렬 후 그룹 중arr.length-k의 원소를 찾아내면 됩니다.

    최대 공통 접두어

    // 
function longestCommonPrefix(strs = []){
    if(!strs.length){
        return '';
    }

    let res = strs[0];

    for(let i = 1; i < strs.length; i++){
        let j = 0;

        for(;j < strs[i].length; j++){
            if(strs[i][j] !== res[j]){
                break;
            }
        }

        res = res.substring(0, j);

        if(!res){
            return '';
        }
    }

    return res;    
}

console.log(' ', longestCommonPrefix(["flower","flow","flight"]));

    중복된 문자가 없는 가장 긴 문자열

    //  
function lengthOfLongestSubstring(s){
    let max = 0;
    const arr = [];

    if(!s){
        return '';
    }

    for(let i = 0; i< s.length; i++){
        if(arr.find(item => item ===s[i])){
            let index = arr.findIndex(item => item === s[i]);
            arr.splice(0, index + 1);
        }

        arr.push(s[i]);

        max = Math.max(arr.length, max);
    }

    return max;

}
console.log(' ', lengthOfLongestSubstring('abcabcbb'));

    참고 문장: 두 갈래 나무가 두루 다니다javascript 데이터 구조와 알고리즘 학습
    Note : unity ml-agents
    Unity 전문 이쑤시개 스타일(삼각형, 사각형, 정다각형)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage