58同城后端笔试复盘

下图是一个B+树的结构,做 range操作(26,35),总共需要查找()次

A. 8

B. 9

C. 10

D. 11

为什么我感觉是6。还是不知道选什么。

查找26、35在第一个磁盘块,各查找了1次;在第2个磁盘块查找26,第三个磁盘块查找35,各1次;在第7个磁盘块查找26,在第9块磁盘块查找35;一共6次啊。之后用B+树的叶子节点链表遍历,不用查找了吧。

机器间传输数据,发送端发送2096字节的数据,接收端会出现丢失部分数据情兄(传输协议使用:UDP),引起这问题最大可能原因()

A. 网络环境问题

B. 接收端网卡问题

C. 数据长度大于接收端缓冲区

D. 网络传输分包

C.
虽然UDP的报文长度最大可以达到64 kb,但是当报文过大时,稳定性会大大减弱。这是因为当报文过大时会被分割,使得每个分割块的长度小于MTU。以太网的MTU通常是1500 bytes,其他一些诸如拨号连接的网络MTU值为1280 bytes。 网络传输分包是要分割的,但不能分得太大。
发送的包较大,超过接受者缓存导致丢包:包超过mtu size数倍,几个大的udp包可能会超过接收者的缓冲,导致丢包。这种情况可以设置socket接收缓冲。调整接收缓冲设置的大小。

Socket 读缓冲区、写缓冲区 默认大小122k好像。通过以下配置修改:
/proc/sys/net/core/rmem_max
/proc/sys/net/core/wmem_max

下列哪种方法不能用来减小过拟合?

A. 更少的训练数据

B. L1正则化

C. L2正则化

D. 减小模型的复杂度

A.
减少过拟合的方法; https://www.zhihu.com/question/59201590

  • 获取更多数据
  • 使用合适的模型
  • 结合多种模型
  • 贝叶斯方法
假设电文A,B,C,D,E的权值为5,6,9,10,15则报文 AECDB的哈夫曼编码为()

A. 101001110010

B. 100110001101

C. 110011011010

D. 100101011010

B. A,B同为3个字符表示,哈夫曼编码必然前2个字符相同。

下边IPv6地址中写法正确的是?

A. fe80:0:b4f9:6c6f:b658:a4aa

B. fe80:0:0:0:b4u9:6c6f:b658:d4aa

C. fe80::04f9:6c6f:b658:d4aa

D. fe80::b4f9:6c6f:b658::d4aa

C. B中有u

IPv6地址为128位长,但通常写作8组,每组为四个十六进制数的形式。
如果四个数字都是零,可以被省略。
如果因为省略而出现了两个以上的冒号的话,可以压缩为一个,但这种零压缩在地址中只能出现一次

如果这个地址实际上是IPv4的地址,后32位可以用10进制数表示;因此: ffff:192.168.89.9 等价于 ::ffff:c0a8:5909, 但不等价于 ::192.168.89.9 和 ::c0a8:5909。
ffff:1.2.3.4格式叫做IPv4映像地址,是不建议使用的。而::1.2.3.4格式叫做IPv4一致地址(这也是混合符号(IPv4-compatible address)表示)。

以下哪项是对单核cpu执行程序时间的正确描述:

A. 程序CPU执行时间=指令数 × 时钟周期时间

B. 程序CPU执行时间=CPU时钟周期数 × 单条指令平均执行周期

C. 程序CPU执行时间=指令数 × 单条指令平均执行周期 × 时钟周期时间

D. 程序CPU执行时间=CPU时钟周期数 × 指令数 × 单条指令平均执行周期×时钟周期时间

C.

程序CPU执行时间=CPU时钟周期数*时钟周期时间
=指令数*单条指令平均执行周期*时钟周期时间

以下关于进程调度算法的描述中,错误的是

A. 优先级调度算法会引起进程的饥饿问题

B. 短作业优先调度算法的平均等待时间最少

C. 当系统最长响应时间一定时,时间片轮转调度算法的时间片大小与系统允许的最大进程数成正比

D. 高响应比优先调度算法综合考虑了进程等待时间和执行时间

C.

响应比 =(等待时间+要求服务时间)/ 要求服务时间,
即RR=(w+s)/s=1+w/s,因此响应比一定是大于1的。

采用快排对3 7 6 9 10 12 1进行排序( 第一个为基准数 ),第1轮探测结果为

A. 1 3 6 9 10 12 7

B. 9 1 6 3 10 12 7

C. 3 1 6 9 10 12 7

D. 1 3 6 7 9 10 12

A.

连接平台通过号码池来管理虚拟号码,如果每个号池管理15个号码,将有7个号码池每个号码池多2个号码;如果每个号码池管理12个号码,则会有11码没有号码池管理;如果每个号码池管理18个号码,将有一个号码池差1个号码。这批虚拟号码数量在500-600之间,这批虛拟号码有多少个()

A. 559

B. 539

C. 540

D. 541

运维同学通知我们台服务器(inux)存放日志的磁盘分区快满了,因此我们决定删除一些日志。但该服务器部醫了多个服务,我们想优先删除磁盘占用量比较大的服务的日志。已知所有服务都将日志打印到 /opt/scf/log/{服务名}/{服务名}.log,请帮忙选出一个命令来查看各个服务日志占用的空间

A. df -h /opt/scf/log

