大厂软开秋招笔试（算法）真题2

一条路上依次排列着N个七色豆，七种颜色分别用字符abcdefg表示。
一条机器小人沿着这条路往前捡豆豆，机器小人会按下发给它的指令串进行动作:指令串由abcdefg*这八个字符组成。其中abcdefg是豆豆的颜色，表示机器小人接下来可以捡一粒该颜色的豆豆。如果指令串接下来出现"*这个字符，表示机器小人可以重复前一个动作任意多次(包括0次)。
如果指令串执行结束，或者遇到当前指令不能匹配的豆豆，机器小人停止前进。
求机器小人最多可以捡到多少个豆豆。
输入描述：
第一行输入一个字符串，为N个豆豆的颜色，长度N不超过1000
第二行输入一个字符串，为机器小人的指令串S，S长度不超过1000
输出描述：
第一行输入一个字符串，为N个豆豆的颜色，长度N不超过1000
第二行输入一个字符串，为机器小人的指令串S，S长度不超过1000
补充说明：
整数值，表示机器小人最多可以捡到多少个豆豆
示例：
输入：
abbbbcdefg
ab*c*d
输出：
7

在一个神秘的森林中，住着一群聪明的小动物。每只小动物都有一个独特的魔法数字。一天，森林中的智者决定进行一次特殊的仪式，需要小动物们按顺序站好，从中挑出不少于一只小动物站成一队，现在需要从这个队伍中挑选出来一些小动物，实现挑出的小动物的魔法数字之和是最大的，要求挑选出来的小动物不能改变其在原始队伍中的相对位置，并且挑选出来的小动物在原队伍中的位置间隔不能小于k。
输入描述：
第一行包含两个整数n和k，表示小动物的数量和最小位置间隔。数组长度n的范围是[1,100000],最小距离k的范围是[1,n]
第二行包含j个整数，表示每只小动物的魔法数字。每个魔法数字的取值范围是[-10000.10000]
输出描述：
输出一个整数，表示满足条件的最大和。
示例 1：
输入：
5 2
3 2 5 10 7
输出：
15
说明：
共有5个小动物，要求挑选出的小动物在原始队伍中的位置间隔不能小于2，当前五个小动物站成一队后，魔法数组分别为3 2 5 10 7，按照要求得到的最大的值为15，其挑选出的队伍为3 5 7
请使用Golang实现

肖林在大学毕业后，计划安排一次愉快的旅游，所以提前对想去的旅游景点进行了量化评估，方便挑选出最优的旅游路线。评估维度分为三个属性，分别为m、n和(x,y)，其中m代表疲劳值，n代表兴奋值，(x,y):代表景点位置。家所在位置为(0，0)。并且从旅游景点(x1,y1)到旅游景点(x2,y2)，会产生一定的疲劳值，其疲劳值为|x1-x2|+|y1-y2|。
选择k个旅游景点，计算最终的疲劳值cm和兴奋值cn，而cn/cm则代表本次旅游的舒适值，舒适值最高的旅游路线，即表示为最优的旅游路线。cm代表所有旅游景点的疲劳值之和，再加上路上所产生的疲劳值。cn代表所有旅游景点的兴奋值之和。
现在有t个旅游景点，肖林准备选择k个景区进行游玩，旅游路线需从家里出发，经过k个景区并最终回到家里。请为肖林规划好最优的旅游路线。
输入描述：
第一行输入t k，空格分割，分别代表旅游景点总数和计划游玩的旅游景点个数。0<k<=t。
第二行到第t+1行输入m n (x y)，空格分割，代表每个旅游景点的属性。
输出描述：
舒适值(保留6位小数点)，表示最优旅游路线的舒适值。
示例：
输入：
3 2
6 20 (10 15)
-5 10 (30 27)
-15 10 (20 25)
输出：
0.370370
说明：
最优旅游路线为:(0,0)->(10,15)->(20,25)->(0,0)或者(0.0)->(20,25)->{10,15)->(0,0)
计算出cm=81,cn=30,最终计算的值为0.370370

