haruhiui

# ASTC 纹理格式 一般的纹理压缩格式都有两个要素，color endpoint 和 weight grid，即端点颜色和权重表，具体的数据部分由权重表示，在解压时通过权重从两个端点颜色之间插值出结果颜色。 weight grid 数据部分的大小定义为 grid size。另一个和 size 相关的概念是 block size，表示将几乘几的像素一起进行压缩。ASTC 格式的压缩结果都是 128 bits，ASTC4X4 就是将 4X4 的像素压缩到 128 bits，这样平均每个像素有 8 bits 数据；ASTC6X6 则是将 6X6 的像素数据压缩到 128...

# Binary Exponentiation Binary Exponentiation 快速幂算法，或者叫二进制取幂。 LeetCode 模板题：50. Pow(x, n) 递归版： bi-exp-recur.pyclass Solution: def myPow(self, x: float, n: int) -> float: if n < 0: return 1 / self.myPow(x, -n) if n == 0: return 1 if n == 1: return x return self.myPow(x * x, n // 2) * (x if n...

# LCA 一个树的 Lowest Common Ancestor 最近公共祖先。 这篇文章主要目的是在于寻找解决类似 LCA 问题的统一方法。就图一乐 # 两个结点都存在 LeetCode 模板题：236. 二叉树的最近公共祖先 lc236.py# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor(self,...

# Length of LIS LIS: Longest Increasing Subsequence 最长递增子序列。Length of LIS 就是求一个数组中最长子序列的长度。 300. Longest Increasing Subsequence 总的来说，有两种方法，一种是 DP，另一种还是 DP。 第一种 DP： len-LIS-1.pyclass Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) dp = [1] * n for i in range(n): for j in...

Binary Tree Traversal 二叉树遍历。 前序、中序、后序遍历用到的数据结构都是栈，使用 Python 的 list 来表示栈，有 append() 和 pop() 方法，都是 O(1) 时间。需要注意的是 list 的带参数的 pop(i) 复杂度是 O(n) 。（所以一般如果要用队列的话最好不要用 list 而是用 collections.deque() 的 append() 和 popleft() 来达到 O(1) 。） # 前序遍历 LeetCode 模板题：144. 二叉树的前序遍历 顺序是根左右。 递归版： preorder-recur.py# Definition...

# Trie 前缀树。 借鉴自 宫水三叶 大佬的 【设计数据结构】实现 Trie (前缀树)。 Trie 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串 / 字符前缀」是否存在的数据结构。 其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。 # 208. 实现 Trie (前缀树) 实现 Trie 类： Trie () 初始化前缀树对象。 void insert (String word) 向前缀树中插入字符串 word 。 boolean search (String word) 如果字符串 word 在前缀树中，返回...

# 博弈论 292. Nim 游戏 只要 n 不能被 4 整除即可。 lc292-1.pyclass Solution: def canWinNim(self, n: int) -> bool: return n % 4 != 0810. 黑板异或游戏 说到异或我想到之前面试时面试官问的一道题，这里顺便说一下：一个数组里只有一个数字单独出现了一次，其他数字都出现了两次，如何找出这个数字。 对一个数异或偶数次结果都是 0，所以把这个数组所有元素进行异或的结果就是单独的数字。 那么如果这个数组有两个不同的、只出现了一次的数字，该怎么找出来？ ……...

Linked List 链表。 面试时要是有链表相关题目，需要问清楚是单链表还是双链表、有没有可能有环。 # 亿点点练习题 # 206. Reverse Linked List 最基础的反转链表。 lc206-1.py# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def reverseList(self, head: Optional[ListNode])...

# 练习 # 37. 解数独 lc37-1.py class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ rows = [[False] * 9 for _ in range(9)] cols = [[False] * 9 for _ in range(9)] cell = [[False] * 9 for _ in...

# 不同的写法 为什么要研究几种不同的写法？说到底只是闲的无聊罢了。 # 写法一 翻译自 Variants of Binary Search 。 binary_search_1.pydef contains(nums, low, high, key): ans = False while low <= high: mid = (low + high) // 2 if nums[mid] < key: low = mid + 1 elif nums[mid] > key: high = mid - 1 elif nums[mid] == key: return...