B. df -h /opt/scf/log/*

C. du -sh /opt/scf/log

D. du -sh /opt/scf/log/*

C.

du 本身就能递归显示到文件,其实 du -h /opt/scf/log 就可以了;
-s, --summarize display only a total for each argument,对每项大小总结,目录算一项。失去了递归显示,反而要加上通配符
du -sh /opt/scf/log ,就只显示 /opt/scf/log 大小
所以, du -sh /opt/scf/log/* 把每个服务名目录总结大小

现有长度分别为1,2,3,4,5,6,7,8,9,10的木棍各根,现要求用这些木棍(可以多根组合,但组合A=B=C=D,ABCD、ACDB等重排列算一种正方形)拼成一个正方形,可以有几种拼法

A. 18种

B. 19种

C. 20种

D. 15种

现有t表存在索引:idx a b c(a,b,c)下面那些SQL会被索引?

A. SELECT * FROM tI WHERE a!=1:

B. SELECT * FROM t1 WHERE b=1 AND a=4;

C. SELECT * FROM t1 WHERE b=2 OR c=3;

D. SELECT * FROM t1 WHERE a=1 AND b=2 AND c=3;

D.

or连接索引失效。!=不能用于索引项,也会失效。
最左前缀匹配原则,指的是查询从索引的最左前列开始并且不跳过索引中的列

以下关于web攻击手段错误的是

A. SQL注入攻击通过将任意SQL代码插入数据库查询,使攻击者能够完全控制web应用程序后面的数据库服务器

B. 对进入数据库的特殊字符等进行转义处理可有效预防SQL注入攻击

C. XSS攻击的主要方法是发送大量请求使服务器痒痪

D. XSS攻击可分为存储型XSS和反射型XSS两大类

C.

XSS攻击通常指的是通过利用网页开发时留下的漏洞,通过巧妙的方法注入恶意指令代码到网页,使用户加载并执行攻击者恶意制造的网页程序。 这些恶意网页程序通常是JavaScript

  • 存储型XSS,持久化,代码是存储在服务器中的,如在个人信息或发表文章等地方,加入代码,如果没有过滤或过滤不严,那么这些代码将储存到服务器中,用户访问该页面的时候触发代码执行。这种XSS比较危险,容易造成蠕虫,盗窃cookie等
  • 反射型XSS,非持久化,需要欺骗用户自己去点击链接才能触发XSS代码(服务器中没有这样的页面和内容),一般容易出现在搜索页面。
游戏中升级一把武器,假定每使用一个石头,有50%的概率会成功让武器升级,50%的概率会失败。如果武器等级大于等于5的话,升级失败会使得武器降1级。如果武器的级数小于5的话,失败没有效果。问:期望用多少个石头可以让一把初始为1级的武器升到级?()

A. 20

B. 26

C. 36

D. 48

在采用LRU算法的系统中,程序P的某次调用依次问8、7、6、5、4、3、2、1、2、3页。假设分配给P的最大内存是4页。则在该次调用中的缓存命中率

A. 0.6

B. 0.5

C. 0.4

D. 0.2

D.

第1道

给定个字符串,字符串是有序的整数集合,逗号相连,移除相同的数字,使每个数字只出现一次,输出最终的数字个数

输入描述:

1,2,2

输出描述:

2

示例1

输入:

0,0,1,1,1,2,2,3,3,4

输出:

5
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.next();
        sc.close();
        String[] splits = line.split(",");
        HashSet<Integer> s = new HashSet<>();
        for (String split : splits) {
            s.add(Integer.parseInt(split));
        }
        System.out.println(s.size());
    }
}

第2道

幼儿园老师给她班上的孩子分饼干。所有的孩子都坐在-条线上,每个孩子都根据在课堂上的表现得到评分。老师必须给每个孩子至少1个饼干。如果两个孩子坐在起,那么评分较高的孩子必须得到更多的饼干(孩子必须左右都比较)。输出老师购买的饼干总数的最小值。例如,假设她的学生的评分为[3,6,3,5,6,2]。她给学生饼干的数量如下: [1,2,1,2,3,1] 。她必须购买至少10个饼干

输入描述:

假设学生评分为:[1,2,3],则输入应为:
3
1
2
3
第1行为数组元素大小,2至n+1行为数组元素(每行一个)

输出描述:

可分配最小值

示例1

输入:

6
3
6
3
5
6
2

输出:

10

示例2

输入:

10
1
2
4
2
6
1
7
8
9
2
1

输出:

19

孩子数量为10,所以饼干数为1+2+1+2+1+2+3+4+2+1=19
(最后一个孩子获得一个饼干,但是他比前一个孩子评分小,所以前一个孩子饼干数加一)

没有通过所有测试用例,事后修改,不知道对不对

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        List<Integer> list = new ArrayList<>();
        int min = Integer.MAX_VALUE, minIdx = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (a[i] < min) {
                min = a[i];
                minIdx = i;
            }
        }
        for (int i = 0; i < n; i++) {
            if (a[i] == a[minIdx])
                list.add(i);
        }
        sc.close();
        Arrays.fill(b, 0);
        b[minIdx] = 1;
        int sum = 0;
        for (int i = minIdx - 1; i >= 0; i--) {
            if (a[i] < a[i + 1]) {
                b[i] = b[i + 1] - 1;
                if (b[i] == 0) {
                    for (int j = i; j < minIdx; j++) {
                        b[j] = b[j] + 1;
                    }
                }
            } else if (a[i] > a[i + 1]) {
                b[i] = b[i + 1] + 1;
            } else {
                b[i] = b[i + 1];
            }
        }
        for (int i = minIdx + 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                b[i] = b[i - 1] - 1;
                if (b[i] == 0) {
                    for (int j = i; j > minIdx; j--) {
                        b[j] = b[j] + 1;
                    }
                }
            } else if (a[i] > a[i - 1]) {
                b[i] = b[i - 1] + 1;
            } else {
                b[i] = b[i - 1];
            }
        }
        // fix
        if (b[n - 1] != 1) {
            int delta = b[n - 1] - 1;
            for (int i = n - 1; i > 0; i--) {
                if (a[i] > a[i - 1]) break;
                if (a[i] < a[i - 1]) {
                    b[i] = b[i] - delta;
                }
            }
        }
        if (b[0] != 1) {
            int delta = b[0] - 1;
            for (int i = 0; i < n; i++) {
                if (a[i] > a[i + 1]) break;
                if (a[i] < a[i + 1]) {
                    b[i] = b[i] - delta;
                }
            }
        }
        for (int i = 0; i < n; i++) sum += b[i];
        System.out.println(sum);
    }
}

第3道

现有一个地图,由横线与竖线组成(参考围棋棋盘),且两点之间有行走距离起点为左上角,终点为右下角在地图上,每次行走只能沿线移动到临近的点,并累加路径计算一个人从地图的起点走到终点的最小路径为多少

输入描述:

mxn地图表示如下:
3
3
1 3 4
2 1 2
4 3 1
其中m=3,n=3表示3*3的矩阵
行走路径为:下>右>右>下

输出描述:

路径总长:1+2+1+2+1=7

示例1

输入:

1
2
1 2

输出:

3

示例2

输入:

2
3
9 8 6
2 3 7

输出:

21

把i写成了 j , 行复制误大事,事后发现懊悔不已,我竟然犯这种错。
算了过去了。

搜索解题,会有测试用例超时。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int ans = Integer.MAX_VALUE;
    static int m;
    static int n;
    static int[][] a;
    static int[][] d = {{1, 0}, {0, 1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        a = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();
        dfs(0, 0, 0);
        System.out.println(ans);
    }

    private static void dfs(int x, int y, int sum) {
        if (x < 0 || y < 0 || x >= m || y >= n) return;
        if (x == m - 1 && y == n - 1) {
            sum += a[m - 1][n - 1];
            ans = Math.min(ans, sum);
            return;
        }
        for (int i = 0; i < d.length; i++) {
            int posx = x + d[i][0];
            int posy = y + d[i][1];
            dfs(posx, posy, sum + a[x][y]);
        }
    }
}

这道题是一道经典的动态规划题。

小米笔试题复盘

下面有关TCP连接建立和释放过程中的状态,描述正确的是()?

A. 连接释放过程中,关闭发起方从 TIME_WAIT状态到 CLOSED状态需要等待1个MSL

B. 连接建立过程中客户端在 SYN_SENT状态收到服务器的SYN+ACK包并发送确认ACK包后,客户端即进入 ESTABLISHED状态

C. 连接释放过程中,处于 CLOSE WAIT状态的一方仍可以继续发送数据

D. 连接建立过程中服务器在 SYN_RCVD状态收到客户端的确认ACK包后,服务器即进入 ESTABLISHED状态。

BCD。A. 2个MSL。

在—个真实的计算机系统中,系统内的资源会新添、损坏或被替换,系统内的进程会新建和退岀。如果用银行家算法控制死锁,下面哪些变化是安全的(不会导致死锁)?()

A. 增加一个进程的Max(进程需要更多的资源,超过所允许给予的资源)

B. 减少可用资源(资源被从系统中永久性地移出)

C. 减少一个进程的Max(进程不再需要那么多资源)

D. 增加可用资源(新的资源被添加到系统)

CD

UNIQUE惟一索引的作用是()

A. 保证惟一索引不能被删除

B. 保证参加惟一索引的各列,不得再参加其他的索引

C. 保证各行在该索引上的值不得为NULL

D. 保证各行在该索引上的值都不得重复

D. 顺便写点最近复习的知识点,唯一索引和普通索引的区别是唯一索引有唯一性约束,也是因为这点,在对读取到内存中的数据页,普通索引可以使用change_buffer缓存,后期再写回磁盘,而唯一索引不行。

下面关于有向无环图说法错误的是?()

A. 有向无环图至少有一个顶点入度为0

B. 有向无环图至少有一个拓扑排序

C. 有向无环图可以转换成树

D. 有向无环图至少有一个顶点出度为0

C. 有向无环图不一定可以转换成树。一个节点可能有多个父节点。

在下列序列中,若以最后一个数字为基准进行快速排序(升序),第一趟数字被移动次数最多的是()

A. 52,40,45,102,110,106,98,120

B. 110,106,102,45,40,120,98,52

C. 102,106,110,120,52,45,40,98

D. 102,106,98,52,40,45,120,110

C

从尚末排序的N名学生的考试分数中挑出排名第K的分数,平均时间复杂度最优可以达到多少?()

A. O(N*K)

B. O(N)

C. O(N^2)

D. O(N*logN)

B. 一开始直观的想法是O(N*logK),维护一个堆。实际上有O(N)的算法——BFPRT算法。

下列关于设计模式说法错误的是()

A. 用饿汉方式实现的单例模式是不能够被继承的

B. 装饰器模式在实现过程中一般不会更改被封装对象的接口定义

C. 简单工厂模式可以实现按客户端条件动态创建对象的效果

D. 适配器模式为客户端提供了与被适配对象接口定义相同的适配对象

D.
A 中饿单例模式和懒单例模式构造方法都是私有的,因而是不能被继承的,虽然有些单例模式可以被继承(如登记式模式) 。
D 中“被适配对象”是Adapter,适配器是Adaptee,Adaptee是提供给客户端调用的适配器。 Adaptee 具体适配Adapter的过程,有类适配器和对象适配器。
- 对象适配器实现目标类的接口,并依赖于源类(有源类的引用)。
- 类适配器继承自源类,并实现目标类的接口。

适配器模式类图
关于排序算法,以下的哪些叙述是正确的?

A. 快速排序的最坏时间复杂度为O(nlog(n)),它是一个不稳定排序

B. 堆排序的最坏时间复杂度为 O(nlog(n)) ,它不需要额外存储空间来完成排序

C. 归并排序的时间复杂度为 O(nlog(n)) ,它需要O(n)的额外存储空间来完成排序

D. 冒泡排序的时间复杂度为O(n^2),它是一个不稳定排序

ABC. D 中冒泡是稳定的。

1,2,3,4,5五个数字,能组成多少种不同的二叉搜索树的结构?()

A. 36

B. 42

C. 40

D. 32

卡特兰数h(5)=42。

类似题目:

  • 对于一个无限大的栈,一共n个元素,请问有几种合法的入栈出栈形式?
    • h(n)
  • 矩阵连乘:P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?
    • h(n-1)
  • n个结点可构造多少个不同的二叉树?
    • h(n)
  • 凸多边形三角划分。 在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数?
    • h(n-2)
  • 给定n对括号,求括号正确配对的字符串数?
    • h(n)
  • 在图书馆一共6个人在排队,3个在还《面试宝典》一书,3个在借《面试宝典》一书,图书馆此时没有《面试宝典》了,求他们排队的总数?
    • f(2n)= h(n)n!n!
  • 高矮排队问题。 12(2n)个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
    • h(n)

其他题目 https://blog.csdn.net/u011489043/article/details/77884434

以下通不过编译的是:
A.abstract class Something {
private abstract String doSomething();
}
B.abstract class Name {
private String name;
public abstract boolean isSomething(String name){};
}
C.public class Something{
void doSomething() {
private String s="";
int l=s.length();
}
}
D.public class Something{
public static void main(String[] args) {
Thing t = new Thing();
new Something().addOne(t);
}

private void addOne(final Thing t) {
t.i++;
}
}
class Thing {
public int i;
}

ABC. A 中Illegal combination of modifiers: 'abstract' and 'private'。

编译程序不仅包含词法分析、语法分析、中间代码生成、目标代码生成,还包括()

A. 源代码优化

B. 代码优化

C. 表格管理

D. 出错处理

BCD. 啊啊啊,不包括源代码优化啊,一股脑都选了。我怎么记得是有源代码优化阶段的。

源码 ->(扫描)-> 单词 ( 词法分析 ) -> 标记 ->(语法分析)-> 语法树 ->(语义分析)-> 标识语义后的语法树 ->(源码优化)-> 中间代码生成 ->(代码优化)-> 目标机器代码 ->(目标代码优化)-> 最终目标代码

编译的各个阶段
在X86平台上,C语言函数调用时,通过以下哪种方式传递参数?

A. 变量地址

B. 内存

C. 寄存器

D. 堆栈

C. 人家題目问的不是传值还是传地址。 https://www.cnblogs.com/clover-toeic/p/3755401.html

搞笑我太难了 上辈子我一定是道数学题
我太难了x1

函数调用过程通常使用堆栈实现,每个用户态进程对应一个调用栈结构(call stack)。编译器使用堆栈传递函数参数、保存返回地址、临时保存寄存器原有值(即函数调用的上下文)以备恢复以及存储本地局部变量。

不同处理器和编译器的堆栈布局、函数调用方法都可能不同,但堆栈的基本概念是一样的。

注:x86平台将参数压入调用栈中。而x86_64平台具有16个通用64位寄存器,故调用函数时前6个参数通常由寄存器传递,其余参数才通过栈传递。

在 Python3中,对于字符编码叙述正确的是

A. str编码为utf-8,byte无编码

B. str编码为utf-16,byte为utf-8

C. str为 unicode字符(内部编码ut-16),byte编码为utf-8

D. str为 unicode字符(内部编码utf-16),byte无编码

A.
Python3 把系统默认编码设置为 UTF-8 ; 文本字符和二进制数据区分得更清晰,分别用 str 和 bytes 表示。文本字符全部用 str 类型表示,str 能表示 Unicode 字符集中所有字符,而二进制字节数据用一种全新的数据类型,用 bytes 来表示。
Python3 中,在字符引号前加‘b’,明确表示这是一个 bytes 类型的对象,实际上它就是一组二进制字节序列组成的数据,bytes 类型可以是 ASCII范围内的字符和其它十六进制形式的字符数据

  • Unicode 是「字符集」
  • UTF-8 是「编码规则」
下面STL容器中,哪些是有序的()

A. stack

B. map

C. set

D. vector

BC. STL中的set和map是有序容器,基于红黑树。

编译程序目标代码生成阶段主要任务是

A. 把中间代码变换成依赖具体机器的目标代码

B. 把高级语言翻译成机器语言

C. 把高级语言翻译成汇编语言

D. 把汇编语言翻译成机器语言

A. 目标代码生成阶段目标代码生成是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令。

关于C++,以下说法错误的是()

A. 变量或函数的定义尽量不要放在头文件中。因为头文件包含在多个源文件中,所以不应该含有变量或函数的定义

B. extern double pi=3.14此声明没有分配及初始化存储空间

C. 类不是在类定义里定义数据成员时初始化数据成员,而是通过构造函数控制初始化。

D. const对象可以定义在头文件中

B.

都好久不写C++工程了,面Java怎么C++、Python都考得到。

搞笑我太难了 上辈子我一定是道数学题
我太难了x2

A 中头文件中不可以放变量的定义!!!一般情况下头文件中只放变量的声明,因为头文件要被其他文件包含(即#include),如果把定义放到头文件的话,就不能避免多次定义变量,C++不允许多次定义变量,一个程序中对指定变量的定义只有一次,声明可以无数次。

B 中 声明仅仅是将变量的名字和类型告诉编译器,并不分配存储空间。 定义则会为其分配存储空间,也可能会为变量赋一个初始值。 extern double pi = 3.14,此时对extern变量赋予初值,就变成定义了。

C++ 初始化类的三个数据成员:const成员、static成员、const static成员
1、const成员:只能在构造函数后的初始化列表中初始化
2、static成员:在类外 初始化 ,且不加static修饰
3、const static成员:类只有唯一一份拷贝,且数值不能改变。因此,可以在类中声明处初始化,也可以像static在类外初始化

D 中对于头文件不应该含有定义这一规则,有三个例外:头文件中可以定义、值在编译时就已知道的const对象(数组的大小可以用const int型变量定义,这在C中是不行的),和inline函数
- 类定义内部的成员可以是声明,类定义和类内部成员的定义不是一回事,可以不同步进行,也”不建议“类定义时定义类内部函数。
- const 变量默认是定义该变量的文件的局部变量。当我们在头文件中定义了 const 变量后,每个包含该头文件的源文件都有了自己的 const 变量,其名称和值都一样。 如果 const 变量不是用常量表达式初始化,那么它就不应该在头文件中定义(若不初始化const变量,这个const变量有什么用呢?)。相反,和其他的变量一样,该 const 变量应该在一个源文件中定义并初始化。应在头文件中为它添加 extern 声明,以使其能被多个文件共享。

下面关于虛函数的描述中,正确的是()

A. 虚函数必须是非静态成员函数。

B. 对于虚函数,virtual关键字只能出现在类定义中的函数原型声明中,不能出现在类体外的函数定义中

C. 对于多态类,应该将构造函数和析构函数都声明为虚函数。

D. 根据类型兼容规则,基类指针(或引用)可以指向其派生类的实例,但在非虚函数的情况下,通过基类指针(或引用)却只能调用基类的函数成员,无法调用其所指实例派生类的函数成员。

ABD.
C 中 构造函数 不能设置为虚函数。
D 中函数覆盖,基类中成员函数要用virtual修饰为虚函数。

C++中,声明 int const** const * const x表示是什么类型?

A. 个 const指针,指向一个 const指针,指向一个普通指针,指向一个 const int

B. 一个 const数组,每个成员都是一个 const二维int类型 consta数组B.

C. 一个 const指针,指向一个 const双层指针,指向一个int

D. 一个 const指针,指向一个 const指针,指向一个 const int,它存着一个指针

搞笑我太难了 上辈子我一定是道数学题
我太难了x3
const int a
int const a
const int *a
int *const a
  • int const a 和 const int a均表示常量类型a
  • const int *a,常量指针,其中a是指向const int的变量指针,a的值可以变化
  • int *const a,指针常量,表示a是指向int变量的指针,但a的值不能发生变化。
int *p[10];
int (*p)[10];
int *p(int)
int (*p)(int)
  • int *p[10]表示指针数组,是一个数组变量,大小为10,数组内的元素指向int类型的指针变量;
  • int (*p)[10]表示数组指针,是指针类型,指向的是一个int类型的数组,这个数组的大小是10;
  • int *p(int)是函数声明,函数名是p,参数类型是int,返回值int*
  • int (*p)(int)是函数指针,是指针类型,指向的具有int参数,返回值是int的函数
 不属于jvm invoke 指令的是

A. invokespecial

B. invokemethod

C. invokevirtual

D. invokedynamic

B.

  • invokestatic : 调用静态方法
  • invokespecial : 调用实例构造器方法, 私有方法和父类方法
  • invokevirtual : 调用虚方法
  • invokeinterface : 调用接口方法
  • invokedynamic : 动态调用

第1道

在某个存储介质以如下形式保存一棵二叉树1(2(3,4(,5),6(7,))
上述序列表示的二叉树如下

观察后可以发现,每个节点的格式为X,X可以为空
或者
X(Y,Z),其中X不为空
请编写程序将以上述格式输入的二叉树输出为中序遍历顺序

输入描述:

上述格式表示的二叉树字符串,用字符1~9表示每个二叉树的每个节点,字符可以重复使用

输出描述:

二又树的中序遍历结果

示例1

输入:

1(2(3,4(,5),6(7,))

输出:

3245176

这道题完全模拟生成二叉树,过不了所有测试用例。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static class Node {
        int num;
        Node left, right;

        public Node(int num) {
            this.num = num;
        }
    }

    /*请完成下面这个函数,实现题目要求的功能
    当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^
    ******************************开始写代码******************************/
    static String solution(String input) {
        char[] line = input.toCharArray();
        Node root = parse(line, 0);
        List<Integer> ans = new ArrayList<>();
        midTrace(root, ans);
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < ans.size(); i++)
            sb.append(ans.get(i));
        return sb.toString();
    }

    private static void midTrace(Node root, List<Integer> ans) {
        if (root == null) return;
        midTrace(root.left, ans);
        ans.add(root.num);
        midTrace(root.right, ans);
    }

    // 1(2(3,4(,5)),6(7,))
    // 1(,6(7,))
    private static Node parse(char[] line, int start) {
        if (start >= line.length) return null;
        if (line[start] == ')') return null;
        Node node = new Node(line[start] - '0');
        if (line[start + 1] == '(') {
            if (line[start + 2] != ',') {
                node.left = parse(line, start + 2);
                if (line[start + 3] == '(') {
                    int cnt = 0;
                    int idx = start + 3;
                    while (idx < line.length && !(cnt == 0 && line[idx] == ',')) {
                        if (line[idx] == '(')
                            cnt++;
                        else if (line[idx] == ')')
                            cnt--;

                        idx++;
                    }
                    node.right = parse(line, idx + 1);
                } else if (line[start + 3] == ',') {
                    node.right = parse(line, start + 4);
                }
            } else {
                node.right = parse(line, start + 3);
            }
        } else if (line[start + 1] == ',') {
            return node;
        }
        return node;
    }

    /******************************结束写代码******************************/


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String res;

        String _input;
        try {
            _input = in.nextLine();
        } catch (Exception e) {
            _input = null;
        }

        res = solution(_input);
        System.out.println(res);
    }
}

