前言

*最近在做一些leetcode的算法題，我會(huì)將自己做過的算法題記錄下來以供大家參考灾前，如果查找不方便請(qǐng)看油猴插件實(shí)現(xiàn)簡書網(wǎng)站左側(cè)目錄生成。

Ⅰ.數(shù)組

一紧唱、刪除排序數(shù)組中的重復(fù)項(xiàng)

給定一個(gè)排序數(shù)組存炮，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次夺姑，返回移除后數(shù)組的新長度墩邀。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成盏浙。

示例：

給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長度 5, 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4眉睹。
你不需要考慮數(shù)組中超出新長度后面的元素荔茬。

解答：

def removeDuplicates(nums) -> int:
    if len(nums) <= 1:
        return len(nums)
    s = 0
    for i in range(1, len(nums)):
        if nums[s] != nums[i]:
            s += 1
            nums[s] = nums[i]
    return s + 1

nums = [1, 2, 2, 3]
s = removeDuplicates(nums)
print(s, nums)

?????

二、買賣股票的最佳時(shí)機(jī) II

給定一個(gè)數(shù)組竹海，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格慕蔚。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）斋配。
注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）孔飒。

示例：

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 艰争。
     隨后坏瞄，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 甩卓。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

解答：

def maxProfit(prices) -> int:
    e = 0
    for i in range(len(prices) - 1):
        if prices[i] < prices[i + 1]:
            e += prices[i + 1] - prices[i]
    return e

prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))

?????

三鸠匀、旋轉(zhuǎn)數(shù)組

給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置猛频，其中 k 是非負(fù)數(shù)狮崩。

示例：

輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

說明:

盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個(gè)問題鹿寻。
要求使用空間復(fù)雜度為 O(1) 的原地算法。

解答：

def rotate(nums, k: int) -> None:
    length = len(nums)
    k = k % length
    if k <= 0 or length <= 1:
        return
    nums[:] = nums[length - k:] + nums[:length - k]

nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
rotate(nums, k)
print(nums)

?????

四诽凌、存在重復(fù)元素

給定一個(gè)整數(shù)數(shù)組毡熏，判斷是否存在重復(fù)元素。
如果任意一值在數(shù)組中出現(xiàn)至少兩次侣诵，函數(shù)返回true痢法。如果數(shù)組中每個(gè)元素都不相同，則返回false杜顺。

示例：

輸入: [1,2,3,1]
輸出: true

輸入: [1,2,3,4]
輸出: false

解答：

def containsDuplicate(nums):
    if len(nums) <= 1:
        return False
    return len(nums) != len(set(nums))

nums = [1,2,3,1]
print(containsDuplicate(nums))

?????

五财搁、只出現(xiàn)一次的數(shù)字

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外躬络，其余每個(gè)元素均出現(xiàn)兩次尖奔。找出那個(gè)只出現(xiàn)了一次的元素。

說明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度穷当。你可以不使用額外空間來實(shí)現(xiàn)嗎提茁？

示例：

輸入: [2,2,1]
輸出: 1

解答：

def singleNumber(nums) -> int:
    c = 0
    for i in nums:
        c ^= i
    return c

nums = [2, 3, 3]
print(singleNumber(nums))

?????

六、兩個(gè)數(shù)組的交集 II

給定兩個(gè)數(shù)組馁菜，編寫一個(gè)函數(shù)來計(jì)算它們的交集茴扁。

示例：

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]

說明：

輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致汪疮。
我們可以不考慮輸出結(jié)果的順序峭火。

進(jìn)階:

如果給定的數(shù)組已經(jīng)排好序呢毁习？你將如何優(yōu)化你的算法？
如果 nums1 的大小比 nums2 小很多卖丸，哪種方法更優(yōu)蜓洪？
如果 nums2 的元素存儲(chǔ)在磁盤上，磁盤內(nèi)存是有限的坯苹，并且你不能一次加載所有的元素到內(nèi)存中隆檀，你該怎么辦？

解答：

def intersect(nums1, nums2):
    r1 = {}
    r2 = {}

    for i in nums1:
        r1[i] = 1 if i not in r1.keys() else r1[i] + 1

    for i in nums2:
        r2[i] = 1 if i not in r2.keys() else r2[i] + 1

    k = set([i for i in r1.keys()]) & set([i for i in r2.keys()])
    r = []
    for i in k:
        r.extend([i] * min(r1[i], r2[i]))
    return r

nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersect(nums1, nums2))

?????

七粹湃、加一

給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)恐仑，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位为鳄，數(shù)組中每個(gè)元素只存儲(chǔ)單個(gè)數(shù)字裳仆。
你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開頭孤钦。

示例：

輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123歧斟。

解答：

def plusOne(digits) -> List:
    l = len(digits)
        for i in range(l):
            digits[l - i - 1] += 1
            if digits[l - i - 1] != 10:
                return digits
            elif i == l - 1:
                digits[l - i - 1] = 0
                digits.insert(0, 1)
                return digits
            else:
                digits[l - i - 1] = 0

nums = [1, 2, 3]
print(plusOne(nums))

?????

八、移動(dòng)零

給定一個(gè)數(shù)組 nums偏形，編寫一個(gè)函數(shù)將所有0移動(dòng)到數(shù)組的末尾静袖，同時(shí)保持非零元素的相對(duì)順序。

示例:

輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]

說明:

必須在原數(shù)組上操作俊扭，不能拷貝額外的數(shù)組队橙。
盡量減少操作次數(shù)。

def moveZeroes(nums):
    count = nums.count(0)
    if count == 0:
        return
    for i in range(count):
        nums.remove(0)
    nums.extend([0] * count)

nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums)

?????

九萨惑、兩數(shù)之和

給定一個(gè)整數(shù)數(shù)組nums和一個(gè)目標(biāo)值target捐康，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)庸蔼。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案解总。但是，數(shù)組中同一個(gè)元素不能使用兩遍姐仅。

