PowerLZY's Blog

算法长征（3）哈希表

发表于 2022-05-23 更新于 2022-07-03 分类于【draft】工程，数据结构本文字数： 841 阅读时长 ≈ 2 分钟

dict 字典

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

Counter(nums).most_common(1)[0] [0]

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return Counter(nums).most_common(1)[0][0]
    def majorityElement(self, nums: List[int]) -> int:
        majority_count = len(nums) // 2
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" 输出：true 解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

迭代器 pairwise

1
2
3

def isAlienSorted(self, words: List[str], order: str) -> bool:
       index = {c: i for i, c in enumerate(order)}
       return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))

算法长征（4）字符串

发表于 2022-05-23 更新于 2022-06-27 分类于【draft】工程，数据结构本文字数： 4k 阅读时长 ≈ 7 分钟

字符串

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

1
2
3

class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(" ", "%20")

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

字符串切片、列表遍历拼接、字符串遍历拼接

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]
		def reverseLeftWords(self, s: str, n: int) -> str:
      	# 列表遍历拼接
        res = []
        for i in range(n, len(s)):
            res.append(s[i])
        for i in range(n):
            res.append(s[i])
        return ''.join(res)
    def reverseLeftWords(self, s: str, n: int) -> str:
      	# 字符串遍历拼接
        res = "" # 字符为不可变对象，每轮都新建
        for i in range(n, len(s)):
            res += s[i]
        for i in range(n):
            res += s[i]
        return res

以 Python 为例开展三种方法的效率测试：

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m, n = len(s1), len(s2)
        if m > n:
            return False
        key = [0] * 26
        cur = [0] * 26 
        for i in range(m):
            key[ord(s1[i]) - ord('a')] += 1
            cur[ord(s2[i]) - ord('a')] += 1
        if key == cur:
            return True
        for j in range(n - m):
            cur[ord(s2[j]) - ord('a')] -= 1
            cur[ord(s2[j + m]) - ord('a')] += 1
            if key == cur:
                return True
        return False

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

字典数组、滑动窗口

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        if s_len < p_len:
            return []
        ans = []
        s_count = [0] * 26
        p_count = [0] * 26
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1
        if s_count == p_count:
            ans.append(0)
        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i + p_len]) - 97] += 1
            if s_count == p_count:
                ans.append(i + 1)
        return ans

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left, lookup, n = 0, set(), len(s)
        max_len, cur_len = 0, 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left]) # 移除做元素直到无重复，到最小无重复子串
                left += 1
                cur_len -= 1
            if cur_len > max_len:
                max_len = cur_len
            lookup.add(s[i])
        return max_len

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

滑动窗口

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        s_len, t_len = len(s), len(t)
        if s_len < t_len:
            return ""
        # 0 不删除
        sdict, tdict = defaultdict(int), Counter(t)
        left, conut = 0, 0
        res = ""
        for i in range(s_len):
            sdict[s[i]] += 1
            if sdict[s[i]] <= tdict[s[i]]:
                conut += 1
            while left <= i and sdict[s[left]] > tdict[s[left]]:
                # 加一个A就减一个A...(无用后缀)
                sdict[s[left]] -= 1
                left += 1
            if conut == t_len:
                if not res or (i - left + 1 < len(res)):
                    res = s[left:i + 1]
        return res

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        n = len(s)
        left, right = 0, n - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if left < right:
                if s[left].lower() != s[right].lower():
                    return False
                left, right = left + 1, right - 1
        return True

给定一个非空字符串 s，请判断如果最多从字符串中删除一个字符能否得到一个回文字符串。

class Solution:
    def validPalindrome(self, s: str) -> bool:
        # 回溯， 广度优先 【字符串长度，暴搜必定超时】
        def checkPalind(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
        n = len(s)
        left, right = 0, n - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return checkPalind(left + 1, right) or checkPalind(left, right - 1)
        return True

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

动态规划、双指针+中心扩展、==Manacher算法==

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 双指针+中心扩散
        result = 0
        def _extend(s, i, j, n):
            res = 0
            while i >= 0 and j < n and s[i] == s[j]: # 确定中心点
                i -= 1
                j += 1
                res += 1 # 扩散过程也是答案
            return res
        for i in range(len(s)):
            result += _extend(s, i, i, len(s)) #以i为中心
            result += _extend(s, i, i+1, len(s)) #以i和i+1为中心
        return result

    def countSubstrings(self, s: str) -> int:
        # 动态规划 dp[i][j]: s[i:j] 是否为回文子串
        # dp[i+1][j-1] -> dp[i][j] 遍历顺序 
        n = len(s)
        dp = [[False] * (n) for _ in range(n)]
        ans = 0
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i] == s[j]:
                    if j - i <= 1:
                        ans += 1
                        dp[i][j] = True
                    elif dp[i+1][j-1]:
                        ans += 1
                        dp[i][j] = True
        return ans

算法长征（4）查找算法

发表于 2022-05-23 更新于 2022-07-14 分类于【draft】工程，数据结构本文字数： 8.8k 阅读时长 ≈ 16 分钟

查找算法

bisect 文档:https://docs.python.org/zh-cn/3.6/library/bisect.html

二分查找求左边界 第一个 False : 不小于target的第一个数

def leftMargin(): # 左边界
   left, right = 0, len(nums) - 1
	while left <= right:
       mid = (left + right) // 2
       if nums[mid] < target: # ... Ture # False ...
          left = mid + 1
       else:
          right = mid - 1
   return left if nums[left] == target else -1 # 越界检验

二分查找右边界 [第一个 True ]

