力扣python100題

❶ 14. 最長公共前綴（python）

更多精彩內容，請關注 【力扣簡單題】 。

難度：★☆☆☆☆
類型：字元串

編寫一個函數來查找字元串數組中的最長公共前綴。

如果不存在公共前綴，返回空字元串 ""。

示例 1:

輸入: ["flower","flow","flight"]
輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

說明:

所有輸入只包含小寫字母 a-z 。

這道題目很簡單，逐一比較各個字元串，出現不同字元則跳出，詳情可見注釋。

如有疑問或建議，歡迎評論區留言~

❷ 力扣236單周賽題目分享

共有 n 名小夥伴一起做游戲。小夥伴們圍成一圈，按 順時針順序 從 1 到 n 編號。確切地說，從第 i 名小夥伴順時針移動一位會到達第 (i+1. 名小夥伴的位置，其中 1 <= i < n ，從第 n 名小夥伴順時針移動一位會回到第 1 名小夥伴的位置。

游戲遵循如下規則：

從第 1 名小夥伴所在位置 開始 。
沿著順時針方向數 k 名小夥伴，計數時需要 包含 起始時的那位小夥伴。逐個繞圈進行計數，一些小夥伴可能會被數過不止一次。
你數到的最後一名小夥伴需要離開圈子，並視作輸掉游戲。
如果圈子中仍然有不止一名小夥伴，從剛剛輸掉的小夥伴的 順時針下一位 小夥伴 開始，回到步驟 2 繼續執行。
否則，圈子中最後一名小夥伴贏得游戲。
給你參與游戲的小夥伴總數 n ，和一個整數 k ，返回遊戲的獲勝者。

示例 1：

輸入：n = 5, k = 2

輸出：3

解釋：
游戲運行步驟如下：

示例 2：

輸入：n = 6, k = 5

輸出：1

解釋：
小夥伴離開圈子的順序：5、4、6、2、3 。小夥伴 1 是游戲的獲勝者。

這是一道標準的約瑟夫環問題，類似的題目很多，比如劍指offer中有一道小朋友們的游戲與此題就如出一轍。大家找個鏈表畫下題目就迎刃而解了，類似斐波那契數列一樣，了解公式直接解題。

給你一個長度為. n. 的. 3 跑道道路. ，它總共包含. n + 1. 個. 點. ，編號為. 0. 到. n. 。一隻青蛙從. 0. 號點第二條跑道. 出發. ，它想要跳到點. n. 處。然而道路上可能有一些障礙。

給你一個長度為 n + 1. 的數組. obstacles. ，其中. obstacles[i]. （取值范圍從 0 到 3）表示在點 i. 處的. obstacles[i]. 跑道上有一個障礙。如果. obstacles[i] == 0. ，那麼點. i. 處沒有障礙。任何一個點的三條跑道中. 最多有一個. 障礙。

比方說，如果. obstacles[2] == 1. ，那麼說明在點 2 處跑道 1 有障礙。
這只青蛙從點 i. 跳到點 i + 1. 且跑道不變的前提是點 i + 1. 的同一跑道上沒有障礙。為了躲避障礙，這只青蛙也可以在. 同一個. 點處. 側跳. 到 另外一條. 跑道（這兩條跑道可以不相鄰），但前提是跳過去的跑道該點處沒有障礙。

比方說，這只青蛙可以從點 3 處的跑道 3 跳到點 3 處的跑道 1 。
這只青蛙從點 0 處跑道 2. 出發，並想到達點 n. 處的 任一跑道 ，請你返回 最少側跳次數. 。

注意：點 0. 處和點 n. 處的任一跑道都不會有障礙。

示例 1：

輸入：obstacles = [0,1,2,3,0]

輸出：2

解釋：最優方案如上圖箭頭所示。總共有 2 次側跳（紅色箭頭）。

注意，這只青蛙只有當側跳時才可以跳過障礙（如上圖點 2 處所示）。

示例 2：

輸入：obstacles = [0,1,1,3,3,0]

輸出：0

解釋：跑道 2 沒有任何障礙，所以不需要任何側跳。

示例 3：

輸入：obstacles = [0,2,1,0,3,0]

輸出：2

解釋：最優方案如上圖所示。總共有 2 次側跳。

我的個人博客： https://qingfengpython.cn

力扣解題合集： https://github.com/BreezePython/AlgorithmMarkdown

❸ 813. 最大平均值和的分組（Python）

難度：★★★☆☆
類型：數組
方法：動態規劃

力扣鏈接請移步 本題傳送門
更多力扣中等題的解決方案請移步 力扣中等題目錄

我們將給定的數組 A 分成 K 個相鄰的非空子數組 ，我們的分數由每個子數組內的平均值的總和構成。計算我們所能得到的最大分數是多少。

注意我們必須使用 A 數組中的每一個數進行分組，並且分數不一定需要是整數。

示例:
輸入:
A = [9,1,2,3,9]
K = 3
輸出: 20
解釋:
A 的最優分組是[9], [1, 2, 3], [9]. 得到的分數是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我們也可以把 A 分成[9, 1], [2], [3, 9].
這樣的分組得到的分數為 5 + 2 + 6 = 13, 但不是最大值.
說明:

1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
答案誤差在 10^-6 內被視為是正確的。

數組問題常用動態規劃來解決。動態規劃的精髓在於，把一個難以解決的大問題轉化為若干個可以通過有限次重復解決的簡單問題。接下來從動態規劃的幾個要素進行介紹：

【數組定義】
我們定義一個二維數組dp，維度為輸入數組A的維度×K，dp[i][k]表示數組A[:i+1]被分成k+1組時，可以得到的最大分數（各組平均值的和）。這里尤其需要注意python下標和它代表的變數的物理含義之間正好相差1的。

【初始狀態】
我們可以很快得知的信息是，如果數組只被分為一組的情況。因此可以先把k=0的一列填好。這一列各個位置dp[i][0]的填充規則，就是A[:i]的均值。

【遞推公式】
我們以分組數k和下標i遞增的方式，構造嵌套循環。這里還需要留意一個情況，就是填充dp[i][k]時，需要考慮到獲得當前位置的各種情況的分組，因此藉助一個中間下標變數j，范圍從0到i，也就是說，我們把數組A[:i+1]從下標j砍成了兩半，因此當前位置處的值可以填充為：

dp[i][k] = max(dp[i][k], dp[j][k-1]+average(j+1, i+1))

這里average是一個函數，用來計算A[i:j]子數組的均值。這里把i和j+1的原因是我們定義dp數組的物理意義決定的。

有了這個遞推公式，就可以迭代進行計算了，
注意k的范圍是從1到K，因為k=0的一列已經算好了；
i的范圍是從k到len(A)，因為組的個數不能比數組中數字的個數還要多；
j的范圍是小於i，因為必須要保證可以把A[:i+1]分開。

【最後結果】

最終范圍dp[-1][-1]也就是最後計算出的值，就可以代表題目所要求的結果。

如有疑問或建議，歡迎評論區留言~

有關更多力扣中等題的python解決方案，請移步 力扣中等題解析

❹ 984. 不含AAA或BBB的字元串（Python）

難度：★★★☆☆
類型：字元串
方法：邏輯

力扣鏈接請移步 本題傳送門
更多力扣中等題的解決方案請移步 力扣中等題目錄

給定兩個整數 A 和 B，返回任意字元串 S，要求滿足：

S 的長度為 A + B，且正好包含 A 個 'a' 字母與 B 個 'b' 字母；
子串 'aaa' 沒有出現在 S 中；
子串 'bbb' 沒有出現在 S 中。

示例 1：

輸入：A = 1, B = 2
輸出："abb"
解釋："abb", "bab" 和 "bba" 都是正確答案。

示例 2：

輸入：A = 4, B = 1
輸出："aabaa"

提示：

0 <= A <= 100
0 <= B <= 100
對於給定的 A 和 B，保證存在滿足要求的 S。

題目很好理解，構建一個「a」的數量為A，「b」的數量為B的字元串，並且不要出現「AAA」或「BBB」。

這個題官網題解還是比較好的，每寫一個字元，都要做下面的判斷：

如果連續出現兩個相同字元了，則下一個字元一定要相反；

否則，寫數量更多的字元。

如有疑問或建議，歡迎評論區留言~

有關更多力扣中等題的python解決方案，請移步 力扣中等題解析

❺ 478. 在圓內隨機生成點（Python）

難度：★★☆☆☆
類型：幾何
方法：拒絕采樣

力扣鏈接請移步 本題傳送門
更多力扣中等題的解決方案請移步 力扣中等題目錄

給定圓的半徑和圓心的 x、y 坐標，寫一個在圓中產生均勻隨機點的函數 randPoint 。

說明:

輸入值和輸出值都將是浮點數。
圓的半徑和圓心的 x、y 坐標將作為參數傳遞給類的構造函數。
圓周上的點也認為是在圓中。
randPoint 返回一個包含隨機點的x坐標和y坐標的大小為2的數組。
示例 1：

輸入:
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
輸出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
示例 2：

輸入:
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
輸出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
輸入語法說明：

輸入是兩個列表：調用成員函數名和調用的參數。Solution 的構造函數有三個參數，圓的半徑、圓心的 x 坐標、圓心的 y 坐標。randPoint 沒有參數。輸入參數是一個列表，即使參數為空，也會輸入一個 [] 空列表。

我們在以圓心為中心，以二倍半徑為邊長的正方形內部進行隨機選點，當點落在圓內或者圓上時，滿足條件，返回該點。

我們可以把上面的直角坐標變換為極坐標，隨機的選取角度和半徑，生成的點一定在圓上或者圓內。這里需要注意，由於在平面維度是均勻采樣的，生成隨機半徑時需要對結果開方。

如有疑問或建議，歡迎評論區留言~

有關更多力扣中等題的python解決方案，請移步 力扣中等題解析

❻ Python挑戰100題（14~20）

題目：給你個小寫英文字元串a和一個非負數b(0<=b<26), 將a中的每個小寫字元替換成字母表中比它大b的字母。這里將字母表的z和a相連，如果超過了z就回到了a。
例如a="cagy", b=3,
則輸出 ：fdjb
提示： ord('a') = 97, ord('b') = 98, chr(97) = a
參考答案：

題目：給你一個字元串a和一個正整數n,判斷a中是否存在長度為n的迴文子串。如果存在，則輸出YES，否則輸出NO。
迴文串的定義： 記串str逆序之後的字元串是str1，若str=str1,則稱str是迴文串，如"abcba".
參考答案：

題目：給你兩個時間st和et(00:00:00<=st <= et<=23:59:59), 請你給出這兩個時間間隔的秒數。
如：st="00:00:00", et="00:00:10", 則輸出10.
參考答案：
方法一：切片

方法二：time模塊

題目：給你一個時間t（t是一個字典，共有六個字元串key(year,month,day,hour,minute,second),值為每個值為數字組成的字元串，
如t={'year':񟭍','month':Ə','day':ཚ','hour':ཌ','minute':ཀྵ','second':ƈ'}
請將其按照以下格式輸出， 格式:XXXX-XX-XX XX:XX:XX。如上例應該輸出： 2013-09-30 16:45:02。
參考答案：
方法一：利用datetime模塊

方法二：一行

題目：給你一個整數組成的列表L，按照下列條件輸出：
若L是升序排列的,則輸出"UP";
若L是降序排列的,則輸出"DOWN";
若L無序，則輸出"WRONG"。
參考答案：

題目：一個環形的公路上有n個加油站，編號為0,1,2,...n-1,
每個加油站加油都有一個上限，保存在列表limit中，即limit[i]為第i個加油站加油的上限，
而從第i個加油站開車開到第(i+1)%n個加油站需要cost[i]升油,cost為一個列表。
現在有一輛開始時沒有油的車，要從一個加油站出發繞這個公路跑一圈回到起點。
給你整數n，列表limit和列表cost,你來判斷能否完成任務。
如果能夠完成任務，輸出起始的加油站編號，如果有多個,輸出編號最小的。
如果不能完成任務，輸出-1。
參考答案：
構造新的limit和cost並遍歷,來源 http://www.pythontip.com/coding/report_detail/3195/

題目：給你一個整數列表L,判斷L中是否存在相同的數字，
若存在，輸出YES，否則輸出NO。
參考答案：

❼ 977. 有序數組的平方（Python）

更多精彩內容，請關注 【力扣簡單題】 。

難度：★☆☆☆☆
類型：數組

給定一個按非遞減順序排序的整數數組 A，返回每個數字的平方組成的新數組，要求也按非遞減順序排序。

提示
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非遞減順序排序。

示例 1
輸入：[-4,-1,0,3,10]
輸出：[0,1,9,16,100]

示例 2
輸入：[-7,-3,2,3,11]
輸出：[4,9,9,49,121]

我們對輸入數組中每個元素進行平方，然後對結果進行數組進行排序即可。

（參考官方解答）

我們可以使用兩個指針分別讀取數組的非負部分與負數部分 —— 指針 i 反向讀取負數部分，指針 j 正向讀取非負數部分。

那麼，現在我們就在使用兩個指針分別讀取兩個遞增的數組了（按元素的平方排序）。接下來，我們可以使用雙指針的技巧合並這兩個數組。

如有疑問或建議，歡迎評論區留言~

❽ Python求數學題 1到100包括100 能被3整除和被5整除餘1的所有數之和 用for

for i in range (1,101): print i, if i%3==0 and i%5==0: print 'A*B', elif i%3==0: print 'A', elif i%5==0: print 'B', print

❾ 求大神幫忙做道Python題。

menu = {'蒜泥黃瓜':6,'花生米':6,'青椒炒肉':28,'西紅柿雞蛋':18,'紅燒肉':38,'烤魚':30,'手撕雞':45,'海帶排骨':35,'白菜':12,'三鮮湯':15}
def order(*dish):
s = 0
for i in dish:
s += menu[i]
return s
m = order('蒜泥黃瓜','花生米','青椒炒肉','西紅柿雞蛋')
print(f'結賬: {m}元')

程序縮進如圖所示

❿ 力扣每日一題：102.二叉樹的層序遍歷 深度優先與廣度優先雙解！

給你一個二叉樹，請你返回其按 層序遍歷 得到的節點值。 （即逐層地，從左到右訪問所有節點）。

對於二叉樹的層序遍歷，一般都是使用BFS配合隊列完成解題。

二叉樹的前、中、後 順序遍歷，一般最簡單的是使用深度優先，但層序遍歷也可以通過DFS來解題。

麻煩一些的就是我們需要在DFS層級遍歷的時候，根據當前深度進行保存，這里由於返回列表，所以
使用defaultdict來構造特殊的Hash表更為快捷。由於字典的key值為深度，是存在默認排序的，
所以遞歸返程回放回即可。

下面來分別看看一下兩種解題...

我的個人博客： https://qingfengpython.cn

力扣解題合集： https://github.com/BreezePython/AlgorithmMarkdown