示例：

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答：

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))

?????

十花枫、有效的數(shù)獨(dú)

判斷一個(gè)9x9的數(shù)獨(dú)是否有效。只需要根據(jù)以下規(guī)則萍嬉，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可乌昔。

數(shù)字1-9在每一行只能出現(xiàn)一次。
數(shù)字1-9在每一列只能出現(xiàn)一次壤追。
數(shù)字1-9在每一個(gè)以粗實(shí)線分隔的3x3宮內(nèi)只能出現(xiàn)一次磕道。

上圖是一個(gè)部分填充的有效的數(shù)獨(dú)

數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用'.'表示行冰。

示例：

輸入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
輸出: true

輸入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
輸出: false
解釋: 除了第一行的第一個(gè)數(shù)字從 5 改為 8 以外溺蕉，空格內(nèi)其他數(shù)字均與 示例1 相同伶丐。
     但由于位于左上角的 3x3 宮內(nèi)有兩個(gè) 8 存在, 因此這個(gè)數(shù)獨(dú)是無效的。

說明:

一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的疯特。
只需要根據(jù)以上規(guī)則哗魂，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
給定數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 漓雅。
給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的录别。

解答：

def isValidSudoku(board) -> bool:
    map1 = [{} for i in range(9)]  # 保存行中的數(shù)字
    map2 = [{} for i in range(9)]  # 保存列中的數(shù)字
    map3 = [{} for i in range(9)]  # 保存塊中的數(shù)字
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                data = int(board[i][j])
                smallBoardi = (i // 3) * 3 + (j // 3)  # 每塊的腳標(biāo)，橫向劃分邻吞。

                # 當(dāng)前單元格的值
                map1[i][data] = map1[i].get(data, 0) + 1
                map2[j][data] = map2[j].get(data, 0) + 1
                map3[smallBoardi][data] = map3[smallBoardi].get(data, 0) + 1

                # 檢查這個(gè)值以前是否出現(xiàn)過
                if map1[i][data] > 1 or map2[j][data] > 1 or map3[smallBoardi][data] > 1:
                    return False
    return True

board = [["5", "3", ".", ".", "7", ".", ".", ".", "."],
         ["6", ".", ".", "1", "9", "5", ".", ".", "."],
         [".", "9", "8", ".", ".", ".", ".", "6", "."],
         ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
         ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
         ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
         [".", "6", ".", ".", ".", ".", "2", "8", "."],
         [".", ".", ".", "4", "1", "9", ".", ".", "5"],
         [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
print(isValidSudoku(board))

?????

十一组题、旋轉(zhuǎn)圖像

給定一個(gè)*n *× *n*的二維矩陣表示一個(gè)圖像。
將圖像順時(shí)針旋轉(zhuǎn)90度抱冷。

說明：
你必須在原地旋轉(zhuǎn)圖像崔列，這意味著你需要直接修改輸入的二維矩陣。請(qǐng)不要使用另一個(gè)矩陣來旋轉(zhuǎn)圖像旺遮。

示例：

給定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋轉(zhuǎn)輸入矩陣赵讯，使其變?yōu)?
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

解答：

def rotate(matrix):
    n = len(matrix)
    # 對(duì)角調(diào)換
    for i in range(n):
        for j in range(n - i):
            matrix[i][j], matrix[n - 1 - j][n - 1 - i] = matrix[n - 1 - j][n - 1 - i], matrix[i][j]
    # 列倒置
    for i in range(n):
        for j in range(n // 2):
            matrix[j][i], matrix[n - 1 - j][i] = matrix[n - 1 - j][i], matrix[j][i]

matrix = [
    [5, 1, 9, 11],
    [2, 4, 8, 10],
    [13, 3, 6, 7],
    [15, 14, 12, 16]
]
rotate(matrix)
print(matrix)

?????

II、字符串

一耿眉、反轉(zhuǎn)字符串

編寫一個(gè)函數(shù)边翼，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 char[] 的形式給出跷敬。
不要給另外的數(shù)組分配額外的空間讯私，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題西傀。
你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。

示例：

輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]

解答：

def reverseString(s):
    s[:] = s[::-1]

s = ["h", "e", "l", "l", "o"]
reverseString(s)
print(s)

?????

二桶癣、整數(shù)反轉(zhuǎn)

給出一個(gè) 32 位的有符號(hào)整數(shù)拥褂，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。

示例：

輸入: 123
輸出: 321

輸入: -123
輸出: -321

輸入: 120
輸出: 21

注意:
假設(shè)我們的環(huán)境只能存儲(chǔ)得下 32 位的有符號(hào)整數(shù)牙寞，則其數(shù)值范圍為 [?231, 231 ? 1]饺鹃。請(qǐng)根據(jù)這個(gè)假設(shè)，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0间雀。

解答：

def reverse(x: int) -> int:
    # 個(gè)位數(shù)直接返回
    if abs(x) < 9:
        return x
    # 超過范圍返回0
    elif not -2 ** 31 < x < 2 ** 31 - 1:
        return 0
    # 記錄符號(hào)悔详，將其轉(zhuǎn)為無符號(hào)數(shù)
    elif x > 0:
        n = 1
    else:
        x = -x
        n = 0

    # 變成列表
    x = list(str(x))
    # 反轉(zhuǎn)
    x[:] = x[::-1]
    # 去掉開頭的0
    while x[0] == '0':
        x = x[1:]
    # 變成整數(shù)
    x = list(map(int, x))
    a = 0
    l = len(x)
    for i in range(l):
        a += x[i] * 10 ** (l - i - 1)
    # 反轉(zhuǎn)后超過范圍返回0，否則判斷正負(fù)并返回
    return 0 if not -2 ** 31 < a < 2 ** 31 - 1 else a if n else -a

x = -1230
print(reverse(x))

?????

三惹挟、字符串中的第一個(gè)唯一字符

給定一個(gè)字符串茄螃，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引连锯。如果不存在归苍，則返回 -1用狱。

示例：

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

解答：

# 這個(gè)是我一開始的想法，測試后超時(shí)拼弃，懷疑count方法耗時(shí)大
'''
def firstUniqChar(s: str) -> int:
    s = list(s)
    for i in range(len(s)):
        if s.count(s[i]) > 1:
            continue
        else:
            return i
    return -1
'''

# 因此棄用count方法夏伊，需用in方法
def firstUniqChar(s: str) -> int:
    for i in range(len(s)):
        if s[i] not in s[i + 1:] and s[i] not in s[:i]:
            return i
    return -1

s = "leetcode"
print(firstUniqChar(s))

?????

四、有效的字母異位詞

給定兩個(gè)字符串 s 和 t 吻氧，編寫一個(gè)函數(shù)來判斷 t 是否是 s 的字母異位詞溺忧。
長度一樣，包含的字母都一樣盯孙，每個(gè)字符出現(xiàn)的頻率也一樣鲁森，只是順序不同而已，這就屬于異位詞镀梭，

示例：

輸入: s = "anagram", t = "nagaram"
輸出: true

說明:
你可以假設(shè)字符串只包含小寫字母刀森。

進(jìn)階:
如果輸入字符串包含 unicode 字符怎么辦？你能否調(diào)整你的解法來應(yīng)對(duì)這種情況报账？

解答：

def isAnagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)  

s = "anagram"
t = "nagaram"
print(isAnagram(s, t))

?????

五研底、驗(yàn)證回文字符串

給定一個(gè)字符串，驗(yàn)證它是否是回文串透罢，只考慮字母和數(shù)字字符榜晦，可以忽略字母的大小寫。
說明：本題中羽圃，我們將空字符串定義為有效的回文串乾胶。

示例：

輸入: "A man, a plan, a canal: Panama"
輸出: true

解答：

# 這個(gè)是我一開始的想法，測試后超時(shí)朽寞。懷疑是測試的字符串賊長识窿，導(dǎo)致for判斷耗時(shí)特長，之前用的while方法耗時(shí)更長脑融。
"""
def isPalindrome(s: str) -> bool:
    s = list(s.lower())
    s1 = set(s)
    for i in s1:
        if not i.isalpha() and not i.isalnum():
            for j in range(s.count(i)):
                s.remove(i)
    return s == s[::-1]
"""

# 因此棄用for方法喻频，選用replace方法
def isPalindrome(s: str) -> bool:
    s1 = set(s)
    for i in s1:
        if not i.isalpha() and not i.isalnum():
            s = s.replace(i, '')
    s = list(s.lower())
    return s == s[::-1]

s = "A man, a plan, a canal: Panama"
print(isPalindrome(s))

?????

六、字符串轉(zhuǎn)換整數(shù) (atoi)

請(qǐng)你來實(shí)現(xiàn)一個(gè)atoi函數(shù)肘迎，使其能將字符串轉(zhuǎn)換成整數(shù)甥温。

首先，該函數(shù)會(huì)根據(jù)需要丟棄無用的開頭空格字符妓布，直到尋找到第一個(gè)非空格的字符為止姻蚓。接下來的轉(zhuǎn)化規(guī)則如下：

如果第一個(gè)非空字符為正或者負(fù)號(hào)時(shí)，則將該符號(hào)與之后面盡可能多的連續(xù)數(shù)字字符組合起來匣沼，形成一個(gè)有符號(hào)整數(shù)狰挡。
假如第一個(gè)非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來，形成一個(gè)整數(shù)圆兵。
該字符串在有效的整數(shù)部分之后也可能會(huì)存在多余的字符跺讯，那么這些字符可以被忽略，它們對(duì)函數(shù)不應(yīng)該造成影響殉农。

注意：假如該字符串中的第一個(gè)非空格字符不是一個(gè)有效整數(shù)字符刀脏、字符串為空或字符串僅包含空白字符時(shí)，則你的函數(shù)不需要進(jìn)行轉(zhuǎn)換超凳，即無法進(jìn)行有效轉(zhuǎn)換愈污。

在任何情況下，若函數(shù)不能進(jìn)行有效的轉(zhuǎn)換時(shí)轮傍，請(qǐng)返回 0 暂雹。

提示：

本題中的空白字符只包括空格字符 ' ' 。
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位大小的有符號(hào)整數(shù)创夜，那么其數(shù)值范圍為 [?231, 231 ? 1]杭跪。如果數(shù)值超過這個(gè)范圍，請(qǐng)返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 驰吓。

示例：

輸入: "42"
輸出: 42

輸入: "   -42"
輸出: -42
解釋: 第一個(gè)非空白字符為 '-', 它是一個(gè)負(fù)號(hào)涧尿。
     我們盡可能將負(fù)號(hào)與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來，最后得到 -42 檬贰。

輸入: "4193 with words"
輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 '3' 姑廉，因?yàn)樗南乱粋€(gè)字符不為數(shù)字搜吧。