考虑用栈来完成中序遍历,非递归中序遍历。

第2道

小米之家有很多米粉喜欢的产品,产品种类很多,价格也不同。比如某签字笔1元,某充电宝79元,某电池1元,某电视1999元等假设库存不限,小明去小米之家买东西,要用光N元预算的钱,请问他最少能买几件产品?

输入描述:

第1行为产品种类数
接下来的每行为每种产品的价格
最后一行为预算金额

输出描述:

能买到的最少的产品的件数,无法没有匹配的返回1

示例1

输入:

2
500
1
1000

输出:

2

这题是完全背包问题改造。

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        int V = sc.nextInt();
        int[] dp = new int[V + 1];
        Arrays.fill(dp, V);
        dp[0] = 0;
        sc.close();
        for (int i = 1; i <= n; i++) {
            for (int v = w[i]; v <= V; v++) {
                dp[v] = Math.min(dp[v - w[i]] + 1, dp[v]);
            }
        }
        System.out.println(dp[V]);
    }
}

我只想给自己一个交代,无论成功还是失败,无论及时还是延迟。

网易互娱笔试-初级游戏研发工程师-复盘

第1道

如果把一个数的各位数字反向排列所得的数和原数一样,则称这个数为回文数。给定一个十迸制的正整数X,判断X在二进制下(去掉前导0)是否是回文数。如的二进制为1011。

