• 來源于leetcode題庫3,31,48,56,146,208,215,238,399

3.無重復(fù)字符的最長子串

• 題目描述

  • 給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

• 示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。

輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"，所以其長度為 3。

請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

• enumerate() 函數(shù)
  • 用于將一個可遍歷的數(shù)據(jù)對象(如列表、元組或字符串)組合為一個索引序列，同時列出數(shù)據(jù)和數(shù)據(jù)下標(biāo)，一般用在 for 循環(huán)當(dāng)中。

普通for循環(huán)
i = 0
seq = ['one', 'two', 'three']
for element in seq:
... print i, seq[i]
... i +=1
...
輸出：
0 one
1 two
2 three

for循環(huán)使用enumerate函數(shù)
seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
...print i, element
...
輸出：
0 one
1 two
2 three

• 題解：

class Solution:
    #以字符串的值為key，以下標(biāo)為value
    def lengthOfLongestSubstring(self, s: str) -> int:
        #初始化
        start,res,newdic=-1,0,{}
        #按循環(huán)順序，把s中的元素挨個放到新的newdic里去
        for i,c in enumerate(s):
            #如果c已經(jīng)在newdic中且下標(biāo)比start大
            if c in newdic and newdic[c]>start:
                start=newdic[c]#重新定位start指針
                newdic[c]=i#給這個重復(fù)字母賦上順序值
            #newdic里還沒有這個重復(fù)字母，且不需要重新定位指針
            else:
                newdic[c]=i
                res=max(res,i-start)   #更新最大子串長度   
        return res

31.

• 題目描述

  • 實(shí)現(xiàn)獲取下一個排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個更大的排列。
    如果不存在下一個更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）。
    必須原地修改，只允許使用額外常數(shù)空間。

• 示例

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

• 題解

48.旋轉(zhuǎn)圖像

• 題目描述

  • 給定一個 n × n 的二維矩陣表示一個圖像。
    將圖像順時針旋轉(zhuǎn) 90 度。
    說明：
    你必須在原地旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請不要使用另一個矩陣來旋轉(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]
]

• 題解

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        '''
        分層平移的策略，左上角坐標(biāo)為(pos1,pos1),右上角(pos1,pos2)
                     左下角作為(pos2,pos1),右下角(pos2,pos)
        '''
        pos1,pos2 = 0,len(matrix)-1
        while   pos1<pos2:
            add = 0
            while   add < pos2-pos1: # 有偏移量
                #左上角為0塊，右上角為1塊，右下角為2塊，左下角為3塊
                temp = matrix[pos2-add][pos1]
                matrix[pos2-add][pos1] = matrix[pos2][pos2-add]
                #3 = 2
                matrix[pos2][pos2-add] = matrix[pos1+add][pos2]
                #2 = 1
                matrix[pos1+add][pos2] = matrix[pos1][pos1+add]
                #1 = 0
                matrix[pos1][pos1+add] = temp
                #0 = temp
                add = add+1
            pos1 = pos1+1
            pos2 = pos2-1

56.合并區(qū)間

• 題目描述
  • 給出一個區(qū)間的集合，請合并所有重疊的區(qū)間。
• 示例