輸入: "words and 987"
輸出: 0
解釋: 第一個(gè)非空字符是 'w', 但它不是數(shù)字或正景用、負(fù)號(hào)。
     因此無法執(zhí)行有效的轉(zhuǎn)換谋国。

輸入: "-91283472332"
輸出: -2147483648
解釋: 數(shù)字 "-91283472332" 超過 32 位有符號(hào)整數(shù)范圍葵礼。 
     因此返回 INT_MIN (?231) 号阿。

解答：

def myAtoi(s: str) -> int:
    s = s.strip()
    if len(s) == 0 or len(s.replace('-', '')) == 0 or len(s.replace('+', '')) == 0:
        return 0
    if s[0] == '-':
        n = 1
        s = s[1:]
    elif s[0] == '+':
        n = 0
        s = s[1:]
    else:
        n = 0
    for i in range(len(s)):
        if not '0' <= s[i] <= '9':
            if i == 0:
                return 0
            else:
                result = int(s[:i])
                break
        if i == len(s) - 1:
            result = int(s)
    if n == 0:
        if result > 2 ** 31 - 1:
            return 2 ** 31 - 1
        else:
            return result
    else:
        if result > 2 ** 31:
            return -2 ** 31
        else:
            return - result

s = "++1"
print(myAtoi(s))