输入描述:

输入的第一行是一个正整数(0<T<=100),表示有组测试数据。对于每一个测试数据包含一个正整数x(0<X<=
10000000)

输出描述:

对于每一组测试样例,如果x在二进制下是回文数则输出YES,否则输NO

示例1

输入:

3
1
4
7

输出:

YES
NO
YES

Integer.toBinaryString() API 很好用

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            Integer t = sc.nextInt();
            String binaryString = Integer.toBinaryString(t);
            char[] s = binaryString.toCharArray();
            boolean flag = true;
            for (int l = 0, r = binaryString.length() - 1; l < r; l++, r--) {
                if (s[l] != s[r]) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

第2道

给定一棵二叉树,每个结点有一个正整数权值。若棵二叉树,每一层的结点权值和都严格小于下一层的结点权值和,则称这棵二叉树为递增二叉树。
现在给你一棵二叉树,你需要判断其是不是一棵递增二叉树。

输入描述:

输入的第一行是一个正整数(0<T<=50)。接下来有T组样例对于每组样例,输入的第一行是一个正整数N,表示树的结点个数(0<N<=1000,结点编号为0到N-1):按下来是N行,第k行表示编号为k的结点,输入格式为:VALUE LEFT RIGHT,其中VALUE表示其权值,是一个不超过5000的自然数;LEFT和RIGHT分别表示该结点的左子编号和右子编号。如果其不存在左子或右子,则工LEFT或R工RIGHT为-1.

输出描述:

对于每一组样例,翰出一个字符串。如果该二叉树是一棵递增树,则输出YES,否则输出NO.

示例1

输入:

2
8
2 -1 -1
1 5 3
4 -1 6
2 -1 -1
3 0 2
2 4 7
7 -1 -1
2 -1 -1
8
21 6 -1
52 4 -1
80 0 3
31 7 -1
21 -1 -1
59 -1 -1
50 5 -1
48 -1 1

输出:

YES
NO

先找根节点,再层次遍历

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();
            if (N == 1) {
                System.out.println("NO");
                break;
            }
            int[][] tree = new int[N][3];
            int[] f = new int[N];
            Arrays.fill(f, -1);
            for (int j = 0; j < N; j++) {
                tree[j][0] = sc.nextInt(); // value
                tree[j][1] = sc.nextInt(); // left
                if (tree[j][1] != -1) f[tree[j][1]] = j;
                tree[j][2] = sc.nextInt(); // right
                if (tree[j][2] != -1) f[tree[j][2]] = j;
            }
            int root = -1;
            for (root = 0; root < N; root++) {
                if (f[root] == -1) {
                    break;
                }
            }
            boolean flag = true;
            Queue<Integer> firstQueue = new ArrayDeque<>();
            Queue<Integer> secondQueue = new ArrayDeque<>();
            firstQueue.offer(root);
            while (!(firstQueue.isEmpty())) {
                int firstSum = 0, secondSum = 0;
                while (!firstQueue.isEmpty()) {
                    Integer parent = firstQueue.poll();
                    firstSum += tree[parent][0];
                    if (tree[parent][1] != -1) {
                        secondQueue.offer(tree[parent][1]);
                        secondSum += tree[tree[parent][1]][0];
                    }
                    if (tree[parent][2] != -1) {
                        secondQueue.offer(tree[parent][2]);
                        secondSum += tree[tree[parent][2]][0];
                    }
                }
                if (secondQueue.size() == 0) break;
                if (firstSum >= secondSum) {
                    flag = false;
                    break;
                }
                Queue<Integer> temp = firstQueue;
                firstQueue = secondQueue;
                secondQueue = temp;
            }
            if (flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
        sc.close();
    }
}

