记录-华为机试(六) | 不爱吃香菜的萌新

URL

type

status

date

slug

summary

📝 算法题

第一题:数据分类处理

描述:

对于给定的分类规则集R={R1,R2,…,Rm}，规范化它，具体地：

将R中的整数按从小到大的顺序重新排序；

去除R中的重复元素；记规范化后的分类规则集为r={r1,r2,…,rm}。

对于收集到的、由若干个整数组成的数据集I，按照下方的要求，使用规范后的分类规则集r输出分类后的结果。

对于第i条分类规则ri，如果I中存在以ri为连续子串的整数，则该规则集有效；进一步地，你需要输出有多少条数据符合该规则，以及这些数据在I中的位置、数据本身。

子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。对应本题中，你需要将整数看作是数字字符串。

输入描述:

第一行先输入一个整数n(1≦n≦100)代表数据集I中的数据条数。随后，在同一行输出n个整数 I1,I2,…,In(0≦Ii<2^31)代表数据。第二行先输入一个整数m(1≦m≦100)代表分类规则集R中的规则条数。随后，在同一行输出m个整数R1,R2,…,Rm(0≦Ri<2^31)代表规则。

输出描述:

在一行上：

先输出一个整数k，代表一共需要输出的数字个数。简单地说，这个数字为下文中你输出数量的个数统计。

随后，对于规范后的每一条规则，如果其有效：先输出这条规则本身，随后输出一个整数p，代表符合该规则的数据条数；随后输出p个二元组 {id1,Iid1},{id2,Iid2},…,{idp,Iidp}，代表符合这条规则的数据在I中的位置、数据本身。其中，位置从0开始计数。如果其无效，则跳过这条规则。

解决方法:

思路:建立两个循环遍历，将符合情况放入集合。

第二题:字符串排序

描述:

对于给定的由可见字符和空格组成的字符串，按照下方的规则进行排序：

按照字母表中的顺序排序（不区分大小写）；

同一字母的大小写同时存在时，按照输入顺序排列；

非字母字符保持原来的位置不参与排序；直接输出排序后的字符串。字符串由ASCII码在 32到126范围内的字符组成。您可以参阅下表获得其详细信息。

输入描述:

在一行上输入一个长度为 1≦length(s)≦1000，由上表中的字符组成的字符串s。

输出描述:

输出一个字符串，代表按照规则排序后的字符串。

解决方法:

思路:两种方法:第一种:建立双循环，遍历字符串。第二种:利用python自带的sorted()函数，可以实现不区分大小写的字母排序。接着，再将非字母字符插入对应的位置。

第三题:查找兄弟单词

描述:

定义一个字符串s的“兄弟单词”为：将s重新排序后得到的与原字符串不同的新字符串。现在，对于给定的n个字符串 s1,s2,…,sn和另一个单独的字符串x，你需要解决两个问题：

统计这n个字符串中，有多少个是x的“兄弟单词”（注意，这n个字符串可能有重复，重复字符串分别计数）；

将这n个字符串中x的“兄弟单词”按字典序从小到大排序，输出排序后的第k个兄弟单词（从1开始计数）。特别地，如果不存在，则不输出任何内容。

【名词解释】从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的字母表顺序，字母序较小的字符串字典序也较小；如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入描述:

在一行上依次输入：

一个整数 n(1≦n≦103)代表字符串的个数；

n个长度为 1≦length(si)≦10，仅由小写字母构成的字符串 s1,s2,…,sn；

一个长度为 1≦length(x)≦10，仅由小写字母构成的字符串x；

一个整数 k(1≦k≦n)代表要查找的第k小的兄弟单词的序号。

输出描述:

第一行输出一个整数，代表给定的n个字符串中，x的“兄弟单词”的数量；第二行输出一个字符串，代表将给定的n个字符串中x的“兄弟单词”按字典序排序后的第k小兄弟单词。特别地，如果不存在，则不输出任何内容（完全省略第二行）。

解决方法:

思路:借鉴Python自带的sorted()函数解决该算法问题。首先，去除单字母和set()后为单字母的情况；接着，for循环遍历，这时会遇到两种情况：第一种字符串相等或字符串长度不相等的情况；第二种经过sorted()之后字符串相等的情况。跳过第一种情况，append第二种情况；紧接着，判断目标兄弟index是否越界；最后，输出结果。

第四题: 素数伴侣

描述:

定义两个正整数a和b是“素数伴侣”，当且仅当a+b是一个素数。现在，密码学会邀请你设计一个程序，从给定的n个正整数{a1,a2,…,an}中，挑选出最多的“素数伴侣”，你只需要输出挑选出的“素数伴侣”对数。保证n为偶数，一个数字只能使用一次。

输入描述:

第一行输入一个正偶数n(2≦n≦100)代表数字个数。第二行输入n个正整数 a1,a2,…,an(1≦ai≦3×104)代表给定的数字。

输出描述:

输出一个整数，代表最多可以挑选出的“素数伴侣”的数量。

解决方法:

思路:使用了匈牙利配对思想。首先，将数据集合分为奇数集合和偶数集合，并建立一个choose集合，choose集合用于标记奇数配对哪一个偶数；接着，循环偶数集合，并在每一次循环时建立一个isprime集合；紧接着，让偶数分别与奇数配对，符合要求则isprime[i]=True(表示该偶数可以和该奇数配对)；再接着，判断choose[i]是否已经选择了其他偶数。如果选择，则将choose[i]重新输入到match()函数，配对寻找其他奇数；最后，输出结果。