?????

七、實(shí)現(xiàn) strStr()

實(shí)現(xiàn) strStr() 函數(shù)鸳粉。
給定一個(gè)haystack字符串和一個(gè)needle字符串倦西，在haystack字符串中找出needle字符串出現(xiàn)的第一個(gè)位置(從0開始)。如果不存在赁严，則返回 -1。

示例：

輸入: haystack = "hello", needle = "ll"
輸出: 2

輸入: haystack = "aaaaa", needle = "bba"
輸出: -1

說明:
當(dāng) needle 是空字符串時(shí)粉铐，我們應(yīng)當(dāng)返回什么值呢疼约？這是一個(gè)在面試中很好的問題。
對(duì)于本題而言蝙泼，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 程剥。這與C語言的strstr() 以及 Java的 indexOf()定義相符

解答：

def strStr(haystack: str, needle: str) -> int:
    if needle == '':
        return 0
    elif needle not in haystack:
        return -1
    else:
        return haystack.index(needle)

h = "hello"
n = 'll'
print(strStr(h, n))

?????

八、外觀數(shù)列

「外觀數(shù)列」是一個(gè)整數(shù)序列，從數(shù)字 1 開始织鲸，序列中的每一項(xiàng)都是對(duì)前一項(xiàng)的描述舔腾。前五項(xiàng)如下：

1被讀作"one 1" ("一個(gè)一"), 即11。
11被讀作"two 1s" ("兩個(gè)一"), 即21搂擦。
21被讀作"one 2", "one 1" ("一個(gè)二" , "一個(gè)一"), 即1211稳诚。
給定一個(gè)正整數(shù) n（1 ≤ n ≤ 30），輸出外觀數(shù)列的第 n 項(xiàng)瀑踢。

注意：整數(shù)序列中的每一項(xiàng)將表示為一個(gè)字符串扳还。

示例：

輸入: 1
輸出: "1"
解釋：這是一個(gè)基本樣例。

輸入: 4
輸出: "1211"
解釋：當(dāng) n = 3 時(shí)橱夭，序列是 "21"氨距，其中我們有 "2" 和 "1" 兩組，"2" 可以讀作 "12"棘劣，也就是出現(xiàn)頻次 = 1 而 值 = 2俏让；類似 "1" 可以讀作 "11"。所以答案是 "12" 和 "11" 組合在一起茬暇，也就是 "1211"首昔。

解答：

def countAndSay(n: int) -> str:
    s = '1'
    for i in range(1, n):
        flag = 1
        rts = ''
        for j, char in enumerate(s):
            if not flag:
                count -= 1
                if count == 1:
                    flag = 1
                continue
            count = s[j: j + 2].count(char)
            if j < len(s) - 1:
                count2 = s[j + 1: j + 3].count(char)
            if count == 2 and count2 == 2:
                count = 3
            if count > 1:
                flag = 0
            rts += str(count) + char
        s = rts
    return s

n = 4
print(countAndSay(n))

# 方法二
def countAndSay(self, n: int) -> str:
    res = '1'
    for i in range(1, n):
        list_res = list(res)
        res = ''
        count = 1
        for j in range(1, len(list_res)):
            if list_res[j] == list_res[j - 1]:
                count += 1
            else:
                res += str(count) + list_res[j - 1]
                count = 1
        res += str(count) + list_res[-1]
    return res

?????

九、最長公共前綴

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴而钞。
如果不存在公共前綴沙廉，返回空字符串""。

示例：

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

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

說明:
所有輸入只包含小寫字母a-z撬陵。

解答：

def longestCommonPrefix(strs) -> str:
    if strs == []:
        return ''
    strs.sort()
    s1 = strs[0]
    result = len(s1)
    for i in range(1, len(strs)):
        for j in range(len(s1)):
            if s1[j] == strs[i][j]:
                continue
            else:
                result = min(result, j)
                break
    return s1[:result]

strs = ["flower", "flow", "flight"]
print(longestCommonPrefix(strs))

?????

III、鏈表

一网缝、刪除鏈表中的節(jié)點(diǎn)

請(qǐng)編寫一個(gè)函數(shù)巨税，使其可以刪除某個(gè)鏈表中給定的（非末尾）節(jié)點(diǎn)，你將只被給定要求被刪除的節(jié)點(diǎn)粉臊。
現(xiàn)有一個(gè)鏈表 -- head = [4,5,1,9]草添，它可以表示為:

示例：

輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后扼仲，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.

輸入: head = [4,5,1,9], node = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個(gè)節(jié)點(diǎn)远寸，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9.

說明：

鏈表至少包含兩個(gè)節(jié)點(diǎn)屠凶。
鏈表中所有節(jié)點(diǎn)的值都是唯一的驰后。
給定的節(jié)點(diǎn)為非末尾節(jié)點(diǎn)并且一定是鏈表中的一個(gè)有效節(jié)點(diǎn)。
不要從你的函數(shù)中返回任何結(jié)果矗愧。

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        if not node:
            return 
        node.val = node.next.val
        node.next = node.next.next

?????

二灶芝、刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)夜涕。

示例：

給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后犯犁，鏈表變?yōu)?1->2->3->5.

說明：
給定的 n 保證是有效的。

進(jìn)階：
你能嘗試使用一趟掃描實(shí)現(xiàn)嗎女器？

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head == None or head.next == None:
            return None
        l1 = head
        l2 = head
        while n != 0:
            l1 = l1.next
            n -= 1
        if l1 == None:
            head = head.next
            return head
        while l1.next != None:
            l1 = l1.next
            l2 = l2.next
        l2.next = l2.next.next
        return head

?????

三酸役、反轉(zhuǎn)鏈表

