線上筆試題
-
-
- 1、移動零
- 2、尋找重複數
- 3、Nim 遊戲
- 4、判斷子序列
- 5、至少有K個重複字元的最長子串
- 6、移掉K位數字
- 7、根據身高重建隊列
- 8、回旋镖的數量
- 9、用最少數量的箭引爆氣球
- 10、可憐的小豬
-
1、移動零
給定一個數組 nums，編寫一個函數将所有 0 移動到數組的末尾，同時保持非零元素的相對順序
示例
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:必須在原數組上操作，不能拷貝額外的數組。盡量減少操作次數
方法一 ：覆寫法
定義兩個指針 i,j 如果前面指針不等于0則後面的值覆寫前面的值，最後再把 0 補回去
def moveZeroes(self, nums: List[int]) -> None:
j = 0
for i in range(len(nums)):
if nums[i] !=0:
nums[j] = nums[i]
j+=1
while j< len(nums):
nums[j] = 0
j+=1
方法二：對方法一進行優化，但本質依然是兩個指針
void moveZeroes(vector<int>& nums) {
int i = 0;
int count = 0;
for(;i<nums.size();++i){
if(nums[i] !=0){
swap(nums[count++],nums[i]);
}
}
}
方法三：python 版本，利用删除和尾加
def moveZeroes(self, nums):
n = nums.count(0)
for i in range(n):
nums.remove(0)
nums.append(0)
2、尋找重複數
給定一個包含 n + 1 個整數的數組 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重複的整數。假設隻有一個重複的整數，找出這個重複的數。
示例 1:
輸入: [1,3,4,2,2]
輸出: 2
示例 2:
輸入: [3,1,3,4,2]
輸出: 3
說明：
(1)不能更改原數組（假設數組是隻讀的）
(2)隻能使用額外的 O(1) 的空間
(3)時間複雜度小于 O(n2)
(4)數組中隻有一個重複的數字，但它可能不止重複出現一次
方法一：首先利用庫函數進行排序，然後利用判斷前一個數字和後一個是否相等，如果相等則傳回它
def findDuplicate(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
for i in range(1,n):
if nums[i] == nums[i-1]:
return nums[i]
方法二：直接利用 sum 求和函數和 set 去重函數
方法三：可以用 O(N) 的時間複雜度完成
思路：周遊數組，如果發現下标對應的資料和目前資料相等，則傳回這個數字，如果不相等，則把該數字和它對應的下标數字進行交換.
def findDuplicate(self, nums: List[int]) -> int:
n = len(nums)
i = 0
while i<n:
if nums[i] != i:
if nums[nums[i]] == nums[i]:
return nums[i]
else:
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
else:
i += 1
方法四：始終和第一個數字進行交換判斷，因為數組中沒有 0 元素，是以不用害怕在 0 的位置上有 0 元素
int findDuplicate(vector<int>& nums) {
while(1){
int num = nums[0];
if(nums[num]==num){
return num;
}
nums[0] = nums[num];
nums[num] = num;
}
}
方法五：把目前元素對應的下标設為負，如果已經是負數了，則說明有一個數把它變為負數了，那麼就傳回目前元素的絕對值
int findDuplicate(vector<int>& nums) {
for(int i = 0;i<nums.size();++i){
// 有元素已經設為負了，就傳回目前元素絕對值
if(nums[abs(nums[i])] < 0){
return abs(nums[i]);
}else{
nums[abs(nums[i])] = -nums[abs(nums[i])];
}
}
return -1;
}
方法六：二分查找，不過從效率來看，沒有前面的方法高
int findDuplicate(vector<int>& nums) {
int low = 0;
int hight = nums.size()-1;
while(low<hight){
int mid = (low+hight)/2;
int count = 0;
for(int i = 0;i<nums.size();++i){
if(nums[i]<=mid){
count+=1;
}
}
if(count<=mid){
low = mid+1;
}else{
hight = mid;
}
}
return low;
}
3、Nim 遊戲
你和你的朋友，兩個人一起玩 Nim 遊戲：桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭，拿掉最後一塊石頭的人就是獲勝者。你作為先手
你們是聰明人，每一步都是最優解。 編寫一個函數，來判斷你是否可以在給定石頭數量的情況下赢得遊戲
輸入: 4
輸出: false
解釋: 如果堆中有 4 塊石頭，那麼你永遠不會赢得比賽；
因為無論你拿走 1 塊、2 塊 還是 3 塊石頭，最後一塊石頭總是會被你的朋友拿走
思路：該你拿的時候，隻要讓棋子變為 4 的倍數即可，例如：現在有5個棋子，你拿一個，剩下4個，對方就必輸無疑，因為對方最多拿3個，而無論他怎麼拿，你最後都能拿走最後的棋子，是以想要赢，讓對方拿的時候，棋子是4的倍數即可… 我忽然想到可以套路一波女朋友了…哈哈哈
def canWinNim(self, n: int) -> bool:
if n % 4 == 0:
return False
return True
4、判斷子序列
給定字元串 s 和 t ，判斷 s 是否為 t 的子序列
你可以認為 s 和 t 中僅包含英文小寫字母。字元串 t 可能會很長（長度 ~= 500,000），而 s 是個短字元串（長度 <=100)
字元串的一個子序列是原始字元串删除一些（也可以不删除）字元而不改變剩餘字元相對位置形成的新字元串
例如，"ace"是"abcde"的一個子序列，而"aec"不是
示例1
s = “abc”, t = “ahbgdc”
傳回 true.
示例2
s = “axc”, t = “ahbgdc”
傳回 false.
方法一：C++版本
時間複雜度是O(N)，思路比較明晰，隻要最後 s[i] 走到結尾就說明存在子串，否則不存在
bool isSubsequence(string s, string t) {
int n = s.size();
int m = t.size();
int i = 0;
int j = 0;
while(i<n && j<m){
if(s[i]==t[j]){
++i;
}
++j;
}
if(s[i] == '\0'){
return true;
}else{
return false;
}
// return i == s.size();
}
方法二：python 版本
def isSubsequence(self, s: str, t: str) -> bool:
# iter 是定義一個疊代器
# 如果s中所有的字元都存在于 t中，則傳回True
# 疊代器的作用就是隻能往前尋找，找過的位置，不能找了
t = iter(t)
return all(c in t for c in s)
方法三：建立一個大型矩陣，然後在這個矩陣中進行查找，當然這種方法是比較慢的，時間都用在建立矩陣的方法上，但是對于查詢來說是非常快的，對于海量資料來說，這種方法很适用了
如下圖，數字代表字元在字元串 t 的位置，-1代表的是接下來不會出現該字元
bool isSubsequence(string s, string t) {
// 步驟一：初始化矩陣
t.insert(t.begin(),' ');
int len1 = s.size(), len2 = t.size();
vector<vector<int> > dp(len2 , vector<int>(26, 0));
for (char c = 'a'; c <= 'z'; c++) {
int nextPos = -1; //表示接下來再不會出現該字元
for (int i = len2 - 1; i>= 0; i--) {
//為了獲得下一個字元的位置，要從後往前
dp[i][c - 'a'] = nextPos;
if (t[i] == c)
nextPos = i;
}
}
// 程序查詢
int index = 0;
for (char c : s) {
index = dp[index][c - 'a'];
if (index == -1)
return false;
}
return true;
}
5、至少有K個重複字元的最長子串
找到給定字元串（由小寫字元組成）中的最長子串 T ， 要求 T 中的每一字元出現次數都不少于 k 。輸出 T 的長度
示例1
輸入:
s = “aaabb”, k = 3
輸出:
3
最長子串為 “aaa” ，其中 ‘a’ 重複了 3 次
示例2
輸入:
s = “ababbc”, k = 2
輸出:
5
最長子串為 “ababb” ，其中 ‘a’ 重複了 2 次， ‘b’ 重複了 3 次
思路：標明字元進行分割字元串，若一個字元出現的總次數小于k，它一定不在子串裡，用它作為界限去分割
def longestSubstring(self, s: str, k: int) -> int:
if len(s)<k:
return 0
# 計算出次數出現最少的字元
c = min(set(s),key=s.count)
# 如果連最少次數的字元都大于 k 了，是以就傳回整個字元串大小
if s.count(c)>=k:
return len(s)
res = 0
# 針對最小字元進行分割，因為它一定不會被傳回的整數計算在内
for t in s.split(c):
m = self.longestSubstring(t,k)
res = max(m,res)
return res
6、移掉K位數字
給定一個以字元串表示的非負整數 num，移除這個數中的 k 位數字，使得剩下的數字最小
示例1
輸入: num = “1432219”, k = 3
輸出: “1219”
解釋: 移除掉三個數字 4, 3, 和 2 形成一個新的最小的數字 1219。
示例2
輸入: num = “10200”, k = 1
輸出: “200”
解釋: 移掉首位的 1 剩下的數字為 200. 注意輸出不能有任何前導零。
示例3
輸入: num = “10”, k = 2
輸出: “0”
解釋: 從原數字移除所有的數字，剩餘為空就是0
思路：周遊字元串，若 num[i] 大于棧頂元素，則num[i]入棧，若num[i]小于棧頂元素，棧頂元素依次出棧，直到棧頂元素小于num[i]或者出棧的總次數大于k。出棧的過程就是移掉數字的過程
def removeKdigits(self, num: str, k: int) -> str:
if len(num)==k:
return '0'
stack = ['0']
i = count = 0
while count < k and i<len(num):
if num[i]<stack[-1]:
while num[i]<stack[-1]:
stack.pop(-1)
count+=1
if count==k:
break
stack = stack+[num[i]]
i+=1
# 把 temp 剩下的值也都轉移到stack
stack +=num[i:]
# 如果彈出的元素次數小于k,則直接尾删除
# 因為stack中的元素都是遞增式的
m = k - count
while m:
stack.pop(-1)
m-=1
# 去掉左邊的'0'字元
string = ''.join(stack).lstrip('0')
return '0' if string == '' else string
7、根據身高重建隊列
假設有打亂順序的一群人站成一個隊列。 每個人由一個整數對(h, k)表示，其中h是這個人的身高，k是排在這個人前面且身高大于或等于h的人數。 編寫一個算法來重建這個隊列
注意：總人數少于 1100 人
示例
輸入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
輸出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
思路：首先這個題目是很難讀懂的，說的是一種規則，前面的值代表升高，後面的值代表升高的名次，要滿足這種規則。示例中的（4,4）前面沒有4個數，隻有一個（7,0） ，是以說（4,4）放在第二個位置不合适，它也不是放在第四個位置，具體放哪個位置，就要看他前面有沒有比他小的值（升高）.如果有就說明它的下标要大于4，如果沒有(4,4)它就是在第四個位置
解題：按照第一個參數降序，第二個參數升序的規則排好序，示例中經過排序後得到 [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
然後按照第二個參數，插入到一個傳回清單中，我們發現首先插入的大元素，因為插入大元素，即使後面他們的中間有小元素也沒關系，因為他們的升高小，不會破壞規則
python 版本
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 根據第一個參數和第二個參數排序
# 第一個參數按照降序的方式，如果相等了，第二個參數按照升序的方式
# 最後根據排好序的第二個參數進行下标插入
people.sort(key=lambda (h, k): (-h, k))
res = []
for p in people:
res.insert(p[1],p)
return res
C++ 版本
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),\
[](const auto&a,const auto&b){
if(a[0]>b[0]){
return true;
}
if(a[0]==b[0] && a[1]<b[1]){
return true;
}
return false;
});
vector<vector<int>>res;
for(auto&e :people){
res.insert(res.begin()+e[1],e);
}
return res;
}
8、回旋镖的數量
給定平面上 n 對不同的點，“回旋镖” 是由點表示的元組 (i, j, k) ，其中 i 和 j 之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序)
找到所有回旋镖的數量,你可以假設 n 最大為 500，所有點的坐标在閉區間 [-10000, 10000] 中
示例
輸入:
[[0,0],[1,0],[2,0]]
輸出: 2
解釋:
兩個回旋镖為 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
思路 : 以每個點作為第一個點進行考慮，計算到各個點之間的距離，相同距離點對的個數記錄在字典中，k:v = 距離：個數
因為要考慮順序，v 個點的排列有v(v-1)種，累加即可
比如：第二個點到各個點之間的距離是 [1,0,2,3,3,3]
那麼第二個點到第四，五，六個點的距離相等，但是需要選取兩個點，意思就是說，在三個點裡選擇兩個，是以是 3 * 2 種，也就對應上面的公式
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
res = 0
for a in points:
dic = {}
for b in points:
d = (a[0]-b[0])**2+(a[1]-b[1])**2
if d in dic:
dic[d]+=1
else:
dic[d] = 1
# dic[d] = 1 + dic.get(d, 0)
for i in dic:
res+=dic[i]*(dic[i]-1)
return res
C++版本
int numberOfBoomerangs(vector<vector<int>>& points) {
int res = 0;
int n = points.size();
unordered_map<int,int>mp;
for(int i = 0;i<n;++i){
for(int j = 0;j<n;++j){
int a = points[i][0]-points[j][0];
int b = points[i][1]-points[j][1];
int c = a*a+b*b;
mp[c]+=1;
}
for(auto e:mp){
res+=e.second*(e.second-1);
}
mp.clear();
}
return res;
}
9、用最少數量的箭引爆氣球
在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水準方向上，氣球直徑的開始和結束坐标。由于它是水準的，是以y坐标并不重要，是以隻要知道開始和結束的x坐标就足夠了。開始坐标總是小于結束坐标。平面内最多存在104個氣球
一支弓箭可以沿着x軸從不同點完全垂直地射出。在坐标x處射出一支箭，若有一個氣球的直徑的開始和結束坐标為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會被引爆。可以射出的弓箭的數量沒有限制。 弓箭一旦被射出之後，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量
示例
輸入:
[[10,16], [2,8], [1,6], [7,12]]
輸出:
2
解釋:
對于該樣例，我們可以在x = 6（射爆[2,8],[1,6]兩個氣球）和 x = 11（射爆另外兩個氣球）
思路：判斷區間是否重疊？
按照區間的結束點從小到大排序,若第i個區間的起始點小于第i-1個區間的結束點，說明有重疊，可公用一支箭反之，沒有重疊，需要再用一支箭
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
# 對清單的第二個元素進行排序
points = sorted(points,key=lambda x:x[1])
res = 1
end = points[0][1]
for p in range(1,len(points)):
if points[p][0]>end:
res+=1
end = points[p][1]
return res
C++版本
int findMinArrowShots(vector<vector<int>>& points) {
int res = points.size();
sort(points.begin(), points.end());
for (int i = 1; i < points.size(); i++) {
// 如果小于前一個的末尾，則箭少用一支
if (points[i][0] <= points[i - 1][1]) {
// 選出公共區間
points[i] = {
max(points[i - 1][0], points[i][0]),
min(points[i - 1][1], points[i][1])
};
res -= 1;
}
}
return res;
}
10、可憐的小豬
有1000隻水桶，其中有且隻有一桶裝的含有毒藥，其餘裝的都是水。它們從外觀看起來都一樣。如果小豬喝了毒藥，它會在15分鐘内死去。
問題來了，如果需要你在一小時内，弄清楚哪隻水桶含有毒藥，你最少需要多少隻豬？
回答這個問題，并為下列的進階問題編寫一個通用算法。
進階:
假設有 n 隻水桶，豬飲水中毒後會在 m 分鐘内死亡，你需要多少豬（x）就能在 p 分鐘内找出“有毒”水桶？n隻水桶裡有且僅有一隻有毒的桶
提示：
可以允許小豬同時飲用任意數量的桶中的水，并且該過程不需要時間。小豬喝完水後，必須有 m 分鐘的冷卻時間。在這段時間裡，隻允許觀察，而不允許繼續飲水。任何給定的桶都可以無限次采樣（無限數量的豬）
思路：
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
times = minutesToTest/minutesToDie+1
num_pig = 0
while times**num_pig<buckets:
num_pig+=1
return num_pig