刷题打卡，第九天
题目一、1640. 能否连接形成数组
题目二、102. 二叉树的层序遍历
题目三、704. 二分查找
题目一、1640. 能否连接形成数组
原题链接：1640. 能否连接形成数组
题目描述：
给你一个整数数组 arr ，数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces，其中的整数也互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i]中的整数重新排序。
如果可以连接 pieces 中的数组形成 arr ，返回true；否则，返回 false 。
/
示例 1：
输入：arr = [15,88], pieces = [[88],[15]]
输出：true
解释：依次连接 [15] 和 [88]
/
示例 2：
输入：arr = [49,18,16], pieces = [[16,18,49]]
输出：false
解释：即便数字相符，也不能重新排列 pieces[0]
/
示例 3：
输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
输出：true
解释：依次连接 [91]、[4,64] 和 [78]
解题思路：
为了验证pieces元素，是否可以连接形成数组arr，我们可以用双列集合map来存放数组pieces中的数组首元素以及下标。
再遍历地比较两个数组的元素；
如果存在两个数组的元素不对应，直接返回false即可；
具体操作可以看代码以及详细的注释：
提交代码：
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;//全部对应，返回真 } }
提交结果：
题目二、102. 二叉树的层序遍历
原题链接：
102. 二叉树的层序遍历
题目描述：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
/
示例 2：
输入：root = [1]
输出：[[1]]
/
示例 3：
输入：root = []
输出：[]
解题思路：
层序遍历，考验的是广度优先搜索，使用队列来实现；
将树的节点按照层次来处理，根节点独自为第一层。
将同一层的节点按顺序入队，出队时用集合存放起来，同时判断是否存在孩子，存在则左右孩子依次入队。
当同一层节点全部出队，集合便记录下来了本层的层序遍历节点顺序，同时下一层的节点也全部一次入队了。
重复上述操作，即可将整颗二叉树遍历完成。
提交代码：
/** * 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; } }
提交结果：
题目三、704. 二分查找
原题链接：704. 二分查找
题目描述：
给定一个 n 个元素有序的（升序）整型数组nums和一个目标值 target ，写一个函数搜索 nums 中的target，如果目标值存在返回下标，否则返回 -1。
/
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
/
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
解题思路：
这道题很简单，题目以及告诉你要怎么做了；
从数组的中间下标元素开始查找，若没找到，分为两种情况。
若中间元素小于指定元素，数组左边界缩减至中间元素的下一位 ；
若中间元素大于指定元素，数组右边界缩减至中间元素的上一位 ；
每次遍历，运算量就减半，直至找到指定的target值，否则返回-1
提交代码：
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 } }
提交结果：
贵在坚持：