反轉(zhuǎn)一個(gè)單鏈表。

示例：

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        index, index_before = head, None
        while index:
            index.next, index_before, index = index_before, index, index.next
        return index_before

?????

四晓避、合并兩個(gè)有序鏈表

將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回簇捍。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        new = ListNode(-1)
        tail = new
        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                tail.next = l1
                tail = tail.next
                l1 = l1.next
            else:
                tail.next = l2
                tail = tail.next
                l2 = l2.next
        if l1 != None:
            tail.next = l1
        if l2 != None:
            tail.next = l2
        return new.next

?????

五俏拱、回文鏈表

請(qǐng)判斷一個(gè)鏈表是否為回文鏈表暑塑。

示例：

輸入: 1->2
輸出: false

輸入: 1->2->2->1
輸出: true

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        l = []
        while head != None:
            l.append(head.val)
            head = head.next
        return l[::-1] == l

?????

六、環(huán)形鏈表

給定一個(gè)鏈表锅必，判斷鏈表中是否有環(huán)事格。
為了表示給定鏈表中的環(huán)，我們使用整數(shù)pos來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）搞隐。如果pos是-1驹愚，則在該鏈表中沒有環(huán)。

示例：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)劣纲，其尾部連接到第二個(gè)節(jié)點(diǎn)逢捺。

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)癞季。

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)劫瞳。

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 快慢指針 
        h1 = h2 = head
        while h2 and h2.next:
            h1 = h1.next
            h2 = h2.next.next
            if h1 == h2:
                return True
        return False

?????

IV、樹

一绷柒、二叉樹的最大深度

給定一個(gè)二叉樹志于，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)废睦。

說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)伺绽。

示例：
給定二叉樹[3,9,20,null,null,15,7]，

返回它的最大深度 3 嗜湃。

解答：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

?????

二奈应、驗(yàn)證二叉搜索樹

給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹购披。
假設(shè)一個(gè)二叉搜索樹具有如下特征：

節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)钥组。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹今瀑。

示例：

輸入:
    2
   / \
  1   3
輸出: true

輸入:
    5
   / \
  1   4
     / \
    3   6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
     根節(jié)點(diǎn)的值為 5 ，但是其右子節(jié)點(diǎn)值為 4 橘荠。

解答：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        minOrderTree = []
        self.MinOrder(root,minOrderTree);
        for i in range(len(minOrderTree)-1):
            if minOrderTree[i] >= minOrderTree[i+1]:
                return False 
        return True
    
    def MinOrder(self,root,res):
        if not root:
            return None
        self.MinOrder(root.left,res)
        res.append(root.val)
        self.MinOrder(root.right,res)

?????

三屿附、對(duì)稱二叉樹

給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的哥童。

例如挺份，二叉樹[1,2,2,3,4,4,3]是對(duì)稱的。

但是下面這個(gè)[1,2,2,null,3,null,3]則不是鏡像對(duì)稱的:

解答：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return True if root == None else self.inn(root.left, root.right)
    
    def inn(self, l1, l2):
        if l1 == None and l2 == None:
            return True
        if l1 == None or l2 == None:
            return False
        return l1.val == l2.val and self.inn(l1.left, l2.right) and self.inn(l1.right, l2.left)

?????

四贮懈、二叉樹的層序遍歷

給你一個(gè)二叉樹匀泊，請(qǐng)你返回其按 層序遍歷 得到的節(jié)點(diǎn)值。（即逐層地朵你，從左到右訪問所有節(jié)點(diǎn)）各聘。

示例：
二叉樹：[3,9,20,null,null,15,7],

返回其層次遍歷結(jié)果：

[
  [3],
  [9,20],
  [15,7]
]

解答：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result = []
        current_level = [root]
        while current_level:
            auxiliary = []
            next_level = []
            for node in current_level:
                auxiliary.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            result.append(auxiliary)
            current_level = next_level
        return result

?????

五、將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

將一個(gè)按照升序排列的有序數(shù)組抡医，轉(zhuǎn)換為一棵高度平衡二叉搜索樹躲因。
本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1忌傻。

示例：
給定有序數(shù)組:[-10,-3,0,5,9],
一個(gè)可能的答案是:[0,-3,9,-10,null,5]大脉，它可以表示下面這個(gè)高度平衡二叉搜索樹：

解答：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        middle = len(nums) // 2
        tn = TreeNode(nums[middle])
        tn.left = self.sortedArrayToBST(nums[:middle])
        tn.right = self.sortedArrayToBST(nums[middle + 1:])
        return tn

?????

V、排序和搜索

一水孩、合并兩個(gè)有序數(shù)組

給你兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2镰矿，請(qǐng)你將 nums2 合并到 nums1 中，使 nums1 成為一個(gè)有序數(shù)組俘种。

說明:

初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n 秤标。
你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素。

示例:

輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

輸出: [1,2,2,3,5,6]

解答：

def merge(nums1, m: int, nums2, n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    if not n:
        return nums1
    nums1[:] = nums1[:m] + nums2
    nums1.sort()


n1 = [1, 2, 3, 0, 0, 0]
n2 = [2, 5, 6]
merge(n1, 3, n2, 3)
print(n1)

?????

二安疗、第一個(gè)錯(cuò)誤的版本

你是產(chǎn)品經(jīng)理抛杨，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是荐类，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測怖现。由于每個(gè)版本都是基于之前的版本開發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的玉罐。
假設(shè)你有n個(gè)版本[1, 2, ..., n]屈嗤，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。
你可以通過調(diào)用bool isBadVersion(version)接口來判斷版本號(hào)version是否在單元測試中出錯(cuò)吊输。實(shí)現(xiàn)一個(gè)函數(shù)來查找第一個(gè)錯(cuò)誤的版本饶号。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)。

示例：

給定 n = 5季蚂，并且 version = 4 是第一個(gè)錯(cuò)誤的版本茫船。

調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true

所以琅束，4 是第一個(gè)錯(cuò)誤的版本。

