【day09】LeetCode（力扣）每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        int len_arr = arr.length;      //记录arr数组长度
        int len_pieces = pieces.length;//记录pieces数组长度

        //创建双列集合map，存放 <pieces内每个数组的首元素，数组的下标>
        Map<Integer,Integer> map = new HashMap<>();

        //遍历pieces[][],将 <pieces内每个数组的首元素，数组的下标>存入集合
        for(int i = 0;i < len_pieces;++i){
            map.put(pieces[i][0],i);
        }

        //遍历arr数组
        for(int i = 0;i < len_arr;){
            //pieces中不存在与arr对应元素，无法对应，返回false
            if(!map.containsKey(arr[i])) return false;

            //当前arr[i]元素在pieces中对应下标记录为n
            int n = map.get(arr[i]);
            //获取此下标数组的长度
            int len = pieces[n].length;

            //遍历下标n位置上的数组
            for(int j = 0;j < len;++j){
                //如果存在不对应得元素，说明无法连接成功
                if(arr[i+j] != pieces[n][j])
                //无法对应即返回false
                return false;

            }
            //遍历完下标为n的数组，说明遍历了数组长度len次
            i += len;
        }
        return true;//全部对应，返回真
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;

        //创建队列，利用先进先出的特性，遍历二叉树
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);//头节点入队
        while(!que.isEmpty()){
            //创建集合，存放同一层的节点
            List<Integer> level = new ArrayList<>();
            //记录当前层的节点数，另其一行写，循环中que.size()会变化，不能作为循环条件
            int size = que.size();
            //遍历当前层次的节点
            for(int i = 0;i < size;++i){
            //记录出队的节点,并存放在代表本层节点的集合中
            TreeNode curr = que.poll();
            level.add(curr.val);

            //将当前出队节点的左右孩子入队
            if(curr.left != null) que.offer(curr.left);
            if(curr.right != null) que.offer(curr.right);
            }

            list.add(level);//以层为单位，分别存放每一层的节点
            
        }
        return list;

    }
}

class Solution {
    public int search(int[] nums, int target) {
        int L = 0,R = nums.length-1,mid,num;
        while(L <= R){//数组左边界与有边界未错位时
            mid = L+((R-L) >> 1); //获取中间下标
            num = nums[mid];      //获取中间下标元素
            if(num == target){    //找到target直接返回
                return mid;
            }else if(nums[mid] < target){
                L = mid+1;       //中间元素较小，左边界缩减
            }else{               
                R = mid-1;       //中间元素较大，有边界缩减
            }
        }
        return -1;               //左右边界错位，代表不存在指定元素，返回-1
    }
}