AI summary
type
status
date
Aug 1, 2024 06:58 AM
slug
summary
tags
category
icon
password
1. Algorithm
1.1 动态规划 DP
概述
个人理解：DP核心是子过程存在缓存（memo/cache），可以复用，此类问题就可考虑用动态规划，更书面的表达是满足以下条件时，可以考虑用DP：
- 子问题无记忆性，结果不依赖后继状态
- 答案具有重复子结构，会重复依赖子问题答案
DP常见数据结构：数组、字符串、哈希表
状压dp
数位dp
因为内容过多，新开一篇文章：算法专题 - 数位DP | Personal Blog (wangqiwei.life)
1.2 递归 DFS
递归和DP其实并不等同，但是两者又有交集
树桩DP、状态机DP等通常需要借助DFS的方式来实现
但是并不意味着所有递归都属于DP，只要没用到cache的都不算DP
递归栈调用实际执行的深度优先搜索，所以通常定义函数为dfs
题型总结
- 全排列递归，时间复杂度为O(N*N!)，另外js数组可利用交换元素实现（见下方）
- 1-1 匹配组合的问题，实际等同于对其中一边做全排列。参考 2850. 将石头分散到网格图的最少移动次数 - 力扣（LeetCode）
1.3 Math
数学类型的题，在你尝试了常规方案（模拟、暴力等）后，仍然 OOM 或着 TLE
那就需要解得题目的代数解，从而将时间和空间复杂度降到 O(1)
涉及题目
2. Data Structure
2.1 位运算
- 被 2 整除：用位运算 & 1
- X & 1：等于1是奇数，等于0是偶数
- X & (X-1)：消掉X二进制的最后一位1
- X & -X：获取X最后一位1
3. Language
3.1 C++
Vector
- 初始化
- empty - 边界情况判断
需要对数组做边界检测的场景，可以考虑用 empty，既简洁又高效
- 交换元素 swap
- 拼接 concat
- 创建 vector 切片
- 翻转数组 reverse
3.2 Python
数组
- 初始化长度为
N，值为val的数组
- 深拷贝数组
- 【Trick】for loop中，可以拼接多个数组：
- 【Trick】max + slice 获取子数组最大值，可在部分动规数组更新场景使用
二进制
- 计算1的个数
- X & 1：等于1是奇数，等于0是偶数
- X & (X-1)：消掉X二进制的最后一位1
- X & -X：获取X最后一位1
字符串
- print格式化
- 使用
%运算符：这是一种较旧的格式化方式，类似于 C 语言的printf。 - 使用
str.format()方法：这是一种更现代的格式化方式，提供了更多的功能。 - 使用 f-string：这是 Python 3.6 引入的新特性，允许你在字符串中直接嵌入表达式。
- 使用模板字符串：Python 的
string模块提供了Template类，可以用于简单的字符串替换。
在 Python 中，有多种方式可以格式化字符串：
你也可以使用位置参数和关键字参数：
在 f-string 中，你可以直接使用变量名，也可以在
{} 中使用任何有效的 Python 表达式。这些都是 Python 中常用的字符串格式化方式，你可以根据你的需求选择合适的方式。
- 获取
ASCII对应索引
- 计算某个字符出现次数 -
count()
- 拼接： 两个思路
char * len(s)char都放进数组arr，最后再用''.join(arr)
下面给出一个拼接二进制的题
Set
（from Copilot）以下是 Python
set 常用API：- add(element) ：将元素添加到集合中。如果元素已经存在于集合中，那么该方法不会有任何效果。
- remove(element)：从集合中移除元素。如果元素不存在于集合中，那么该方法会抛出一个
KeyError。
- discard(element)：从集合中移除元素。如果元素不存在于集合中，那么该方法不会有任何效果。
- pop()：移除并返回集合中的一个元素。如果集合为空，那么该方法会抛出一个
KeyError。
- clear()：移除集合中的所有元素。
- union(set2)、intersection(set2)、difference(set2) 和 symmetric_difference(set2)：这些方法分别返回两个集合的并集、交集、差集和对称差集。
- issubset(set2)、issuperset(set2) 和 isdisjoint(set2)：这些方法分别检查当前集合是否是另一个集合的子集、超集或者是否和另一个集合没有交集。
Map (defaultdict)
在Python中，处理键值对（key-value pairs）的主要数据结构是字典（
dict）。Python的字典是内置的，无需导入任何库就可以使用。以下是Python字典的一些常用API：
dict(): 创建一个新的空字典。
d[key]: 获取字典中键为key的值。如果key不存在，会抛出KeyError异常。
d[key] = value: 将键为key的值设置为value。如果key已经存在，其值会被覆盖。
d.get(key, default): 获取字典中键为key的值。如果key不存在，返回default值。
d.keys(): 返回一个包含字典所有键的视图对象。
d.values(): 返回一个包含字典所有值的视图对象。
d.items(): 返回一个包含字典所有键值对的视图对象。
key in d: 检查字典是否包含键为key的项。
d.update(other): 将另一个字典other的键值对添加到d中。如果有相同的键，d中的值会被覆盖。
那defaultdict是什么？类似的lib还有哪些？
collections.defaultdict是Python的一个内置字典类，它继承自dict，并添加了一个特性：如果你试图访问或修改一个不存在的键，defaultdict会首先使用一个提供的默认工厂函数来创建和返回一个默认值。例如：
除了
defaultdict，Python的collections模块还提供了其他几种字典类型：collections.OrderedDict: 一个字典子类，它保持了它们被添加到字典中的顺序。在Python 3.7及以后的版本中，普通的dict也保持了这个特性，所以OrderedDict主要的用途是它的popitem(last=True)方法，它可以弹出（移除并返回）字典的第一个或最后一个键值对。
collections.Counter: 一个字典子类，用于计数可哈希对象。它是一个集合，元素像字典键一样存储，它们的计数存储为值。例如，Counter('hello world')会返回一个Counter，其中'l'的计数是3。
collections.ChainMap: 一个字典类，用于创建多个映射的单一视图。如果你有多个字典，但希望能够像操作一个字典那样操作它们，那么ChainMap会非常有用。
以上这些类都在
collections模块中，这个模块提供了许多有用的数据结构，可以帮助你更有效地处理数据。实战
队列（Queue）
- 队列 - queue
- 双端队列 - deque
- 优先级队列 - heapq
其他语法
- 记忆化搜索装饰器 @cache
- 交换赋值 A,B = B,A
先说结论：
用 Python 多重赋值做交换的话，涉及嵌套对象的场景，注意嵌套深的对象放左边先交换，避免更新后影响右侧后续的赋值（该结论理论上适用于更多的赋值操作——3 层及以上数组）
Context：
问了下 Copilot：
python A,B = B,A 的实现原理是什么
Python中的多重赋值操作
A, B = B, A实际上是使用了一个临时的元组来完成交换操作。首先，Python会将等号右边的表达式
B, A封装成一个元组(B, A)。然后，Python会按照元组中的顺序依次将元素赋值给等号左边的变量，即将B赋值给A，将A赋值给B。由于在元组中元素的赋值是按照从左到右的顺序进行的，因此在交换赋值的过程中，先将
B的值赋给A，然后再将A的值赋给B，从而实现了A和B的值的交换。需要注意的是，多重赋值操作只能在等号右边的表达式是一个可迭代对象（如列表、元组等）时才可以使用。同时，等号左边的变量数量必须与等号右边的元素数量一致，否则会发生ValueError错误。
看了下上述打印值，可以看到，如果按照
list[i], list[list[i]] = list[list[i]], list[i] 的写法，原来应该是位置 0 （val 2）和位置 2（val 3） 交换， 结果位置 2 （val 3）是交换到位置 0 了，但是位置 0 （val 2）的值放到位置 3 了（val 0），即下图问题就在于，我们预期是位置 0 的 val 2交换到位置 2，但是它却跑到了位置 3，把 val 0 覆盖了
仔细分析可以看出，还是赋值语句的写法问题
因为赋值是从左往右赋值的，所以相当于先赋值
list[i] 为 3，此时再赋值 list[list[i]] 就会有问题了，因为 list[i] 已经变为新的值 3，所以导致 list[list[i]] 指向了新位置 3 的 0，最终导致交换赋值失败而如果写为
因为先赋值
list[list[i]] ，更新位置 2 的值，但不会影响到左侧 list[i] 的位置，并且根据 GPT 的回答：Python 赋值语句右侧的第二个值是存储的临时变量，i.e.，右侧 list[list[i]] 在赋值之前就定下来了，不会实时计算导致变更3.3 JavaScript
数组
- 初始化索引数组：利用
obj.keys()
- 高维数组初始化：用
[…Array(n)].map(xxx)，注意高维不能用fill（其实是fill的参数是对象引用就不行，低维也一样），否则是浅拷贝，改一个数会变化整一列，正确写法如下：
- 全排列：js的数组全排列，可以利用数组交换顺序写dfs，性能优于slice或者splice
Set
字符串
- 获取charCode
MDN
- 重复字符串（repeat）
- 操作char数组比直接增删string效率低：
二进制
- 异或 ^
- 取反 ~
- 0 - 1 互换 !
- 计算二进制的个数
3.4 Rust
3.4.1 基本类型
- i32 & i64 & i128
在Rust中，
i32和i64都是整数类型，但它们的大小和范围是不同的。i32：这是一个32位有符号整数类型，其大小为32位，取值范围从-2^31到2^31-1（即从-2147483648到2147483647），通常对应10^9范围内的数字。
i64：这是一个64位有符号整数类型，其大小为64位，取值范围从-2^63到2^63-1（即从-9223372036854775808到9223372036854775807），通常对应10^19范围内的数字。
i128：通常对应10^39范围内的数字
浮点数类型：
f32: 32位单精度浮点数。
f64: 64位双精度浮点数。
做题时，注意变量的数值范围，选择合适的类型，否则会导致计算错误
涉及题目：
- char 转 int
3.4.2 所有权 + match + Option/Result 等
以题目236. 二叉树的最近公共祖先 - 力扣（LeetCode）为例，
Copilot 和另外一个Rust Solution分别如下：== Copilot Solution ==
== Another Rust Solution ==
其中涉及的语法：
match:match是Rust的模式匹配语句，用于根据不同的模式执行不同的代码。
if let:if let是一种特殊的if语句，它尝试将表达式的值匹配到模式。如果匹配成功，它就执行相应的代码块。
Option和Result：Option是Rust的一个枚举类型，用于表示一个值可能存在（Some）或不存在（None）。- 定义/介绍：
- panic是什么？
- 还有没有其他处理方式？ — A：
unwrap和Rc<RefCell>+clone+borrow unwrapRc + clone和RefCell + borrow
as_ref和map_or：在比较node和p或q是否相等时，我们使用了Option::as_ref和Option::map_or方法。如果p或q是None，map_or方法将返回false，否则，它将使用Rc::ptr_eq函数比较node和p或q。
-
|n|
3.4.4 动态分发 dyn、迭代器Iter（chain、once）等
引自 145. 二叉树的后序遍历 - 力扣（LeetCode） ，其中一 Rust Solution
这段Rust代码使用了以下语法和特性：
- 结构体（Structs）：
TreeNode是一个结构体，它有三个字段：val，left，right。
- 枚举（Enums）：
Option是Rust的一个内建枚举，用于表示一个值可能存在（Some）或不存在（None）。
- 智能指针（Smart Pointers）：
Rc和RefCell都是Rust的智能指针。Rc允许多个所有者，RefCell允许在运行时检查借用规则。
- 模式匹配（Pattern Matching）：
match语句用于对Option进行模式匹配。
- 闭包（Closures）和迭代器（Iterators）：
iter::empty()，iter::once()，chain()都是迭代器方法。Box<dyn iter::Iterator<Item = i32>>是一个动态分发的迭代器对象。
- 函数（Functions）：
inorder是一个内部函数，它在postorder_traversal函数内部定义并使用。
- 引用（References）：
&用于创建引用，borrow()用于获取RefCell的引用。
- 类型别名（Type Aliases）：
Box<dyn iter::Iterator<Item = i32>>是一个类型别名，它表示一个在堆上分配的，能产生i32类型元素的迭代器。
- 方法（Methods）：
postorder_traversal是Solution结构体的一个方法。
- 类型推断（Type Inference）：Rust编译器可以根据上下文推断出大部分类型，例如
collect()方法的返回类型。
- Trait（Traits）：
iter::Iterator是Rust的一个Trait，它定义了一个迭代器应该具有的行为。
Box是什么？Box<dyn iter::Iterator<Item = i32>>是什么意思？
在Rust中，
Box<T>是一个"box"指针类型，它在堆上分配内存。当你有一个大型数据结构或者你想要转移数据的所有权，但又希望数据在离开作用域时自动清理，那么Box<T>就非常有用。Box<dyn Trait>是一个特殊的用法，它允许你创建一个指向实现了某个特定trait的动态类型的对象的指针。这种用法在你需要存储不同类型的对象，但又希望通过共同的trait来处理它们时非常有用。Box<dyn iter::Iterator<Item = i32>>是一个Box指针，它指向一个实现了Iterator trait的动态类型的对象，这个迭代器产生的元素类型是i32。这意味着你可以将任何产生i32元素的迭代器存储在这个Box中，然后像处理普通迭代器一样处理它。在Rust中，
Box<dyn Trait>的用法非常广泛，它允许你在运行时处理不同类型的值，只要这些值实现了特定的trait。这是一种非常强大的抽象机制，它允许你编写更加通用和灵活的代码。例如，你可能有一个函数，它接受一个
Box<dyn Display>参数，这意味着你可以传递任何实现了Display trait的类型给这个函数，函数会在运行时正确地调用相应类型的Display方法。在这个例子中，
print_it函数可以接受任何实现了Display trait的类型，包括&str和i32。这是通过Box<dyn Display>实现的，它创建了一个指向实现了Display trait的动态类型的对象的指针。同样，
Box<dyn iter::Iterator<Item = i32>>允许你处理任何产生i32元素的迭代器，无论它的具体类型是什么。这使得你可以编写处理各种迭代器的通用代码，而不需要关心它们的具体类型。dyn是什么关键字？
在Rust中，
dyn是一个关键字，用于指示"动态分发"或"动态类型"。当你有一个指向实现了某个特定trait的对象的指针时，你可以使用dyn Trait来表示这个类型。例如，
Box<dyn Display>表示一个Box，它指向一个实现了Display trait的动态类型的对象。这意味着这个Box可以包含任何实现了Display trait的类型的对象。动态分发是一种在运行时确定调用哪个方法的机制。当你调用一个通过
dyn Trait指定的方法时，Rust会在运行时查找并调用正确的方法。这与静态分发不同，静态分发在编译时就确定了调用哪个方法。使用
dyn Trait可以让你编写更加灵活和通用的代码，因为你可以处理任何实现了特定trait的类型，而不需要在编译时知道具体的类型。item的chain和once是什么含义？在什么场景下使用？
chain和once都是Rust的迭代器方法。chain方法用于将两个迭代器链接在一起，形成一个新的迭代器。新的迭代器首先返回第一个迭代器的所有元素，然后返回第二个迭代器的所有元素。这在你需要将两个迭代器的元素按顺序处理，但又不想创建一个新的包含所有元素的集合时非常有用。
例如：
这段代码将打印出1到6的所有数字。
once方法用于创建一个只产生一个元素的迭代器。这在你需要将一个单独的元素与一个迭代器的元素一起处理时非常有用。
例如：
这段代码将打印出1到4的所有数字。
在你的代码中
chain和once的使用是为了实现二叉树的后序遍历。后序遍历的顺序是先遍历左子树，然后遍历右子树，最后访问根节点。这正是chain和once所做的事情。inorder(&tree.left).chain(inorder(&tree.right))首先创建了一个迭代器，它会遍历左子树和右子树的所有节点。然后，.chain(iter::once(tree.val))将当前节点的值添加到迭代器的末尾。这样，当你遍历这个迭代器时，你就会按照后序遍历的顺序访问所有节点。这是一个非常巧妙的使用迭代器的方式，它允许你使用简洁的代码实现复杂的算法。你可以使用类似的技术来实现其他的树遍历算法，例如前序遍历和中序遍历。
rust中chain和once底层是如何实现的？大致原理是怎样？
在Rust中，
chain和once都是迭代器的方法，它们的实现都依赖于Rust的迭代器特性（Iterator trait）。chain方法的实现主要依赖于一个叫做Chain的结构体，这个结构体保存了两个迭代器。在调用next方法时，Chain首先尝试从第一个迭代器获取元素，如果第一个迭代器已经没有元素了，就从第二个迭代器获取元素。这样，Chain就能按顺序返回两个迭代器的所有元素。
once方法的实现则更为简单。它返回一个叫做Once的结构体，这个结构体保存了一个Option。在第一次调用next方法时，Once返回保存的Option并将其设置为None。在之后的调用中，Once总是返回None。这样，Once就能只产生一个元素。
这两个方法的实现都非常高效，因为它们只需要保存少量的状态，并且可以在常数时间内产生新的元素。这也是Rust迭代器的一个重要特性，即它们通常可以在不需要分配额外内存的情况下处理序列和集合。
- 作者:Tony
- 链接:https://wangqiwei.life/article/algo-snippet
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。