解答：

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return n if isBadVersion(n) else 0
        st = 1
        while st <= n:
            mid = st + (n - st) // 2
            if isBadVersion(mid):
                n = mid - 1 
            else:
                st = mid + 1
        return st

?????

VI算谈、動(dòng)態(tài)規(guī)劃

一涩禀、爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂然眼。
每次你可以爬 1 或 2 個(gè)臺(tái)階艾船。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)高每。

示例：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂屿岂。
1.  1 階 + 1 階
2.  2 階

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階

解答：

def climbStairs(n: int) -> int:
    if n <= 3:
        return n
    temp = [1, 1]
    result = 0
    while (n > 1):
        result = temp[-1] + temp[-2]
        temp[-1] = temp[-2]
        temp[-2] = result
        n = n - 1
    return result

print(climbStairs(5))

?????

二鲸匿、買賣股票的最佳時(shí)機(jī)

給定一個(gè)數(shù)組爷怀，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票一次）晒骇，設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤霉撵。
注意：你不能在買入股票前賣出股票。

示例：

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入洪囤，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出徒坡，最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格瘤缩；同時(shí)喇完，你不能在買入前賣出股票。

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入剥啤，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出锦溪，最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格府怯；同時(shí)刻诊，你不能在買入前賣出股票。

解答：

def maxProfit(prices) -> int:
    if len(prices) <= 1:
        return 0
    buy = prices[0]
    sell = 0
    for i in range(len(prices)):
        buy = min(buy, prices[i])
        sell = max(sell, prices[i] - buy)
    return sell

prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))

?????

三牺丙、最大子序和

給定一個(gè)整數(shù)數(shù)組 nums 则涯，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和冲簿。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大粟判，為 6。

解答：

def maxSubArray(nums) -> int:
    l = len(nums)
    if l == 0:
        return 0
    elif l == 1:
        return nums[0]
    else:
        dp = [0 for _ in range(l)]
        dp[0] = nums[0]
        for i in range(1, l):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
        return max(dp)


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))

?????

四峦剔、打家劫舍

你是一個(gè)專業(yè)的小偷档礁，計(jì)劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金吝沫，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)呻澜，如果兩間相鄰的房屋在同一晚上被小偷闖入递礼，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組易迹，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下宰衙，能夠偷竊到的最高金額。

示例：

輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號(hào)房屋 (金額 = 1) 睹欲，然后偷竊 3 號(hào)房屋 (金額 = 3)。
     偷竊到的最高金額 = 1 + 3 = 4 一屋。

輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)窘疮，接著偷竊 5 號(hào)房屋 (金額 = 1)。
     偷竊到的最高金額 = 2 + 9 + 1 = 12 冀墨。

解答：

def rob(nums) -> int:
    l = len(nums)
    if l == 0:
        return 0
    elif l <= 2:
        return max(nums)
    else:
        a = [-1] * (l + 1)
        a[0], a[1] = 0, nums[0]
        for i in range(1, l):
            a[i + 1] = max(a[i], a[i - 1] + nums[i])
        return a[-1]


nums = [2, 7, 9, 3, 1]
print(rob(nums))

?????

VII闸衫、設(shè)計(jì)問題

一、打亂數(shù)組

打亂一個(gè)沒有重復(fù)元素的數(shù)組诽嘉。

示例：

// 以數(shù)字集合 1, 2 和 3 初始化數(shù)組蔚出。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打亂數(shù)組 [1,2,3] 并返回結(jié)果。任何 [1,2,3]的排列返回的概率應(yīng)該相同虫腋。
solution.shuffle();

// 重設(shè)數(shù)組到它的初始狀態(tài)[1,2,3]骄酗。
solution.reset();

// 隨機(jī)返回?cái)?shù)組[1,2,3]打亂后的結(jié)果。
solution.shuffle();

解答：

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.nums

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        nums2 = self.nums[:]
        l = len(nums2)
        for i in range(l):
            n = random.randrange(i, l)
            nums2[i], nums2[n] = nums2[n], nums2[i]
        return nums2


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

?????

二悦冀、最小棧

設(shè)計(jì)一個(gè)支持push趋翻，pop，top操作盒蟆，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧踏烙。

push(x)—— 將元素 x 推入棧中。
pop()—— 刪除棧頂?shù)脑亍?/li>
top()—— 獲取棧頂元素历等。
getMin()—— 檢索棧中的最小元素讨惩。

示例：

輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

輸出：
[null,null,null,null,-3,null,0,-2]

解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解答：

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return min(self.stack)

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

?????

VIII、數(shù)學(xué)

一寒屯、Fizz Buzz

寫一個(gè)程序荐捻，輸出從 1 到 n 數(shù)字的字符串表示。

如果 n 是3的倍數(shù)浩螺，輸出“Fizz”靴患；
如果 n 是5的倍數(shù)，輸出“Buzz”要出；
如果 n 同時(shí)是3和5的倍數(shù)鸳君，輸出 “FizzBuzz”。

示例：

n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

解答：

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        result = []
        for i in range(1, n + 1):
            if i % 3 == 0:
                if i % 5 == 0:
                    result.append("FizzBuzz")
                else:
                    result.append("Fizz")
            elif i % 5 == 0:
                result.append("Buzz")
            else:
                result.append(str(i))
        return result

?????

二患蹂、計(jì)數(shù)質(zhì)數(shù)

統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量或颊。

示例：

輸入: 10
輸出: 4
解釋: 小于 10 的質(zhì)數(shù)一共有 4 個(gè), 它們是 2, 3, 5, 7 砸紊。

解答：

# 一開始用的暴力循環(huán)超時(shí)了
"""
def countPrimes(n: int) -> int:
    result = 0
    if n < 3:
        return result
    result += 1
    for i in range(3, n):
        for j in range(2, i):
            if i % j == 0:
                break
            if j == i - 1:
                result += 1
    return result
"""

