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

URL

type

status

date

slug

summary

📝 算法题

第一题:求int型正整数在内存中存储时1的个数

描述:

对于给定的int型的十进制整数n，统计其在内存中存储时1的个数。换句话说，即统计其二进制表示中1的个数。

输入描述:

在一行上输入一个整数n(0≦n<2^31)，代表给定的数字。

输出描述:

在一行上输出一个整数，代表n的二进制表示中1的个数。

解决方法:

思路:两种方法:第一种:通过循环，不断除以2取余和整除，直到目标值等于1或者等于0。第二种:通过Python自带功能转换为2进制，然后求取”1”的总和。

第二题:购物单

描述:

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件。

主件可以没有附件，至多有 22 个附件。附件不再有从属于自己的附件。

若要购买某附件，必须先购买该附件所属的主件，且每件物品只能购买一次。

王强查到了m件物品的价格，而他只有n元的预算。为了先购买重要的物品，他给每件物品规定了一个重要度，用整数1∼5表示。他希望在不超过预算的前提下，使满意度最大。满意度定义为所购每件物品价格与重要度乘积之和。具体地说，记第i件物品的价格为vi，重要度为wi；若共选中k件物品，编号为 j1,j2,…,jk，则满意度计算为：∑t=1kvjt×wjt=vj1wj1+vj2wj2+⋯+vjkwjk请你帮助王强计算可获得的最大的满意度。

输入描述:

第一行输入两个整数n,m(1≦n≦3×104; 1≦m≦60)代表预算、查询到的物品总数。此后m行，第i行输入三个整数 vi,wi,qi(1≦vi≦104; 1≦wi≦5; 0≦qi≦m)代表第i件物品的价格、重要度、主件编号。特别地，qi=0代表该物品为主件，否则表示该附件从属于主件qi。编号即输入顺序，从1开始。特别地，保证全部物品的价格v均为10的倍数；且每个主件的附件数不超过2个。

输出描述:

在一行上输出一个整数，代表王强可获得的最大满意度。

解决方法:

思路:这是一个关于“背包”的问题。假设：我们手里有3元，柜台有3间商品，价格分别为1、1和3，满意度分别为2，3和3(已经和价格相乘)。那么，当背包放一个物品时，0元可购买商品的满意度，1元可购买商品的满意度…3元可购买商品的满意度；解决完第一个物品时，那么当背包放前两个物品时，0元可购买的商品满意度（依然为0），但是1元、2元和3元可购买商品满意度的计算有所不同，如下表dp：

分析如下:

首先，需要获取max_i=dp[1][1]的值。
接着，再计算dp[1][0] + 物品2的满意度=3
最后，比较两者哪一个最大，即max_i = max(max_i, dp[1][0] + 物品2的满意度)

后边的物品计算方式相同。

第三题:坐标移动

描述:

我们定义一个无限大的二维网格上有一个小人，小人初始位置为(0,0)点，小人可以读取指令上下左右移动。一个合法的指令由三至四个符号组成：

第一个符号为 "A/D/W/S"中的一个，代表小人移动的方向；分别代表向左、向右、向上、向下移动；记某个时刻小人的坐标为(x,y)，向左移动一格即抵达(x−1,y)、向右移动一格即抵达 (x+1,y)、向上移动一格即抵达(x,y+1)、向下移动一格即抵达(xy−1)。

最后一个符号为‘;’，代表指令的结束，该符号固定存在；

中间为一个大于0且小于100的数字，代表小人移动的距离。特别地，如果这个数字小于10，那么它可能包含一个前导零，此时也视为合法。

如果你遇到了一个不合法的指令，则直接忽略；例如，指令"A100;" 是不合法的，因为100超出了规定的数字范围；"Y10;"也是不合法的，因为Y不是"A/D/W/S"中的一个。输出小人最终的坐标。

输入描述:

在一行上输入一个长度 1≦length(s)≦104，由大写字母、数字和分号（‘;’）构成的字符串s，代表输入的指令序列。保证字符串中至少存在一个‘;’，且末尾一定为‘;’。

输出描述:

在一行上输出一个两个整数，代表小人最终位置的横纵坐标，使用逗号间隔。

解决方法:

思路:首先，将输入字符串按照”;”拆分为集合；接着，去除不符合情况的字符；最后，进行移动计算坐标位置。

第四题:识别有效的IP地址和掩码并进行分类统计

描述:

在本题中，我们需要处理地址信息，其由IP地址和子网掩码组成，这两者均形如 "*.*.*.*"，由四段数字组成（每一个‘*’表示一个数字），每一段的数字均为0到255之间的一个整数，每段数字之间以点分隔。我们定义五类 IP 地址：

A类："1.0.0.0"∼"127.255.255.255"；

B类："128.0.0.0"∼"191.255.255.255"；

C类："192.0.0.0"∼"223.255.255.255"；

D类："224.0.0.0"∼"239.255.255.255"；

E类："240.0.0.0"∼"255.255.255.255"。

我们定义私有IP地址：

"10.0.0.0"∼"10.255.255.255"

"172.16.0.0"∼"172.31.255.255"；

"192.168.0.0"∼"192.168.255.255"。

我们定义合法的子网掩码为：将掩码的每一段数字依次转换为八位长度的二进制字符串并进行拼接，这个字符串必须由若干个连续的1后跟若干个连续的0组成，才视为子网掩码合法。例如，掩码 "255.254.255.0"转换拼接得到字符串 11111111 11111110 11111111 00000000，显然不合法；掩码 "255.255.255.248"转换拼接得到字符串 11111111 11111111 11111111 11111000，合法。注意，全为1或全为0的掩码也视为非法。我们定义错误的IP地址和错误的子网掩码为不符合上述定义的IP地址和子网掩码。例如，格式错误、数字超出范围等等。现在，你需要分类统计 A、B、C、D、E 类地址的数量、错误 IP 或错误子网掩码的数量、私有IP的数量。特别地：

类似 "0.*.*.*"和 "127.*.*.*"的IP地址不计入任何类别，也不计入非法统计，直接跳过；

一个IP既可计入私有 IP，也可计入五类地址之一，二者分别累计。

输入描述:

本题将会给出 1≦T≦1000条地址信息，确切数字未知，您需要一直读取至文件结尾；您也可以参考 牛客网在线判题系统使用帮助 获得更多的使用帮助。每条地址信息描述如下：每行输入一个 "*.*.*.*"形式的IP地址和一个"*.*.*.*"形式的子网掩码，中间用波浪线（∼）分隔。保证‘*’要么为空，要么是一个0到255间的整数。

输出描述:

在一行上输出七个整数，分别代表A类地址数、B类地址数、C类地址数、D类地址数、E类地址数、错误IP或错误子网掩码数、私有IP数。

解决方法:

思路:在做该算法题前，伙伴们需要尽可能考虑到各种错误情况(博主处理掩码的代码还可以进一步优化，可以自己尝试一下)。首先，IP和掩码分开处理。IP需要先处理特殊情况，然后再根据IP类别进行分类。同样，掩码也需要先处理特殊情况，然后再根据掩码特性判断是否符合规则；接着，将函数返回情况，通过字典将结果封装。