示例 1:
輸入: intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2:
輸入: intervals = [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。

• 題解
  • 來源于題解區(qū)大佬蓮子熊貓

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 本題要點(diǎn)為先按左邊界排序
        if len(intervals) == 0:
            return []
        res = []
        # 先按區(qū)間左邊界值由小到大排序
        intervals.sort(key=lambda x: x[0])  
        for inter in intervals:
            # 如果結(jié)果集最后一個元素的右邊界比新加入?yún)^(qū)間的左邊界小，直接加入結(jié)果集
            if len(res) == 0 or res[-1][1] < inter[0]:  
                res.append(inter)
            else:  # 否則，說明新加入的和結(jié)果集最后一個區(qū)間有重合，更新區(qū)間右邊界即可
                res[-1][1] = max(res[-1][1], inter[1])
        return res

146.LRU緩存機(jī)制

• 題目描述

  • 運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和實(shí)現(xiàn)一個 LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。
    獲取數(shù)據(jù) get(key) - 如果關(guān)鍵字 (key) 存在于緩存中，則獲取關(guān)鍵字的值（總是正數(shù)），否則返回 -1。
    寫入數(shù)據(jù) put(key, value) - 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字/值」。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

• 示例

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

• 題解
  • 來源于題解區(qū)大佬liye

class ListNode:
    # 用哈希表和雙鏈表實(shí)現(xiàn)
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 新建兩個節(jié)點(diǎn) head 和 tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化鏈表為 head <-> tail
        self.head.next = self.tail
        self.tail.prev = self.head

    # 因?yàn)間et與put操作都可能需要將雙向鏈表中的某個節(jié)點(diǎn)移到末尾，所以定義一個方法
    def move_node_to_tail(self, key):
            # 先將哈希表key指向的節(jié)點(diǎn)拎出來，為了簡潔起名node
            #      hashmap[key]                               hashmap[key]
            #           |                                          |
            #           V              -->                         V
            # prev <-> node <-> next         pre <-> next   ...   node
            node = self.hashmap[key]
            node.prev.next = node.next
            node.next.prev = node.prev
            # 之后將node插入到尾節(jié)點(diǎn)前
            #                 hashmap[key]                 hashmap[key]
            #                      |                            |
            #                      V        -->                 V
            # prev <-> tail  ...  node                prev <-> node <-> tail
            node.prev = self.tail.prev
            node.next = self.tail
            self.tail.prev.next = node
            self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            # 如果已經(jīng)在鏈表中了久把它移到末尾（變成最新訪問的）
            self.move_node_to_tail(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res
        else:
            return res.value

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            # 如果key本身已經(jīng)在哈希表中了就不需要在鏈表中加入新的節(jié)點(diǎn)
            # 但是需要更新字典該值對應(yīng)節(jié)點(diǎn)的value
            self.hashmap[key].value = value
            # 之后將該節(jié)點(diǎn)移到末尾
            self.move_node_to_tail(key)
        else:
            if len(self.hashmap) == self.capacity:
                # 去掉哈希表對應(yīng)項(xiàng)
                self.hashmap.pop(self.head.next.key)
                # 去掉最久沒有被訪問過的節(jié)點(diǎn)，即頭節(jié)點(diǎn)之后的節(jié)點(diǎn)
                self.head.next = self.head.next.next
                self.head.next.prev = self.head
            # 如果不在的話就插入到尾節(jié)點(diǎn)前
            new = ListNode(key, value)
            self.hashmap[key] = new
            new.prev = self.tail.prev
            new.next = self.tail
            self.tail.prev.next = new
            self.tail.prev = new

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

208.

• 題目描述
  • 實(shí)現(xiàn)一個 Trie (前綴樹)，包含 insert, search, 和 startsWith 這三個操作。
• 示例

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true

• 題解
  • 來源于題解區(qū)大佬powcai

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = {}
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                tree[a] = {}
            tree = tree[a]
        # 單詞結(jié)束標(biāo)志
        tree["#"] = "#"
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                return False
            tree = tree[a]
        if "#" in tree:
            return True
        return False
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tree = self.lookup
        for a in prefix:
            if a not in tree:
                return False
            tree = tree[a]
        return True
        



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

215.數(shù)組中第k個最大元素

• 題目描述

  • 在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

• 示例
  示例 1:
  輸入: [3,2,1,5,6,4] 和 k = 2
  輸出: 5
  示例 2:
  輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
  輸出: 4

• 題解

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 堆排序
        def adjust_heap(idx, max_len):
            left = 2 * idx + 1
            right = 2 * idx + 2
            max_loc = idx
            if left < max_len and nums[max_loc] < nums[left]:
                max_loc = left
            if right < max_len and nums[max_loc] < nums[right]:
                max_loc = right
            if max_loc != idx:
                nums[idx], nums[max_loc] = nums[max_loc], nums[idx]
                adjust_heap(max_loc, max_len)
        
        # 建堆
        n = len(nums)
        for i in range(n // 2 - 1, -1, -1):
            adjust_heap(i, n)
        #print(nums)
        res = None
        for i in range(1, k + 1):
            #print(nums)
            res = nums[0]
            nums[0], nums[-i] = nums[-i], nums[0]
            adjust_heap(0, n - i)
        return res

238.除自身以外數(shù)組的乘積

• 題目描述

  • 給你一個長度為 n 的整數(shù)數(shù)組 nums，其中 n > 1，返回輸出數(shù)組 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積。

• 示例

輸入: [1,2,3,4]
輸出: [24,12,8,6]

• 題解
  • 來源于題解區(qū)大佬krahets

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        '''
        res數(shù)組列為乘積形式(當(dāng)前位置數(shù)字不相乘可以等價為乘1)
        res[0] =  1  *  nums[1]  *  nums[2]  ...  *  nums[n-1]
        res[1] =  nums[0]  *  1  *  nums[2]  ...  *  nums[n-1]
        ...
        res[n-1] = nums[0]  *  nums[1]  ...  *  nums[n-2]  *  1
        經(jīng)過上述排列可發(fā)現(xiàn)矩陣主對角線上全為1，分別計算矩陣的上三角和下三角，并存儲值
        '''
        res, p, q = [1], 1, 1
        for i in range(len(nums) - 1): # 下三角
            p *= nums[i]
            res.append(p)
        for i in range(len(nums) - 1, 0, -1): # 上三角
            q *= nums[i]
            res[i - 1] *= q
        return res

399.

• 題目描述

• 示例

• 題解