# 初始化一個(gè)長度為n的列表，將坐標(biāo)為質(zhì)數(shù)的標(biāo)1囱挑，非質(zhì)數(shù)標(biāo)0醉顽。

def countPrimes(n: int) -> int:
    result = [1] * max(2, n)
    result[0], result[1] = 0, 0
    x = 2
    while x * x < n:
        if result[x]:
            p = x * x
            while p < n:
                result[p] = 0
                p += x
        x += 1
    return sum(result)

n = 10
print(countPrimes(n))

?????

三、3的冪

給定一個(gè)整數(shù)平挑，寫一個(gè)函數(shù)來判斷它是否是 3 的冪次方游添。

示例：

輸入: 27
輸出: true

輸入: 0
輸出: false

解答：

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n == 1:
            return True
        elif n == 0:
            return False
        else:
            while n != 1:
                if n % 3 == 0:
                    n //= 3
                else:
                    return False
            return True

# 方法二
def isPowerOfThree(self, n: int) -> bool:
    return n > 0 and pow(3, 19) % n == 0

?????

四、羅馬數(shù)字轉(zhuǎn)整數(shù)

羅馬數(shù)字包含以下七種字符:I通熄，V唆涝，X，L唇辨，C廊酣，D和M。

字符	數(shù)值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如赏枚，羅馬數(shù)字2寫做II亡驰，即為兩個(gè)并列的1。12寫做XII饿幅，即為X + II凡辱。 27寫做XXVII, 即為XX + V + II。

通常情況下诫睬，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊煞茫。但也存在特例，例如4不寫做IIII摄凡，而是IV续徽。數(shù)字1在數(shù)字5的左邊，所表示的數(shù)等于大數(shù)5減小數(shù)1得到的數(shù)值4亲澡。同樣地钦扭，數(shù)字9表示為IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：

I可以放在V(5) 和X(10) 的左邊床绪，來表示4和9客情。
X可以放在L(50) 和C(100) 的左邊，來表示40和90癞己。
C可以放在D(500) 和M(1000) 的左邊膀斋，來表示400和900。
給定一個(gè)羅馬數(shù)字痹雅，將其轉(zhuǎn)換成整數(shù)仰担。輸入確保在1到3999的范圍內(nèi)。

示例：

輸入: "III"
輸出: 3

輸入: "IV"
輸出: 4

輸入: "IX"
輸出: 9

輸入: "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.

輸入: "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

解答：

def romanToInt(s: str) -> int:
    nums = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
        '1': 4,
        '2': 9,
        '3': 40,
        '4': 90,
        '5': 400,
        '6': 900
    }
    s = s.replace('IV', '1').replace('IX', '2').replace('XL', '3').replace('XC', '4').replace('CD', '5').replace('CM', '6')
    result = 0
    for i in s:
        result += nums[i]
    return result

s = 'MCMXCIV'
print(romanToInt(s))

?????

IX绩社、其他

一摔蓝、位1的個(gè)數(shù)

編寫一個(gè)函數(shù)赂苗，輸入是一個(gè)無符號(hào)整數(shù)，返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 ‘1’ 的個(gè)數(shù)（也被稱為漢明重量）贮尉。

示例：

輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進(jìn)制串 00000000000000000000000000001011 中拌滋，共有三位為 '1'。

輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進(jìn)制串 00000000000000000000000010000000 中猜谚，共有一位為 '1'败砂。

輸入：11111111111111111111111111111101
輸出：31
解釋：輸入的二進(jìn)制串 11111111111111111111111111111101 中，共有 31 位為 '1'魏铅。

提示：

請(qǐng)注意吠卷，在某些語言（如 Java）中，沒有無符號(hào)整數(shù)類型沦零。在這種情況下，輸入和輸出都將被指定為有符號(hào)整數(shù)類型货岭，并且不應(yīng)影響您的實(shí)現(xiàn)路操，因?yàn)闊o論整數(shù)是有符號(hào)的還是無符號(hào)的，其內(nèi)部的二進(jìn)制表示形式都是相同的千贯。
在 Java 中屯仗，編譯器使用二進(jìn)制補(bǔ)碼記法來表示有符號(hào)整數(shù)。因此搔谴，在上面的示例中魁袜，輸入表示有符號(hào)整數(shù) -3。

解答：

class Solution:
    def hammingWeight(self, n: int) -> int:
        return str(bin(n)).count('1')

?????

二敦第、漢明距離

兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對(duì)應(yīng)二進(jìn)制位不同的位置的數(shù)目峰弹。
給出兩個(gè)整數(shù) x 和 y，計(jì)算它們之間的漢明距離芜果。

注意：
0 ≤ x, y < 2³¹.

示例：

輸入: x = 1, y = 4
輸出: 2

解釋:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭頭指出了對(duì)應(yīng)二進(jìn)制位不同的位置鞠呈。

解答：

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        if not 0 <= x <= 2 ** 31 and not 0 <= y <= 2 ** 31:
            return None
        return str(bin(x ^ y)).count('1')

?????

三、顛倒二進(jìn)制位

顛倒給定的 32 位無符號(hào)整數(shù)的二進(jìn)制位右钾。

示例：

輸入: 00000010100101000001111010011100
輸出: 00111001011110000010100101000000
解釋: 輸入的二進(jìn)制串 00000010100101000001111010011100 表示無符號(hào)整數(shù) 43261596蚁吝，
     因此返回 964176192，其二進(jìn)制表示形式為 00111001011110000010100101000000舀射。

輸入：11111111111111111111111111111101
輸出：10111111111111111111111111111111
解釋：輸入的二進(jìn)制串 11111111111111111111111111111101 表示無符號(hào)整數(shù) 4294967293窘茁，
     因此返回 3221225471 其二進(jìn)制表示形式為 10111111111111111111111111111111 。

提示：

