Week 4

题目

本周做了16题

题目	难度
#200 岛屿数量	中等
#455 分发饼干	简单
#45 跳跃游戏 II	困难
#153 寻找旋转排序数组中的最小值	中等
#74 搜索二维矩阵	中等
#33 搜索旋转排序数组	中等
#367 有效的完全平方数	简单
#55 跳跃游戏	中等
#529 扫雷游戏	中等
#127 单词接龙	中等
#874 模拟行走机器人	简单
#860 柠檬水找零	简单
#122 买卖股票的最佳时机 II	简单
#509 斐波那契数	简单
#841 钥匙和房间	中等
#46 全排列	中等

知识点

dfs、bfs、贪心、二分

总结

dfs为栈的形式，先进后出，所以优先考虑递归法，类似二叉树的后序遍历，这里可能会出现多叉的情况。bfs为队列形式，所以优先考虑队列迭代法。

二分摸板
public void binarySearch(int[]  data, int target) {
    int left = 0, right = data.length - 1;
    while(left <= right) {
        int mid = (left + right) /2 ;
        if(target < data[mid]) {
            //往前查找
            right = mid - 1;
        } else if(target > data[mid]) {
            //往后查找
            left = mid + 1;
        } else {
            //找到目标
        }
    } 
}