第3道

小Y很喜欢喝咖啡,但是同事告诉他经常喝咖啡可能不太好,所以小Y限制自己喝咖啡的间隔不能低于κ天。但是,在一个月30天当中,固定有M天是小Y最喜欢的游戏更新版本的日子,这个时候小Y一定会喝咖啡庆祝这些日子。
小Y想知道,在满足上面的条件下,这个月最多能喝多少次咖啡呢?

输入描述:

输入的第一行是一个正整数T(0<T<=500),表示样例个数。对于每一个样例,第一行是两个正整数K(0<=K<=30)、M(0<=M<=30)分别表示喝咖啡的最小间隔和固定喝咖啡的日子。按下来一行是M个不重复的由空格分隔的整数,表示小Y固定喝咖啡的日子。题目保证这些日子按照从小到大的顺序给出,它们之间的间隔不会低于K天,且范国均在1到30之间(含1和30)。

输出描述:

对于每一组样例,输出一个正整数,表示小Y这个月最多能喝咖啡的次数。

示例1

输入:

5
0 10
1 2 3 4 5 6 7 8 9 10
1 15
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
1 7
5 9 13 17 21 25 29
5 2
1 30
5 2
7 30

输出:

30
15
15
5
5

这道题目的边界条件真的很经典。

边界条件一定要写出恒成立的不等式,推出来;
而不是像我之前,+1 - 1 取上界 取下界 地凑一凑就行了,运行一下匹配验证,根本濑得去思考,这道题上吃了大亏

