BFS

用「队列」这种数据结构，每次将一个节点周围的全部节点加入队列。web

框架数组

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构 队列
    Set<Node> visited; // 避免走回头路 维护一个visited集合

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的全部节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

111. 二叉树的最小深度

var minDepth = function(root) { 
 
  
    if(!root) return 0;
    let queue = [root];
    let depth = 1;
    while(queue.length) { 
 
  
        let sz = queue.length;
        for(let i=0; i<sz; i++) { 
 
  
            let cur = queue.shift();
            if(!cur.left && !cur.right) { 
 
  
                return depth;
            }
            if(cur.left) queue.push(cur.left);
            if(cur.right) queue.push(cur.right);
        }
        depth++;
    }
};

752. 打开转盘锁

var openLock = function(deadends, target) { 
 
  
    let queue = ['0000'];
    let deads = new Set(deadends);
    let visited = new Set();
    let step = 0;
    while(queue.length) { 
 
  
        let sz = queue.length;
        for(let i=0; i<sz; i++) { 
 
  
            let cur = queue.shift();
            if(deads.has(cur)) continue;
            if(cur == target) return step;
            for(let j=0; j<4; j++) { 
 
  
                let u = up(cur, j);
                let d = down(cur, j);
                if(!visited.has(u)) { 
 
  
                    queue.push(u);
                    visited.add(u);
                }
                if(!visited.has(d)) { 
 
  
                    queue.push(d);
                    visited.add(d)
                }
            }
            
        }
        step ++;
    }
    return -1;
    function up(str, index) { 
 
  
        let tmp = parseInt(str[index]);
        tmp = tmp == 9 ? 0 : tmp+1
        return str.slice(0,index) + tmp + str.slice(index+1);
    }
    function down(str, index) { 
 
  
        let tmp = parseInt(str[index]);
        tmp = tmp == 0 ? 9 : tmp-1
        return str.slice(0,index) + tmp + str.slice(index+1);
    }
};

二分查找

框架数据结构

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

704. 二分查找

var search = function(nums, target) { 
 
  
    let left = 0;
    let right = nums.length-1;
    while(left <= right) { 
 
  
        let mid = left + Math.floor((right-left)/2);
        if(nums[mid] === target) { 
 
  
            return mid;
        } else if(nums[mid] > target) { 
 
  
            right = mid-1;
        } else { 
 
  
            left = mid+1;
        }
    }
    return -1;
};

34. 在排序数组中查找元素的第一个和最后一个位置

var searchRange = function(nums, target) { 
 
  
    let low = findLow(nums, target);
    let high = findHigh(nums, target);
    return [low, high];

    function findLow(nums, target) { 
 
  
        let left = 0;
        let right = nums.length-1;
        let res;
        while(left <= right) { 
 
  
            let mid = left + Math.floor((right-left)/2);
            if(nums[mid] == target) { 
 
  
                right = mid-1;
            } else if(nums[mid] > target) { 
 
  
                right = mid-1;
            } else { 
 
  
                left = mid+1;
            }
        }
        if(left >= nums.length || nums[left] !== target) { 
 
  
            return -1;
        }
        return left;
    }
    function findHigh(nums, target) { 
 
  
        let left = 0;
        let right = nums.length-1;
        let res;
        while(left <= right) { 
 
  
            let mid = left + Math.floor((right-left)/2);
            if(nums[mid] == target) { 
 
  
                left = mid+1;
            } else if(nums[mid] > target) { 
 
  
                right = mid-1;
            } else { 
 
  
                left = mid+1;
            }
        }
        if(right<0 || nums[right] !== target) { 
 
  
            return -1;
        }
        return right;
    } 
};