筆試題:兩個整數集合A和B,求其交集
兩個整數集合A和B,求其交集。
分析:
1. 讀取整數集合A中的整數,將讀到的整數插入到map中,並將對應的值設為1。
2. 讀取整數集合B中的整數,如果該整數在map中並且值為1,則將此數加入到交集當中,並將在map中的對應值改為2。
通過更改map中的值,避免了將同樣的值輸出兩次。
筆試題:找出1到10w中沒有出現的兩個數字
分析:
有1到10w這10w個數,去除2個並打亂次序,如何找出那兩個數?
申請10w個bit的空間,每個bit代表一個數字是否出現過。
開始時將這10w個bit都初始化為0,表示所有數字都沒有出現過。
然後依次讀入已經打亂循序的'數字,並將對應的bit設為1。
當處理完所有數字後,根據為0的bit得出沒有出現的數字。
首先計算1到10w的和,平方和。
然後計算給定數字的和,平方和。
兩次的到的數字相減,可以得到這兩個數字的和,平方和。
所以我們有
x + y = n
x^2 + y^2 = m
解方程可以得到x和y的值。