CSDN话题挑战赛第2期 参赛话题：学习笔记
刷题打卡，第九天
- 题目一、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即可； 具体操作可以看代码以及详细的注释：
提交代码：
代码语言：javascript复制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 = [] 输出：[]
解题思路： 层序遍历，考验的是广度优先搜索，使用队列来实现； 将树的节点按照层次来处理，根节点独自为第一层。 将同一层的节点按顺序入队，出队时用集合存放起来，同时判断是否存在孩子，存在则左右孩子依次入队。 当同一层节点全部出队，集合便记录下来了本层的层序遍历节点顺序，同时下一层的节点也全部一次入队了。 重复上述操作，即可将整颗二叉树遍历完成。
提交代码：
代码语言：javascript复制/**
* 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
提交代码：
代码语言：javascript复制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
}
}提交结果：
贵在坚持：
