最近在學python,網上很難找到對應的演算法題網站,專業演算法網站大部分都是國外的,之前在w3cschool看到有三個級別的Javascript腳本演算法挑戰,嘗試用python實現,代碼量相對比較少,如果你有更好的解法,還請不吝賜教,初學python,希望和大家一起日有所長。 目錄 1.判斷電話號碼算 ...
最近在學python,網上很難找到對應的演算法題網站,專業演算法網站大部分都是國外的,之前在w3cschool看到有三個級別的Javascript腳本演算法挑戰,嘗試用python實現,代碼量相對比較少,如果你有更好的解法,還請不吝賜教,初學python,希望和大家一起日有所長。
目錄
1.判斷電話號碼演算法挑戰
如果傳入字元串是一個有效的美國電話號碼,則返回 true
.
用戶可以在表單中填入一個任意有效美國電話號碼. 下麵是一些有效號碼的例子(還有下麵測試時用到的一些變體寫法):
555-555-5555 (555)555-5555 (555) 555-5555 555 555 5555 5555555555 1 555 555 5555
在本節中你會看見如 800-692-7753
or 8oo-six427676;laskdjf
這樣的字元串. 你的任務就是驗證前面給出的字元串是否是有效的美國電話號碼. 區號是必須有的. 如果字元串中給出了國家代碼, 你必須驗證其是 1
.如果號碼有效就返回 true
; 否則返回 false
.
def telephoneCheck(s): i = 0 for x in s: if x.isdigit(): i += 1 if "(" in s or ")" in s: if "(" not in s or ")" not in s: return False if s[0] == "(" and s[-1] == ")": return False if i == 10: return True elif i == 11: return True if s[0] == "1" else False else: return False print(telephoneCheck("1 555-555-5555")) # 應該返回 true. print(telephoneCheck("1 (555) 555-5555")) # 應該返回 true. print(telephoneCheck("555-555-5555")) # 應該返回 true. print(telephoneCheck("(555)555-5555")) # 應該返回 true. print(telephoneCheck("1(555)555-5555")) # 應該返回 true. print(telephoneCheck("1 555)555-5555")) # 應該返回 false. print(telephoneCheck("123**&!!asdf#")) # 應該返回 false. print(telephoneCheck("(6505552368)")) # 應該返回 false print(telephoneCheck("(275)76227382")) # 應該返回 false.
2.集合交集演算法挑戰
創建一個函數,接受兩個或多個數組,返回所給數組的 對等差分(symmetric difference)(△
or ⊕
)數組.
給出兩個集合 (如集合 A = {1, 2, 3}
和集合 B = {2, 3, 4}
), 而數學術語 "對等差分" 的集合就是指由所有隻在兩個集合其中之一的元素組成的集合(A △ B = C = {1, 4}
). 對於傳入的額外集合 (如 D = {2, 3}
), 你應該安裝前面原則求前兩個集合的結果與新集合的對等差分集合 (C △ D = {1, 4} △ {2, 3} = {1, 2, 3, 4}
).
sym([1, 2, 5], [2, 3, 5], [3, 4, 5])
應該返回 [1, 4, 5]
import functools def sym(*args): def diff(lst1, lst2): lst = [] for i in lst1: if i not in lst2: lst.append(i) for i in lst2: if i not in lst1: lst.append(i) return list(set(lst)) lst = functools.reduce(diff, args) return lst print(sym([1, 2, 3], [5, 2, 1, 4])) # 應該返回 [3, 4, 5]. print(sym([1, 2, 5], [2, 3, 5], [3, 4, 5])) # 應該返回 [1, 4, 5] print(sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5])) # 應該返回 [1, 4, 5]. print(sym([3, 3, 3, 2, 5], [2, 1, 5, 7], [3, 4, 6, 6], [1, 2, 3])) # 應該返回 [2, 3, 4, 6, 7]. print(sym([3, 3, 3, 2, 5], [2, 1, 5, 7], [3, 4, 6, 6], [1, 2, 3], [5, 3, 9, 8], [1])) # 應該返回 [1, 2, 4, 5, 6, 7, 8, 9].
3.收銀系統演算法挑戰
設計一個收銀程式 checkCashRegister()
,其把購買價格(price
)作為第一個參數 , 付款金額 (cash
)作為第二個參數, 和收銀機中零錢 (cid
) 作為第三個參數.
cid
是一個二維數組,存著當前可用的找零.
當收銀機中的錢不夠找零時返回字元串 "Insufficient Funds"
. 如果正好則返回字元串 "Closed"
.
否者, 返回應找回的零錢列表,且由大到小存在二維數組中.
數據轉換有點麻煩,整型和浮點型,字典與列表,解決的關鍵在於面額夠不夠找,找多少張的邏輯判斷,感覺不是很完善,演算法還可以改進。
from math import floor def checkCashRegister(price, cash, cid): num = round(cash - price, 2) # 浮點數精度問題,用round函數精確到分位即可得出金額準確數值 dct = {"PENNY": 0.01, "NICKEL": 0.05, "DIME": 0.1, "QUARTER": 0.25, "ONE": 1, "FIVE": 5, "TEN": 10, "TWENTY": 20, "ONE HUNDRED": 100} dct_rev = {v: k for k, v in dct.items()} # 面額作為鍵,數量作為值,去掉0和大於需找零金額的鍵,得到dct_aftdel dct_aftdel = {dct[i[0]]: round(i[1] / dct[i[0]]) for i in cid if i[1] and dct[i[0]] <= num} sum_all = sum([i[1] for i in cid if dct[i[0]] in dct_aftdel]) if sum_all < num: return "Insufficient Funds" elif sum_all == num: return "Closed" else: print(f"要找{num}元") print(f"從這些錢裡面找:{dct_aftdel}") print(f"這些錢裡面一共有{sum_all}元") dct_return = {} for i in sorted(dct_aftdel, reverse=True): if i <= num: if floor(num / i) <= dct_aftdel[i]: # 例如:要找他90,你有5張20,只需找他4張,如果只有4張,則4張都找給他 dct_return[i] = floor(num / i) # 向下取整 print(f"找了{floor(num / i)}張{i}塊的,還剩", end="") num -= i * floor(num / i) print(f"{round(num, 2)}") num = round(num, 2) # num_temp為浮點型,自減完之後需要分位取整 else: dct_return[i] = dct_aftdel[i] num -= i * dct_aftdel[i] print(f"找了{dct_aftdel[i]}張{i}塊的,還剩{round(num, 2)}") num = round(num, 2) lst_return = [[dct_rev[k], k * v] for k, v in dct_return.items()] return lst_return print(checkCashRegister(19.50, 20.00, [["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.10], ["QUARTER", 4.25], ["ONE", 90.00], ["FIVE", 55.00], ["TEN", 20.00], ["TWENTY", 60.00], ["ONE HUNDRED", 100.00]])) # 應該返回 [["QUARTER", 0.50]]. print(checkCashRegister(3.26, 100.00, [["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.10], ["QUARTER", 4.25], ["ONE", 90.00], ["FIVE", 55.00], ["TEN", 20.00], ["TWENTY", 60.00], ["ONE HUNDRED", 100.00]])) # 應該返回 [["TWENTY", 60.00], ["TEN", 20.00], ["FIVE", 15], ["ONE", 1], ["QUARTER", 0.50], ["DIME", 0.20], ["PENNY", 0.04]]. print(checkCashRegister(19.50, 20.00, [["PENNY", 0.01], ["NICKEL", 0], ["DIME", 0], ["QUARTER", 0], ["ONE", 0], ["FIVE", 0], ["TEN", 0], ["TWENTY", 0], ["ONE HUNDRED", 0]])) # 應該返回 "Insufficient Funds". print(checkCashRegister(19.50, 20.00, [["PENNY", 0.01], ["NICKEL", 0], ["DIME", 0], ["QUARTER", 0], ["ONE", 1.00], ["FIVE", 0], ["TEN", 0], ["TWENTY", 0], ["ONE HUNDRED", 0]])) # 應該返回 "Insufficient Funds". print(checkCashRegister(19.50, 20.00, [["PENNY", 0.50], ["NICKEL", 0], ["DIME", 0], ["QUARTER", 0], ["ONE", 0], ["FIVE", 0], ["TEN", 0], ["TWENTY", 0], ["ONE HUNDRED", 0]])) # 應該返回 "Closed".
4.庫存更新演算法挑戰
依照一個存著新進貨物的二維數組,更新存著現有庫存(在 arr1
中)的二維數組. 如果貨物已存在則更新數量 . 如果沒有對應貨物則把其加入到數組中,更新最新的數量. 返回當前的庫存數組,且按貨物名稱的字母順序排列.
updateInventory([[21, "Bowling Ball"], [2, "Dirty Sock"], [1, "Hair Pin"], [5, "Microphone"]], [[2, "Hair Pin"], [3, "Half-Eaten Apple"], [67, "Bowling Ball"], [7, "Toothpaste"]])
應該返回 [[88, "Bowling Ball"], [2, "Dirty Sock"], [3, "Hair Pin"], [3, "Half-Eaten Apple"], [5, "Microphone"], [7, "Toothpaste"]]
.
def updateInventory(lst1, lst2): lst_name = [i[1] for i in lst1] + [i[1] for i in lst2] lst_quntity = [i[0] for i in lst1] + [i[0] for i in lst2] dct = {} # 字典去重名時計算數量 for i, j in zip(lst_name, lst_quntity): if dct.get(i): dct[i] = dct.get(i) + j else: dct[i] = j lst = sorted([i for i in dct.items()]) # 按字母排序 lst = list(map(lambda x: list(reversed(x)), lst)) # 逆序 return lst print(updateInventory([[21, "Bowling Ball"], [2, "Dirty Sock"], [1, "Hair Pin"], [5, "Microphone"]], [[2, "Hair Pin"], [3, "Half-Eaten Apple"], [67, "Bowling Ball"], [7, "Toothpaste"]])) # 應該返回 [[88, "Bowling Ball"], [2, "Dirty Sock"], [3, "Hair Pin"], [3, "Half-Eaten Apple"], [5, "Microphone"], [7, "Toothpaste"]] print(updateInventory([[21, "Bowling Ball"], [2, "Dirty Sock"], [1, "Hair Pin"], [5, "Microphone"]], [])) # 應該返回 [[21, "Bowling Ball"], [2, "Dirty Sock"], [1, "Hair Pin"], [5, "Microphone"]]. print(updateInventory([], [[2, "Hair Pin"], [3, "Half-Eaten Apple"], [67, "Bowling Ball"], [7, "Toothpaste"]])) # 應該返回 [[67, "Bowling Ball"], [2, "Hair Pin"], [3, "Half-Eaten Apple"], [7, "Toothpaste"]]. print(updateInventory([[0, "Bowling Ball"], [0, "Dirty Sock"], [0, "Hair Pin"], [0, "Microphone"]], [[1, "Hair Pin"], [1, "Half-Eaten Apple"], [1, "Bowling Ball"], [1, "Toothpaste"]])) # 應該返回 [[1, "Bowling Ball"], [0, "Dirty Sock"], [1, "Hair Pin"], [1, "Half-Eaten Apple"], [0, "Microphone"], [1, "Toothpaste"]].
5.排列組合去重演算法挑戰
把一個字元串中的字元重新排列生成新的字元串,返回新生成的字元串里沒有連續重覆字元的字元串個數.連續重覆只以單個字元為準
例如, aab
應該返回 2 因為它總共有6中排列 (aab
, aab
, aba
, aba
, baa
, baa
), 但是只有兩個 (aba
and aba
)沒有連續重覆的字元 (在本例中是 a
).
permAlone("aaa")
應該返回 0.
permAlone("aabb")
應該返回 8.
自己想沒做出來,偷個巧python內置排列組合函數,嘻嘻
import itertools def permAlone(s): num = 0 for i in itertools.permutations(s, len(s)): for x in range(len(i) - 1): if i[x] == i[x + 1]: break else: num += 1 return num print(permAlone("aab")) # 應該返回 2. print(permAlone("aaa")) # 應該返回 0. print(permAlone("abc")) # 應該返回 6. print(permAlone("aabb")) # 應該返回 8. print(permAlone("abcdefa")) # 應該返回 3600. print(permAlone("abfdefa")) # 應該返回 2640. print(permAlone("zzzzzzzz")) # 應該返回 0.
6.日期改寫演算法挑戰
讓日期區間更友好!
把常見的日期格式如:YYYY-MM-DD
轉換成一種更易讀的格式。
易讀格式應該是用月份名稱代替月份數字,用序數詞代替數字來表示天 (1st
代替 1
).
記住不要顯示那些可以被推測出來的信息: 如果一個日期區間里結束日期與開始日期相差小於一年,則結束日期就不用寫年份了。月份開始和結束日期如果在同一個月,則結束日期月份就不用寫了。
另外, 如果開始日期年份是當前年份,且結束日期與開始日期小於一年,則開始日期的年份也不用寫。
例如:
makeFriendlyDates(["2016-07-01", "2016-07-04"])
應該返回 ["July 1st, 2016","4th"]
makeFriendlyDates(["2016-07-01", "2018-07-04"])
應該返回 ["July 1st, 2016", "July 4th, 2018"]
.
makeFriendlyDates(["2016-12-01", "2017-02-03"])
should return ["December 1st, 2016","February 3rd"]
.
def makeFriendlyDates(lst): dct1 = {1: "January", 2: "Februry", 3: "March", 4: "April", 5: "May", 6: "June", 7: "July", 8: "August", 9: "September", 10: "October", 11: "November", 12: "December"} dct2 = {1: "1st", 2: "2nd", 3: "3rd", 4: "4th", 5: "5th", 6: "6th", 7: "7th", 8: "8th", 9: "9th", 10: "10th", 11: "11th", 12: "12th", 13: "13th", 14: "14th", 15: "15th", 16: "16th", 17: "17th", 18: "18th", 19: "19th", 20: "20th", 21: "21st", 22: "22nd", 23: "23rd", 24: "24th", 25: "25th", 26: "26th", 27: "27th", 28: "28th", 29: "29th", 30: "30th", 31: "31st"} date1 = lst[0].split("-") date1 = list(map(int, date1)) date2 = lst[1].split("-") date2 = list(map(int, date2)) if date1[0] == date2[0]: # 同年 if date1[1] == date2[1]: if date1[2] == date2[2]: return [f"{dct1[date1[1]]} {dct2[date1[2]]}", f" {date1[0]}"] # 同月同日 else: return [f"{dct1[date1[1]]} {dct2[date1[2]]} {date1[0]}", f"{dct2[date2[2]]}"] # 同月不同日 else: return [f"{dct1[date1[1]]} {dct2[date1[2]]}, {date1[0]}", f" {dct1[date2[1]]} {dct2[date2[2]]}"] # 不同月 else: if date2[0] == date1[0] + 1 and (date2[1] < date1[1] or (date2[1] == date1[1] and date2[2] < date1[2])): return [f"{dct1[date1[1]]} {dct2[date1[2]]}, {date1[0]}", f" {dct1[date2[1]]} {dct2[date2[2]]}"] # 不同年相隔一年以內 else: return [f"{dct1[date1[1]]} {dct2[date1[2]]}, {date1[0]}", f" {dct1[date2[1]]} {dct2[date2[2]]}, {date2[0]}"] # 不同年相隔超過一年 print(makeFriendlyDates(["2016-07-01", "2016-07-04"])) # 應該返回 ["July 1st, 2016","4th"] print(makeFriendlyDates(["2016-07-01", "2018-07-04"])) # 應該返回 ["July 1st, 2016", "July 4th, 2018"]. print(makeFriendlyDates(["2016-12-01", "2017-02-03"])) # 應該返回 ["December 1st, 2016","February 3rd"]. print(makeFriendlyDates(["2016-12-01", "2018-02-03"])) # 應該返回 ["December 1st, 2016","February 3rd, 2018"]. print(makeFriendlyDates(["2017-03-01", "2017-05-05"])) # 應該返回 ["March 1st, 2017","May 5th"] print(makeFriendlyDates(["2018-01-13", "2018-01-13"])) # 應該返回 ["January 13th, 2018"]. print(makeFriendlyDates(["2022-09-05", "2023-09-04"])) # 應該返回 ["September 5th, 2022","September 4th"]. print(makeFriendlyDates(["2022-09-05", "2023-09-05"])) # 應該返回 ["September 5th, 2022","September 5th, 2023"]
7.類及對象構建演算法挑戰
用下麵給定的方法構造一個對象.
方法有 getFirstName(), getLastName(), getFullName(), setFirstName(first), setLastName(last), and setFullName(firstAndLast).
所有有參數的方法只接受一個字元串參數.
所有的方法只與實體對象交互.
python基礎的構造類、魔法初始化方法、實例方法
class Person: def __init__(self, s): self.fullname = s self.firstname = s[:s.find(" ")] self.lastname = s[s.find(" ") + 1:] # self.fullname = self.firstname + " " + self.lastname def getFirstName(self): print(f"FirstName是:{self.firstname}") return self.firstname def getLastName(self): print(f"LastName是:{self.lastname}") return self.lastname def getFullName(self): print(f"FullName是:{self.fullname}") return self.fullname def setFirstName(self, s): print(f"FirstName:{self.firstname}被修改為{s}") self.firstname = s self.fullname = s + " " + self.lastname def setLastName(self, s): print(f"LastName:{self.lastname}被修改為{s}") self.lastname = s self.fullname = self.firstname + " " + s def setFullName(self, s): print(f"FullName:{self.fullname}被修改為{s}") self.fullname = s self.firstname = s[:s.find(" ")] self.lastname = s[s.find(" ") + 1:] bob = Person('Bob Ross') bob.getFullName() bob.setFirstName("David") bob.getFirstName() bob.setLastName("Alen") bob.getLastName() bob.setFullName("Bruce Lee") bob.getFullName()
8.軌道周期演算法挑戰
返回一個數組,其內容是把原數組中對應元素的平均海拔轉換成其對應的軌道周期.
原數組中會包含格式化的對象內容,像這樣 {name: 'name', avgAlt: avgAlt}
.
至於軌道周期怎麼求,戳這裡 on wikipedia (不想看英文的話可以自行搜索以軌道高度計算軌道周期的公式).
求得的值應該是一個與其最接近的整數,軌道是以地球為基準的.
地球半徑是 6367.4447 kilometers, 地球的GM值是 398600.4418, 圓周率為Math.PI
orbitalPeriod([{name : "sputnik", avgAlt : 35873.5553}]) 應該返回 [{name: "sputnik", orbitalPeriod: 86400}]. import math def orbitalPeriod(lst): r = 6367.4447 GM = 398600.4418 for dct in lst: avgAlt = 2 * math.pi * math.sqrt(((dct["avgAlt"] + r) ** 3) / GM) dct["orbitalPeriod"] = round(avgAlt) del dct["avgAlt"] return lst print(orbitalPeriod([{"name": "sputnik", "avgAlt": 35873.5553}])) print(orbitalPeriod( [{"name": "iss", "avgAlt": 413.6}, {"name