面试题

【2分】以下关于 linux 文件系统说法错误的是

A /proc是真实存在于磁盘上的目录
B /dev/null和/dev/zero是一个特殊的设备文件，并不会存在于磁盘上
C /sys是sysfs文件系统挂载的标准位置
D cgroups系统通过读写文件与其交互

正确答案：A

【2分】如果由于某些原因需要查看多进程运行时的所有系统调用，可以使用什么命令

A ptrace
B strace -f 
C strace 
D ptrace -f

正确答案：B

【2分】下面这段代码输出什么？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
package main
import (
    "fmt"
)

func main() {
  var m = map[string]int{
    "A": 21,
    "B": 22,
    "C": 23,
  }
  counter := 0
  for k, v := range m {
    if counter == 0 {
      delete(m, "A")
    }
    counter++
    fmt.Println(k, v)
  }
  fmt.Println("counter is ", counter)
}

A 1
B 2
C 3
D 2 或 3

正确答案：D

【2分】存储器读写速率越高，每位的成本也越高，存储容量也小。解决这一问题的主要方法是采用

A Cache 
B 并行存储器 
C 多级存储体系结构
D 缓冲技术

正确答案：C

【2分】以下关于CPU与主存之间增加高速缓存(cache)的叙述中，错误的是

A cache扩充了主存储器的容量
B cache可以降低由于CPU与主存之间的速度差异造成的系统性能影响
C cache的有效性是利用了对主存储器访问的局部性特征
D cache通常保存着主存储器中部分内容的一份副本

正确答案：A

【2分】下面这段代码输出什么？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main
import (
    "fmt"
)

func increaseA() int {
  var i int
  defer func() {
    i++
  }()
  return i
}

func increaseB() (r int) {
  defer func() {
    r++
  }()
  return r
}

func main() {
  fmt.Println(increaseA())
  fmt.Println(increaseB())
}

正确答案：B

【2分】已知字符串S为”abaabaabacacaabaabcc”，模式串t为”abaabc”。采用KMP算法进行匹配，第一次出现“失配”（s[i]!=t[j]）时，i=j=5，则下次开始匹配时，i和j的值分别是

A i=1 j=0
B i=5 j=0
C i=5 j=2
D i=6 j=2

正确答案：C

【2分】假设初始栈为空，在对中缀表达式 a/b+(cd-ef)/g 转化为后缀表达式的过程中，当扫描到 f 时，栈中元素依次是：

