python每日經典演算法題5(基礎題)+1(較難題)

一：基礎演算法題5道

1.阿姆斯特朗數

如果一個n位正整數等於其各位數字的n次方之和,則稱該數為阿姆斯特朗數。判斷用戶輸入的數字是否為阿姆斯特朗數。

(1)題目分析：這裡要先得到該數是多少位的，然後再把每一位的數字截取出來，把各位數字的n次方之和和該數一起判斷即可。
(2)演算法分析：python中有len()函數可以得到一個字元串的長度，因此需要先把一個正整數轉化為正整數字元串。然後從高位向低位截取(也可以反過來)。或者高效演算法利用for迴圈切片。

從高位到低位：用正整數除了10的n次方，得到的商就是高位的數，餘數就是下次迴圈的數。

從低位到高位：用正整數除以10，得到的餘數就是低位的數，商就是下次迴圈的數。

for迴圈：用for迴圈依次得到每一位數。就是可迭代對象依次顯示。

(3)用到的python語法：while迴圈，for迴圈，if語句，函數。

(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('該數是阿姆斯特朗數')
    else:
        print('該數不是阿姆斯特朗數')


num = int(input('請輸入一個整數:'))
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('該數是阿姆斯特朗數')
    else:
        print('該數不是阿姆斯特朗數')


num = int(input('請輸入一個整數:'))
judge(num)

(5)高效方法：

for迴圈：

def judge(num):
    n = len(num)
    sum = 0
    for i in num:
        sum += int(i) ** n
    if sum == int(num):
        print('該數是阿姆斯特朗數')
    else:
        print('該數不是阿姆斯特朗數')


num = input('請輸入一個整數:')
judge(num)

2.整數數組

給定一個整數數組，判斷是否存在重覆元素。

(1)題目分析：利用list的內置函數count計算每一個元素的數量，時間會很多，內置函數list.count(i)時間複雜度為O(n) 外面嵌套一層迴圈，總的時間為O(n^2)，不是一個高效演算法。

可以排序後對相鄰元素判斷是否相等。還有一個方法是利用set()特性進行判斷。

(2)演算法分析：根據上面的題目分析用高效一點的演算法展示。
(3)用到的python語法：
(4)博主答題代碼：

def judgeInt(num):
    this_set = set(num)
    if len(this_set) == len(num):
        print('沒有重覆')
    else:
        print('有重覆')


my_num = input('請輸入一個整數:')
judgeInt(my_num)

3.迴文數

判斷一個整數是否是迴文數。

(1)題目分析：迴文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。

(2)演算法分析：可以利用python的切片很方便地解決該問題，但是如果是其它語言的話，沒有切片。因此需要考慮普遍的方法。

演算法分析如下：

可以看到，我們根據兩種不同情況分析，即可得結果。

(3)用到的python語法：if判斷語句，切片，函數。
(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('請輸入一個整數:')
if judge(num):
    print('{0}是迴文數'.format(num))
else:
    print('{0}不是迴文數'.format(num))

(5)高效方法：

def judge(x):
    return str(x) == str(x)[::-1]


num = input('請輸入一個整數:')
if judge(num):
    print('{0}是迴文數'.format(num))
else:
    print('{0}不是迴文數'.format(num))

只需要一行代碼即可以判斷，這就是切片的好處。

是不是很簡單呢。

4.迴文數進階演算法，不限轉化為字元串

       那有沒有什麼不需要先轉化為字元串的方法呢？也是有的。可以利用前面的阿姆斯特朗數從高位到低位和從低位到高位獲取兩個列表或者字典進行比較，這裡就不分析了，直接上代碼：

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('請輸入一個整數:'))
if judge(num):
    print('{0}是迴文數'.format(num))
else:
    print('{0}不是迴文數'.format(num))

效率確實很低。

5.插入排序

 對於未排序數組，在已排序序列中從前向後或從後向前掃描，找到相應位置並插入。

(1)題目分析：這是個簡單的演算法，只需要把要每個元素依次和相鄰的元素比較即可。

(2)演算法分析：想用一個變數標記遍歷到的元素，然後，有兩種方法。

從後先前，把該元素和左邊的元素進行對比，如果比左邊的元素小，就互換，當左邊的元素的編號為-1時停止。

從前先後，把該元素和右邊的元素進行對比，如果比右邊的元素大，就互換，當右邊的元素的編號為數組的長度減1時停止。

(3)用到的python語法：while迴圈，函數，數據交換。

(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('請輸入數組:').split(',')))
insert(my_arr)
print(my_arr)

(5)高效代碼

用python的列表排序函數sort()可以很方便進行排序。

二：較難演算法題1道

這些等到下一篇博客會詳細講解。

1.串聯所有單詞的字串

給定一個字元串 s 和一些長度相同的單詞 words。找出 s 中恰好可以由 words 中所有單詞串聯形成的子串的起始位置。

註意子串要與 words 中的單詞完全匹配，中間不能有其他字元，但不需要考慮 words 中單詞串聯的順序。

2.解數獨

編寫一個程式，通過已填充的空格來解決數獨問題。

空白格用 '.' 表示。

較難演算法題等到之後博客會詳細講解。