严格不等式:
① day[0] - cnt * (K+1) >= 1
=> cnt <= (day[0] -1)/(K+1) 数学除
=> 根据题目意思,(day[0] - 1)/(K+1) 向下取整
② day[j-1] + cnt * (K+1) < day[j]
=> cnt < (day[j] - day[j-1])/(K+1) 数学除
=> 根据题目意思,(day[j] - day[j-1])/(K+1) 向下取整 再-1
③ day[M-1] + cnt * (K+1) <= 30
=> cnt <= (30 - day[M-1])/(K+1) 数学除
=> 根据题目意思, (30 - day[M-1])/(K+1) 向下取整

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int K = sc.nextInt();
            int M = sc.nextInt();
            int max = M;
            int[] days = new int[M];
            for (int j = 0; j < M; j++) {
                days[j] = sc.nextInt();
            }
            if (M == 0) {
                max = 30 / (K + 1);
            } else {
                for (int j = 0; j < M; j++) {
                    if (j == 0) {
                        int cnt = (days[j] - 1) / (K + 1);
                        max += cnt;
                    } else {
                        int gap = days[j] - days[j - 1];
                        int cnt = gap / (K + 1) - 1;
                        max += cnt;
                    }
                    if (j == M - 1) {
                        int gap = 30 - days[j];
                        max += gap / (K + 1);
                    }
                }
            }
            System.out.println(max);
        }
        sc.close();
    }
}

