深信服2019春招技术岗部分编程题汇总

从字符串string开始完整匹配子串sub，返回匹配到的字符个数。

sub中如果出现'?'表示可以匹配一到三个除'\0'以外的任意字符。
如果sub还有找不到匹配的字符，则说明不能完整匹配。

如果能完整匹配，返回匹配到的字符个数，如果有多种匹配方式，返回匹配字符数最少的那个，如果不能完整匹配，返回-1

输入描述： 第一行输入字符串string，长度小于10000

第二行输入子串sub，长度小于100输入样例： abcdefg a?c 输出描述： 从string开头位置完整匹配sub，匹配到的字符个数。输出样例 3

有K种颜色的小球(K<=10)，每种小球有若干个，总数小于100个。
现在有一个小盒子，能放N个小球(N<=8)，现在要从这些小球里挑出N个小球，放满盒子。
想知道有哪些挑选方式。注：每种颜色的小球之间没有差别。

请按数字递增顺序输出挑选小球的所有方式。

如有3种颜色，每种颜色小球的个数分别为a:1,b:2,c:3，挑出3个小球的挑法有：
003,012,021,102,111,120
输入描述： 第一行两个数字K N，分别表示小球种类数目和挑选的小球个数
第二行开始为每种小球的数目，共K行数据输入样例： 3 3 1 2 3 输出描述： 输出所有可行的挑选方案，按升序排列输出样例 003 012 021 102 111 120

8x8的棋盘上，布有黑白两色棋子，白子先下，当白子下N手后，棋盘上最多有可能留下多少颗白子？

下法规则：
1.每次落子后，以该棋子为中心的8个方向(米字形的8条直线)，如果有同色棋子，
且两个同色棋子之间连续排列着若干个异色棋子，无空白及同色棋子。则，这次落子可以把这些夹在中间的异色棋子全部翻色（即黑变白，白变黑）。

2. 黑白子交错落子。

3. 如果一个位置上有棋子，不能继续在该位置上落子；

4. 如果一个位置上落子后，不能翻对手的棋子，则该位置不能落子；

1表示黑色，2表示白色，0表示空白未落子
白棋落子后，棋盘变化情况如下所示：
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 1 2 0 0 0    =>   0 0 0 1 2 0 0 0 
0 0 0 2 1 0 0 0         0 0 0 2 2 2 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 1 2 0 0 0    =>   0 0 0 1 2 0 0 0 
0 0 1 2 1 2 0 0         0 0 1 2 1 1 1 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
输入描述： 第一行为白子需要走的步数

接下来8行数据，指明棋盘上的棋子状态，其中1为黑子，2为白子，0为空位置输入样例： 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 输出描述： 白子下完N手后，棋盘上的白子个数的最大可能。输出样例 4

一个长方体，长宽高分别为x,y,z，都为自然数。

现在要把若干个相同的长方体摆成高为N的一根柱形体。

每层摆1个，如果两种摆法的高度是一样的，则认为这两种摆法等价，所以每层只有三种摆法。

求一共有多少种摆法。

输入描述： 第一行为一个数字N，N>=1且N<=100，表示要摆放的高度
第二行为长方体的长宽高,x、y、z都为无符号整数，按升序排列。输入样例： 10 5 6 7 输出描述： 摆法总数，已知该总数会小于10000000输出样例 1

一个数字段由首尾两个数字标识，表示一个自然数集合，
比如数字段[beg, end)表示从beg到end之间的所有自然数，
包含beg，但不包含end。

有若干个数字段，这些数字段之间可能有重叠，
怎么把这些数字段合并去重，用最少个数的数字段来表示。

合并前后，整个集合包含的数字不发生变化。


输入描述： 第一行为数字N，表示接下来有N个数字段(N<=100000)
第二行开始一共有N行，每行两个数字，分别表示一个数字段的beg和end
(beg和end为无符号32位整数)输入样例： 4 3 8 3 7 4 6 7 9 输出描述： 合并去重后形成的数字段集合，按升序排列。输出样例 3 9

已知某序列S=<e1,e2,…,en>，序列中的元素类型为整数（en <= 2^10），序列的长度为可变长度。
现在有若干序列S1，S2,…,Sn，现在要求设计一种算法，找出这些重复的序列。输出重复序列的序号，如果有多组重复，需全部输出。

所有序列中的数字个数加起来，小于1000000，序列个数小于10000个。

例如现有3个序列
S1=<65,43,177,655>
S2=<1,2,3,4,5,6,7>
S3=<65,43,177,655,3>
这时序列无重复。又如
S1=<65,43,177,655,3>
S2=<1,2,3,4,5,6,7>
S3=<65,43,177,655,3>
这时序列有重复。
输入描述： 第一行为一个正整数N，N>=1且N<10000

接下来为2*N数据，每两行表示一个序列，序列的第一行为序列长度L，第二行为序列的数字，一共L个输入样例： 11 10 794 472 991 500 615 872 518 827 673 203 1 427 7 367 718 202 187 683 321 831 10 1023 78 310 816 158 500 518 705 553 470 8 205 190 306 492 166 49 791 961 6 665 211 1009 614 15 683 2 195 946 3 678 198 495 8 205 190 306 492 166 49 791 961 5 83 74 1023 453 692 2 176 157 输出描述： 重复序列的序号，每一行X个数字，表示一组相同的序列，这一组相同序列共有X个，输出这X个序列的序号输出样例 4 8