請(qǐng)注意脆烟，在某些語言（如 Java）中山林，沒有無符號(hào)整數(shù)類型。在這種情況下浩淘，輸入和輸出都將被指定為有符號(hào)整數(shù)類型捌朴，并且不應(yīng)影響您的實(shí)現(xiàn)吴攒，因?yàn)闊o論整數(shù)是有符號(hào)的還是無符號(hào)的，其內(nèi)部的二進(jìn)制表示形式都是相同的砂蔽。
在 Java 中洼怔，編譯器使用二進(jìn)制補(bǔ)碼記法來表示有符號(hào)整數(shù)。因此左驾，在上面的 示例 2 中镣隶，輸入表示有符號(hào)整數(shù) -3，輸出表示有符號(hào)整數(shù) -1073741825诡右。

解答：

class Solution:
    def reverseBits(self, n: int) -> int:
        b = list(bin(n))[2:][::-1]
        b.extend('0' * (32 - len(b)))
        b.insert(0, '0b')
        b = ''.join(b)
        return int(b, 2)

?????

四安岂、帕斯卡三角形

給定一個(gè)非負(fù)整數(shù) numRows，生成楊輝三角的前 numRows 行帆吻。

在楊輝三角中域那，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。

示例：

輸入: 5
輸出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解答：

def generate(numRows: int):
    result = []
    if numRows == 0:
        return []
    elif numRows == 1:
        result.append([1])
        return result
    else:
        result.append([1])
        for i in range(1, numRows):
            flag = []
            for j in range(i + 1):
                if j == 0 or j == i:
                    flag.append(1)
                else:
                    flag.append(result[i - 1][j - 1] + result[i - 1][j])
            result.append(flag)
        return result

numRows = 5
print(generate(numRows))

# 方法二
def generate(numRows: int) -> List[List[int]]:
    if numRows == 0:
        return []
    res = [[1]]
    if numRows != 1:
        for i in range(1, numRows):
            l = [1]
            for j in range(1, i):
                l.append(res[i - 1][j - 1] + res[i - 1][j])
            l.append(1)
            res.append(l)
    return res

?????

五猜煮、有效的括號(hào)

給定一個(gè)只包括'('次员，')'，'{'王带，'}'淑蔚，'['，']'的字符串愕撰，判斷字符串是否有效刹衫。
有效字符串需滿足：

左括號(hào)必須用相同類型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合搞挣。

注意：空字符串可被認(rèn)為是有效字符串带迟。

示例：

輸入: "()"
輸出: true

輸入: "()[]{}"
輸出: true

輸入: "(]"
輸出: false

輸入: "([)]"
輸出: false

輸入: "{[]}"
輸出: true

解答：

class Solution:
    def isValid(self, s: str) -> bool:
        for i in range(len(s) // 2):
            s = s.replace('{}', '').replace('()', '').replace('[]', '')
        if not s:
            return True
        else:
            return False

?????

六、缺失數(shù)字

給定一個(gè)包含0, 1, 2, ..., n中 n 個(gè)數(shù)的序列柿究，找出 0 .. n 中沒有出現(xiàn)在序列中的那個(gè)數(shù)邮旷。

示例：

輸入: [3,0,1]
輸出: 2

輸入: [9,6,4,2,3,5,7,0,1]
輸出: 8

說明：
你的算法應(yīng)具有線性時(shí)間復(fù)雜度。你能否僅使用額外常數(shù)空間來實(shí)現(xiàn)?

解答：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums) - 1
        s1 = n * (n + 1) // 2
        s2 = sum(nums)
        return n - (s2 - s1) + 1

leetcode算法

前言

Ⅰ.數(shù)組

一紧唱、刪除排序數(shù)組中的重復(fù)項(xiàng)

二、買賣股票的最佳時(shí)機(jī) II

三鸠匀、旋轉(zhuǎn)數(shù)組

四诽凌、存在重復(fù)元素

五财搁、只出現(xiàn)一次的數(shù)字

六、兩個(gè)數(shù)組的交集 II

七粹湃、加一

八、移動(dòng)零

九萨惑、兩數(shù)之和

十花枫、有效的數(shù)獨(dú)

十一组题、旋轉(zhuǎn)圖像

II、字符串

一耿眉、反轉(zhuǎn)字符串

二桶癣、整數(shù)反轉(zhuǎn)

三惹挟、字符串中的第一個(gè)唯一字符

四、有效的字母異位詞

五研底、驗(yàn)證回文字符串

六、字符串轉(zhuǎn)換整數(shù) (atoi)

七、實(shí)現(xiàn) strStr()

八、外觀數(shù)列

九、最長公共前綴

III、鏈表

一网缝、刪除鏈表中的節(jié)點(diǎn)

二灶芝、刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

三酸役、反轉(zhuǎn)鏈表

四晓避、合并兩個(gè)有序鏈表

五俏拱、回文鏈表

六、環(huán)形鏈表

IV、樹

一绷柒、二叉樹的最大深度

二奈应、驗(yàn)證二叉搜索樹

三屿附、對(duì)稱二叉樹

四贮懈、二叉樹的層序遍歷

五、將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

V、排序和搜索

一水孩、合并兩個(gè)有序數(shù)組

二安疗、第一個(gè)錯(cuò)誤的版本

VI算谈、動(dòng)態(tài)規(guī)劃

一涩禀、爬樓梯

二鲸匿、買賣股票的最佳時(shí)機(jī)

三牺丙、最大子序和

四峦剔、打家劫舍

VII闸衫、設(shè)計(jì)問題

一、打亂數(shù)組

二悦冀、最小棧

VIII、數(shù)學(xué)

一寒屯、Fizz Buzz

二患蹂、計(jì)數(shù)質(zhì)數(shù)

三、3的冪

四、羅馬數(shù)字轉(zhuǎn)整數(shù)

IX绩社、其他

一摔蓝、位1的個(gè)數(shù)

二敦第、漢明距離

三、顛倒二進(jìn)制位

四安岂、帕斯卡三角形

五猜煮、有效的括號(hào)

六、缺失數(shù)字