算法：附錄 - 簡書

這里面存放亂七八糟懶得分類石景、但都很有趣的算法題目劈猿，供自己把玩。這里懶得說人話潮孽，直接英文復(fù)制了揪荣。

目錄：
算法：附錄
 算法（1）：遞歸
 算法（2）：鏈表
 算法（3）：數(shù)組
 算法（4）：字符串
 算法（5）：二叉樹
 算法（6）：二叉查找樹
 算法（7）：隊列和堆棧（附贈BFS和DFS）
算法（8）：動態(tài)規(guī)劃
 算法（9）：哈希表
 算法（10）：排序
 算法（11）：回溯法
 算法（12）：位操作

Question 1：Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
example1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
example2:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
explaination:
Maintain buckets each of size t+1 holding the last k elements. This is the invariant.
Buckets are [0, t], [t+1,2t+1], [2t+2, 3t+2],....
What are the conditions of a match? Either x lies in a bucket which already has a member (this directly means that x and this element are within t of each other). Or the two neighbors of around this bucket may have a potential match. Check the code for an explanation.
Lastly we notice how we purge elements from the cache/buckets which are stale i.e. outside the window of k elements.
Notice one more thing: -3//5 = -1 - Python does this automatically and hence we dont need any special magic for handling negative numbers.

maybe you will have this question:
In this code d[m] = nums[i],this will let d[m] always be last nums[i] since one key can only be one value. In abs(nums[i] - d[m - 1]) , why is that d[m-1] value not others in (m-1)th bucket.
The answer is:There will be at most 1 value in 1 bucket. If you have others in (m-1)th bucket, it must have already returned True when you find two values in the same (m-1)th bucket.

def containsNearbyAlmostDuplicate( nums: list, k: int, t: int) -> bool:
    if k < 1 or t < 0:
        return False
    cache = {}
    for i in range(len(nums)):
        if i - k > 0:
            bucket_id_to_delete = nums[i - k - 1] // (t + 1)
            del cache[bucket_id_to_delete]
        bucket_id = nums[i] // (t + 1)
        condition1 = (bucket_id in cache)
        condition2 = ((bucket_id - 1 in cache and abs(cache[bucket_id - 1] - nums[i]) <= t))
        condition3 = ((bucket_id + 1 in cache and abs(cache[bucket_id + 1] - nums[i]) <= t))
        if condition1 or condition2 or condition3:
            return True
        cache[bucket_id] = nums[i]
    return False

if __name__ == '__main__':
    nums = [1, 2, 3, 1]
    k = 3
    t = 0
    ans = containsNearbyAlmostDuplicate(nums,3,0)
    print(ans)

Question 2：01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

Example 1: 
Input:     Output:
0 0 0      0 0 0
0 1 0      0 1 0
0 0 0      0 0 0

Example 2: 
Input:     Output:
0 0 0      0 0 0
0 1 0      0 1 0
1 1 1      1 2 1

Codes are as follows：

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        q, m, n = [], len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] != 0:
                    matrix[i][j] = 0x7fffffff   ##其實大于10000就好了
                else:
                    q.append((i, j))
        while q:
            i,j = q.pop(0)
            for r, c in ((i, 1+j), (i, j-1), (i+1, j), (i-1, j)):
                z = matrix[i][j] + 1
                if 0 <= r < m and 0 <= c < n and matrix[r][c] > z:
                    matrix[r][c] = z
                    q.append((r, c))
        return matrix

Question3：Valid Sudoku
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        return 1 == max(list(collections.Counter(
            x
            for i, row in enumerate(board)
            for j, c in enumerate(row)
            if c != '.'
            for x in ((c, i), (j, c), (i//3, j//3, c))
        ).values()) + [1])

Question4: Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        def trv(root):
            if not root: return "null"
            struct = "%s,%s,%s" % (str(root.val), trv(root.left), trv(root.right))
            nodes[struct].append(root)
            return struct
        
        nodes = collections.defaultdict(list)
        trv(root)
        return [nodes[struct][0] for struct in nodes if len(nodes[struct]) > 1]

Question5：4Sum II
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:2
Explanation:
The two tuples are:
1.(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2.(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        AB = collections.Counter(a+b for a in A for b in B)
        return sum(AB[-c-d] for c in C for d in D)

Question6：Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.

Example1：
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example2：
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxlen = 0
        hashmap = {}
        index = 0
        for idx,i in enumerate(s):
            if i in hashmap:
                #這里坑了我，當(dāng)時我寫的是 index = hashmap[i]+1往史，沒有考慮到此處該求 max
                index = max(hashmap[i]+1,index)   
            maxlen = max(maxlen, idx - index + 1)
            hashmap[i] = idx
        return maxlen

Question7：

Question8：

呃(⊙﹏⊙)仗颈，這篇文章我就不求贊了，椎例，挨决，知道對大家而言參考價值很小请祖，，脖祈，沒臉求贊肆捕，，盖高，福压，，或舞，