A + ( * -    
B + ( - *
C / + ( * - *
D / + - *

正确答案：B

【2分】用哈希算法处理冲突时可能出现堆积现象，会受堆积直接影响的是：

A 储存效率
B 散列函数
C 装载因子
D 平均查找长度

正确答案：D

【2分】互斥锁，运行下面这段代码输出什么？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main
import (
    "fmt"
    "sync"
)

var mu sync.Mutex
var chain string

func main() {
  chain = "main"
  A()
  fmt.Println(chain)
}

func A() {
  mu.Lock()
  defer mu.Unlock()
  chain = chain + " --> A"
  B()
}

func B() {
  chain = chain + " --> B"
  C()
}

func C() {
  mu.Lock()
  defer mu.Unlock()
  chain = chain + " --> C"
}

A can't compile
B output main --> A --> B --> C
C output main
D the program exits because of panic

正确答案：D

【2分】对线性表进行折半查找时，要求线性表必须___ ___。

A 以顺序方式存储
B 以链接方式存储
C 以顺序方式存储，且元素按关键字有序排序
D 以链接方式存储，且元素按关键字有序排序

正确答案：B

【2分】关于内存分配说法错误的是

A 分页与分段都能达到地址隔离的效果
B 硬件中的TLB，帮助操作系统快速从虚拟地址定位到物理地址
C 如果TLB无法命中，则CPU或者操作系统会遍历分页表
D 操作系统运行时，程序获取的变量的内存地址是真实的物理地址

正确答案：D

【2分】关于 inode 以下说法错误的是

A inode的数量是有限的
B inode信息中有一项叫做"链接数"，软链接会修改链接数
C 不同名称的文件有可能对应相同的inode
D 如果inode被使用完，则会导致无法创建文件

正确答案：B

【2分】关于 Linux 的进程调度算法，相关说法错误的是

A 目前使用的调度算法只依靠优先级进行调度的
B 目前使用的调度算法可以保证IO密集型进程优先得到CPU资源
C 目前使用的调度算法在选择最优进程时时间复杂度为O(logN) 
D 目前使用的调度方式拥有多个优先级列表

正确答案：A

【2分】关于进程间通讯说法错误的是

A 匿名管道只能用于父子进程间单向通讯
B 命名管道实际是创建了一个管道文件
C 信号量只能用于父子进程间通讯与同步
D socket通讯可以跨主机通讯

正确答案：A

【2分】关于 linux 中进程状态叙述错误的是

A 处于D（TASK_UNINTERRUPTIBLE）状态的进程在状态改变前不能接受任何信号，也无法被强制退出
B 处于Z（EXIT_ZOMBIE）状态的进程产生的原因是因为其父进程未收集其退出状态
C 处于R（TASK_RUNNING）状态的进程不可能处于就绪状态
D 处于S（TASK_INTERRUPTIBLE）状态的进程可能是正在等待IO事件

正确答案：C

【2分】活锁与死锁类似，都是资源匮乏导致的，产生的原因是进程彼此释放资源又同时占用对方释放的资源，以下相关说法错误的是

A 死锁产生的必要条件仍然是活锁的产生的必要条件
B 处于活锁的多个进程处于非阻塞状态
C 消除死锁与活锁都可以通过杀掉进程来解决
D 活锁产生的必要条件不包括循环等待

正确答案：D

【2分】linux 中如果希望让内核跟踪数据包在iptables内的处理过程，可以在哪个表中加入相关规则

A raw
B nat
C filter
D mangle

正确答案：A

【2分】关于map，下面说法正确的是（）

A map反序列化时json.unmarshal的入参必须为map的地址
B 在函数调用中传递map，则子函数中对map元素的增加不会导致父函数中map的修改
C 在函数调用中传递map，则子函数中对map元素的修改不会导致父函数中map的修改
D 不能使用内置函数delete删除map的元素

正确答案：A

【2分】某文件的权限为-rw-r--r-x, 其对应权限用数值形式表示为

正确答案：C

【2分】下面这段代码输出什么？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
package main

func main() {
	var (
		a int         = 0
		b int64       = 0
		c interface{} = int(0)
		d interface{} = int64(0)
	)

	println(c == 0)
	println(c == a)
	println(c == b)
	println(d == b)
	println(d == 0)
}

A true true false true false
B true false false true false
C true true true false false
D true true false true true

正确答案：A

【2分】对任意实数c，从有N个无序元素的数组中寻找元素a、b，使得 a+b 的结果最接近c，最快的平均时间复杂度是

A O(N^2)
B O(log N)
C O(N)
D O(N^3)
E O(NLogN)
F 不确定

正确答案：E

参考答案：

2sum问题，稍微改了改让google直接搜不到

【2分】请问以下哪个协议使用UDP作为网络层传输？

A HTTP
B Telnet
C DNS
D SMTP

正确答案：C

【2分】 top命令中，哪个字段表示进程所占用的常驻内存使用量？

A VIRT
B RES
C SWAP
D DATA

正确答案：B

【2分】用户数据包 UDP 的首部字段有 16 个字节，这种说法正确吗？

A 正确
B 不正确

正确答案：B

【2分】在使用ping 命令时使用什么参数可以指定网卡或IP？

A -i
B -I
C -d
D -D

正确答案：B

【2分】默认情况下，ping命令每一次发出的icmp包大小为多少？

A 32
B 56
C 64
D 72

正确答案：C

【2分】在分层中继系统中，数据链路层接收或发送信息的基本单位是（）

A 比特
B 字节
C 帧
D 数据报

正确答案：C

【2分】epoll底层的工作机制属于以下哪种io模型：

A asynchronous I/O
B I/O multiplexing
C signal driven I/O
D nonblocking I/O

正确答案：B

【2分】当掩码位为/27时，子网中一共有多少个可用IP？

A 30
B 64
C 32
D 62

正确答案：A

参考答案：

网络号和广播地址不能算在内

【2分】在 TCP/IP 体系结构中的 TCP 和 IP 所提供的服务分别为（）

A 链路层服务和网络层服务
B 网络层服务和传输层服务
C 传输层服务和应用层服务
D 传输层服务和网络层服务

正确答案：D

【2分】以下哪种加密方式属于非对称加密：

A 3DES
B AES
C RSA256
D SHA256

正确答案：C

【2分】以下这段代码的输出是？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
  var a [2]int
	for _, x := range a {
		fmt.Println("x =", x)
		a[1] = 8
	}
	fmt.Println("a =", a)
	for _, n := range a {
		n += 1
	}
	fmt.Println("a =", a) 

A x = 0, x = 8, a = [0 8], a = [1 9]
B x = 0, x = 0, a = [0 8], a = [0 8]
C x = 0, x = 0, a = [0 8], a = [1 9]
D x = 0, x = 8, a = [0 8], a = [0 8]

正确答案：B

【2分】现假设A进程与B进程建立了tcp连接。A进程发起了中断连接的动作（发送FIN报文），但B进程接收FIN报文后由于代码错误只发送了ACK报文即结束进程。假设此ACK报文被A进程接收。那么tcp连接的A端和B端分别处于什么状态：

A FIN-WAIT-1, CLOSE-WAIT
B FIN-WAIT-2, TIME-WAIT
C FIN-WAIT-1, TIME-WAIT
D FIN-WAIT-2, CLOSE-WAIT

正确答案：D

【2分】 mkdir 命令中，添加什么参数，使得在父目录不存在时，先创建父目录？

A -m
B -f
C -d
D -p

正确答案：D

【2分】 linux发起socket读写操作时，线程状态转换将如何转换：

A 运行->就绪
B 运行->阻塞
C 就绪->阻塞

正确答案：B

【2分】如何将 test 文件打包并使用gzip压缩？

A tar -zcvf test test.tar.gz
B tar -zcvf test.tar.gz test
C tar -jcvf test.tar.gz test
D tar -jcvf test test.tar.gz

正确答案：B

参考答案：

Linux tar命令使用

【2分】下面这段程序的输出是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func Foo() error {
	var err *os.PathError = nil
	return err
}

func main() {
	err := Foo()
	fmt.Println(err)
	fmt.Println(err == nil)
}

A nil, false
B "", true
C nil, true
D nil, runtime error

正确答案：A

参考答案：

在Golang中，interface的动态类型和值都为空时才为nil

【2分】如何根据free命令的输出，得知目前实际可用内存？

A free列数据
B free列数据 - buffers列数据 + cached列数据
C free列数据 + buffers列数据 + cached列数据
D free列数据 + buffers列数据 - cached列数据

正确答案：C

【2分】 ctrl + c 会给前台进程组中的进程发送什么信号？

A SIGINT
B SIGTSTP
C SIGQUIT
D SIGTERM

正确答案：A

参考答案：

Linux信号机制

【2分】通道，运行下面这段代码输出什么？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import "fmt"

func main() {
  var ch chan int
  var count int

  go func() {
    ch <- 1
  }()

  go func() {
    count++
    close(ch)
  }()

  <-ch

  fmt.Println(count)
}

A can't compile
B output 1
C output 0
D the program exits because of panic

正确答案：D

【2分】 ctrl + z 会给前台进程组中的进程发送什么信号？

A SIGINT
B SIGTSTP
C SIGQUIT
D SIGTERM

正确答案：B

参考答案：

Linux信号机制

【2分】 ctrl + / 会给前台进程组中的进程发送什么信号？

A SIGINT
B SIGTSTP
C SIGQUIT
D SIGTERM

正确答案：C

参考答案：

Linux信号机制

【2分】以下哪个应用(Application)需要用到ICMP协议？

A ftp
B traceroute
C tcpdump
D netstat

正确答案：B

【2分】读写锁，运行下面这段代码输出什么？ package main

import ( "fmt" "sync" "time" )

var mu sync.RWMutex var count int

func main() { go A() time.Sleep(2 * time.Second) mu.Lock() defer mu.Unlock() count++ fmt.Println(count) }

func A() { mu.RLock() defer mu.RUnlock() B() }

func B() { time.Sleep(5 * time.Second) C() }

func C() { mu.RLock() defer mu.RUnlock() }

Acan't compile
Boutput 1
Cthe program is hung
Dthe program exits because of panic

正确答案：D

【2分】下述协议中，不建立于IP协议之上的协议是_____。

AARP
BICMP
CSNMP
DTCP

正确答案：A

【2分】在MySql中，如果要修改表的列名，下列语句的语法正确的是

AALTER TABLE 表名字 CHANGE 列名称 新列名称
BALTER TABLE 表名字 ALTER 列名称 新列名称
CALTER TABLE 表名字 MODIFY 列名称 新列名称
DALTER TABLE 表名字 列名称 新列名称

正确答案：A

【2分】以下关于堆的叙述中正确的是（）Ⅰ.在一个大根堆中，最小关键字的记录一定属于最底层的叶子结点层Ⅱ.在一个小根堆中，从根结点到某个叶子结点所经路径上的结点构成一个递增有序序列Ⅲ.堆一定是一棵完全二叉树Ⅳ.由某关键字序列构造的一棵完全二叉树经过一次筛选便可以变成一个堆

A仅Ⅰ、Ⅲ
B仅Ⅱ、Ⅲ
C仅Ⅱ、Ⅲ、Ⅳ
D仅Ⅰ、Ⅱ、Ⅲ

正确答案：B

【2分】以下情况对性能影响由大到小排列，最接近的选项是？ A.分支预测失败 B.L1 Cache 失效 C.IO等待 D.虚拟内存page miss

AA > B > C > D
BC > B > D > A
CD > A > C > B
DD > B > C > A
EA > C > D > B
FB > D > A > C
GC > D > B > A

正确答案：G

【2分】在使用Nmap对目标网络进行扫描时发现，某一个主机开放了25 SMTP和110 POP3端口，此主机最有可能是什么？

A文件服务器
B邮件服务器
CWEB服务器
DDNS服务器

正确答案：B. 【2分】能用二分法进行查找的是（）

A顺序存储的有序线性表
B线性链表
C二叉链表
D有序线性链表

正确答案：A

【2分】浏览器访问某页面，HTTP 协议返回状态码为 401 时表示

A找不到该页面
B未授权
C禁止访问
D服务器繁忙

正确答案：B

【2分】顺序表含有127个元素,向其插入一个新元素并保持原来顺序不变,平均要移动____个元素()

A63.5
B8
C32
D7

正确答案：A

【2分】 Mysql中，下列哪个是对某个IP段开放使用User用户访问数据库的权限的正确操作？

AGRANT ALL PRIVILEGES ON database.* TO 'user'@'192.168.100.1/255.255.255.240';
BGRANT ALL PRIVILEGES ON database.* TO 'user'@'192.168.100.1/28';
CGRANT ALL PRIVILEGES ON database.* TO 'user'@'192.168.100.1~14';
DGRANT ALL PRIVILEGES ON database.* TO 'user'@'192.168.100.1,192.168.100.2,192.168.100.3,192.168.100.4,192.168.100.5,192.168.100.6,192.168.100.7,192.168.100.8,192.168.100.9,192.168.100.10,192.168.100.11,192.168.100.12,192.168.100.13,192.168.100.14';

正确答案：A

【2分】有两个从小到大排好序的数组，长度分别为N和M，将这两个数组合并成一个有序数组的最小比较次数是？

AMin(N, M)
BM + N -1
CN + M
DMax(N, M)

正确答案：A

【2分】以下关于VPN说法正确的是

AVPN指的是用户自己租用线路，和公共网络物理上完全隔离的、安全的线路
BVPN指的是用户通过公用网络建立的临时的、安全的连接
CVPN不能做到信息认证和身份认证
DVPN只能提供身份认证、不能提供加密数据的功能

正确答案：B

【2分】 epoll底层的工作机制属于以下哪种io模型：

Aasynchronous I/O
BI/O multiplexing
Csignal driven I/O
Dnonblocking I/O

正确答案：B

【2分】数据库事务的特性不包括以下哪一项？

A原子性
B分区容错性
C一致性
D隔离性

正确答案：B

【2分】以下哪种加密方式属于非对称加密：

A3DES
BAES
CRSA256
DSHA256

正确答案：C

【2分】下列有关MySQL数据库中的NULL值,说法正确的是

ANULL与它本身的比较可以使用=,<>或!=
BNULL是"有数据的"
CNULL与0的比较可以使用=,<>或!=
DNULL是"无数据"或"未知数据"

正确答案：D

【2分】现假设A进程与B进程建立了tcp连接。A进程发起了中断连接的动作（发送FIN报文），但B进程接收FIN报文后，只发送了ACK报文并被A进程接收。那么tcp连接的A端和B端分别处于什么状态：

AFIN-WAIT-1, CLOSE-WAIT
BFIN-WAIT-2, TIME-WAIT
CFIN-WAIT-1, TIME-WAIT
DFIN-WAIT-2, CLOSE-WAIT

正确答案：D

【2分】以下关于NAT地址类型中的描述，错误的是

A复用地址转换是一种特殊的静态地址转换
B动态地址转换是从内部合法地址池中动态地选择一个未使用的地址对内部本地地址进行转换
C端口地址转换使多个内部节点共享一个全局IP地址，而使用源和目的的TCP/UDP的端口号来区分NAT表中的转换条目及内部
D静态NAT将内部地址一对一静态映射到内部全局地址

正确答案：A

【2分】 linux发起socket读写操作时，线程状态转换将如何转换：

A运行->就绪
B运行->阻塞
C就绪->阻塞

正确答案：B

【2分】以下关于TCP/IP协议的叙述中，说法错误的是

AICMP协议用于控制数据报传送中的差错情况
BRIP协议根据交换的路由信息动态生成路由表
CFTP协议在客户服务器之间建立起两条连接
DRARP协议根据IP地址查询对应的MAC地址

正确答案：D

【2分】一台主机要实现通过局域网与另一个局域网通信，需要做的工作是

A配置域名服务器
B定义一条本机指向所在网络的路由
C定义一条本机指向所在网络网关的路由
D定义一条本机指向目标网络网关的路由

正确答案：C

【2分】当同一网段中两台工作站配置了相同的IP 地址时，会导致

A先入者被后入者挤出网络而不能使用
B双方都会得到警告，但先入者继续工作，而后入者不能
C双方可以同时正常工作，进行数据的传输
D双主都不能工作，都得到网址冲突的警告

正确答案：B

【2分】在区间[-2, 2]里任取两个实数，它们的和>1的概率是：

A3/8
B3/16
C9/32
D9/64

正确答案：C

参考答案：

作图可解

【2分】下列关于程序优化的说法正确的是：

A在任何场景下面，实现同样逻辑的JIT代码都比native代码运行的速度慢；
B循环展开得越多越彻底，程序的性能越好；
C寄存器分配能够解决程序中的数据依赖问题；
D现代主流C/C++编译器可以对简单的小函数进行自动inline

正确答案：D

参考答案：

JIT在某些场景可以缓存中间结果，不一定比native慢；循环过度展开可能引起cache miss；

【2分】如果 22, 24, 26, 14, 16, 18, 46, 8, 10 是第二次排序后的结果，以下哪种排序算法可以满足？

A冒泡排序
B插入排序
C选择排序
D快速排序

正确答案：B

【2分】如果把传输速率定义为单位时间内传送的信息量(以字节计算)多少。关于一下几种典型的数据传输速率：(1)使用USB3.0闪存盘，往USB闪存盘上拷贝文件的数据传输速率(2)使用100M以太网，在局域网内拷贝大文件时网络上的数据传输速率(3)使用一辆卡车拉1000块单块1TB装满数据的硬盘，以100km/h的速度从上海到天津(100km)一趟所等价的数据传输宽带(4)使用电脑播放MP3，电脑的pci总线到声卡的数据传输速率在通常情况下，关于这几个传输速率的排序正确的是：

A4<2<1<3
B1<4<2<3
C4<1<3<2
D1<4<3<2

正确答案：A

【2分】一个人上楼梯有两种走法：一次上一级和一次上两级，那么走上一个有11级的楼梯有多少种走法：

A110;
B89;
C140;
D144;

正确答案：D

参考答案：

斐波那契数列，F(0) = F(1) = 1, F(11) = 144

【2分】在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是。

A41
B82
C113
D122

正确答案：B

参考答案：

除根节点外，每个节点都有一个入度，总入度为20 * 4 + 10 * 3 + 1 * 2 + 10 * 1 = 122，所以总节点数为123，叶子节点为123 - 20 - 10 - 1 - 10 = 82

【2分】设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g 依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是：

A1
B2
C3
D4

正确答案：C

参考答案：

略

【2分】设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为 ()

A12
B13
C14
D15

正确答案：B

【2分】给定下列归并排序代码:int *tmp = new int[10000];void MergeSort(int *ptr, int size) {if (size <= 1) {return;}auto half_size = size / 2;MergeSort(ptr, half_size);MergeSort(ptr + half_size, size - half_size); // 断点Merge(ptr, size, tmp);}int main() {int ary[] = { 2, 1, 3, 4, 7, 6, 5 };MergeSort(ary, 7);return 0;}假设注释所在的行被加了一个断点，当这个断点第3次被hit到时，ary的元素顺序依次是:

A2 1 3 4 5 6 7;
B2 1 3 4 6 7 5;
C1 2 3 4 7 6 5;
D1 2 3 4 5 6 7;

正确答案：C

参考答案：

略

【2分】 HTTP/3 (Hypertext Transfer Protocol (HTTP) over QUIC) 是基于什么传输层的协议的？

ATCP
BUDP
CICMP
DIP

正确答案：B

【2分】具有3个结点的二叉树有()

A2种形态
B4种形态
C7种形态
D5种形态

正确答案：D

【2分】如果下面源码被编译成32位程序（g++ -o test -m32 ./test.cpp），程序的输出是多少:includeusing namespace std;struct Foo { char c; int x; short y; };int main() { cout << sizeof(Foo) << endl; return 0; }

A7;
B12;
C8;
D都不对；

正确答案：B

参考答案：

考虑地址对齐

【2分】栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是()

AABCED
BDBCEA
CCDABE
DDCBEA

正确答案：D

【2分】下列代码中三个变量x, y, z的内存位置分别是:int using namespace std;static int x = 0;void add(int e) { int y = 2 * e; x += y; }int main() {add(1);int *z = &x;cout << *z << endl;return 0;}

A数据段，栈，堆；
B栈，数据段，堆；
CBSS段，栈，栈；
D数据段，栈，栈;

正确答案：D

参考答案：

x是被初始化的全局变量位于数据段，y位于栈中，z是指针变量，也位于栈中；

【2分】已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是()

Acedba
Bacbed
Cdecab
Ddeabc

正确答案：A

【2分】下列命中组合情况中，一次访存过程中不．可能发生的是。

ATLB 未命中，Cache 未命中，Page 未命中
BTLB 未命中，Cache 命中，Page 命中
CTLB 命中，Cache 未命中，Page 命中
DTLB 命中，Cache 命中，Page 未命中

正确答案：D

参考答案：

TLB为页表缓冲，不可能发生page为命中，但是TLB命中的情况

【2分】相同session的数据包(packet)在以下哪个或哪些协议中有可能通过不同的路由路径传输？

ATCP, but not UDP
BTCP and UDP
CUDP, but not TCP
DNeither TCP nor UDP

正确答案：B

【2分】以下数据结构中不属于线性数据结构的是()

A队列
B线性表
C二叉树
D栈

正确答案：C

【2分】在一棵二叉树上第5层的结点数最多是()

A8
B16
C32
D15

正确答案：B

【2分】有一个算法的递推关系式为：T(N) = T(2N/3) + 1，则该算法的时间复杂度为（）(^符号是幂的意思)

AO(1)
BO(N^log2(3) )
CO(N^log3(2) )
DO(logN)
EO(N)

正确答案：D

【2分】命题p→q与下面哪个命题等价

A~p∧q
Bp∧q
C~p∨q
Dp∨q

正确答案：C

【2分】关于 HTTP 协议说法中错误的是

AHTTP协议是无状态协议
BHTTP/1.0中已经支持KeepAlive
CHTTP/2协议支持多路复用与首部压缩
DHTTP/3将会使用UDP来传输数据

正确答案：B

【2分】关于路由跟踪错误的是（请考虑任意平台中任意可用于做路由跟踪的软件）

ATCP与UDP协议也可用来做路由跟踪
B如果使用ICMP协议做路由跟踪，需要指定目目标端口
Clinux下做路由跟踪的软件包括traceroute和mtr 
D如果使用TCP协议做路由跟踪，目标主机不一定能有回应

正确答案：B

【2分】关于 TCP 连接中拥塞控制中，正确的是

A拥塞窗口的大小，在首次出现丢包时一直是指数增长
B 快重传输算法中，如果发送方收到三个重复确认就应当立即重传对方尚未收到的报文段
C快重传算法触发后，快恢复不一定触发
D快重传算法触发后，慢启动阈值根据原慢启动阈值进行改变

正确答案：B

问答题

【6分】在go语言中，数组与切片的区别？

参考答案：

(1). 数组数组是具有固定长度且拥有零个或者多个相同数据类型元素的序列。数组的长度是数组类型的一部分，所以[3]int 和 [4]int 是两种不同的数组类型。数组需要指定大小，不指定也会根据初始化的自动推算出大小，不可改变 ; 数组是值传递; 数组是内置(build-in)类型,是一组同类型数据的集合，它是值类型，通过从0开始的下标索引访问元素值。在初始化后长度是固定的，无法修改其长度。当作为方法的参数传入时将复制一份数组而不是引用同一指针。数组的长度也是其类型的一部分，通过内置函数len(array)获取其长度。数组定义： var array [10]int

var array = [5]int{1,2,3,4,5}

(2). 切片切片表示一个拥有相同类型元素的可变长度的序列。切片是一种轻量级的数据结构，它有三个属性：指针、长度和容量。切片不需要指定大小; 切片是地址传递; 切片可以通过数组来初始化，也可以通过内置函数make()初始化 .初始化时len=cap,在追加元素时如果容量cap不足时将按len的2倍扩容；切片定义： var slice []type = make([]type, len)

【6分】Go程序资源初始化顺序？

参考答案：

一个程序中所涉及到的所有的在运行时刻要用到的代码包的加载是串行执行的。在一个程序启动时，每个包中总是在它所有依赖的包都加载完成之后才开始加载。程序代码包总是最后一个被加载的代码包。每个被用到的包会被而且仅会被加载一次。在加载一个代码包的过程中，所有的声明在此包中的init函数将被串行调用并且仅调用执行一次。一个代码包中声明的init函数的调用肯定晚于此代码包所依赖的代码包中声明的init函数。所有的init函数都将在调用main入口函数之前被调用执行。在同一个源文件中声明的init函数将按从上到下的顺序被调用执行。对于声明在同一个包中的两个不同源文件中的两个init函数，Go语言白皮书推荐（但不强求）按照它们所处于的源文件的名称的词典序列（对英文来说，即字母顺序）来调用。所以最好不要让声明在同一个包中的两个不同源文件中的两个init函数存在依赖关系。在加载一个代码包的时候，此代码包中声明的所有包级变量都将在此包中的任何一个init函数执行之前初始化完毕。在同一个包内，包级变量将尽量按照它们在代码中的出现顺序被初始化，但是一个包级变量的初始化肯定晚于它所依赖的其它包级变量。

【6分】在Go语言中，函数调用time.Sleep(d)和通道接收<-time.After(d)操作之间有何区别？

参考答案：

两者都会将当前的goroutine执行暂停一段时间。区别在于time.Sleep(d)函数调用将使当前的协程进入睡眠字状态，但是当前协程的（主）状态依然为运行状态；而通道接收<-time.After(d)操作将使当前协程进入阻塞状态。

【6分】Go语言中除了使用+运算符来衔接字符串，我们还可以用哪些方法来衔接字符串？

参考答案：

fmt标准库包中的Sprintf/Sprint/Sprintln函数可以用来衔接各种类型的值的字符串表示，当然也包括字符串类型的值。
使用strings标准库包中的Join函数。
bytes标准库包提供的Buffer类型可以用来构建一个字节切片，然后我们可以将此字节切片转换为一个字符串。
strings标准库包中的Builder类型可以用来拼接字符串。和bytes.Buffer类型类似，此类型内部也维护着一个字节切片，但是它在将此字节切片转换为字符串时避免了底层字节的深复制。

【6分】运行下面这段代码输出什么？ package main

import ( "fmt" )

func main() { slice := []int{0, 1, 2, 3} m := make(map[int]*int)

for key, val := range slice { m[key] = &val }

for k, v := range m { fmt.Printf("key: %d, value: %d \n", k, *v) } }

参考答案：

key: 0, value: 3 key: 1, value: 3 key: 2, value: 3 key: 3, value: 3

解析: for range 循环的时候会创建每个元素的副本，而不是元素的引用，所以 m [key] = &val 取的都是变量 val 的地址，所以最后 map 中的所有元素的值都是变量 val 的地址，因为最后 val 被赋值为 3，所有输出都是 3.

【6分】在go语言中，new和make的区别？

参考答案：

new 的作用是初始化一个指向类型的指针(*T) new函数是内建函数，函数定义：func new(Type) *Type 使用new函数来分配空间。传递给new 函数的是一个类型，不是一个值。返回值是指向这个新分配的零值的指针。 make 的作用是为 slice，map 或 chan 初始化并返回引用(T)。

make函数是内建函数，函数定义：func make(Type, size IntegerType) Type · 第一个参数是一个类型，第二个参数是长度 · 返回值是一个类型 make(T, args)函数的目的与new(T)不同。它仅仅用于创建 Slice, Map 和 Channel，并且返回类型是 T（不是T*）的一个初始化的（不是零值）的实例。

【6分】缓存在计算机系统中广泛使用，请设计一个缓存系统，满足如下要求：基于k-v形式存储和访问数据且时间复杂度满足O(1)，在并发情况下保证数据同步。工程实现中，需要考虑在系统内存大小约束下的数据淘汰规则，通常基于LRU等规则进行数据淘汰。请在上述实现的基础上，增加基于LRU的数据淘汰规则，使得系统中最多保存最近被访问的N条数据。

【6分】以下这段代码是否存在问题？如有请纠正，并指出问题如没有，则程序的输出是？ func main() { var wg sync.WaitGroup wg.Add(5) for i := 0; i < 5; i++ { go func() { fmt.Print(i) wg.Done() }() } wg.Wait() fmt.Println() }

【6分】Go语言中哪些表达式的估值结果可以包含一个额外的可选的值？

参考答案：

【6分】简述一下golang的MPG调度模型?

参考答案：

M(machine): 关联了一个内核线程。 P(processor): 代表了M所需的上下文环境,也是处理用户级代码逻辑的处理器。

G(goroutine): 调度系统的最基本单位goroutine,存储了goroutine的执行stack信息、goroutine状态以及goroutine的任务函数等。

M关联了一个内核线程，通过调度器P（上下文）的调度，可以连接1个或者多个G,相当于把一个内核线程切分成了了N个用户线程；

M和P是一对一关系（但是实际调度中关系多变），通过P调度N个G（P和G是一对多关系），实现内核线程和G的多对多关系（M:N），通过这个方式，一个内核线程就可以起N个Goroutine，同样硬件配置的机器可用的用户线程就成几何级增长，并发性大幅提高。

【6分】Go语言中哪些种类型的值可以用做内置len（以及cap、close、delete和make）函数调用的实参？

参考答案：

【6分】 Go语言中运行时错误信息all goroutines are asleep - deadlock意味着什么?

参考答案：

用词asleep在这里其实并不准确，实际上它的意思是处于阻塞状态。

因为一个处于阻塞状态的协程只能被另一个协程解除阻塞，如果程序中所有的协程都进入了阻塞状态，则它们将永远都处于阻塞状态。这意味着程序死锁了。

一个正常运行的程序永远不应该死锁，一个死锁的程序肯定是由于逻辑实现上的bug造成的。因此官方Go标准运行时将在一个程序死锁时令其崩溃退出。

【6分】假设某信息流推荐引擎后台需要记录每一小时内访问某篇文章的不同用户数量，由于可能存在爆款文章，通过内存存储某一小时的用户id并进行去重计算可能导致oom。请设计一个合理的存储机制，保证访问数据存储的高效性和计算的可靠性。

编程题

完善核心代码语言限制【10分】标题：合并二叉树 | 时间限制：1秒 | 内存限制：262144K已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：两颗二叉树是: Tree 1
1
/ \
3 2 /
5

Tree 2 2 /
1 3 \
4 7

合并后的树为 3 /
4 5 / \
5 4 7

示例1

输入{1,3,2,5},{2,1,3,#,4,#,7}输出{3,4,5,5,4,#,7}

完善核心代码语言限制【10分】标题：需要排序的最短子数组长度 | 时间限制：2秒 | 内存限制：262144K给定一个无序数组arr，求出需要排序的最短子数组的长度，对子数组排序后能使得整个数组有序，即为需要排序的数组。例如：arr=[1,5,3,4,2,6,7]返回4，因为只有[5,3,4,2]需要排序。备注: $1 \leq n \leq 10^5$ 示例1输入[1,5,3,4,2,6,7]输出4 `

完善核心代码语言限制【10分】标题："之"字形打印矩阵 | 时间限制：2秒 | 内存限制：262144K给定一个矩阵matrix，按照“之”字形的方式打印这个矩阵，如样例所示。备注: $1 \leq n,m \leq 200$ 示例1输入[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]输出[1,2,5,9,6,3,4,7,10,13,14,11,8,12,15,16] `

完善核心代码语言限制【10分】标题：将正方形矩阵顺时针旋转90度 | 时间限制：2秒 | 内存限制：262144K给定一个n*n的矩阵matrix，请把这个矩阵顺时针转动90度。备注: $1 \leq n \leq 200$ 示例1输入[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]输出[[13,9,5,1],[14,10,6,2],[15,11,7,3],[16,12,8,4]] `

完善核心代码语言限制【10分】标题：在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数 | 时间限制：2秒 | 内存限制：262144K给定一个数字arr，其中只有有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。备注: $1 \leq n \leq 10^5$ 示例1输入[1,1,2,3]输出[2,3] 示例2输入[11,22,11,23,23,45]输出[22,45] `

完善核心代码语言限制【10分】标题：在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数 | 时间限制：2秒 | 内存限制：262144K给一个数组arr，其中只有一个数出现了奇数次，其它数出现了偶数次，打印这个数。备注: $1 \leq n \leq 10^5$ 示例1输入[3,1,3,1,2]输出2 示例2输入[6,6,3]输出3 `

完善核心代码语言限制【10分】标题：整数的二进制数表达中有多少个1 | 时间限制：2秒 | 内存限制：262144K给定一个32位整数n，返回该整数二进制形式1的个数。示例1输入1输出1 示例2输入-2输出31

完善核心代码语言限制【10分】标题：不用算术运算符实现整数的加减乘除运算 | 时间限制：2秒 | 内存限制：262144K给定两个32位整数a和b。要求不使用算术运算符，分别实现a和b的加减乘除运算。如果给定的a和b执行加减乘除的某些结果本来就会导致数据的溢出，那么你实现的函数不需要对那些结果负责（你的输出和加减乘除溢出的结果保持一致就行）。运算符为“+”，“-”，“*”，""中的一个。（数据保证不会出现除0的情况）示例1输入2,*,4输出8 示例2输入5,\,4输出1

完善核心代码语言限制【10分】标题：子数组的最大异或和 | 时间限制：2秒 | 内存限制：262144K数组异或和的定义：把数组中所有的数异或起来得到的值。给定一个整型数组arr，其中可能有正、有负，有零，求其中子数组的最大异或和。备注: $1 \leq n \leq 10^5$ 示例1输入[3,-28,-29,2]输出7 说明{-28，-29}这个子数组的异或和为7，是所有子数组中最大的`

完善核心代码语言限制【10分】标题：字典树的实现 | 时间限制：2秒 | 内存限制：262144K字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。void insert(String word)：添加word，可重复添加；void delete(String word)：删除word，如果word添加过多次，仅删除一次；boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。备注: $m \leq 10^5$ $|word| \leq 20$ 示例1输入[["1","qwer"],["1","qwe"],["3","qwer"],["4","q"],["2","qwer"],["3","qwer"],["4","q"]]输出["YES","2","NO","1"] `

完善核心代码语言限制【10分】标题：表达式得到期望结果的组合种数 | 时间限制：2秒 | 内存限制：262144K给定一个只由0（假）、1（真）、&（逻辑与）、|（逻辑或）和^（异或）五种字符组成的字符串express，再给定一个布尔值desired。求出express能有多少种组合方式，可以达到desired的结果。并输出你所求出的总方案数对 $10^{9}+7$ 取模后的值。备注: $1 \leq |express| \leq 500$ 示例1输入"1^0|0|1",false输出2 说明1^((0|0)|1)和1^(0|(0|1))可以得到false示例2输入"1",false输出0 `

完善核心代码语言限制【10分】标题：数字字符转化为字母组合的种数 | 时间限制：2秒 | 内存限制：262144K给定一个字符串str，str全部由数字字符组成，如果str中的某一个或者相邻两个字符组成的子串值在1~26之间，则这个子串可以转换为一个字母。规定‘1’转换为“A”，“2”转换为“B”......"26"转化为“Z“。请求出str有多少种不同的转换结果，由于答案可能会比较大，所以请输出对 $10^{9}+7$ 取模后的答案。备注: $1 \leq |str| \leq 10^5$ 示例1输入"1111"输出5 示例2输入"01"输出0 `

完善核心代码语言限制【10分】标题：在数组中找到出现次数大于n/k的数 | 时间限制：2秒 | 内存限制：262144K给定一个整型数组arr，再给定一个整数k，按从小到大顺序打印所有出现次数大于n/k的数，如果没有这样的数,请打印”-1“。备注: $1 \leq k \leq n \leq 10^5$ 示例1输入[1,2,3,1,2,3,4],7输出[1,2,3] 示例2输入[1,1,2,3],1输出[-1] `

完善核心代码语言限制【10分】标题：在数组中找到出现次数大于一半的数 | 时间限制：2秒 | 内存限制：262144K给定一个整型数组arr，请打印其中出现次数大于一半的数，如果没有这样的数，请输出-1。备注: $n \leq 10^5$ 示例1输入[11,7,5,7,7]输出7 示例2输入[2,2,3,3]输出-1 `

完善核心代码语言限制【10分】标题：打印两个升序链表的公共部分 | 时间限制：2秒 | 内存限制：262144K给定两个升序链表，按升序打印两个升序链表的公共部分。示例1输入[1,2,3,4],[1,2,3,5,6]输出[1,2,3]

完善核心代码语言限制【10分】标题：表达式求值 | 时间限制：1秒 | 内存限制：262144K请写一个整数计算器，支持加减乘三种运算和括号。示例1输入"1+2"输出3 示例2输入"(2*(3-4))*5"输出-10 示例3输入"3+2*3*4-1"输出26

完善核心代码语言限制【10分】标题：打印二叉树的边界节点 | 时间限制：3秒 | 内存限制：262144K给定一颗二叉树的根节点 root，按照如下两种标准分别实现二叉树的边界节点的逆时针打印。标准一：1，根节点为边界节点。2，叶节点为边界节点。3，如果节点在其所在的层中是最左的或最右的，那么该节点也是边界节点。标准二：1，根节点为边界节点。2，叶节点为边界节点。3，树左边界延伸下去的路径为边界节点。4，树右边界延伸下去的路径为边界节点。ps:具体请对照样例备注: $n \leq 10^6$ 示例1输入{1,2,3,#,4,5,6,7,8,9,10,#,#,#,#,#,11,12,#,#,#,13,14,15,16}输出[[1,2,4,7,11,13,14,15,16,12,10,6,3],[1,2,4,7,13,14,15,16,10,6,3]] `

完善核心代码语言限制【10分】标题：实现二叉树先序，中序和后序遍历 | 时间限制：3秒 | 内存限制：262144K分别按照二叉树先序，中序和后序打印所有的节点。备注: $n \leq 10^6$ 示例1输入{1,2,3}输出[[1,2,3],[2,1,3],[2,3,1]] `

完善核心代码语言限制【10分】标题：链表的奇偶重排 | 时间限制：1秒 | 内存限制：262144K给定一个单链表，请设定一个函数，讲链表的奇数位节点和偶数位节点分别放在一起，重排后输出。注意是节点的编号而非节点的数值。

备注:链表长度不大于200000。每个数范围均在int内。示例1输入{1,2,3,4,5,6}输出{1,3,5,2,4,6} 示例2输入{1,4,6,3,7}输出{1,6,7,4,3} 说明奇数节点有1,6,7，偶数节点有4,3。重排后为1,6,7,4,3

完善核心代码语言限制【10分】标题：合并两个有序的单链表 | 时间限制：3秒 | 内存限制：262144K给定两个升序的单链表的头节点 head1 和 head2，请合并两个升序链表，合并后的链表依然升序，并返回合并后链表的头节点。备注: $n \leq 10^6$ 示例1输入[1,2,3,4,5],[7,8,9,10,11,12]输出{1,2,3,4,5,7,8,9,10,11,12} `

完善核心代码语言限制【10分】标题：股票交易的最大收益 | 时间限制：1秒 | 内存限制：262144K假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。备注:总天数不大于200000。保证股票每一天的价格在[1,100]范围内。示例1输入[5,4,3,2,1]输出0 说明由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。 示例2输入[1,2,3,4,5]输出4 说明第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

完善核心代码语言限制【10分】标题：把数字翻译成字符串 | 时间限制：1秒 | 内存限制：262144K有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。现在给一串数字，返回有多少种可能的译码结果示例1输入"12"输出2 说明2种可能的译码结果（”ab” 或”l”）示例2输入"31717126241541717"输出192 说明192种可能的译码结果

完善核心代码语言限制【10分】标题：一行代码求两个数的最大公约数 | 时间限制：2秒 | 内存限制：262144K给定两个不等于0的整数M和N，求M和N的最大公约数。备注: $1 \leq M,N \leq 10^9$ 示例1输入6,12输出6 示例2输入2,3输出1 `

完善核心代码语言限制【10分】标题：容器盛水问题 | 时间限制：2秒 | 内存限制：262144K给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。具体请参考样例解释备注: $1 \leq N \leq 10^6$ 示例1输入[3,1,2,5,2,4]输出5 说明 示例2输入[4,5,1,3,2]输出2 `

完善核心代码语言限制【10分】标题：加油站良好出发点问题 | 时间限制：2秒 | 内存限制：262144KN个加油站组成一个环形，给定两个长度都是N的非负数组oil和dis(N>1)，oil[i]代表第i个加油站存的油可以跑多少千米，dis[i]代表第i个加油站到环中下一个加油站相隔多少千米。假设你有一辆油箱足够大的车，初始时车里没有油。如果车从第i个加油站出发，最终可以回到这个加油站，那么第i个加油站就算良好出发点，否则就不算。请返回长度为N的boolean型数组res，res[i]代表第i个加油站是不是良好出发点规定只能按照顺时针走，也就是i只能走到i+1，N只能走到1[要求]时间复杂度为，空间复杂度为备注: $1 \leq N \leq 10^5$ $0 \leq oil_i, dis_i \leq 10^9$ 示例1输入[4,2,0,4,5,2,3,6,2],[6,1,3,1,6,4,1,1,6]输出[0,0,0,0,0,0,0,0,0] 示例2输入[4,5,3,1,5,1,1,9],[1,9,1,2,6,0,2,0]输出[0,0,1,0,0,1,0,1] `

完善核心代码语言限制【10分】标题：判断回文 | 时间限制：1秒 | 内存限制：262144K给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。备注:字符串长度不大于1000000，且仅由小写字母组成示例1输入"absba"输出true 示例2输入"ranko"输出false 示例3输入"yamatomaya"输出false

完善核心代码语言限制【10分】标题：判断一棵二叉树是否为搜索二叉树和完全二叉树 | 时间限制：2秒 | 内存限制：262144K给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。备注: $n \leq 500000$ 示例1输入{2,1,3}输出[true,true] `

完善核心代码语言限制【10分】标题：根据后序数组重建搜索二叉树 | 时间限制：2秒 | 内存限制：262144K给定一个有 n 个不重复整数的数组 arr，判断 arr 是否可能是节点值类型为整数的搜索二叉树后序遍历的结果。备注: $1 \leq n \leq 500000$ 示例1输入[1,3,2]输出true `

完善核心代码语言限制【10分】标题：判断二叉树是否为平衡二叉树 | 时间限制：2秒 | 内存限制：262144K平衡二叉树的性质为: 要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过 1。给定一棵二叉树，判断这棵二叉树是否为平衡二叉树。一颗树的高度指的是树的根节点到所有节点的距离中的最大值。备注: $1 \leq n \leq 500000$ 示例1输入{1,2,3}输出true `

完善核心代码语言限制【10分】标题：判断t1树中是否有与t2树拓扑结构完全相同的子树 | 时间限制：2秒 | 内存限制：262144K给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 等于 E1 ，则表示 t1 树和t2 树的拓扑结构完全相同。备注: $1 \leq n \leq 500000$ 示例1输入{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}输出true `

完善核心代码语言限制【10分】标题：判断t1树是否包含t2树全部的拓扑结构 | 时间限制：2秒 | 内存限制：262144K给定彼此独立的两棵二叉树，判断 t1 树是否包含 t2 树全部的拓扑结构。设 t1 树的边集为 E1，t2 树的边集为 E2，若 E2 是 E1 的子集，则表示 t1 树包含 t2 树全部的拓扑结构。备注: $1 \leq n,m \leq 2000$ 示例1输入{1,2,3,4,5,6,7,8,9,10},{2,4,5,8}输出true `

完善核心代码语言限制【10分】标题：找到二叉树中符合搜索二叉树条件的最大拓扑结构 | 时间限制：2秒 | 内存限制：262144K给定一颗二叉树，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。拓扑结构是指树上的一个联通块。备注: $1 \leq n \leq 2 \times 10^5$ 示例1输入{2,1,3}输出3 `

完善核心代码语言限制【10分】标题：找到二叉树中的最大搜索二叉子树 | 时间限制：3秒 | 内存限制：262144K给定一颗二叉树，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子树，输出该子树总节点的数量。搜索二叉树是指对于二叉树的任何一个节点，如果它有儿子，那么左儿子的值应该小于它的值，右儿子的值应该大于它的值。备注: $1 \leq n \leq 10^6$ 示例1输入{2,1,3}输出3 `

完善核心代码语言限制【10分】标题：在二叉树中找到累加和为指定值的最长路径长度 | 时间限制：2秒 | 内存限制：262144K给定一颗二叉树和一个整数 sum，求累加和为 sum 的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。备注: $1 \leq n \leq 2 \times 10^5$ 示例1输入{-3,3,-9,1,0,2,1,#,#,1,6},-9输出1 `

完善核心代码语言限制【10分】标题：在二叉树中找到两个节点的最近公共祖先 | 时间限制：2秒 | 内存限制：262144K给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。示例1输入[3,5,1,6,2,0,8,#,#,7,4],5,1输出3

完善核心代码语言限制【10分】标题：通过先序和中序数组生成后序数组 | 时间限制：2秒 | 内存限制：262144K给出一棵二叉树的先序和中序数组，通过这两个数组直接生成正确的后序数组。备注: $n \leq 10000$ 示例1输入[1,2,3],[2,1,3]输出[2,3,1] `

完善核心代码语言限制【10分】标题：二叉树节点间的最大距离问题 | 时间限制：2秒 | 内存限制：262144K从二叉树的节点 A 出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点 B 时，路径上的节点数叫作 A 到 B 的距离。现在给出一棵二叉树，求整棵树上每对节点之间的最大距离。备注: $n \leq 500000$ 示例1输入{1,2,3,4,5,6,7}输出5 `

完善核心代码语言限制【10分】标题：股票交易的最大收益（二） | 时间限制：1秒 | 内存限制：262144K假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。备注:总天数不大于200000。保证股票每一天的价格在[1,100]范围内。示例1输入[8,9,3,5,1,3]输出4 说明第三天买进，第四天卖出，第五天买进，第六天卖出。总收益为4。

完善核心代码语言限制【10分】标题：跳跃游戏 | 时间限制：2秒 | 内存限制：262144K给定数组arr，arr[i]==k代表可以从位置向右跳1~k个距离。比如，arr[2]==3,代表可以从位置2跳到位置3、位置4或位置5。如果从位置0出发，返回最少跳几次能跳到arr最后的位置上。备注: $1 \leq n \leq 10^5$ 示例1输入[3,2,3,1,1,4]输出2 说明arr[0]==3，选择跳到位置2，arr[2]==3,可以跳到最后的位置。所以返回2。`

完善核心代码语言限制【10分】标题：有关阶乘的两个问题 | 时间限制：2秒 | 内存限制：262144K给定一个非负整数N，如果用二进制数表达N!的结果，返回最低位的1在哪个位置上，认为最右的位置为位置0。备注: $1 \leq N \leq 10^{18}$ 示例1输入1输出0 说明1! = 1，最低位的1在0位置上示例2输入2输出1 说明2 != 2，最低位的1在1位置上示例3输入1000000000输出999999987 `

完善核心代码语言限制【10分】标题：矩阵最长递增路径 | 时间限制：1秒 | 内存限制：262144K给定一个矩阵，矩阵内所有数均为非负整数。求一条路径，该路径上所有数是递增的。这个路径必须满足以下条件：1、对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外。2、你不能走重复的单元格。即每个格子最多只能走一次。备注:矩阵的长和宽均不大于1000，矩阵内每个数不大于1000示例1输入[[1,2,3],[4,5,6],[7,8,9]]输出5 说明1->2->3->6->9即可。当然这种递增路径不是唯一的。 示例2输入[[1,2],[4,3]]输出4 说明1->2->3->4

完善核心代码语言限制【10分】标题：有关阶乘的两个问题1 | 时间限制：2秒 | 内存限制：262144K给定一个非负整数N，返回N!结果的末尾为0的数量备注: $1 \leq N \leq 10^{18}$ 示例1输入3输出0 说明3!=6 示例2输入5输出1 说明5!=120 示例3输入1000000000输出249999998 `

完善核心代码语言限制【10分】标题：汉诺塔问题 | 时间限制：2秒 | 内存限制：262144K给定一个整数n，代表汉诺塔游戏中从小到大放置n个圆盘，假设开始所有圆盘都在左边的柱子上，那么用最优的办法把所有圆盘都移动到右边的柱子上的过程，就称为最优移动轨迹。给定一个整型数组arr, 其中只含有1、2和3,代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，a[i]的值代表第i+1个圆盘的位置（a[i]下标从0开始）。比如，arr=[3,3,2,1], 代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，输出arr这种状态是最优移动轨迹中的第几个状态（由于答案可能较大，请输出对 $10^9+7$ 取模后的答案）。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则输出-1。备注: $1 \leq n \leq 2 \times 10^6$ 示例1输入[1,1]输出0 示例2输入[3,3]输出3 `

完善核心代码语言限制【10分】标题：大数乘法 | 时间限制：1秒 | 内存限制：262144K以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。（字符串长度不大于10000，保证字符串仅由'0'~'9'这10种字符组成）示例1输入"11","99"输出"1089" 说明11*99=1089

完善核心代码语言限制【10分】标题：环形链表的约瑟夫问题 | 时间限制：2秒 | 内存限制：262144K据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。 n 表示环形链表的长度， m 表示每次报数到 m 就自杀。备注: $1 \leq n, m \leq 10000$ 示例1输入5,2输出3 `

完善核心代码语言限制【10分】标题：随时找到数据流的中位数 | 时间限制：2秒 | 内存限制：262144K有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。 [要求] \1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。 \2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1) 每行有一个整数opt表示操作类型若opt=1，则接下来有一个整数N表示将N加入到结构中。若opt=2，则表示询问当前所有数的中位数

示例1输入[[1,5],[2],[1,3],[2],[1,6],[2],[1,7],[2]]输出[5,4,5,5.5] 说明第一次查询时结构内的数为：5第二次查询时结构内的数为：3 5第二次查询时结构内的数为：3 5 6第二次查询时结构内的数为：3 5 6 7 示例2输入[[2],[1,1],[2]]输出[-1,1]

完善核心代码语言限制【10分】标题：最长重复子串 | 时间限制：1秒 | 内存限制：262144K一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。给定一个字符串，请编写一个函数，返回其最长的重复字符子串。若不存在任何重复字符子串，则返回0。备注:字符串长度不超过10000，且仅由小写字母组成示例1输入"ababc"输出4 说明abab为最长的重复字符子串，长度为4 示例2输入"abcab"输出0 说明该字符串没有重复字符子串

完善核心代码语言限制【10分】标题：反转部分单向链表 | 时间限制：4秒 | 内存限制：262144K给定一个单链表，在链表中把第 L 个节点到第 R 个节点这一部分进行反转。备注: $1 \leq n \leq 10^6$ 示例1输入[1,2,3,4,5],1,3输出{3,2,1,4,5} `

完善核心代码语言限制【10分】标题：test | 时间限制：1秒 | 内存限制：262144K21312示例1输入[1]输出1

完善核心代码语言限制【10分】标题：反转单向链表 | 时间限制：4秒 | 内存限制：262144K实现反转单向链表的函数。如 1->2->3 反转后变成 3->2->1。备注: $1 \leq n \leq 10^6$ 示例1输入[1,2,3]输出{3,2,1}`

完善核心代码语言限制【10分】标题：分糖果问题进阶问题 | 时间限制：2秒 | 内存限制：262144K一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下： \1. 每个孩子不管得分多少，起码分到一个糖果。 \2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。 \3. 任意两个相邻的孩子之间的得分如果一样多，糖果数必须相同给定一个数组arr代表得分数组，请返回最少需要多少糖果。 [要求] 时间复杂度为, 空间复杂度为备注: $1 \leq N \leq 10^5$ $0 \leq a_i \leq 10^5$ 示例1输入[1,2,2]输出5 说明最优分配方案为1, 2, 2示例2输入[0,1,2,3,3,3,2,2,2,2,2,1,1]输出30 说明最优的分配方案为1 2 3 4 4 4 2 2 2 2 2 1 1`

完善核心代码语言限制【10分】标题：判断数组中所有的数字是否只出现一次 | 时间限制：2秒 | 内存限制：262144K给定一个数组arr，判断数组arr中是否所有的数字都只出现过一次。备注: $1 \leq n \leq 10^5$ 示例1输入[1,2,3]输出true 示例2输入[1,2,1]输出false `

完善核心代码语言限制【10分】标题：可见的山峰对数量 | 时间限制：2秒 | 内存限制：262144K一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时针)。山峰 A 和山峰 B 能够相互看见的条件为: \1. 如果 A 和 B 是同一座山，认为不能相互看见。 \2. 如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。 \3. 如果 A 和 B 是不同的山，并且在环中不相邻，假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰，或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。问题如下：给定一个不含有负数且没有重复值的数组 arr，请问有多少对山峰能够相互看见？每组数据的第一行有三个数字 n, p, m，其中 n 表示山峰的数量，山峰的高度数组等于 1 - p 的 p! 个全排列按字典序排序后的第 m 个全排列的前 n 项。

备注: $1 \leq T \leq 10000$ $1 \leq n \leq p \leq 10^6$ $1 \leq m \leq p!$ 示例1输入[[5,5,2]]输出[7] 说明1-5 的全排列排序后的第二个排列为 1 2 3 5 4`

完善核心代码语言限制【10分】标题：派对的最大快乐值 | 时间限制：2秒 | 内存限制：262144K整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则：1.如果某个员工来了，那么这个员工的所有直接下级都不能来。2.派对的整体快乐值是所有到场员工快乐值的累加。3.你的目标是让派对的整体快乐值尽量大。给定一棵多叉树，请输出派对的最大快乐值。备注: $1 \leq n \leq 500000$ 示例1输入[[1,2],[1,3]],[0,5,1,1],1输出5 `

完善核心代码语言限制【10分】标题：在有序但是含有空的数组中查找字符串 | 时间限制：2秒 | 内存限制：262144K给定一个字符串数组strs[]，在strs中有些位置为null，但在不为null的位置上，其字符串是按照字典序由小到大出现的。在给定一个字符串str，请返回str在strs中出现的最左位置，如果strs中不存在str请输出“-1”。每行包含一个字符串构成，字符串只包含小写字符，如果这一行为“0”，代表该行字符串为空，这n行字符串代表strs。备注: $|srr_i| \leq 10$ $1 \leq n \leq 10^5$ 示例1输入["0","a","0","a","ab","ac","0","b"],"a"输出1 说明在strs中，最左边的“a”在位置1，strs为[null,"a",null,"a","ab","ac",null,"b"]`

完善核心代码语言限制【10分】标题：矩阵的最小路径和 | 时间限制：2秒 | 内存限制：262144K给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。备注: $1 \leq n,m \leq 2000$ $1 \leq arr_{i,j} \leq 100$ 示例1输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]输出12 `

完善核心代码语言限制【10分】标题：将整数字符串转成整数值 | 时间限制：2秒 | 内存限制：262144K给定一个字符串str，如果str符合日常书写的整数形式，并且属于32位整数范围，返回str代表的整数值，否则返回0。备注: $1 \leq |str| \leq 100$ 示例1输入"123"输出123 示例2输入"023"输出0 示例3输入"A13"输出0 示例4输入"2147483648"输出0 `

完善核心代码语言限制【10分】标题：统计和生成所有不同的二叉树(进阶) | 时间限制：2秒 | 内存限制：262144K给出一个整数 n，如果 n < 1，代表空树，否则代表中序遍历的结果为 {1, 2, 3... n}。请输出可能的二叉树结构有多少。答案对1e9+7取模备注: $1 \leq n \leq 10^6$ 示例1输入8输出1430 `

完善核心代码语言限制【10分】标题：判断两个字符串是否互为旋转词 | 时间限制：2秒 | 内存限制：262144K如果一个字符串为str，把字符串的前面任意部分挪到后面形成的字符串交str的旋转词。比如str=“12345”，str的旋转串有“12345”、“45123”等等。给定两个字符串，判断是否为旋转词。备注: $1 \leq |str_1|,|str_2| \leq 10^5$ 示例1输入"abcd","cdab"输出true 示例2输入"ab","aaa"输出false `

完善核心代码语言限制【10分】标题：最大的leftMax与rightMax之差的绝对值 | 时间限制：2秒 | 内存限制：262144K给定一个长度为N(N>1)的整形数组arr, 可以划分成左右两个部分，左部分为arr[0…K]，右部分为arr[K+1…N-1], K可以取值的范围是[0,N-2]。求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值中，最大是多少[要求]时间复杂度为O(n), 空间复杂度为O(n)备注: $\begin{array}{l}1 \leqslant N \leqslant 10^{6} \\ 1 \leqslant a r r_{i} \leqslant 10^{9}\end{array}$ 示例1输入[2,7,3,1,1]输出6 说明当左部分为[2, 7]，右部分为[3, 1, 1]时，左部分中的最大值减去右部分的最大值的绝对值为4,。当左部分为[2, 7, 3]，右部分为[1, 1]时，左部分中的最大值减去右部分最大值的绝对值为6。还有很多划分方案，但最终返回6.`

完善核心代码语言限制【10分】标题：判断两个字符串是否为变形词 | 时间限制：2秒 | 内存限制：262144K给定两个字符串str1和str2，如果str1和str2中出现的字符种类出现的一样且每种字符出现的次数也一样，那么str1和str2互为变形词。请判断str1和str2是否为变形词。备注: $1 \leq |str_1|, |str_2| \leq 10^5$ 示例1输入"123","321"输出true 示例2输入"123","2331"输出false `

完善核心代码语言限制【10分】标题：统计和生成所有不同的二叉树 | 时间限制：2秒 | 内存限制：262144K给出一个整数 n，如果 n < 1，代表空树，否则代表中序遍历的结果为 {1, 2, 3... n}。请输出可能的二叉树结构有多少。答案对1e9+7取模备注: $1 \leq n \leq 10000$ 示例1输入7输出429 `

完善核心代码语言限制【10分】标题：N皇后问题 | 时间限制：2秒 | 内存限制：262144KN皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列也不再同一条斜线上，求给一个整数n，返回n皇后的摆法。备注: $1 \leq n \leq 14$ 示例1输入1输出1 示例2输入8输出92 `

完善核心代码语言限制【10分】标题：数组中的最长连续子序列 | 时间限制：2秒 | 内存限制：262144K给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）备注: $1 \leq n \leq 10^5$ $1 \leq arr_i \leq 10^8$ 示例1输入[100,4,200,1,3,2]输出4 示例2输入[1,1,1]输出1 `

完善核心代码语言限制【10分】标题：最长递增子序列 | 时间限制：2秒 | 内存限制：262144K给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）备注: $n \leq 10^5$ $1 \leq arr_i \leq 10^9$ 示例1输入[2,1,5,3,6,4,8,9,7]输出[1,3,4,8,9] 示例2输入[1,2,8,6,4]输出[1,2,4] 说明其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）`

完善核心代码语言限制【10分】标题：画匠问题 | 时间限制：2秒 | 内存限制：262144K给定一个整型数组arr, 数组中的每个值都为正数，表示完成一幅画作需要的时间，再给定一个整数num，表示画匠的数量，每个画匠只能画连在一起(即数组内连续的一段)的画作。所有画家并行工作，请返回完成所有的画作的最少时间。[要求]时间复杂度为 $O(n \log S)$ (其中S表示所有画作所需时间的和)备注: $1 \leq K \leq N \leq 10^5$ $1 \leq \sum arr_i \leq 10^{18}$ 示例1输入[3,1,4],2输出4 说明最好的分配方式为第一个画匠画3和1，所需时间为4，第二个画匠画4，所需时间为4。因为并行工作，所以最少时间为4，如果分配方式为第一个画匠画3，所需时间为3，第二个画匠画1和4，所需的时间为5，那么最少时间为5，显然没有第一种分配方式好，所以返回4示例2输入[1,1,1,4,3],3输出4 说明最好的分配方式为第一个画匠画前三个1，所需时间为3，第二个画匠画4，所需时间为4，第三个画匠画3，所需时间为3，返回4示例3输入[99,82,44,35,3],2输出164 说明[99] [82 44 35 3]`

完善核心代码语言限制【10分】标题：丢棋子问题 | 时间限制：2秒 | 内存限制：262144K一座大楼有 $0 \sim N$ 层，地面算作第0层，最高的一层为第N层。已知棋子从第0层掉落肯定不会摔碎，从第i层掉落可能会摔碎，也可能不会摔碎( $1 \leqslant i \leqslant N$ )。给定整数N作为楼层数，再给定整数K作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。[要求]时间复杂度在最坏情况下为备注: $1 \leq N,K \leq 10^6$ 示例1输入10,1输出10 说明因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次示例2输入3,2输出2 说明先在2层扔1棵棋子，如果碎了，试第1层，如果没碎，试第3层示例3输入105,2输出14 说明第一个棋子先在14层扔，碎了则用仅存的一个棋子试1~13层若没碎，第一个棋子继续在27层扔，碎了则用仅存的一个棋子试15~26层若没碎，第一个棋子继续在39层扔，碎了则用仅存的一个棋子试28~38层若没碎，第一个棋子继续在50层扔，碎了则用仅存的一个棋子试40~49层若没碎，第一个棋子继续在60层扔，碎了则用仅存的一个棋子试51~59层若没碎，第一个棋子继续在69层扔，碎了则用仅存的一个棋子试61~68层若没碎，第一个棋子继续在77层扔，碎了则用仅存的一个棋子试70~76层若没碎，第一个棋子继续在84层扔，碎了则用仅存的一个棋子试78~83层若没碎，第一个棋子继续在90层扔，碎了则用仅存的一个棋子试85~89层若没碎，第一个棋子继续在95层扔，碎了则用仅存的一个棋子试91~94层若没碎，第一个棋子继续在99层扔，碎了则用仅存的一个棋子试96~98层若没碎，第一个棋子继续在102层扔，碎了则用仅存的一个棋子试100、101层若没碎，第一个棋子继续在104层扔，碎了则用仅存的一个棋子试103层若没碎，第一个棋子继续在105层扔，若到这一步还没碎，那么105便是结果`

完善核心代码语言限制【10分】标题：出现次数的TopK问题 | 时间限制：2秒 | 内存限制：262144K给定String类型的数组strArr，再给定整数k，请严格按照排名顺序打印出次数前k名的字符串。[要求]如果strArr长度为N，时间复杂度请达到 $O(N \log K)$ 输出K行，每行有一个字符串和一个整数（字符串表示）。你需要按照出现出现次数由大到小输出，若出现次数相同时字符串字典序较小的优先输出

备注: $1 \leq N \leq 10^5$ 示例1输入["1","2","3","4"],2输出[["1","1"],["2","1"]] 示例2输入["1","1","2","3"],2输出[["1","2"],["2","1"]] `

完善核心代码语言限制【10分】标题：环形链表的约瑟夫问题(进阶) | 时间限制：2秒 | 内存限制：262144K据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。备注: $1 \leq n,m \leq 5 \times 10^6$ 示例1输入5,2输出3 `

完善核心代码语言限制【10分】标题：在两个长度相等的排序数组中找到上中位数 | 时间限制：2秒 | 内存限制：262144K给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n个数[要求]时间复杂度为，额外空间复杂度为备注: $1 \leq N \leq 10^5$ $0 \leq arr_{1i}, arr_{2i} \leq 10^9$ 示例1输入[1,2,3,4],[3,4,5,6]输出3 说明总共有8个数，上中位数是第4小的数，所以返回3。示例2输入[0,1,2],[3,4,5]输出2 说明总共有6个数，那么上中位数是第3小的数，所以返回2`

完善核心代码语言限制【10分】标题：矩阵乘法 | 时间限制：1秒 | 内存限制：262144K给定两个nn的矩阵A和B，求AB。备注: $n≤500\$ ，初始两个矩阵中每个数 $0≤a_{ij}≤100$ 示例1输入[[1,2],[3,2]],[[3,4],[2,1]]输出[[7,6],[13,14]] `

完善核心代码语言限制【10分】标题：邮局选址问题 | 时间限制：2秒 | 内存限制：262144K一条直线上有居民点，邮局只能建在居民点上。给定一个有序整形数组arr，每个值表示居民点的一维坐标，再给定一个正数num，表示邮局数量。选择num个居民点建立num个邮局，使所有的居民点到邮局的总距离最短，返回最短的总距离。备注: $1 \leq N \leq 3000$ $1 \leq arr_i \leq 10\,000$ 示例1输入[1,2,3,4,5,1000],2输出6 说明第一个邮局建立在3位置，第二个邮局建立在1000位置。那么1位置到邮局的距离为2,2位置到邮局距离为1,3位置到邮局的距离为0，4位置到邮局的距离为1,5位置到邮局的距离为2,1000位置到邮局的距离为0.这种方案下的总距离为6。`

完善核心代码语言限制【10分】标题：信封嵌套问题 | 时间限制：2秒 | 内存限制：262144K给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。备注: $1 \leq n \leq 10^5$ 示例1输入[[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]]输出4 说明从里到外分别是{1，2}，{2，3}，{3，4}，{4，5}。示例2输入[[1,4],[4,1]]输出1 `

完善核心代码语言限制【10分】标题：最长公共子串 | 时间限制：2秒 | 内存限制：262144K给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。备注: $1 \leq |str_1|, |str_2| \leq 5\,000$ 示例1输入"1AB2345CD","12345EF"输出"2345" `

完善核心代码语言限制【10分】标题：寻找峰值 | 时间限制：1秒 | 内存限制：262144K山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。假设 nums[-1] = nums[n] = -∞。示例1输入[2,4,1,2,7,8,4]输出5

完善核心代码语言限制【10分】标题：大数加法 | 时间限制：1秒 | 内存限制：262144K以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。（字符串长度不大于100000，保证字符串仅由'0'~'9'这10种字符组成）示例1输入"1","99"输出"100" 说明1+99=100

完善核心代码语言限制【10分】标题：判断一个点是否在三角形内部 | 时间限制：2秒 | 内存限制：262144K在二维坐标系中，所有的值都是double类型，那么一个三角形可以由3个点来代表，给定3个点代表的三角形，再给定一个点(x, y)，判断(x, y)是否在三角形中备注: $0 \leq |x_1|,|x_2|,|x_3|,|y_1|,|y_2|,|y_3|,|x|,|y| \leq 2 \times 10^{10}$ 示例1输入-1,0,1.5,3.5,2.73,-3.12,2333.33,2333333.33输出false 示例2输入-1,0,1.5,3.5,2.73,-3.12,1.23,0.23输出true `

完善核心代码语言限制【10分】标题：字符串的交错组成 | 时间限制：2秒 | 内存限制：262144K给定三个字符串str1、str2 和aim,如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成. 备注: $1 \leq |s1|, |s2| \leq 5\,000$ $1 \leq |aim| \leq 10\,000$ 示例1输入"AB","12","1A2B"输出true 示例2输入"2019","9102","22001199"输出false `

完善核心代码语言限制【10分】标题：LFU缓存结构设计 | 时间限制：2秒 | 内存限制：262144K一个缓存结构需要实现如下功能。set(key, value)：将记录(key, value)插入该结构get(key)：返回key对应的value值但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；如果调用次数最少的key有多个，上次调用发生最早的key被删除这就是LFU缓存替换算法。实现这个结构，K作为参数给出 [要求]set和get方法的时间复杂度为O(1) 若opt=1，接下来两个整数x, y，表示set(x, y) 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1

对于每个操作2，输出一个答案备注: $1 \leq k \leq n \leq 10^5$ $-2 \times 10^9 \leq x,y \leq 2 \times 10^9$ 示例1输入[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3输出[4,-1] 说明在执行"1 2 4"后，"1 1 1"被删除。因此第二次询问的答案为-1`

完善核心代码语言限制【10分】标题：最小编辑代价 | 时间限制：2秒 | 内存限制：262144K给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。备注: $1 \leq |str_1|, |str_2| \leq 5000$ $1 \leq ic, dc, rc \leq 10000$ 示例1输入"abc","adc",5,3,2输出2 示例2输入"abc","adc",5,3,100输出8 `

完善核心代码语言限制【10分】标题：子数组异或和为0的最多划分 | 时间限制：2秒 | 内存限制：262144K给定一个整型数组arr，其中可能有正有负有零。你可以随意把整个数组切成若干个不相容的子数组，求异或和为0的子数组最多可能有多少个？整数异或和定义：把数组中所有的数异或起来得到的值。示例1输入[3,2,1,9,0,7,0,2,1,3]输出4 说明最优划分：{3,2,1},{9},{0},{7},{0},{2,1,3} 其中{3,2,1},{0},{0},{2,1,3}的异或和为0

完善核心代码语言限制【10分】标题：数组中未出现的最小正整数 | 时间限制：2秒 | 内存限制：262144K给定一个无序数组arr，找到数组中未出现的最小正整数例如arr = [-1, 2, 3, 4]。返回1arr = [1, 2, 3, 4]。返回5[要求]时间复杂度为，空间复杂度为备注: $1 \leq N \leq 10^6$ $|arr_i| \leq 10^9$ 示例1输入[-1,2,3,4]输出1 `

完善核心代码语言限制【10分】标题：输出二叉树的右视图 | 时间限制：1秒 | 内存限制：262144K请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图备注:二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。示例1输入[1,2,4,5,3],[4,2,5,1,3]输出[1,3,5]

完善核心代码语言限制【10分】标题：求最短通路值 | 时间限制：2秒 | 内存限制：262144K用一个整形矩阵matrix表示一个网格，1代表有路，0代表无路，每一个位置只要不越界，都有上下左右四个方向，求从最左上角到右下角的最短通路值例如，matrix为：1 0 1 1 11 0 1 0 11 1 1 0 10 0 0 0 1通路只有一条，由12个1构成，所以返回12[要求]时间复杂度为，空间复杂度为备注: $1 \leq N,M \leq 1000$ 示例1输入["10111","10101","11101","00001"]输出12 `

完善核心代码语言限制【10分】标题：正数数组的最小不可组成和 | 时间限制：2秒 | 内存限制：262144K给定一个正数数组arr，其中所有的值都为整数，以下是最小不可组成和的概念把arr每个子集内的所有元素加起来会出现很多值，其中最小的记为min，最大的记为max在区间[min, max]上，如果有数不可以被arr某一个子集相加得到，那么其中最小的那个数是arr的最小不可组成和在区间[min, max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和请写函数返回正数数组arr的最小不可组成和时间复杂度为 $O(n \times \sum_{i=1}^n arr_i)$ ，额外空间复杂度为 $O(n \times \sum_{i=1}^n arr_i)$ 备注: $1 \leq n \leq 100$ $N < (\sum^N_{i = 1} arr_i) \leq 10^4$ 示例1输入[2,3,9]输出4 示例2输入[1,2,4]输出8 说明3 = 1 + 25 = 1 + 46 = 2 + 47 = 1 + 2 + 4`

完善核心代码语言限制【10分】标题：数字的英文表达和中文表达 | 时间限制：2秒 | 内存限制：262144K给定一个32位整数num，写两个函数分别返回num的英文与中文表达字符串注意: 如果你的程序出现了本地测试争取但题解错误的情况，请检查字符集以及行末空格问题[举例] num=319英文表达字符串为：Three Hundred Nineteen中文表达字符串为：三百一十九num=1014英文表达字符串为：One Thousand, Fourteen中文表达字符串为：一千零十四num=-2147483648英文表达字符串为：Negative, Two Billion, One Hundred Forty Seven Million, Four Hundred Eighty Three Thousand, Six Hundred Forty Eight中文表达字符串为：负二十一亿四千七百四十八万三千六百四十八num=0英文表达字符串为：Zero中文表达字符串为：零示例1输入319输出["Three Hundred Nineteen","三百一十九"] 示例2输入1014输出["One Thousand, Fourteen","一千零十四"] 示例3输入-2147483648输出["Negative, Two Billion, One Hundred Forty Seven Million, Four Hundred Eighty Three Thousand, Six Hundred Forty Eight","负二十一亿四千七百四十八万三千六百四十八"]

完善核心代码语言限制【10分】标题：路径数组变为统计数组 | 时间限制：2秒 | 内存限制：262144K给定一个路径统计数组paths，表示一张图。paths[i]==j代表城市i连向城市j，如果paths[i]==i，则表示i城市是首都，一张图里只会有一个首都且图中除首都指向自己之外不会有环。例如，paths=[9,1,4,9,0,4,8,9,0,1]，代表的图如图9-14所示。由数组表示的图可以知道，城市1是首都，所以距离为0，离首都距离为1的城市只有城市9，离首都距离为2的城市有城市0、3和7，离首都距离为3的城市有城市4和8，离首都距离为4的城市有城市2、5和6。所以距离为0的城市有1座，距离为1的城市有1座，距离为2的城市有3座，距离为3的城市有2座，距离为4的城市有3座。那么统计数组为nums=[1,1,3,2,3,0,0,0,0,0][要求]时间复杂度为，额外空间复杂度为备注: $N \leq 2 \times 10^5$ 示例1输入[9,1,4,9,0,4,8,9,0,1]输出[1,1,3,2,3,0,0,0,0,0] `

完善核心代码语言限制【10分】标题：字符串的转换路径问题 | 时间限制：2秒 | 内存限制：262144K给定两个字符串，记为start和to，再给定一个字符串列表list，list中一定包含to，list中没有重复的字符串。所有的字符串都是小写的。规定start每次只能改变一个字符，最终的目标是彻底变成to，但是每次变成新字符串必须在list中存在。请返回所有的最短的变换路径（按照字典序最小的顺序输出）。如果存在转换的路径，请先输出“YES”，然后按照字典序最小的顺序输出所有路径。如果不存在请输出“NO”。备注: $1 \leq n \leq 5\,000$ $|start|,|to|,|lis_i| = 3$ 示例1输入["cab","acc","cbc","ccc","cac","abb","aab","abb"],"abc","cab"输出["YES","abc -> abb -> aab -> cab","abc -> cbc -> cac -> cab"] `

完善核心代码语言限制【10分】标题：验证IP地址 | 时间限制：1秒 | 内存限制：32768K编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址

IPv4 地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255，用(".")分割。比如，172.16.254.1；同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。

IPv6 地址由8组16进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。

然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。

说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。备注:ip地址的类型，可能为IPv4, IPv6, Neither示例1输入"172.16.254.1"输出"IPv4" 说明这是一个有效的 IPv4 地址, 所以返回 "IPv4"示例2输入"2001:0db8:85a3:0:0:8A2E:0370:7334"输出"IPv6" 说明这是一个有效的 IPv6 地址, 所以返回 "IPv6"示例3输入"256.256.256.256"输出"Neither" 说明这个地址既不是 IPv4 也不是 IPv6 地址

完善核心代码语言限制【10分】标题：0左边必有1的二进制字符串的数量 | 时间限制：2秒 | 内存限制：262144K给定一个整数n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，满足“0”字符的左边必有“1”字符的字符串的数量。由于答案巨大，请对 $2^{29}$ 取模备注: $1 \leq n \leq 2 \times 10^7$ 示例1输入1输出1 说明只有“1”满足示例2输入2输出2 说明只有“10”和“11”满足示例3输入3输出3 说明只有“101”，“110”，“111”满足`

完善核心代码语言限制【10分】标题：公式字符串求值 | 时间限制：2秒 | 内存限制：262144K给定一个字符串str，str表示一个公式，公式里可以有整数，加减乘除和左右括号，返回公式的计算结果（注意：题目中所有运算都是整型运算，向下取整,且保证数据合法，不会出现除0等情况）。备注: $1 \leq |str| \leq 1000$ 示例1输入"48*((70-65)-43)+8*1"输出-1816 示例2输入"3+1*4"输出7 `

完善核心代码语言限制【10分】标题：分糖果问题 | 时间限制：2秒 | 内存限制：262144K一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下： \1. 每个孩子不管得分多少，起码分到一个糖果。 \2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制) 给定一个数组arr代表得分数组，请返回最少需要多少糖果。 [要求] 时间复杂度为On, 空间复杂度为O1备注: $1 \leq N \leq 10^5$ $0 \leq arr_i \leq 10^5$ 示例1输入[1,1,2]输出4 说明最优分配方案为1, 1，2

完善核心代码语言限制【10分】标题：添加最少的字符让字符串变成回文串（2） | 时间限制：2秒 | 内存限制：262144K给定一个字符串str，再给定str的最长回文子序列字符串strlps, 请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。进阶问题比原问题多了一个参数，请做到时间复杂度比原问题的实现低。备注: $1 \leq |str| \leq 5000$ 示例1输入"A1B21C","121"输出"AC1B2B1CA" `

完善核心代码语言限制【10分】标题：排序 | 时间限制：1秒 | 内存限制：262144K给定一个数组，请你编写一个函数，返回该数组排序后的形式。备注: 数组的长度不大于100000，数组中每个数的绝对值不超过 $10^9$ 示例1输入[5,2,3,1,4]输出[1,2,3,4,5] 示例2输入[5,1,6,2,5]输出[1,2,5,5,6]

完善核心代码语言限制【10分】标题：添加最少的字符让字符串变为回文字符串（1） | 时间限制：2秒 | 内存限制：262144K给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。备注: $1 \leq n \leq 5000$ 示例1输入"ABA"输出"ABA" 示例2输入"AB"输出"ABA" `

完善核心代码语言限制【10分】标题：丢棋子问题 | 时间限制：1秒 | 内存限制：262144K 一座大楼有 $0∼N\$ 层，地面算作第0层，最高的一层为第 $N\$ 层。已知棋子从第0层掉落肯定不会摔碎，从第 $i\$ 层掉落可能会摔碎，也可能不会摔碎 $(1⩽i⩽N)\$ 。给定整数 $N\$ 作为楼层数，再给定整数 $K\$ 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。

备注: $0≤N,K≤10^6$ 示例1输入10,1输出10 说明因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次 示例2输入3,2输出2 说明先在2层扔1棵棋子，如果碎了，试第1层，如果没碎，试第3层 示例3输入105,2输出14 说明第一个棋子先在14层扔，碎了则用仅存的一个棋子试1~13层若没碎，第一个棋子继续在27层扔，碎了则用仅存的一个棋子试15~26层若没碎，第一个棋子继续在39层扔，碎了则用仅存的一个棋子试28~38层若没碎，第一个棋子继续在50层扔，碎了则用仅存的一个棋子试40~49层若没碎，第一个棋子继续在60层扔，碎了则用仅存的一个棋子试51~59层若没碎，第一个棋子继续在69层扔，碎了则用仅存的一个棋子试61~68层若没碎，第一个棋子继续在77层扔，碎了则用仅存的一个棋子试70~76层若没碎，第一个棋子继续在84层扔，碎了则用仅存的一个棋子试78~83层若没碎，第一个棋子继续在90层扔，碎了则用仅存的一个棋子试85~89层若没碎，第一个棋子继续在95层扔，碎了则用仅存的一个棋子试91~94层若没碎，第一个棋子继续在99层扔，碎了则用仅存的一个棋子试96~98层若没碎，第一个棋子继续在102层扔，碎了则用仅存的一个棋子试100、101层若没碎，第一个棋子继续在104层扔，碎了则用仅存的一个棋子试103层若没碎，第一个棋子继续在105层扔，若到这一步还没碎，那么105便是结果 `

完善核心代码语言限制【10分】标题：字符串匹配问题 | 时间限制：2秒 | 内存限制：262144K对于字符串str，其中绝对不含有字符’.’和‘’。再给定字符串exp，其中可以含有’.’或’‘’，’’字符不能是exp的首字符，并且任意两个’‘字符不相邻。exp中的’.’代表任何一个字符，exp中的’**’表示’*‘的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配(注意：输入的数据不保证合法，但只含小写字母和‘.’和‘’)。备注: $1 \leq |str|, |exp| \leq 300$ 示例1输入"abc","abc"输出true

完善核心代码语言限制【10分】标题：最短包含字符串的长度 | 时间限制：2秒 | 内存限制：262144K给定字符串str1和str2，求str1的字串中含有str2所有字符的最小字符串长度，如果不存在请输出0。备注: $1 \leq |str1| , |str2| \leq 10^5$ 示例1输入"abcde","ac"输出3 说明“abc”中包含“ac”，且“abc”是所有满足条件中最小的。

完善核心代码语言限制【10分】标题：找到指定类型的新类型字符 | 时间限制：2秒 | 内存限制：262144K新类型字符的定义如下: 1.新类型字符是长度为1或者2的字符串。 \2. 表现形式可以仅是小写字母，例如，"e"; 也可以是大写字母+小写字母，例如，"Ab";还可以是大写字母+大写字母，例如，"DC"。现在给定一个字符串str, str 一定是若干新类型字符正确组合的结果。比如"eaCCBi"，由新类型字符"e"、"a”、"CC"和"Bi"拼成。再给定一个整数k，代表str中的位置。请返回第k个位置的新类型字符。备注: $1 \leq |str| \leq 10^5$ 示例1输入"aaABCDEcBCg",7输出"Ec"

100

完善核心代码语言限制【10分】标题：拼接所有的字符串产生字典序最小的字符串 | 时间限制：2秒 | 内存限制：262144K给定一个字符串的数组strs，请找到一种拼接顺序，使得所有的字符串拼接起来组成的字符串是所有可能性中字典序最小的，并返回这个字符串。备注: $1 \leq n \leq 10^5$

$1 \leq |strs_i| \leq 10$ 示例1输入["abc","de"]输出"abcde"

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

问答题

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

参考答案：

编程题

相关文章：