拼多多2019寻梦计划——笔试题

笔试试题类型:是1到基础题+1道搜索题+1道找规律( 数学计算 )题+1道LeetCode题( 测试用例数据规模分层 )。

第1道

读入一个数列和N值,返回按优先级排序的N个数,满足
(1)所有偶数优先级大于奇数
(2)同为偶数或同为奇数时,数值大的优先级高

输入描述:

每个测试输入的测试用例,包含一个用半角逗号(,)分开的自然数数列和1个参数N,数列和参数N用半角分号(;)隔开这里保证N小于数列的元素个数(不超过100)。

输出描述:

在一行内输出N个满足题目条件的自然数,用逗号隔开

示例1

输入:

555503,772867,756893,339138,399447,40662,859037,628085,855723,974471,599631,636153,581541,174761,948135,411485,554033,858627,402833,546467,574367,360461,566480,755523,222921,164287,420256,40043,977167,543295,944841,917125,331763,188173,353275,175757,950417,284578,617621,546561,913416,258741,260569,630583,252845;10

输出:

913416,566480,420256,339138,284578,40662,977167,974471,950417,948135
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String line = sc.next();
        String[] split = line.split(";");
        int N = Integer.valueOf(split[1]);
        String[] nums = split[0].split(",");
        List<Long> nums_1 = new ArrayList<>();
        List<Long> nums_2 = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            long t = Long.valueOf(nums[i]);
            if (t % 2 == 0) {
                nums_2.add(t);
            } else {
                nums_1.add(t);
            }
        }
        Collections.sort(nums_1, Collections.reverseOrder());
        Collections.sort(nums_2, Collections.reverseOrder());
        List<Long> res = new ArrayList<>(N);
        for (int i = 0; i < Math.min(nums_2.size(), N); i++) {
            res.add(nums_2.get(i));
        }
        if (res.size() < N) {
            for (int i = res.size(), j = 0; i < N; i++, j++) {
                res.add(nums_1.get(j));
            }
        }
        for (int i = 0; i < N; i++) {
            if (i == 0)
                System.out.print(res.get(i));
            else
                System.out.print("," + res.get(i));
        }
    }
}

第2道

产品经理小梅喜欢和他的男朋友小白一块玩扑克游戏。每一局,小梅抽取N张扑克牌,自左向右依次排列在桌面上;小白也抽取M(8>=N>=M>=1)张扑克牌,自左向右依次排列在桌面上。
小梅需要进行N个回合,使用手中的扑克牌,组成一个新的扑克牌的序列每个回合,小梅有d、l、r三种策略
选择d时,小梅将最左边的扑克牌丢弃
选择l时,小梅将最左边的扑克牌取出,放到新的扑克牌序列的最左边
选择r时,小梅将最左边的扑克牌取出,放到的扑克牌序列的最右边
N个回合完成,新的扑克牌序列与小白的扑克牌完全样(只考虑数字,不考虑花色),则小梅胜出
小梅向程序员小岛提了一个需求,希望了解获胜的全部方法。简化起见扑克牌仅包合1-9。