def rightMargin(): # 右边界
		left, right = 0, len(nums) - 1
    while left <= right:
    		mid = (left + right) // 2
        if nums[mid] > target: # ... False # Ture ...
           right = mid - 1
        else:
           left = mid + 1
    return right if nums[right] == target else -1

找出数组中重复的数字。==在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内==。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

哈希表 / Set、原地交换（空间0（1））
合理利用 val 和 key 的关系

class Solution:
    def findRepeatNumber(self, nums: [int]) -> int:
        dic = set()
        for num in nums:
            if num in dic: return num
            dic.add(num)
        return -1
		def findRepeatNumber(self, nums: [int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i:
                i += 1
                continue
            if nums[nums[i]] == nums[i]: 
              	return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1

统计一个数字在排序数组中出现的次数。

找到目标值「最后」出现的分割点，并「往前」进行统计

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        # 求右边界
        while left <= right:
            mid = (right + left) // 2
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        # 最后要检查 right 越界的情况
        if right < 0 or nums[right] != target:
            return 0
        ans = 0
        while right >= 0 and nums[right] == target :
            right -= 1
            ans += 1
        return ans

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

排序数组中的搜索问题，首先想到 二分法 解决。
- 根据题意，数组可以按照以下规则划分为两部分
  - 左子数组： nums[i] = i
  - 右子数组： nums[i] = i
缺失的数字等于 “右子数组的首位元素” 对应的索引；因此考虑使用二分法查找 “右子数组的首位元素” 。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == m: 
              	i = m + 1
            else: 
              	j = m - 1
        return i

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

我们将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        i, j = len(matrix) - 1, 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target: 
              	i -= 1
            elif matrix[i][j] < target: 
              	j += 1
            else: 
              	return True
        return False

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

二分查找

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        # 无法判断左右， right -= 1 缩小范围
        left, right = 0, len(numbers) - 1
        while left < right:
            mid = left + (right - left) // 2
            if numbers[mid] < numbers[right]:
                right = mid
            elif numbers[mid] > numbers[right]:
                left = mid + 1
            else:
                right -= 1
        return numbers[left]

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

哈希表存储频数、索引

class Solution:
    def firstUniqChar(self, s: str) -> str:
        frequency = collections.Counter(s)
        for i, ch in enumerate(s):
            if frequency[ch] == 1:
                return ch
        return ' '

队列：使用了「延迟删除」这一技巧

class Solution:
    def firstUniqChar(self, s: str) -> str:
        position = dict()
        q = collections.deque()
        n = len(s)
        for i, ch in enumerate(s):
            if ch not in position:
                position[ch] = i
                q.append((s[i], i))
            else:
                position[ch] = -1
                while q and position[q[0][0]] == -1:
                    q.popleft()
        return ' ' if not q else q[0][0]

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

from sortedcontainers import SortedList

class Solution:
    def reversePairs(self, nums):
        # 逆序 + 二分插入
        import bisect
        res = 0
        q = []
        n = len(nums)
        for i in range(n-1,-1,-1):
            s = nums[i]
            j = bisect.bisect_left(q, s)
            res += j
            q[j:j] = [s] 
        return res
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)       
        sl = SortedList()
        ans = 0
        for i in range(n-1, -1, -1):        # 反向遍历
            cnt = sl.bisect_left(nums[i])   # 找到右边比当前值小的元素个数
            ans += cnt                      # 记入答案
            sl.add(nums[i])                 # 将当前值加入有序数组中
        
        return ans

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

二分查找、双指针

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 二分查找
        n = len(numbers)
        for i in range(n):
            left, right = i + 1, n - 1
            while left <= right:
                mid = (left + right) // 2
                if numbers[mid] == target - numbers[i]:
                    return [i + 1, mid + 1]
                elif numbers[mid] > target - numbers[i]:
                    right = mid - 1
                else:
                    left = mid + 1
        return [-1, -1] 
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 双指针
        low, high = 0, len(numbers) - 1
        while low < high:
            total = numbers[low] + numbers[high]
            if total == target:
                return [low + 1, high + 1]
            elif total < target:
                low += 1
            else:
                high -= 1
        return [-1, -1]

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

排序 + 双指针 + 去重

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 排序 + 双指针 + 去冲
        n = len(nums)
        nums.sort()
        ans = []
        for i in range(n):
            if nums[i] > 0: # 剪枝加速
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i + 1, n - 1
            while left < right:
                cur = nums[i] + nums[left] + nums[right]
                if cur == 0:
                    ans.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    right -= 1
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    left += 1
                elif cur > 0:
                    right -= 1
                else:
                    left += 1
        return ans

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

前缀和 + 二分查找 o(nlogn)、滑动窗口o(n)【连续，正整数】

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 【前缀和 + 二分查找 o(nlogn)】
        if sum(nums) < target:
            return 0
        n = len(nums)
        pre = list(accumulate([0] + nums)) # itertools.accumulate()
        ans = n + 1
        for i in range(n + 1):
            cur = target + pre[i]
            """
            left = bisect.bisect_left(pre, cur)
            """ 
            left = i + 1
            right = n
            while left <= right:
                mid = (left + right) // 2
                if pre[mid] < cur:
                    left = mid + 1
                else:
                    right = mid - 1
            if left != n+1: 
                ans = min(ans, left - i)
        return ans 
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if sum(nums) < target:
            return 0
        cur, res = 0, len(nums) + 1
        i = 0
        for j, var in enumerate(nums):
            cur += var
            while i <= j and cur >= target:
                if (t:= j - i + 1) < res:
                    res = t 
                cur -= nums[i]
                i += 1
        return res

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 前缀和单调 + 二分查找
        if k == 0:
            return 0
        k = math.log(k)
        pre = [0]
        for num in nums:
            pre.append(pre[-1] + math.log(num))
        cur = res =  0
        for i in range(1, len(pre)):
            cur = k + pre[i - 1]
            j = bisect.bisect_left(pre, cur, lo = i)
            res += j - i 
        return res
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 滑动窗口
        n = len(nums)
        left, right = 0, n - 1
        res = 0
        i, cur =0,  1
        for j, num in enumerate(nums):
            cur *= num
            while i <= j and cur >= k: # 左跟着右
                cur //= nums[i]
                i += 1
            res += j - i + 1
        return res

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

二分查找 o(logN)

利用按位异或的性质，可以得到mid 和相邻的数之间的如下关系，其中 ⊕ 是按位异或运算符：

当mid 是偶数时，mid+1=mid⊕1；
当mid 是奇数时，mid−1=mid⊕1。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) // 2
            if nums[mid] == nums[mid ^ 1]:
                low = mid + 1
            else:
                high = mid
        return nums[low]

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

