一：基礎(chǔ)算法題5道
1.阿姆斯特朗數(shù)
如果一個(gè)n位正整數(shù)等于其各位數(shù)字的n次方之和,則稱該數(shù)為阿姆斯特朗數(shù)。判斷用戶輸入的數(shù)字是否為阿姆斯特朗數(shù)。
(1)題目分析：
這里要先得到該數(shù)是多少位的，然后再把每一位的數(shù)字截取出來(lái)，把各位數(shù)字的n次方之和和該數(shù)一起判斷即可
。
(2)算法分析：python中有l(wèi)en()函數(shù)可以得到一個(gè)字符串的長(zhǎng)度，因此需要先把一個(gè)正整數(shù)轉(zhuǎn)化為正整數(shù)字符串。然后從高位向低位截取(也可以反過(guò)來(lái))。或者高效算法利用for循環(huán)切片。
從高位到低位： 用正整數(shù)除了10的n次方，得到的商就是高位的數(shù)，余數(shù)就是下次循環(huán)的數(shù)。
從低位到高位： 用正整數(shù)除以10，得到的余數(shù)就是低位的數(shù)，商就是下次循環(huán)的數(shù)。
for循環(huán)： 用for循環(huán)依次得到每一位數(shù)。就是可迭代對(duì)象依次顯示。
(3)用到的python語(yǔ)法：while循環(huán)，for循環(huán)，if語(yǔ)句，函數(shù)。
(4)博主答題代碼：
從高位到低位：
def
judge(num):
mysum
=
0
n
= len(str(num)) - 1
m
= n + 1
firstNum
=
num
while
num >
0:
quotient
= num // (10**
n)
remainder
= num % (10**
n)
mysum
+= quotient **
m
num
=
remainder
n
-= 1
if
mysum ==
firstNum:
print
(
'
該數(shù)是阿姆斯特朗數(shù)
'
)
else
:
print
(
'
該數(shù)不是阿姆斯特朗數(shù)
'
)
num
= int(input(
'
請(qǐng)輸入一個(gè)整數(shù):
'
))
judge(num)
從低位到高位：
def
judge(num):
mysum
=
0
n
= len(str(num)) - 1
m
= n + 1
firstNum
=
num
while
num >
0:
quotient
= num // 10
remainder
= num % 10
mysum
+= remainder **
m
num
=
quotient
n
-= 1
if
mysum ==
firstNum:
print
(
'
該數(shù)是阿姆斯特朗數(shù)
'
)
else
:
print
(
'
該數(shù)不是阿姆斯特朗數(shù)
'
)
num
= int(input(
'
請(qǐng)輸入一個(gè)整數(shù):
'
))
judge(num)
(5)高效方法：
for循環(huán)：
def
judge(num):
n
=
len(num)
sum
=
0
for
i
in
num:
sum
+= int(i) **
n
if
sum ==
int(num):
print
(
'
該數(shù)是阿姆斯特朗數(shù)
'
)
else
:
print
(
'
該數(shù)不是阿姆斯特朗數(shù)
'
)
num
= input(
'
請(qǐng)輸入一個(gè)整數(shù):
'
)
judge(num)
?
?
2.整數(shù)數(shù)組
給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素。
(1)題目分析： 利用list的內(nèi)置函數(shù)count計(jì)算每一個(gè)元素的數(shù)量，時(shí)間會(huì)很多，內(nèi)置函數(shù)list.count(i)時(shí)間復(fù)雜度為O(n) 外面嵌套一層循環(huán)，總的時(shí)間為O(n^2)，不是一個(gè)高效算法。
可以排序后對(duì)相鄰元素判斷是否相等。還有一個(gè)方法是利用set()特性進(jìn)行判斷。
(2)算法分析：根據(jù)上面的題目分析用高效一點(diǎn)的算法展示。
(3)用到的python語(yǔ)法：
(4)博主答題代碼：
def
judgeInt(num):
this_set
=
set(num)
if
len(this_set) ==
len(num):
print
(
'
沒(méi)有重復(fù)
'
)
else
:
print
(
'
有重復(fù)
'
)
my_num
= input(
'
請(qǐng)輸入一個(gè)整數(shù):
'
)
judgeInt(my_num)
?
?
3.回文數(shù)
判斷一個(gè)整數(shù)是否是回文數(shù)。
(1)題目分析： 回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù) 。
(2)算法分析： 可以利用python的切片很方便地解決該問(wèn)題，但是如果是其它語(yǔ)言的話，沒(méi)有切片。因此需要考慮普遍的方法 。
算法分析如下：
可以看到，我們根據(jù)兩種不同情況分析，即可得結(jié)果。
(3)用到的python語(yǔ)法：if判斷語(yǔ)句，切片，函數(shù)。
(4)博主答題代碼：
def
judge(x):
this_str
=
str(x)
if
len(this_str) % 2 !=
0:
mid
= int((len(this_str) + 1 ) / 2 - 1
)
left
= mid - 1
right
=
mid
if
this_str[0:left+1] == this_str[-1:right:-1
]:
return
True
else
:
return
False
if
len(this_str) % 2 ==
0:
mid
= int(len(this_str)/2) - 1
if
this_str[0:mid+1] == this_str[-1:mid:-1
]:
return
True
else
:
return
False
num
= input(
'
請(qǐng)輸入一個(gè)整數(shù):
'
)
if
judge(num):
print
(
'
{0}是回文數(shù)
'
.format(num))
else
:
print
(
'
{0}不是回文數(shù)
'
.format(num))
(5)高效方法：
def
judge(x):
return
str(x) == str(x)[::-1
]
num
= input(
'
請(qǐng)輸入一個(gè)整數(shù):
'
)
if
judge(num):
print
(
'
{0}是回文數(shù)
'
.format(num))
else
:
print
(
'
{0}不是回文數(shù)
'
.format(num))
只需要一行代碼即可以判斷，這就是切片的好處。
是不是很簡(jiǎn)單呢。
?
?
4.回文數(shù)進(jìn)階算法，不限轉(zhuǎn)化為字符串
? ? ? ?那有沒(méi)有什么不需要先轉(zhuǎn)化為字符串的方法呢？也是有的?？梢岳们懊娴陌⒛匪固乩蕯?shù)從高位到低位和從低位到高位獲取兩個(gè)列表或者字典進(jìn)行比較，這里就不分析了，直接上代碼：
def
judge(num1):
if
'
-
'
in
str(num1):
return
False
if
num1 >= 0
and
num1 < 10
:
return
True
list1
= [];list2 =
[]
num2
=
num1
n1
= len(str(num1)) - 1
n2
= len(str(num2)) - 1
while
num1 >
0:
quotient1
= num1 // (10**
n1)
remainder1
= num1 % (10**
n1)
list1.append(quotient1)
num1
=
remainder1
n1
-= 1
while
num2 >
0:
quotient2
= num2 // 10
remainder2
= num2 % 10
list2.append(remainder2)
num2
=
quotient2
n2
-= 1
num
=
0
for
i
in
range(0,len(list1)):
if
list2[i] ==
list1[i]:
num
+= 1
if
num ==
len(list1):
return
True
else
:
return
False
num
= int(input(
'
請(qǐng)輸入一個(gè)整數(shù):
'
))
if
judge(num):
print
(
'
{0}是回文數(shù)
'
.format(num))
else
:
print
(
'
{0}不是回文數(shù)
'
.format(num))
效率確實(shí)很低。
?
?
5.插入排序
?對(duì)于未排序數(shù)組，在已排序序列中從前向后或從后向前掃描，找到相應(yīng)位置并插入。
(1)題目分析： 這是個(gè)簡(jiǎn)單的算法，只需要把要每個(gè)元素依次和相鄰的元素比較即可 。
(2)算法分析：想用一個(gè)變量標(biāo)記遍歷到的元素，然后，有兩種方法。
從后先前，把該元素和左邊的元素進(jìn)行對(duì)比，如果比左邊的元素小，就互換，當(dāng)左邊的元素的編號(hào)為-1時(shí)停止。
從前先后，把該元素和右邊的元素進(jìn)行對(duì)比，如果比右邊的元素大，就互換，當(dāng)右邊的元素的編號(hào)為數(shù)組的長(zhǎng)度減1時(shí)停止。
(3)用到的python語(yǔ)法：while循環(huán)，函數(shù)，數(shù)據(jù)交換。
(4)博主答題代碼：
def
insert(arr):
for
i
in
range(1
,len(arr)):
j
=
i
while
j >
0:
if
arr[j] < arr[j-1
]:
arr[j
-1],arr[j] = arr[j],arr[j-1
]
j
-= 1
my_arr
= list(map(int,input(
'
請(qǐng)輸入數(shù)組:
'
).split(
'
,
'
)))
insert(my_arr)
print
(my_arr)
(5)高效代碼
用python的列表排序函數(shù)sort()可以很方便進(jìn)行排序。
?
二：較難算法題1道
這些等到下一篇博客會(huì)詳細(xì)講解。
1.串聯(lián)所有單詞的字串
給定一個(gè)字符串?s?和一些長(zhǎng)度相同的單詞?words。找出 s 中恰好可以由?words 中所有單詞串聯(lián)形成的子串的起始位置。
注意子串要與?words 中的單詞完全匹配，中間不能有其他字符，但不需要考慮?words?中單詞串聯(lián)的順序。
?
2.解數(shù)獨(dú)
編寫(xiě)一個(gè)程序，通過(guò)已填充的空格來(lái)解決數(shù)獨(dú)問(wèn)題。
空白格用?
'.'
?表示。
?
較難算法題等到之后博客會(huì)詳細(xì)講解。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