微隔离产品有个流量可视的模块，流量可视会图形化展示服务器之间的所有访问关系，其中访问关系需要匹配***策略以让用户观测该流量是否被放行or拒绝，拒绝的原因是匹配到了某一条***策略。请你设计一个算法来快速完成访问关系的策略匹配。
流量数据和***策略均为五元组(src_ip,src_port,dst_ip,dst_port,protocol)
流量五元组示例和格式说明
src_ip:字符串，仅支持ipv4格式。如:1.1.1.1
src_port:整数，1-65535。如:222
dst_ip:字符串，仅支持ipv4格式。如:1.1.1.1
dst_port:整数，1-65535。如:111
protocol:整数:仅支持tcp:17，icmp:1，udp:6
***规则示例和格式说明
src_ip:字符串，支持ip段/单个ip/任意IP。如:1.1.1.1,1.1.1.1-1.1.10.1,0.0.0.0
src_port:字符串，支持端口范围/单个端口/任意端口。如:80,80-90,0
dst_ip:字符串，支持ip段/单个ip/任意IP。如:1.1.1.1,1.1.1.1-1.1.10.1,0.0.0.0
dst_port:字符串，支持端口范围/单个端口/任意端口。如80,80-90,0
protocol:整数，支持17/6/1/0(tcp:17,udp:6,icmp:1，ALL:0)

有n颗珍珠，编号0~n-1，它们中间有细线连接，每颗珍珠至多与其他3颗珍珠连接，且不形成环路，所有珍珠都连接在一起。对于每颗珍珠，他们的重要度定义如下:假设去掉编号为k的珍珠，那么剩下的珍珠按照连接关系会分裂成1-3组，每组的珍珠数量的乘积即为k号珍珠的重要度。求:具有最高重要度的珍珠有几颗?
输入描述：
第一行输入n，下面n行输入编号0~n-1的珍珠的邻接珍珠，第一个数代表邻居的数量k，后面跟k个数代表邻居编号，为了避免重复数据，只输入编号比自己编号大的邻居。
示例:
5
1 1
1 2
2 3 4
0
0
上面的数据代表:
0号连接着1;
1号连接着2;
2号连接着1，3，4，因为1比2小，之前的数据里包含了这个连接关系，所以只输入3，4;
3号连接着2，因为2比3小，3没有与其他编号比它大的数连接，所以输入0;
4号连接着2，因为2比4小，4没有与其他编号比它大的数连接，所以输入0;
输出描述：
一个整数，代表具有最高重要度的珍珠的数量
对于刚刚输入的例子，输出为
3
解释：
节点0的分数是4
节点1的分数是1*3=3
节点2的分数是1*1*2=2
节点3的分数是4
节点4的分数是4
最高得分为4，有3个节点得分为4，输出3
示例1
输入：
5
1 1
1 2
2 3 4
0
0
输出
3
请使用Golang实现该算法

小红和小紫正在玩一个游戏，每一关都有一个分数。如果某人某一关分数比上一关高，但另一个人这一关分数比上一关低，那么他就可以嘲笑对方。如果两个人这一关游戏的分数都比上一关多，则增量更多的可以嘲笑对方;如果两个人这一关游戏的分数都比上一关少，则减量更少的可以嘲笑对方。只有当他们的增量相同或者减量相同时，才不会互相嘲笑。
例如，假设小红第一关的分数为5，第二关的分数为10;小紫第一关的分数为2，第二关的分数为8，显然小红增加的比小紫多，那么小红就可以嘲笑小紫。
现在给定了小红和小紫每一关的分数，你可以选择一段连续的关卡，使得这一段关卡中两个人都不会互相嘲笑，问最多可以选择多少个关卡。特别的，一段连续关卡中的第一关两人不会互相嘲笑。
输入描述：
第一行输入一个正整数几，代表关卡数。
第二行输入n个整数ai;，代表小红每一关的分数。
第三行输入n个整数bi;，代表小紫每一关的分数。
2 ≤n< 10^5
-10^9≤ ai,bi≤ 10^9
输出描述：
输出可以选择最多的关卡数。
示例 1：
输入：
5
1 2 3 1 3
-1 0 3 -1 1
输出：
2
说明：
可以选择前两个数，[1,2]和[-1,0]相似，长度为2。选择后两个数也是可以的。

对于一个仅由左括号'('和右括号')'组成的字符串，小红想知道它的最长合法前缀的长度是多少。
对于某一个前缀，我们定义它是合法的，当且仅当该前缀满足以下条件:
存在一种拆分方案，可以将该前缀拆分为若干对匹配的括号'()'如'(),'()()','(())'都是合法的，而')()(','))'是非法的。
特殊的，空串我们认为也是合法的。
输入描述：
第一行输入一个整数n，表示字符串的长度。
接下来一行输入一个长度为n的，仅由'('和')'组成的字符串
1 ≤n≤ 10^5
输出描述：
输出一个整数，表示最长的合法前缀长度。
示例1
输入
5
(()))
输出
4
说明
可以证明前缀(())是最长且合法的前缀