算法_python_牛客华为机试笔记_01
刷题是必须的，通过刷题以及别人对题目的解析，可以快速理解，提高效率。
00_题库与参考视频
华为机试_在线编程_牛客网
HJ3 明明的随机数_哔哩哔哩_bilibili
这套华为机试是华为笔试面试机考在线练习，共138道题，目前我刚做到15题，这篇笔记是基于题目以及解析视频，自己先尝试写一遍，通过或通不过都跟视频对照一下，借鉴别人的解题思路，不断进行自我整理和归纳，提升个人的算法解题基础能力。
01_HJ1~HJ15_学习整理
HJ1-字符串最后一个单词的长度
作为第1题，是典型的输入/输出基础，如果是C/C++，无论scanf或是cin>>它的特点都是空字符截断，所以最后一个输入的单词已经被分离出来了，再一步就是计算长度，C++也可以直接使用.size()来获取。
相比较而言，python在这道题上反而要考虑更多，因为它的输入input()是以行为单元的，还需要手动把最后一个单词分离出来，如果对split()没有深入了解，还会对只有一个单词(没有空格时)用空格分割是否会报错，是不是还需要异常处理或者增加语句进行判断(比如判断空格是否存在)。所以这题的知识点共4个：
| 知识点 | 重要内容 | |
| 1 | 输入 input() | s = input() # 输入一行字符串 # s = 'HelloNowcoder' # s='A B C D' |
| 2 | 分割 split() | l = s.split(' ') # 以空格分割的列表 # l = ['HelloNowcoder'] # l = ['A','B','C','D'] word1 = l[-1] |
| 3 | 求长度 len() | ilength = len(word1) |
| 4 | 输出 print() | print(ilength) |
关键函数split()的问题
python split()函数，如果一个字符串中没有空格或没有逗号，我们能否用split(' ')或split(',')进行分割？是否报错
回答是：不会报错。
split()函数的工作原理是：在字符串中查找你指定的分隔符（比如空格' '或逗号','）。
- 如果找到了，它就在找到的位置将字符串“切”开，然后返回一个包含所有部分的列表。
- 如果没找到，它就认为整个字符串是一个不可分割的整体，然后返回一个只包含这一个完整字符串的列表。
HJ2 - 计算某字符出现次数
计算某字符出现次数_牛客题霸_牛客网
作为第2题，也没有什么坏心思，主要的知识点就是把大写转小写、计数；在C++里也可以直接用tolower()和count_if()函数直接完成，python中基本思路也是这样，把字符串以及单个字符全部转成小写或大写，然后count即可
| 知识点 | 重要内容 | |
| 1 | s.lower() #转小写 s.upper() #转大写 s.swapcase() #互转 | s1 = s.lower() ch1 = ch.lower() |
| 2 | count() 计数 | out = s1.count(ch1) |
额外知识点，在学习C语言时知道char是字符型，可以用数字来表示，python中用ord,chr进行相互的转换，这个在后序的字母循环等"密码"问题中经常用到
| 知识点 | 重要内容 | |
| 1 | ASCII 码与字符互转 ord('o') chr(65) | c1 = 'A' # ord(c1) --> 65 chr(111) --> 'o' |
HJ3 - 明明的随机数
明明的随机数_牛客题霸_牛客网
题目是随机数，但实际上是考去重和排序，另外输入/输出升级为循环输入和循环输出。
在前面的文章中，我们专门讨论了排序，一般的水平能知道选择排序和冒泡排序这两个基础排序方法就很不错，而这两个恰恰又是O(n^2)的时间复杂度，用来解竞赛题肯定是超时，所以排序并不是考察的目标，无论是C++，Java还是python都有内置的排序函数，直接使用就好了。
去重是基本操作，需要熟练掌握，很多人看到用set()方法很简单就不去记基本操作，这是肯定不行的。
| 知识点 | 重要内容 | |
| 1 | 去重(for 循环+列表append) | l = [] for x in arr: if x not in l: l.append(x) |
| 2 | 排序 sort() 与 sorted() | # 1. 列表才能用.sort()，且列表直接变化 list1.sort() # 2. sorted()可以用于列表以及其他结构 li2 = sorted(li1) # 逆序排序 list1.sort(reverse=True) |
| 3 | set | set常见用法是1.去重 2. 元素检查是否在集合中 3. 集合运算，如交集，并集，差集等 注意：集合无序，不能直接排序，需要转换 li3 = list(set(xxx)) |
| 4 | set辅助列表推导 | 上面的list(set(xxx))会破坏原来列表的顺序，如果需要保留原来的顺序： seen=set(); [x for x in arr if not (x in seen or seen.add(x))] |
循环输入与输出的知识点
| 知识点 | 重要内容 | |
| 1 | 循环输入 | for i in range(n): line = input() 这里我们通常2种做法，1种是把输入与处理分开来，也就是先用一个列表来记录输入的所有元素，再进行处理；第2种是直接在循环中进行处理，调用def functionx()函数 |
| 2 | 循环输出 | 循环输出也是2种做法，1种是用for 循环，print(x, end=' ')的方式，类似于C/C++的方式；第2种是把要输出的做成一行的字符串，然后print(line)即可 |
| 3 | 制作行字符串 | 如果使用print(line),则可以通过.join()函数把各种类型的列表连接成字符串，比如以空格连接： s1 = ' '.join(list1) |
HJ4 - 字符串分隔
题目取名总好像是故意产生误导，字符串分隔会让人直接想到split()函数，但这题并不考这个，仔细看题，它考察的是字符串补零，模余和整除运算与循环步长不为1。
从解题思路上会有不同分支，一部分倾向于先补足0再分隔，另一部分喜欢直接分隔，到最后不足再补，都是可以的，这里我们采用视频中的先补0的方式。
1. 补0的个数计算
补0的方式很多，但首先要计算得到补0的个数。这里需要用到模余的方法
| 知识点 | 重要内容 | |
| 1 | 模余 A%10 | 就是取余数运算，以本题为例，8个一组则%8 iremain = len(s) % 8 就是余数，取值范围0~7 所以 8 - iremain就是补0的个数 |
2. 补0的方法
| 知识点 | 重要内容 | |
| 1 | 左侧补0 | 可以用zfill(n)的函数，常用于十六进制显示，比如s=‘A' s1 = s.zifll(2) 就得到了'0A' |
| 2 | 右侧补0 | 可以用ljust()函数 例如 s.ljust(3,'0') --> 'A00' (参数1是指定宽度，2是填充字符） |
| 3 | 使用加号和乘号 | s + '0' * 5 |
| 4 | format | s = "42" padded_s = f"{s:<05}" # < 表示左对齐，0 表示填充字符，5 表示总宽度 # 输出: "42000" |
3. 步长不为1的循环及切片
| 知识点 | 重要内容 | |
| 1 | 循环步长不为1 | for i in range(0,len(s),8): print(s[i:i+8]) |
HJ5 - 进制转换
这道题本身是很基础的函数应用，把一个十六进制字符串转换成十进制数字，如果使用C++也可以直接用stoi(str1,0,16)进行转换，在python中用int(s, 16)就可以搞定。
| 知识点 | 重要内容 | |
| 1 | 十六进制字符串转整数 | int(s, 16) |
| 2 | 整数转十六进制字符串 转二进制字符串 | hex (95) bin (95) |
但这里我们可以开始思考进阶的问题，如果是任意进制，比如26进制，我们需要怎么办？
如果时间充足，我们当然可以手工敲入一个字典，通过字典查值，再位数上乘以进制计算出来；那么可不可以通过一个函数直接做出这个字典呢？
d = {}
for j in range(10):d[str(j)] = j
for i in range(65,65+16):d[chr(i)] = (i-65)+10--------------
{'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15, 'G': 16, 'H': 17, 'I': 18, 'J': 19, 'K': 20, 'L': 21, 'M': 22, 'N': 23, 'O': 24, 'P': 25}HJ6 - 质数因子
这道题考的是数学算法，1是什么是质数，2是质数应该怎么计算。在刷题的过程中，我们会多次遇到求质数的模块，很多难题也是由质数筛函数与其他算法组合应用的。这道题是质数筛函数的增强版，因为它不仅要判断某个数是不是质数，还需要把所有的质因数都求出来。后序的哥德巴赫猜想、权值计算都会用到，且不仅是所有质因数，还需要每个质因数的个数计算等。
基本的思路是从2开始，能整除则列表append(2)，继续整除2直到不能后再整除3......
进阶的思路是2的倍数是合数不是质数可以都跳过，所以step 可以为2(从3开始）
从时间复杂度上看，是没有必要把一个数例如（20000014）从2直到它自己的，所以最少可以除以2，到它的一半的时候如果都没有质因数，则可以结束了，但这只是减少了一半，对于很大的数还是会超时的
在数学方法上只需要做到它的开方数就可以了，sqrt(20000014) = 4472，由这个计算可以看到它的计算量要少得多，而这就是我们在质数函数中使用的计算方法，其他算法也有更好的，但暂时记住这个就可以了。当使用这个方法计算时，我们甚至都不需要考虑跳过2的倍数这一操作也不会有超时的风险。
| 知识点 | 重要内容 | |
| 1 | 质数计算的范围 | k = int(n**0.5)+1 |
| 2 | 模余与整除运算 | for i in range(2, k): while n%i == 0: n //= i l.append(i) |
| 3 | 如果这个数本身就是质数 | if n > 1: l.append(n) |
代码
n = int(input())k = int(n**0.5)+1 # 质数计算的范围
l = []
for i in range(2,k):while n % i == 0:n//= il.append(i)
if n>1: # 剩余部分或本身是质数l.append(n)
# print(l)
for x in l:print(x, end=' ')HJ7 - 取近似值
这道题不是考察四舍五入，千万注意别被坑了，它要求的小数部分大于等于0.5是整个小数部分。
所以这里的考点是查找字符串中某个字符的位置，或者split()函数；这里先列出查找位置
| 知识点 | 重要内容 | |
| 1 | s.find('.') | 查找分找到和找不到两种情况，找到了返回索引，找不到返回-1 idx1 = s.find('.') if idx1 == -1: # 没找到 |
| 2 | s.index('.') | index找不到会抛异常 try: index = s.index('.') print(f"小数点位于索引: {index}") except ValueError: print("字符串中没有小数点。") |
| 3 | 遍历字符串(手动查找） | 视频里就是用的这种方法，它比较好理解但慢 for i, char in enumerate(s): if char == '.': index = i break |
找到小数点后第一个字符，还涉及到比大小的问题，一般情况是要转成数字的，但视频中使用的是字符比大小，这是利用了字符的ASCII值的顺序。
HJ8 - 合并表记录
这道题标明的知识点是哈希，也就是字典的基础操作，现在很多人所谓的基操。
字典的键值对添加一般容易理解的方式是
d = {}
for i in range(n):k,v = map(int, input().split())if k not in d:d[k] = velse:d[k] += v但比较正规的python的dict的操作应该是.get()，这个可以直接避免键不存在的报错，因此在多次练习后，可以直接使用下面的形式
d[k] = d.get(k,0)+v| 知识点 | 重要内容 | |
| 1 | 键值对的添加及累加 | d[k] = d.get(k,0)+v 这项基操在后面的字符串进阶题中都会使用到，比如最大不重复子串，最小覆盖子串等 |
| 2 | 字典的排序 按 | 字典用sorted(d.items())进行排序，注意 |
| 3 | 按键排序 | 1. l = sorted(d.items()) # 默认为以键进行排序 2. l = sorted(d.items(), key=lambda x:x[0]) #也是按键排序 |
| 4 | 按值排序 | l = sorted(d.items(), key=lambda x:x[1]) |
| 5 | 按计算关系排序 | 比如{’luna':(79,33,59), 'Limi':(80,66,88)...}这样的字典，值又是一个元组或列表的情况下，如果我们要根据总分和排序 l = sorted(d.items(), key=lambda x: sum(x[1])) |
| 6 | 逆序 | l = sorted(d.items(), key=lambda x:x[0], reverse=True) |
HJ9 - 提取不重复的整数
本题考点是字符串逆序+去重，我们在HJ3中已经使用了列表去重，字符串去重逻辑上差不多，只需要把append改为+=就可以了。
逆序是本题新增知识点，这个在后面的回文数等题目中也会使用到
| 知识点 | 重要内容 | |
| 1 | 字符串逆序 | 即for 循环从最后一个开始，向前step，步长为-1 s1 = s[::-1] 即可 |
| 2 | 字符串去重 | |
HJ10 - 字符个数统计
又是一道典型的逆序+去重的题目，逆序和去重都与HJ9一致，只需要加上求长度函数len(sout)即可。
HJ11 - 数字颠倒
HJ12 - 字符串反转
HJ11和HJ12其实在python中可以用同一个方式完成，并且和HJ9字符串逆序是相同的知识点，但如果用C/C++这两个可能就会有比较大的差别了，其中数字的可以用到数学的方法，也就是前面一直在说的模余和整除的运算。
| 知识点 | 重要内容 | |
| 1 | 字符串逆序 | 即for 循环从最后一个开始，向前step，步长为-1 s1 = s[::-1] 即可 |
| 2 | 模余+整除运算 |
n = int(input())
if n == 0:print(0) # 会有输入就是0的情况
while n!=0:tmp = n % 10print(tmp, end='')n //= 10HJ13 - 句子逆序
句子逆序_牛客题霸_牛客网
前面好几道都是字符，数字逆序，这次稍有不同是单词逆序，也就是空格分隔(split())后的单词逆序输出，所以知识点在split()字符串成列表，以及.join(list1)成字符串，还有就是逆序
| 知识点 | 重要内容 | |
| 1 | 空格分隔 split() | l = s.split(' ') # 这里注意一下split(' ')与split()有很大区别，不要认为是相同的 |
| 2 | 单词逆序（数组逆序） | l1 = l[::-1] |
| 3 | 组成字符串 | sout = ' '.join(l1) |
HJ14 - 字符串排序
前面已经讨论过了，如果出现需要排序的，一般大家都只会选择、冒泡或者插入这三个时间复杂度为O(n^2)的简单排序，只要使用了多半就是运行超时，排序的任务通常直接用内置函数就行！
所以这道题的知识点是把循环输入的字符串存入列表中，以及内置的排序函数
| 知识点 | 重要内容 | |
| 1 | 循环保存输入 | l=[] for _ in range(n): s = input() l.append(s) |
| 2 | 内置排序函数 | l.sort() |
| 3 | 循环输出 | for x in l: print(x) # 换行 |
HJ15 - 求int型正整数在内存中存储时1的个数
这道题是某个分支算法的基础题，有很多种的计算方法，不要因为能用某一种方法解出来就沾沾自喜了，尽可能的思考一下用某种方法后续会有什么样的变化和进阶。
第一种，十进制转成二进制，标准常规是除以2取余，也是前面我们一直在用的模余+整除的运算。以7为例，7%2 = 1 (7//2 = 3) 3%2 = 1(3//2 = 1) 1%2 = 1(1//2 = 0)，得到二进制111（逆序）
cnt = 0
while n:tmp = n%2if tmp == 1:cnt += 1n //= 2第二种，在python里使用bin()函数转成二进制字符串，再用count('1')得到1的个数。
n = int(input())
s2 = bin(n)
cnt = s2.count('1')第三种，Brian Kernighan算法，又称B&K算法，这个算法很精妙，采用n & (n-1)的方式快速计算得到二进制中1的计数。其实很多精妙的算法都在做位运算，比如异或2次，比如左移、右移，这个我们以前可能接触的很少，但以后很可能经常用到。
cnt = 0
while n:n &= n-1cnt += 1
print(cnt)至此，先完成1~15的练习和整理，后面的题目接着看视频、接着练~