输入描述:

首先,输入数字S,作为局数(1<=10)每一局,分别输入两行字符串,分别代表小梅的抽取的扑克牌(从左向右排列)和小白抽取到的扑克牌(从左向右排列)

输出描述:

对于每一局,在开始和结束,分别输出{和}输出获胜的方法,回合策略的结尾输出一个空格。若存在多个获胜方法,请按字典序的升序输出。

示例1

输入:

3
123
3
123
321
45
67

输出:

{
d d l
d d r
}
{
l l l
r l l
}
{
}

真是刷题少了,一开始都没做出来,每步“有三种策略”,这是明显的搜索题啊。暴力搜索可破。

import java.util.*;

public class Main {
    static List<String> res;
    static Queue<String> road;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        for (int i = 0; i < S; i++) {
            String nums1 = sc.next();
            String nums2 = sc.next();
            res = new ArrayList<>();
            road = new ArrayDeque<>();
            find(nums1, "", nums2);
            printResult(res);
        }
    }

    private static void find(String origin, String now, String target) {
        if (target.equals(now)) {
            if (origin.length() >= 0) {
                for (int i = 0; i < origin.length(); i++) {
                    road.offer("d");
                }
            }
            res.add(String.join(" ",road));
            return;
        }
        if (origin == null || origin.length() == 0) {
            return;
        }

        String left = String.valueOf(origin.charAt(0));
        String norigin = origin.substring(1);

        road.offer("d");
        find(norigin, now, target);
        road.poll();

        road.offer("l");
        find(norigin, left + now, target);
        road.poll();

        road.offer("r");
        find(norigin, now + left, target);
        road.poll();
    }

    private static void printResult(List<String> res) {
        System.out.println("{");
        if (res == null || res.size() == 0) {
            System.out.println("}");
            return;
        } else {
            Collections.sort(res, (o1, o2) -> o1.compareTo(o2));
            for (int i = 0; i < res.size(); i++) {
                String s = res.get(i);
                System.out.println(String.join(" ", s));
            }
        }
        System.out.println("}");
    }
}

第3道

扔n个般子,第i个骰子有可能投掷出Xi种等概率的不同的结果,数字从1到Xi。所有般子的结果的最大值将作为最终结果。求最终结果的期望。

输入描述:

第一行一个整数n,表示有n个骰子。(1<=n<=50)
第二行n个整数,表示每个骰子的结果数xi。(2<=Xi<=50)

输出描述:

输出最终结果的期望,保留两位小数

示例1

输入:

2
2 2

输出:

1.75

这道计算题的技巧是,如计算f(3),将f(2)、f(1)的概率也囊括了进来,从整体上再将先前计算的f(2)、f(1)减去。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    static HashMap<Integer, Long> map;
    static int n;
    static int[] a;
    static double[] p;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        p = new double[a[a.length - 1] + 1];
        int begin = 0;
        for (int max = 1; max <= a[a.length - 1]; max++) {
            while (a[begin] < max)
                begin ++;
            double p_max = 1.0;
            for (int i = begin; i < n; i++) {
                p_max *= max / (double)a[i];
            }
            p_max -= Arrays.stream(p).sum();
            p[max] = p_max;
        }
        double EX = 0;
        for (int X = 1; X <= a[a.length - 1]; X++) {
            EX += X * p[X];
        }
        System.out.printf("%.2f",EX);
    }
}

第4道

在一块长为n,宽为m的场地上,有n X m个1 X 1的单元格。每个单元格上的数字就是按照从1到n和1到m中的数的乘积。具体如下:
n = 3, m = 3
1 2 3
2 4 6
3 6 9
给出一个查询的值K,求出按照这个方式列举的的数中第k大的值v例如上面的例子里,从大到小为(9,6,6,4,3,3,2,2,1)
k=1,v=9
K=2,v=6
K=3,v=6
...
k=8,v=2
k=9,V=1

输入描述:

只有一行是3个数n,m,k表示场地的宽高和需要查询的k。使用空格隔开

输出描述:

给出第k大的数的值。

示例1

输入:

3 3 4

输出:

4

备注:

【数据范围】
100%的效据
1 <= n,m <= 40000
1 <= k <= n*m
30%的数据
1 <= n, m <= 1000

原是LeetCode改编,668. 乘法表中第k小的数

  • 先用一个数组把所有数存起来,然后用找第K大的方法去算(剑指offer方法),会报内存溢出,超出内存限制。
    • 时间复杂度:O((mn)) 创建表,然后 O(mn log(mn)) 对其进行排序。
    • 空间复杂度:O(mn)存储乘法表。
  • 建堆,会超出时间限制。k和mn的规模达到16*10^8,线性解法也会失效。那就只能log(N)了,这么明显的二分查找
    • 时间复杂度:O(mnlog(k))
    • 空间复杂度:O(k)
    • 有基于堆的改造算法,时间复杂度O(n^2 mlog(n))
  • 从矩阵的对角线入手,从右下角开始z字扫描;当时有这个想法,但自觉笔试时间内还不能达到精细的逻辑控制能力。
  • 现在复盘,猛然醒悟,这不是改造二分查找吗!真想抽自己。
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int low = 1, high = m * n;
        while (low < high) {
            int mid = (low + high) / 2;
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                cnt += (mid / i > m) ? 0 : m - mid / i;
            }
            if (cnt < k) high = mid;
            else low = mid + 1;
        }
        System.out.println(low);
    }
}