小红书-2020测开（二）
- 224个叶子节点的完全二叉树, 最多有几个结点（）
答案
448
题解
1、度为0的结点个数=度为2的结点个数+1，即n0=n2+1（其中n0表示度为0的结点个数，n2表示度为2的结点个数）。注 ：二叉树的度代表某个结点的孩子或者说直接后继的个数。
2、完全二叉树中度为1的结点个数要么0个，要么1个。
3、二叉树结点个数n=n0+n1+n2
综合性质，结合题目有 n0=224，故224=n2+1，得n2=224-1=223。
当为度1的结点不存在时，结点总数为n=n0+n1+n2=224+0+223=447。
当为度1的结点存在时，结点总数为n=n0+n1+n2=224+1+223=448。
故最多为448个，选B
2. 散列表中解决冲突的方法有（）
答案
再散列法 开放寻址法
题解
平方取中法和除数留余法属于哈希函数，另外还有直接定址法和随机数法，而解决哈希冲突的方法有，开放地址法（再哈希，二次探测、线性探测）和常用的链地址法
3. UDP报头中没有下面那些信息:()
答案
目的地址 窗口大小 序列号
题解
UDP报文段结构：源端口号，目的端口号，长度，检验和，应用数据
编程题
1. 笔记草稿 - 括号匹配/栈
薯队长写了一篇笔记草稿，请你帮忙输出最后内容。
1.输入字符包括，"(" , ")" 和 "<"和其他字符。
2.其他字符表示笔记内容。
3.()之间表示注释内容，任何字符都无效。 括号保证成对出现。
4."<"表示退格, 删去前面一个笔记内容字符。括号不受"<"影响 。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer stringBuffer = new StringBuffer();
stringBuffer = new StringBuffer(scanner.nextLine());
List<Integer> k = new ArrayList<>();
//用一个列表来装括号的匹配
//遇见‘（’添加首次匹配位置进去
//遇见‘）’从最后一次‘（’匹配位置开始删除字符串
for(int i = 0; i < stringBuffer.length();){
if(stringBuffer.charAt(i)=='(') {
k.add(i);
i++;
}
else if(stringBuffer.charAt(i)=='<'&&k.size()==0) {
stringBuffer.delete(i - 1, i + 1);
i = i - 1;
}
else if(stringBuffer.charAt(i)==')') {
stringBuffer.delete(k.get(k.size() - 1),i + 1);
i = k.get(k.size() - 1);
k.remove(k.size() - 1);
}
else
i++;
}
System.out.println(stringBuffer);
}
}2. 迷宫游戏 - DFS/BFS
薯队长最近在玩一个迷宫探索类游戏，迷宫是一个N*N的矩阵形状，其中会有一些障碍物禁止通过。这个迷宫还有一个特殊的设计，它的左右 边界以及上下边界是连通的，比如在(2,n)的位置继续往右走一格可以到(2,1)， 在(1,2)的位置继续往上走一格可以到(n,2)。请问薯队长从起点位置S，最少走多少格才能到达迷宫的出口位置E。
输入描述:
第一行一个正整数N。 接下来N行。每行两个整数分别表示X 和 H X1 H1 X2 H2 … XN HN
输入限制： 对于70%的数据：
0<N<10^4
0<Xi<10^6
0<Hi<10^6
100%的数据：
0<N<10^6
0<Xi<10^6
0<Hi<10^6
输出描述:
一个整数，表示最多可以卖出的宝物数
输入
5
.#...
..#S.
.E###
.....
.....
输出
4
importjava.util.Scanner;
importjava.io.File;
importjava.util.Queue;
importjava.util.LinkedList;
classNode{
publicintx;
publicinty;
publicintlayer;
publicNode(intx,inty,intlayer) {
this.x = x;
this.y = y;
this.layer = layer;
}
}
publicclassMain {
publicstaticvoidmain(String[] args)throwsException{
//File file = new File("in.txt");
//Scanner in = new Scanner(file);
Scanner in =newScanner(System.in);
intn = in.nextInt();
in.nextLine();
char[][] board =newchar[n][n];
intstartX = -1;intstartY = -1;
intendX = -1;intendY = -1;
for(inti =0; i < n; i++) {
String line = in.nextLine();
for(intj =0; j < n; j++) {
board[i][j] = line.charAt(j);
if(board[i][j] =='S') {
startX = i;
startY = j;
}elseif(board[i][j] =='E') {
endX = i;
endY = j;
}
}
}
in.close();
if(startX == -1&& startY == -1) System.out.println("-1");
if(endX == -1&& endY == -1) System.out.println("-1");
Queue<Node> queue =newLinkedList<Node>();
intx = -1;inty = -1;
queue.offer(newNode(startX, startY,0));
while(!queue.isEmpty()) {
Node node = queue.poll();
//找到最后结果
if(node.x == endX && node.y == endY) {
System.out.println(node.layer);
return;
}
//四个方向
x = node.x +1; y = node.y;
if(x == n) x =0;
if(board[x][y] !='#') {queue.offer(newNode(x, y, node.layer +1)); board[x][y] ='#';}
x = node.x -1; y = node.y;
if(x == -1) x = n-1;
if(board[x][y] !='#') {queue.offer(newNode(x, y, node.layer +1)); board[x][y] ='#';}
x = node.x; y = node.y +1;
if(y == n) y =0;
if(board[x][y] !='#') {queue.offer(newNode(x, y, node.layer +1)); board[x][y] ='#';}
x = node.x; y = node.y -1;
if(y == -1) y = n-1;
if(board[x][y] !='#') {queue.offer(newNode(x, y, node.layer +1)); board[x][y] ='#';}
}
System.out.println("-1");
}
}3. 倒卖战利品
在游戏中，击败魔物后，薯队长获得了N件宝物，接下来得把这些宝物卖给宝物回收员来赚点小钱。这个回收员有个坏毛病，每次卖给他一件宝 物后，之后他就看不上比这件宝物差的宝物了。在这个世界中，衡量宝物的好坏有两个维度，稀有度X和实用度H，回收员在回收一个宝物A 后，下一个宝物的稀有度和实用度都不能低于宝物A。那么薯队长如何制定售卖顺序，才能卖给回收员宝物总个数最多。
输入描述:
第一行一个正整数N。 接下来N行。每行两个整数分别表示X 和 H X1 H1 X2 H2 … XN HN
输入限制： 对于70%的数据：
0<N<10^4
0<Xi<10^6
0<Hi<10^6
100%的数据：
0<N<10^6
0<Xi<10^6
0<Hi<10^6
输出描述:
一个整数，表示最多可以卖出的宝物数
示例1
输入
4
3 2
1 1
1 3
1 2
输出
3
分析
思路 先对数组排序(sort函数会同时对两个维度排序，第一个维度相同时会比较第二个维度)，然后在另一个维度上搜索最长上升子序列。
input: [[32],[11],[13],[12]]
sorted(input):[[11],[12],[13],[32]]
时间复杂度的限制：在找最长上升子序列时不能使用DP方法(O(N^2))，考虑通过二分查找来找到LIS。
LIS的二分查找算法：参考: leetcode 300.最长上升子序列
构造单调上升数组res，对原数组nums逐个遍历：
如果nums[i]>res[-1]，说明满足上升条件，将其插入数组中；
否则，通过二分查找res数组中刚好比它大的值并进行替换。当完成多次替换后该数组的最大值会减小，从而能向res中添加一些原数组中较小的值。
计算数组的长度得到LIS的最大值。
注意二分搜索时的边界以及返回值选择
按照一个维度排序后按照另一个维度寻找最长增加子序列即可，这个是>=的比较简单一点，注意不能用O(n2)，要二分查找优化
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] ans = new int[n][2];
for(int i=0;i<n;i++){
ans[i][0] = scanner.nextInt();
ans[i][1] = scanner.nextInt();
}
Arrays.sort(ans,(a,b)->a[0]!=b[0]?a[0]-b[0]:a[1]-b[1]);
int[] arr = new int[n];
for(int i=0;i<n;i++)arr[i] = ans[i][1];
System.out.println(LIS(arr));
}
public static int LIS(int[] arr){
int[] dp = new int[arr.length];
int res = 0;
for(int num:arr){
int l = 0,r = res;
while (l<r){
int m = (l+r)/2;
if(dp[m]<num)l = m+1;
else r = m;
}
dp[l] = num;
if(l==res)res++;
}
return res;
}
}