class Solution:
    def __init__(self, w: List[int]):
        self.pre = list(accumulate(w))
        self.total = sum(w)
    def pickIndex(self) -> int:
        # 前缀和 + 二分查找
        r = random.randint(1, self.total)
        return bisect_left(self.pre, r)

狒狒喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。狒狒可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = max(1, sum(piles) // h), max(piles)
        def check(k):
            count = 0
            for pile in piles:
                count += ceil(pile / k)
            return count > h
        while left <= right: 
            mid = (left + right) // 2
            if check(mid): # ... Ture # False(r) ...
                left = mid + 1
            else:
                right = mid - 1
        return left

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 输出：13 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

优先队列：这个矩阵的每一行均为一个有序数组。问题即转化为从这 nn 个有序数组中找第 kk 大的数，可以想到利用归并排序的做法，归并到第 kk 个数即可停止。需要用小根堆维护，以优化时间复杂度。
二分查找
- 初始位置在 matrix [n - 1] [0]（即左下角）；
- 设当前位置为 matrix [i] [j]。若 matrix [i] [j] ≤mid，则将当前所在列的不大于 mid 的数的数量（即 i + 1i+1）累加到答案中，并向右移动，否则向上移动；
- 可以线性计算对于任意一个 mid，矩阵中有多少数不大于它。这满足了二分查找的性质。

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # 优先队列
        n = len(matrix)
        heap = [(matrix[i][0], i, 0) for i in range(n)]
        heapq.heapify(heap)
        res = 0
        for i in range(k - 1):
            num, x, y = heapq.heappop(heap)
            if y != n - 1:
                heapq.heappush(heap, (matrix[x][y + 1], x, y + 1))
        return heap[0][0]
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # 二分查找
        n = len(matrix)
        def check(mid):
            i, j = n - 1, 0
            num = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    num += i + 1
                    j += 1
                else:
                    i -= 1
            return num < k 
        # 【第一个False】
        left, right = matrix[0][0], matrix[-1][-1]
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return left

算法长征（1）数组

发表于 2022-05-23 更新于 2022-06-16 分类于【draft】工程，数据结构本文字数： 709 阅读时长 ≈ 1 分钟

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。【分治】【==大数打印解法==】

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        def dfs(index, num, digit):
            if index == digit:
                res.append(int(''.join(num)))
                return
            for i in range(10):
                num.append(str(i))
                dfs(index + 1, num, digit)
                num.pop()
        res = []
        for digit in range(1, n + 1):
            for first in range(1, 10):
                num = [str(first)]
                dfs(1, num, digit)
        
        return res

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的==子数组==的个数 。

-1000 <= nums[i] <= 1000
前缀和 + 哈希表优化

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = collections.defaultdict(int)
        dic[0] = 1
        res = preNum = 0
        for i in range(len(nums)):
            preNum += nums[i]
            res += dic[preNum - k]
            dic[preNum] += 1
        return res

算法长征（2）链表

发表于 2022-05-23 更新于 2022-07-13 分类于【draft】工程，数据结构本文字数： 6k 阅读时长 ≈ 11 分钟

链表

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

递归、辅助栈

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

class Solution:
  	def reversePrint(self, head: ListNode) -> List[int]:
    		# 递归法
        return self.reversePrint(head.next) + [head.val] if head else []
    def reversePrint(self, head: ListNode) -> List[int]:
      	# 辅助栈法
        if not head:
            return []
        ans = []
        while head:
            ans.append(head.val)
            head = head.next
        return list(reversed(ans))

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

递归、迭代

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
      	# 迭代
        cur, pre = head, None
        while cur:
            tmp = cur.next # 暂存后继节点 cur.next
            cur.next = pre # 修改 next 引用指向
            pre = cur      # pre 暂存 cur
            cur = tmp      # cur 访问下一节点
        return pre
      
    def reverseList(self, head: ListNode) -> ListNode:
      	# 递归
        def recur(cur, pre):
            if not cur: return pre     # 终止条件
            res = recur(cur.next, cur) # 递归后继节点
            cur.next = pre             # 修改节点引用指向
            return res                 # 返回反转链表的头节点
        
        return recur(head, None)       # 调用递归并返回

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

defaultdict()，空为0

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        # 拼接+拆分 【哈希表】
        if not head:
            return head
        dic = collections.defaultdict()
        cur = head
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            dic[cur].next = dic[cur.next] if cur.next else None
            dic[cur].random = dic[cur.random] if cur.random else None# keyerror
            cur = cur.next
        return dic[head]

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next

给定一个链表，返回链表开始入环的第一个节点。从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA and not headB:
            return headA
        p, q = headA, headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

从后往前加【反转链表初始化】、倒序添加

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def reverseList(head: ListNode) -> ListNode:
            if not head:
                return head
            pre, cur = None, head
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            return pre

        if not l1 and not l2:
            return 
        l1 = reverseList(l1)
        l2 = reverseList(l2)
        more = 0
        p = None
        while l1 or l2:
            # 倒序添加
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            total = val1 + val2 + more
            more, cur = divmod(total, 10)
            p = ListNode(cur, p)
            l1 = l1.next if l1 else l1
            l2 = l2.next if l2 else l2
        if more != 0:
            p = ListNode(more, p)
        return p

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

列表的中点、插入节点; 线性表存储

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        def reverseList(head: ListNode) -> ListNode:
            pre, cur = None, head
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            return pre
        fast, slow = head.next, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        mid, slow.next = slow.next, None
        left, cur = head, reverseList(mid)
        slow.next = None
        while cur:
            tmp = cur.next
            cur.next = left.next
            left.next = cur
            left = cur.next
            cur = tmp
        return head

给定一个链表的 头节点 head ，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        def reverseList(head: ListNode) -> ListNode:
            pre, cur = None, head
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            return pre
        slow = fast = head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
        left, right = head, slow.next
        slow.next = None
        right = reverseList(right)
        while left and right:
            if left.val != right.val:
                return False
            left, right = left.next, right.next
        return True

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

深度优先搜索、栈迭代

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
      	# 栈迭代
        if head == None:
            return head
        dummy = Node(-1, None, None, None)
        pre = dummy
        stk = [head]
        while stk:
            x = stk.pop()
            pre.next = x
            x.prev = pre
            if x.next:
                stk.append(x.next)
            if x.child:
                stk.append(x.child)
                x.child = None
            pre = x
        dummy.next.prev = None
        return dummy.next
		def flatten(self, head: 'Node') -> 'Node':
        if head == None:
            return head
        dummy = Node(-1, None, None, None)
        def dfs(pre: 'Node', cur: 'Node') -> 'Node':
            if cur == None:
                return pre   
            pre.next = cur
            cur.prev = pre

            nxt_head = cur.next         #相当于4

            tail = dfs(cur, cur.child)  #相当于dfs(3, 7)
            cur.child = None
            
            return dfs(tail, nxt_head)  #相当于dfs(12, 4)
        dfs(dummy, head)
        dummy.next.prev = None
        return dummy.next

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

循环链表边界判断

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if not head:
            node =  Node(insertVal)
            node.next = node
            return node
        cur = head
        while True:
            if cur.val <= insertVal <= cur.next.val:
                cur.next = Node(insertVal, cur.next)
                return head
            elif cur.next.val < cur.val:
                if insertVal >= cur.val or insertVal <= cur.next.val:
                    cur.next = Node(insertVal, cur.next)
                    return head
            else:
                # 走到原点了，还是没有
                if cur.next == head:
                    cur.next = Node(insertVal, cur.next)
                    return head
            cur = cur.next

列表反转二

算法长征-Hot100

发表于 2022-05-23 分类于【draft】工程，数据结构本文字数： 781 阅读时长 ≈ 1 分钟

一、前缀树

一种好用的树结构：Trie树:https://zhuanlan.zhihu.com/p/508575094

1.1 Trie树简介 [有限状态自动机] [文本词频统计]

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie这个术语来自于retrieval。根据词源学，trie的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是，其他作者把它读作/ˈtraɪ/ "try"。

在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。 Eg.一个保存了8个单词的字典树的结构如下图所示，8个单词分别是：“A”，“to”，“tea”，“ted”，“ten”，“i” ，“in”，“inn”。

另外，单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

1.2 Trie树性质

它有3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符；
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
每个节点的所有子节点包含的字符都不相同。

1.3 基本操作

其基本操作有：查找、插入和删除,当然删除操作比较少见。

二、LRU

算法长征（13）结构设计

发表于 2022-05-23 更新于 2022-07-11 分类于【draft】工程，数据结构本文字数： 9k 阅读时长 ≈ 16 分钟

一、前缀树

一种好用的树结构：Trie树:https://zhuanlan.zhihu.com/p/508575094

1.1 Trie树简介 [有限状态自动机] [文本词频统计]

Trie这个术语来自于retrieval。根据词源学，trie的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是，其他作者把它读作/ˈtraɪ/ "try"。

1.2 Trie树性质

它有3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符；
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
每个节点的所有子节点包含的字符都不相同。

1.3 基本操作

其基本操作有：查找、插入和删除,当然删除操作比较少见。

1.4 实现方法

搜索字典项目的方法为：

从根结点开始一次搜索；
取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
迭代过程……
在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。其他操作类似处理

1.5 实现Trie (前缀树)

Trie（发音类似 "try"）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() :初始化前缀树对象。
- self.children = [None] * 26 , 指向子节点的指针数组 children
- self.isEnd = False , 表示该节点是否为字符串的结尾。
void insert(String word) :向前缀树中插入字符串 word 。
- 我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
  - 子节点存在。沿着指针移动到子节点，继续处理下一个字符。
  - 子节点不存在。创建一个新的子节点，记录在children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
- 重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
- 我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
  - 子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
  - 子节点不存在。说明字典树中不包含该前缀，返回空指针。
- 重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
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

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False
    
    def searchPrefix(self, prefix: str) -> "Trie":
        node = self # 根节点
        for ch in prefix:
            ch = ord(ch) - ord("a")
            if not node.children[ch]:
                return None
            node = node.children[ch]
        return node

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            ch = ord(ch) - ord("a")
            if not node.children[ch]:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None

二、LRU

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

class DLinkedNode:
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
        
class LRUCache:
    def __init__(self, capacity: int):
      	# 使用伪头部和伪尾部节点    
        self.cache = dict()
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 如果 key 存在，先通过哈希表定位，再移到头部
        node = self.cache[key]
        self.moveToHead(node)# "如果数据被访问过。那未来的访问几率更高"
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
          	# 如果 key 不存在，创建一个新的节点
            node = DLinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            # 添加至双向链表的头部
            self.size += 1
            self.addToHead(node)
            if self.size > self.capacity:
              	# 如果超出容量，删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
          	# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node): 
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

LFU，最近不经常使用，把数据加入到链表中，按频次排序，一个数据被访问过，把它的频次+1，发生淘汰的时候，把频次低的淘汰掉。比如有数据 1，1，1，2，2，3 缓存中有（1(3次)，2(2次)）当3加入的时候，得把后面的2淘汰，变成（1(3次)，3(1次)）区别：LRU 是得把 1 淘汰。

三、并查集

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给定一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

class UnionFind:
  	# 并查集
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.count = n
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            self.parent[x] = y
            self.count -= 1

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
      	# 相似的字符串
        m, n = len(strs), len(strs[0])
        un = UnionFind(m)
        for i in range(m):
            for j in range(i + 1, m):
                cnt = 0
                for k in range(n):
                    if strs[i][k] != strs[j][k]:
                        cnt += 1
                        if cnt > 2:
                            break
                else: # 上下文管理器
                    un.union(i, j)
        return un.count

四、序列化与反序列化

https://zhuanlan.zhihu.com/p/40462507

序列化：把对象转化为可传输的字节序列过程称为序列化。

反序列化：把字节序列还原为对象的过程称为反序列化。

4.1 序列化的定义

序列化：把对象转化为可传输的字节序列过程称为序列化。

反序列化：把字节序列还原为对象的过程称为反序列化。

4.2 为什么要序列化？

其实序列化最终的目的是为了对象可以跨平台存储，和进行网络传输。而我们进行跨平台存储和网络传输的方式就是IO，而我们的IO支持的数据格式就是字节数组。序列化只是一种拆装组装对象的规则，那么这种规则肯定也可能有多种多样，比如现在常见的序列化方式有：

JDK（不支持跨语言）、JSON、XML、Hessian、Kryo（不支持跨语言）、Thrift、Protostuff、FST（不支持跨语言）

请实现两个函数，分别用来序列化和反序列化二叉树。你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

深度优先遍历

class Codec:
    def serialize(self, root):
        # 后续遍历 比 前序遍历快很多 pop(), pop(0)
        """ DFS : ncodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return 'None'
        return  str(self.serialize(root.left)) + ',' + str(self.serialize(root.right)) + ',' + str(root.val) 

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def dfs(dfslist:list()):
            val = dfslist.pop()
            if val == 'None':
                return None
            root = TreeNode(int(val))
            root.right = dfs(dfslist)
            root.left = dfs(dfslist)
            return root
        dfslist = data.split(',')
        return dfs(dfslist)

五、线段树

算法学习笔记(14): 线段树：https://zhuanlan.zhihu.com/p/106118909

线段树（Segment Tree）几乎是算法竞赛最常用的数据结构了，它主要用于维护区间信息（要求满足结合律）。与树状数组相比，它可以实现 $O(\log n)$ 的区间修改，还可以同时支持多种操作（加、乘)，更具通用性。

class BIT:
    # 线段树: 动态维护前缀和数据的结构
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n+1)
    @staticmethod
    def lowbit(x):
        # 二进制最小位1的位置
        return x&(-x)
    def query(self, x):
        ans = 0
        while x>0:
            ans += self.tree[x]
            x -= BIT.lowbit(x)
        return ans
    def update(self, x):
        while x<=self.n:
            self.tree[x] += 1
            x += BIT.lowbit(x)

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

离散化树状数组
- 单点更新 update(i, v)： 把序列 ii 位置的数加上一个值 v，这题 v=1
- 区间查询 query(i)： 查询序列 [1⋯i] 区间的区间和，即 ii 位置的前缀和

修改和查询的时间代价都是 O(logn)，其中 n为需要维护前缀和的序列的长度。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # 离散化+线性数组 nums = [7,5,6,4]
        n = len(nums)
        # 求每个数比他小的有几个
        tmp = sorted(nums)
        for i in range(n):
            nums[i] = bisect.bisect_left(tmp, nums[i]) + 1
        # nums = [4,2,3,1]
        bit = BIT(n) # [0,0,0,0,0]
        ans = 0
        for i in range(n-1, -1, -1):
            ans += bit.query(nums[i] - 1)
            bit.update(nums[i])
        return ans

自动机

字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。

因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：

我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s'。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s' 的表格即可解决题目中的问题。

算法：

本题可以建立如下图所示的自动机：

fig1

我们也可以用下面的表格来表示这个自动机：

接下来编程部分就非常简单了：我们只需要把上面这个状态转换表抄进代码即可。另外自动机也需要记录当前已经输入的数字，只要在 s' 为 in_number 时，更新我们输入的数字，即可最终得到输入的数字。

INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31

class Automaton:
    def __init__(self):
        self.state = 'start'
        self.sign = 1
        self.ans = 0
        self.table = {
            'start': ['start', 'signed', 'in_number', 'end'],
            'signed': ['end', 'end', 'in_number', 'end'],
            'in_number': ['end', 'end', 'in_number', 'end'],
            'end': ['end', 'end', 'end', 'end'],
        }
    def get_col(self, c):
        if c.isspace():
            return 0
        if c == '+' or c == '-':
            return 1
        if c.isdigit():
            return 2
        return 3

    def get(self, c):
        self.state = self.table[self.state][self.get_col(c)]
        if self.state == 'in_number':
            self.ans = self.ans * 10 + int(c)
            self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
        elif self.state == 'signed':
            self.sign = 1 if c == '+' else -1

class Solution:
    def myAtoi(self, str: str) -> int:
        automaton = Automaton()
        for c in str:
            automaton.get(c)
        return automaton.sign * automaton.ans

安全场景（3）高级威胁发现

发表于 2022-05-20 分类于【draft】应用，应用场景，网络安全本文字数： 1.4k 阅读时长 ≈ 2 分钟

安全场景 - 高级威胁发现

CSKB: A Cyber Security Knowledge Base Based on Knowledge Graph

一、背景

APT 一般具有三个特性，即高级性、持续性和危害性。在 APT 的攻击模型方面，包括了杀伤链模型、钻石模型、TTP模型和ATT&CK模型等。

1.1 威胁模型

（a) 杀伤链模型

杀伤链模型，最初起源于军事中的 C5KISR 系统中的 K（kill），后由洛克希德-马丁公司（全球最大的国防工程承包商，根据 Cybersecurity 500 名单，洛克希德-马丁公司在全球上市网络安全企业中位列前十）提出网络安全杀伤链七步模型，用来识别和防护网络入侵行为。网络安全杀伤链七步模型包括侦测、武器化、投递、漏洞利用、安装、控制和目标行动等。

（b) 钻石模型

钻石模型是由 Sergio Caltagirone、Andrew Pendergast、Christopher Betz 在 2013 年论文 The Diamond Model of Intrusion Analysis 中提出的一个针对网络入侵攻击的分析框架模型。该模型由四个核心特征组成，分别为：对手（adversary）、能力（capability）、基础设施（infrastructure）和受害者（victim）。四个核心特征间用连线表示相互间的基本关系，并按照菱形排列，从而形成类似“钻石”形状的结构，因此得名为“钻石模型”。同时，模型还定义了社会-政治关系（对手和受害者之间的）和技术能力（用于确保能力和基础设施可操作性的）两个重要的扩展元特征。该模型也认为，无论何种入侵活动，其基本的元素都是一个一个的事件，而每个事件都可以由上述四个基本核心特征组成。

（c) TTP模型

TTP，该术语来自于三个英文词汇的首字母组合，即战术 Tactics、技术 Techniques 和过程 Procedures，是描述高级威胁组织网络攻击的重要指标，出自于《美国国防部军事及相关术语词典》，最早用于军事领域和反恐活动，后延伸到信息安全领域，并被用来描述相应的过程。TTP 在网络情报中是核心信息，它与指标、事件、活动、攻击者、攻击目标有着密切的关联关系。

（d) ATT&CK模型

ATT&CK 也就是 Adversarial Tactics, Techniques, and Common Knowledge。顾名思义，这并不是一项技术，而是“对抗战术、技术和常识”框架，是更加底层“知识库”的基础框架，是由攻击者在攻击企业时会利用的 12 种战术和 244 种企业技术组成的精选知识库。它的着眼点不是单个的 IOC，而是 IOC 处于攻击过程中的上下文，也就是从点扩展到了面扩展到了链。当 ATT&CK 把那些翻阅字典一样，轻易地找到相对应的常见战术动作，甚至做到杀伤链还原，更好地应对攻击。

APT 最经典的防护模型之一则是滑动标尺模型，它来源于美国系统网络安全协会（SANS），主要应对日益复杂的网络环境和不断变化的攻击手段。

滑动标尺模型分为五大类别，这五大类别之间具有连续关系，并有效展示了防御逐步提升的理念。这五大类别不是固定不变的，且重要程度不是均等的, 每个类别的某些措施与相邻类别密切相关,实现网络安全目标，组织应构建安全根基和文化，并不断完善，滑动标尺模型还能潜在促进组织的安全成熟进程。

特征工程（0）特征工程 vs 表示学习

发表于 2022-05-19 更新于 2023-04-26 分类于算法，特征工程本文字数： 2.1k 阅读时长 ≈ 4 分钟

1. 表示学习

当我们学习一个复杂概念时，总想有一条捷径可以化繁为简。机器学习模型也不例外，如果有经过提炼的对于原始数据的更好表达，往往可以使得后续任务事倍功半。这也是表示学习的基本思路，即找到对于原始数据更好的表达，以方便后续任务（比如分类）。

举个简单的例子, 假设我们有 $\{x, y\}$, 想要寻找 $x$ 与 $y$ 之间的关系。 \[ x=\left[\begin{array}{cccc} 1 & 2 & 1 & 0 \\ 2 & 3 & 2 & 1 \\ 1 & 6 & 1 & 4 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 17 \end{array}\right], \quad y=\left[\begin{array}{c} 6 \\ 10 \\ 14 \\ 18 \\ 22 \end{array}\right] \] 如果单用肉眼看的话, $x$ 这个矩阵其实还是比较复杂的, 无法直接发现与 $y$ 间的关系。但如果我们非常幸运, 发现 $x$ 每行相加后的结果 $[4,8,12,16,20]^T$, 就可以直接看出 $x$ 与 $y$ 之间的关系是 $y=x+2$ 。这个例子是为了说明: 同样的数据的不同表达, 会直接决定后续任务的难易程度, 因此找到好的数据表示往往是机器学习的核心任务。值得注意的是, 在现实情况中我们所提炼的到表示往往是很复杂的, 往往对于高维矩阵提取到特征也是高维矩阵。这个例子仅供抛砖引玉之用, 表示学习不等于维度压缩或者特征选择。

2. 特征工程与表示学习：人工 vs. 自动

正因为数据表示的重要性，机器学习一般有两种思路来提升原始数据的表达：

特征学习(feature learning)，又叫表示学习(representation learning)或者表征学习，一般指的是自动学习有用的数据特征。深度学习的最终目标，就是完全自动化的广义数据处理。
特征工程(feature engineering)，主要指对于数据的人为处理提取，有时候也代指“洗数据”。

不难看出，两者的主要区别在于前者是“学习的过程”，而后者被认为是一门“人为的工程”。用更加白话的方式来说，特征学习是从数据中自动抽取特征或者表示的方法，这个学习过程是模型自主的。而特征工程的过程是人为的对数据进行处理，得到我们认为的、适合后续模型使用的样式。根据这个思路，机器学习模型对于数据的处理可以被大致归类到两个方向：

表示学习：模型自动对输入数据进行学习，得到更有利于使用的特征(*可能同时做出了预测)。代表的算法大致包括：
- 深度学习，包括大部分常见的模型如CNN/RNN/DBN等。
- 某些无监督学习算法，如主成分分析(PCA) 及 自编码器（autoencoder）通过对数据转化而使得输入数据更有意义。
- 某些树模型可以自动的学习到数据中的特征并同时作出预测。
特征工程：模型依赖人为处理的数据特征，而模型的主要任务是预测，比如简单的线性回归期待良好的输入数据(如离散化后的数据)

3. 模型选择

回归到问题的本质，就要谈谈什么时候用「手工提取」什么时候用「表示学习」。一种简单的看法是，要想自动学习到数据的良好表达，就需要大量的数据。这个现象也解释了为什么「特征工程」往往在中小数据集上表现良好，而「表示学习」在大量复杂数据上更有用武之地。

而一切的根本，其实在于假设。比如我们会假设数据分布，会假设映射函数的性质，也会假设预测值与输入值间的关系。这一切假设其实并非凭空猜想，而是基于我们对于问题的理解，从某种角度来看，这是一种先验，是贝叶斯模型。在中小数据集上的机器学习往往使用的就是强假设模型（人类知识先验）+一个简单线性分类器。当数据愈发复杂，数据量逐渐加大后，我们对于数据的理解越来越肤浅，做出的假设也越来越倾向于随机，那么此时人工特征工程往往是有害的，而需要使用摆脱了人类先验的模型，比如深度学习或者集成模型。

换句话说，模型选择的过程其实也是在衡量我们对于问题及数据的理解是否深刻，是在人类先验与数据量之间的一场博弈。从这个角度来看，深度学习首先革的是传统机器学习模型的命：最先被淘汰的不是工人，而是特定场景下的传统机器学习模型。

但话说回来，在很多领域数据依然是稀缺的，我们依然需要人工的手段来提炼数据。而这样的尝试其实并不罕见，我也写过一篇「Stacking」与「神经网络」介绍如何模拟神经网络在中小数据集上无监督的抽取特征，并最终提升数据的表示。另一个相关的问题是，到底多少数据才算多？可以参考这篇文章：「机器学习」到底需要多少数据？。

然而，相同的数据对于不同的任务也要求不同的数据表达，最优的数据表示并非是绝对的。类比来看，人类是由细胞组成的，器官也是由细胞组成的。在器官层面来看，细胞是很好的表达。而从人类角度来看，器官是比较好的表达，因为我们可以通过身高体重来区分人，而无法直观地通过细胞来区分人。然而再往前看一步，每个人的细胞携带不同的遗传信息，因此也可以被认为是一种很强的数据表达。讲这个故事的目的是说明，什么是好的数据表达，其实是非常模棱两可的问题，在不同语境下可能大不相同。

特征工程（5）特征融合

发表于 2022-05-17 更新于 2023-04-26 分类于算法，特征工程本文字数： 2.3k 阅读时长 ≈ 4 分钟

特征工程｜数据清洗（预处理）、特征生成、特征拼接

这或许是全网最全机器学习模型融合方法总结！：https://zhuanlan.zhihu.com/p/511246278

特征工程的完整流程是：特征设计 -> 特征获取 -> 特征处理 -> 特征存储 -> 特征监控。前边介绍了那么多，相当于是对特征设计、特征获取、特征存储进行了说明，而特征工程中最重要的环节则是特征处理。特征处理中还包括：数据清洗、特征生成、特征拼接、特征处理、特征转换、特征选择。本篇主要介绍数据清洗、特征生成、特征拼接。

一、数据清洗

从特征工程角度讲，数据清洗是特征工程的前置阶段（但是也会贯穿整个数据应用过程），其本义是对数据进行重新的审查和校验，目的在于删除重复信息、纠正存在的错误数据，并保证数据的一致性。数据清洗是整个数据分析过程中不可缺少的一个环节，其结果质量直接关系到模型效果和最终结论。

一个特征处理的完整流程可以表示为：

因此基础数据的准确性、完备性、一致性决定了后续特征数据的有效性。在我们日常使用的公开数据集中，很多都是已经被处理后的了，比如学术界中使用很广泛的MovieLens数据集，但是在真实的业务场景中，我们拿到的数据其实直接是没有办法使用的，可能包含了大量的缺失值，可能包含大量的噪音，也可能因为人工录入错误导致有异常点存在，对我们挖据出有效信息造成了一定的困扰，所以我们需要通过一些方法，尽量提高数据的质量。

初期数据清洗更多的是针对单条样本数据的清洗和检测，包括：

数据表示一致性处理
逻辑错误值处理
缺失值处理
非必要性数据剔除

在实际的业务场景中，数据是由系统收集或用户填写而来，有很大可能性在格式和内容上存在一些问题，同样类型的数据在不同的团队上报过程中产出的内容或格式会不一致，同样不同数据源采集而来的数据内容和格式也会不一致。

数据格式的一致性。比如时间信息（以2020年6月18日，11点11分12秒为例），有的用毫秒时间戳表示（1592449872000），有的用秒时间戳表示（1592449872），有的用带横线的时间表示（2020-06-18 11:11:12），有的则用不带横线的时间表示（20200618 11:11:12）。

数据类型的一致性。比如不同的数据表中，同样表示用户ID的字段，有的可能是string类型，有的是int类型。如果用string类型表示，如果用户id缺失的话，正常可以留空，但是不同团队，不同人对于缺失的id处理方式也会不一致，比如有的用None，有的用Null，有的则用0表示，可谓是千奇百怪。小编在日常工作中也会经常遇到这种情况，被折磨的体无完肤。

二、特征生成

对基础数据进行清理之后需要做的就是生成我们需要的特征，在特征设计部分提到特征主要分为四大维度，根据小编的经验特征又可以根据其值的属性划分为：

类别特征：即特征的属性值是一个有限的集合，比如用户性别、事物的类别、事物的ID编码类特征等
连续特征：即用户行为、类别、组合特征之类的统计值，比如用户观看的视频部数、某类别下事物的个数等
时间序列特征：即和时间相关的特征，比如用户来访时间、用户停留时长、当前时间等。
组合特征：即多种类别的组合特征，比如用户在某个类别下的行为统计特征、当天内事物被访问次数特征等
文本特征：即和文本相关的特征，比如评论数据、商品描述、新闻内容等。
Embedding特征：即一些基础特征的高层次表示，比如用户ID编码的Embedding表示、事物ID编码的Embedding表示、用户访问事物序列的Embedding编码等。

三、特征融合

多模态特征融合三部曲: https://zhuanlan.zhihu.com/p/390668652

推荐系统（六）—— 特征融合 : https://zhuanlan.zhihu.com/p/459012483

3.1 特征处理

假设你有三种类型数据，或者说可以是三个不同维度的向量.

\[ x_1 \in \mathbb{R}^{n_1}, x_2 \in \mathbb{R}^{n_2}, x_3 \in \mathbb{R}^{n_3} \]

第一种融合手段就是在训练前进行的

三个向量直接concat，可能维度会比较高，再进行个PCA
自编码器结构：三个向量通过MLP映射成一个维度后相加，用还原回去；融合特征再用来做后续的模型设计和训练就好了。

3.2 模型结构

一种直接的思想就是分而治之，多分支网络；还有一种比较出名的在中间层进行融合的方法，多模态双线性矩阵分解池化方法（MFB），本质上就是对不同模态数据进行双线性融合，借助矩阵分解的思想，再对原始特征进行高维映射，然后element-wise相乘后再做pooling操作。

3.3 后处理

后处理其实也是分而治之的思想，多模态数据分别训练不同的模型，再将不同模型的预测输出进行融合，比如平均、加权，或者fix住原来的多个网络，后面再加一层进行微调。

3.4 特征融合是什么？和特征交叉有什么区别呢？

在上一篇文章（yu-lzn：推荐系统（五）—— 特征交叉）中，我们讨论了特征交叉，特征交叉也称为特征组合，旨在提高模型对非线性的建模能力，从而提高模型的性能。特征融合和特征交叉有相同的目的，都是为了提高模型的性能。特征融合是想更好地利用不同特性的特征。

随着信息时代的发展，在推荐系统中，多模态信息的融合也变得越来越重要。以淘宝购物为例，用户在决策是否购买物品时，会考虑物品的属性、物品图片的展示、其他用户的评论信息、甚至是观看物品的介绍视频等等。换句话说，这些多模态信息（文本、图片、视频）会影响用户的行为。所以如何利用这些多模态信息来建模，是提高推荐系统准确度的一个途径。那么如何去融合这些不同来源的信息便是一个关键的问题。

dict 字典

字符串

查找算法

链表

列表反转二

一、前缀树

1.1 Trie树简介 [有限状态自动机] [文本词频统计]

1.2 Trie树性质

1.3 基本操作

二、LRU

一、前缀树

1.1 Trie树简介 [有限状态自动机] [文本词频统计]

1.2 Trie树性质

1.3 基本操作

1.4 实现方法

1.5 实现Trie (前缀树)

二、LRU

三、并查集

四、序列化与反序列化

4.1 序列化的定义

4.2 为什么要序列化？

深度优先遍历

五、线段树

离散化树状数组

自动机

算法：

安全场景 - 高级威胁发现

一、背景

1.1 威胁模型

（a) 杀伤链模型

（b) 钻石模型

（c) TTP模型

（d) ATT&CK模型

1. 表示学习

2. 特征工程与表示学习：人工 vs. 自动

3. 模型选择

特征工程｜数据清洗（预处理）、特征生成、特征拼接

一、数据清洗

二、特征生成

三、特征融合

3.1 特征处理

3.2 模型结构

3.3 后处理

3.4 特征融合是什么？和特征交叉有什么区别呢？