这里面存放乱七八糟懒得分类、但都很有趣的算法题目，供自己把玩。这里懒得说人话，直接英文复制了。
- 目录：
算法：附录
算法（1）：递归
算法（2）：链表
算法（3）：数组
算法（4）：字符串
算法（5）：二叉树
算法（6）：二叉查找树
算法（7）：队列和堆栈（附赠BFS和DFS）
算法（8）：动态规划
算法（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:
#这里坑了我，当时我写的是 index = hashmap[i]+1，没有考虑到此处该求 max
index = max(hashmap[i]+1,index)
maxlen = max(maxlen, idx - index + 1)
hashmap[i] = idx
return maxlen
Question7：
Question8：
呃(⊙﹏⊙)，这篇文章我就不求赞了，，，知道对大家而言参考价值很小，，，没脸求赞，，，，，，
网友评论