刷題是必須的，通過刷題以及別人對題目的解析，可以快速理解，提高效率。
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的練習和整理，后面的題目接著看視頻、接著練~
)
)
