現在，越來越多的公司面試以及考驗面試對算法要求都提高了一個層次，從現在，我講每日抽出時間進行5+1算法題講解，5是指基礎題，1是指1道中等偏難。希望能夠讓大家熟練掌握python的語法結構已經一些高級函數的應用。這些題目是在某些刷題的網站上登記的有水平的題目。這里如果有需要input的簡單題，就略去了輸出結果。如果時間充裕，則就會增加每日更多習題。
?
一：基礎算法題5道
1.判斷用戶輸入的年份是否為閏年
題目解析:
(1)問題分析： 能被4整除但不能被100整除的年份為普通閏年，能被400整除的年份為世紀閏年，判斷是否滿足上述情況 。
(2)算法分析：輸入一個數，先判斷如果是400的倍數，則滿足；如果不是400的倍數，再判斷如果該數能夠被4整除，卻不能被100整除，則滿足。
(3)用到的python語法：input()標準輸入函數，if判斷語句，or，and邏輯運算符。
(4)博主答題代碼：
n = int(input(
'
請輸入年份:
'
))
if
n % 400 == 0
or
n % 4 == 0
and
n % 100 !=
0:
print
(
'
{0}是閏年
'
.format(n))
else
:
print
(
'
{0}不是閏年
'
.format(n))
(5)高效方法：
python 的 calendar 庫中已經封裝好了一個方法 isleap() 來實現這個判斷是否為閏年：
import
calendar
n
= int(input(
"
請輸入年份：
"
))
year
=
calendar.isleap(n)
if
year ==
True:
print
(
"
{0}是閏年
"
.format(n))
else
:
print
(
"
{0}不是閏年
"
.format(n))
?
2.判斷一個數是否是質數
題目解析:
(1)問題分析： 除了1和它本身以外不再有其他的因數的數就是質數 。
(2)算法分析：輸入一個數，如果該數大于1，則從2開始循環到該數并一一整除該數，如果余數為0，則該數不是質數；否則該數是質數。
(3)用到的python語法：input()標準輸入函數，for循環，if判斷語句。
(4)博主答題代碼：
n = int(input(
''
))
if
n > 1
:
for
i
in
range(2
,n):
if
n % i ==
0:
print
(
'
{0}不是質數
'
.format(n))
print
(
'
{n}={a}*{b}
'
.format(n=n,a=i,b=int(n/i)))
#
這里也可為b=n//i
break
else
:
print
(
'
{0}是質數
'
.format(n))
break
這時如果想把非質數的所有非1與自己的因數輸出，則可以改為如下代碼：
n = int(input(
''
))
if
n > 1
:
m1
= 0;m2 =
0
for
i
in
range(2
,n):
if
n % i ==
0:
str
=
'
{0}不是質數
'
.format(n)
print
(
'
{n}={a}*{b}
'
.format(n=n,a=i,b=int(n/i)))
#
這里也可為b=n//i
m1 = 1;m2 = 1
elif
m1==
0:
print
(
'
{0}是質數
'
.format(n))
break
if
[m1,m2].count(1) == 2
:
print
(
'
{0}不是質數
'
.format(n))
(5)高效方法：
num = int(input(
""
))
i
= 2
while
i <
num:
s
= num %
i
if
s ==
0:
break
else
:
i
+= 1
if
num ==
i:
print
(
"
{0}是質數
"
.format(num))
else
:
print
(
"
{0}不是質數
"
.format(num))
?
3.輸出指定范圍內的素數
(1)題目分析：
素數就是質，上一題已經介紹了如何求質數，這里我們需要加一個范圍
。
(2)算法分析：把上一題判斷的內容放在一個for循環選擇范圍里進行分析。
(3)用到的python語法：input()標準輸入函數，map函數，for循環，if判斷語句。
(4)博主答題代碼：
my_index1,my_index2 = map(int,input(
'
請選擇一個范圍:
'
).split(
'
,
'
))
result
=
[]
for
num
in
range(my_index1,my_index2+1
):
if
num > 1
:
for
i
in
range(2
,num):
if
(num % i) ==
0:
break
else
:
result.append(num)
print
(
'
{a}到{b}所有的質數有:{c}
'
.format(a = my_index1,b = my_index2,c = result))
這里的if和else是就近匹配，和上面的不同，這就避免了重復，這是要注意的一點。
展示這是最簡單的方法，如果大家有好的方法，請評論。
?
4.約瑟夫生者死者小游戲
30 個人在一條船上，超載，需要 15 人下船。
于是人們排成一隊，排隊的位置即為他們的編號。
報數，從 1 開始，數到 9 的人下船。
如此循環，直到船上僅剩 15 人為止，問都有哪些編號的人下船了呢？
這一題可以擴展為：
m個人在一條船上，超載，需要n人下船。
于是人們排成一隊，排隊的位置即為他們的編號。
報數，從 1 開始，數到 k 的人下船。
如此循環，直到船上僅剩 m - n人為止，問都有哪些編號的人下船了呢？
(1)題目分析：
(2)算法分析：這里設置編號從1開始，先給出從1到m的所有編號，用一個列表表示，需要n個人下船，則船上就生了m-n個人。以此循環遞歸，其實也可以轉化為遞歸問題。但這里每次遞歸，當找到數到編號k，就把編號k所在的序號，就是編號刪除。這里可以設置一個外部變量，從第一個編號index開始，當index=k時，把編號重新置為1，每次都這樣，直到循環完畢，直到所有最后剩余元素個數為m-n。
(3)用到的python語法：for循環，函數，列表操作，列表切片。
(4)博主答題代碼：
?
def
yueSeFu(m,n,k):
serial_num
= list(range(1,m +1))
#
創建從1到m的序號
index = 0
#
設置外部變量index
while
len(serial_num) > m - n:
#
當最后剩余人數為m - n之前，一直進行下面的程序
for
i
in
serial_num:
#
遍歷每個編號
index += 1
#
把外部變量index進行真實遍歷
if
index == k:
#
當外部變量index找到k時，進行下面代碼塊的操作
serial_num.remove(i)
#
移除需要下船的人的編號
index = 1
#
這時候index已經找到序號k了，就要重新遍歷
print
(
'
{0}號人下船了
'
.format(i))
if
__name__
==
'
__main__
'
:
#
傳入起始人數m，需要下船的人數n，數到多少下船的序號k,這里可自行設置
yueSeFu(30,15,9)
(5)高效方法：
def
yueSeFu(m,n,k):
people
= list(range(1, m+1
))
i
=
0
while
len(people) > m -
n:
i
+= (k - 1
)
if
i >=
len(people):
i
-=
len(people)
print
(
"
{}號下船了
"
.format(people[i]))
del
people[i]
if
__name__
==
'
__main__
'
:
#
傳入起始人數m，需要下船的人數n，數到多少下船的序號k
yueSeFu(30,15,9)
?
5.二分查找，返回某個值在數組中的索引
(1)題目分析：二分搜索是一種在有序數組中查找某一特定元素的搜索算法。從數組的中間元素開始，正好是要查找的元素，則搜索過程結束；如果某一特定元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。
(2)算法分析：這里重復查找需要用到遞歸，用到一個一維數組，先判斷數組查找的元素末尾下標是否大于等于1。如果是的話，就要先找到中間位置，如果大于中間位置，就只比較左邊的元素重新遞歸；如果小于中間位置，則比較右邊的元素重新遞歸。找不到就返回-1。
(3)用到的python語法：if判斷語句，函數，遞歸算法。
(4)博主答題代碼：
def
twoSearch(x,arr,begin,end):
#
x為要查詢的元素,arr為數組,begin和and是每次查找的范圍
if
end >= 1
:
mid
= int(begin + (end-1)/2)
#
每次范圍的元素中間位置
if
int(arr[mid]) ==
x:
return
mid
elif
int(arr[mid]) > x:
#
元素小于中間的元素，需要比較左邊的元素
return
twoSearch(x,arr,begin,end - 1
)
else
:
#
元素大于中間的元素，需要比較右邊的元素
return
twoSearch(x,arr,begin + 1
,end)
else
:
return
-1
if
__name__
==
'
__main__
'
:
my_arr
= list(map(int,input(
'
請輸入數組:
'
).split(
'
,
'
)))
#
返回可迭代對象
my_x = int(input(
'
請輸入要查找的元素:
'
))
result
= twoSearch(my_x, my_arr, 0, len(my_arr) - 1
)
if
result != -1
:
print
(
'
元素在數組中的索引為:{0}
'
.format(result))
else
:
print
(
'
元素不在數組中
')
?
二：中等算法題1道
1.兩數之和
給定一個整數數組?
nums
?和一個目標值?
target
，請你在該數組中找出和為目標值的那?兩個?整數，并返回他們的數組下標。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
(1)算法解析：
我們給出一個列表，進行兩次循環，就可以得到結果
。
(2)博主代碼：
def
twoSum(nums, target):
for
index1,i
in
enumerate(nums):
for
index2,j
in
enumerate(nums):
if
i+j == target
and
i !=
j:
return
index1,index2
a
= list(map(int,input().split(
'
,
'
)))
b
=
int(input())
print
(list(twoSum(a,b)))
主要代碼為：
for
index1,i
in
enumerate(nums):
for
index2,j
in
enumerate(nums):
if
i+j == target
and
i !=
j:
return
index1,index2
(3)代碼問題
但是在運行很多個數字的列表中，需要兩次循環遍歷列表，如果列表的長度為n，則時間復雜度為O(n)，時間執行效率太差，最差為O(n^2)，故上面的代碼實際上是不太可取的。
(4)高級算法
下面有一些改進的高級一點的算法：
列表生成式三行代碼搞定：
for
i
in
range(len(nums)):
#
循環遍歷列表
#
這里是用和減去列表中的某一元素，并且兩個元素下標不同，就返回兩個下標
if
(target-nums[i]
in
nums
and
i != nums.index(target-
nums[i])):
return
[i,nums.index(target-nums[i])]
執行用時 :1284ms，內存消耗 :14.7MB左右，比上面的代碼節省了一層循環遍歷的過程。
字典查找，利用哈希表，不用遍歷：
my_dict = {}
#
創建一個字典
for
index, num1
in
enumerate(nums):
#
利用函數enumerate輸出列表或數組的下標和元素
num2 = target - num1
#
另一個元素
#
這里是判斷，如果字典中有另一個元素值的話，返回下標，以及該元素下標
#
這里由于字典是鍵值對，就避免了兩個元素和符合，單元素是同一個元素的情況
if
num2
in
my_dict:
return
[my_dict[num2], index]
#
把字典中的元素對應于鍵
my_dict[num1] =
index
return
-1
執行用時 :68ms，內存消耗 :15 MB左右，時間效率更高。
利用集合進行操作，效率和字典差不多：
my_set =
set(nums)
for
i, v
in
enumerate(nums):
if
(target - v)
in
my_set
and
i != nums.index(target -
v):
return
[i, nums.index(target - v)]
執行用時 :80ms，內存消耗 :15 .2MB左右。
?
總結：
1.用python字典或集合的效率要高很多，不建議常用列表。
2.生成一個整數序列可以先生成一個可迭代對象
比如生成一個只有整數的可迭代對象：
map(int,input('請選擇一個范圍:').split(','))
3.calendar.isleap(n可以判斷是否為閏年。
4.列表生成式常用可以減少代碼量，當然是有必要用列表的時候。
5.enumerate對既需要元素和下標值的序列很有用。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
