零、碎碎念
我们时代的问题是，在第二等重要的事情上聪明，在头等重要的事情上全然无知；在小事上理智而冷静，在大事上像个疯子在赌博。我们零售的是理智，批发的是疯狂。
──列奥·施特劳斯《自然权利与历史》
我想人的确是会在某个时间点上意识到，人生可以在长达五到十年的尺度上演化。
阿里系企业常常有一个员工入职时长的纪念日，所谓“三年陈，五年醇”。这是时间在职场上的尺度。
惊闻以前高中同学因为抑郁症离世，这才发觉死亡已经逐步逼近。假设人生有百年时光，我可能已经走了三分之一了。
“答对了！” 老师说。“微积分也是如此。你学习微积分，不是因为要在日常生活中使用，而是因为它让你的思维变得更强大。”
一、Algorithm
每周至少做一个算法题。
计划每天做两道新题目，复习之前的题目，这样可以有更好的刷题效果。
本周主题是哈希表、树&二叉树&二叉搜索树，时间稍微有点紧。不过没关系，加加油。
1.1 有效的字母异位词 242. Valid Anagram
字母异位词是指两个单词由同样个数、种类的字母组成，但是顺序不一样的情况。
例如：s = “anagram”, t = “nagaram” 就是字母异位词。Anagram
题目分析：
由字母异位词的特征可以得到，两个单词的字母种类、数量一样，但是顺序不一致。
如何确定两个单词由相同的字母序列组成呢？
可以简化成两个单词中的字母数量都相同。此时只需遍历两个单词数组，对每个字母进行计数即可。
暴力法就我把两个单词的每个单词出现的数量都算出来，然后对比一下
做的过程中做了优化，直接用一个数组来计算，遍历两次，一次在数组上做加法，第二次在数组上做减法。并且使用了字符编码来做数组下标，因此时间复杂度到了 O(n)，空间复杂度也是 O(n)
最终做到了接近最优的性能：
Beats 95.53%of users with JavaScript
var isAnagram = function(s, t) {
const words = [];
for (let i = 0; i < s.length; ++i) {
const strCode = s[i].charCodeAt();
words[strCode] = words[strCode] === undefined ? 1 : words[strCode] +1;
}
for (let i = 0; i < t.length; ++i) {
const strCode = t[i].charCodeAt();
words[strCode] = words[strCode] === undefined ? 1 : words[strCode] -1;
}
return words.every(it=>it===0||it === null);
};
const result = isAnagram('anagram','nagaram');
console.log(result)1.2 两数之和 1. Two Sum
经典题目，这里用哈希表来实现
JavaScript 版本
var twoSum = function(nums,target){
var map = new Map();
for (var i = 0; i < nums.length; ++i) {
var complement = target - nums[i];
if(map.has(complement)){
return [map.get(complement), i];
}
map.set(nums[i],i)
}
console.log('No complement');
}Python 版本
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_dict = {} # 哈希表，用于存储元素和索引的映射关系
for i in range(len(nums)):
complement = target - nums[i] # 当前元素的补数
if complement in num_dict:
return [num_dict[complement], i]
num_dict[nums[i]] = i # 将当前元素及其索引存入哈希表1.3 三数之和 15. 3Sum
TwoSum 的升级版本。
解析：要求从给定数组中找出三个元素，其值加起来等于 0.
思路一：双指针法
一个外层指针，两个内层指针。
const result = [];
const n = nums.length;
// 首先对数组进行排序
nums.sort((a, b) => a - b);
for (let i = 0; i < n - 2; i++) {
// 跳过重复的外层指针元素
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let left = i + 1;
let right = n - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
// 跳过重复的内层指针元素
while (left < right && nums[left] === nums[left + 1]) {
left++;
}
while (left < right && nums[right] === nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;思路二：分解成两次 Two Sum，即先遍历数组，对每个元素 a 都计算一遍 TwoSum，找到其对应的值 b，再对 b 和剩下的元素计算一次 TwoSum，这样将三数之和分解成找 2 个数字
1.4 验证二叉搜索树 98. Validate Binary Search Tree
这道题需要确定什么是二叉搜索树，它有什么性质。
二叉搜索树是二叉树的一种，他的每个节点的值都满足以下条件：
- 左子树上所有节点都小于根节点的值
- 右子树上的节点都大于跟节点的值
- 左右子树本身也是二叉搜索树
而要验证是否是有效的二叉搜索树，只要进行一次中序遍历，验证每个子树是否符合上面三个条件即可。遍历二叉树通常可以使用递归方法。可以写出以下 js 代码
var isValidBST = function(root) {
// 初始化成负无穷，避免第一个节点的值小于初始化的prev而引起错判。
let prev = -Infinity;
function inorderTraversal(node) {
if (node === null) {
return true;
}
// 遍历左子树
if (!inorderTraversal(node.left)) {
return false;
}
// 检查当前节点值是否大于前一个节点值
if (node.val <= prev) {
return false;
}
prev = node.val;
// 遍历右子树
return inorderTraversal(node.right);
}
return inorderTraversal(root);
}时间复杂度是 O(n)，因为在中序遍历二叉树时，每个节点都会被访问并且只被访问一次。
Python 版本
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def inorder_traversal(node,prev):
if node is None:
return True
if not inorder_traversal(node.left,prev):
return False
if node.val <= prev[0]:
return False
prev[0] = node.val
return inorder_traversal(node.right,prev)
prev = [float('-inf')]
return inorder_traversal(root,prev)也可以用迭代法来写中序遍历：
js 版本
1.5 二叉树的最近公共祖先
236. Lowest Common Ancestor of a Binary Tree
使用递归来实现
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root is None or root == p or root == q:
return root
left_LCA = self.lowestCommonAncestor(root.left, p, q)
right_LCA = self.lowestCommonAncestor(root.right, p, q)
if left_LCA and right_LCA:
return root
elif left_LCA:
return left_LCA
else:
return right_LCA迭代法实现
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# 使用字典来存储每个节点的父节点
parent = {root: None}
# 使用栈进行迭代
stack = [root]
# 建立每个节点的父节点信息
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
# 存储所有p节点的祖先
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
# 找到第一个同时也是q节点的祖先
while q not in ancestors:
q = parent[q]
return q1.6 二叉搜索树的最近公共祖先
235. Lowest Common Ancestor of a Binary Search Tree
解法和 236 一样，逐步去迭代即可，甚至解法都一样…
不知道为啥，可能有别的玄机？
1.7 Pow(x,n) 50. Pow(x, n)
使用一次循环实现，并且用二分法来计算幂，还需要考虑 n 为负数的情况
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n == 0:
return 1.0
if n < 0:
x = 1 / x
n = -n
result = 1
while n > 0:
if n % 2 == 1:
result *= x
x *= x
n //= 2
return result此时的时间复杂度是 O(log n)
快速幂方法
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
def fast_pow(x, n):
if n == 0:
return 1.0
half_pow = fast_pow(x, n // 2)
if n % 2 == 0:
return half_pow * half_pow
else:
if n > 0:
return x * half_pow * half_pow
else:
return (1 / x) * half_pow * half_pow
if n < 0:
x = 1 / x
n = -n
return fast_pow(x, n)在 n 比较大时，快速幂算法比二分法更具优势
其他的优化方法：
分治法加速版，在分治的基础上，利用指数的奇偶性来进一步减少计算次数
def power(x, n):
if n == 0:
return 1.0
if n < 0:
x = 1 / x
n = -n
half_pow = power(x, n // 2)
if n % 2 == 0:
return half_pow * half_pow
else:
return x * half_pow * half_pow时间复杂度仍然是 O(log n)
1.8 求众数 169. Majority Element
这里的众数指在长度为 n 的数组中出现次数大于 n/2 的元素
Boyer-Moore 投票算法
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count = 1
elif num == candidate:
count += 1
else:
count -=1
return candidate这个方法只需要遍历一次，因此时间复杂度是 O(n)
哈希表统计法
将每个元素出现的个数存到哈希表里，然后取出出现次数超过一半的元素
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count_map = {}
threshold = len(nums) // 2
for num in nums:
if num in count_map:
count_map[num] += 1
else:
count_map[num] = 1
if count_map[num] > threshold:
return num
return None这个方法的时间复杂度是 O(n)，每个元素遍历一次
二、Review
每周阅读并点评至少一篇英文文章。
看别人写的文章并点评
为什么学微积分
“答对了！” 老师说。“微积分也是如此。你学习微积分，不是因为要在日常生活中使用，而是因为它让你的思维变得更强大。”
刷算法题也一样，日常工作中不大会有需要你写算法的时候，但是算法练习可以让思维变得强大，让你更关注性能和优化。
How is LLaMa.cpp possible
https://finbarr.ca/how-is-llama-cpp-possible/
大语言模型运行起来往往需要昂贵的大显存 GPU，但是 llama.cpp 工程实现了仅使用 CPU 来实现推理，甚至能够在树莓派上以较低的速度运行。它是怎么做到的呢？
整个环节中的影响因素是显存带宽和计算单元。
三、Tip
每周学习并分享至少一个技术技巧
日常开发中的技巧
3.1 如何将数组转换成对象？
使用 for xxx in 配合 Object.entries()
export function convertArrayToObject(inputArray) {
const licenseExtMap = {};
for (const [index, item] of inputArray.entries()) {
if (item && item.licenseUrl) {
const licenseType: number = index;
licenseExtMap[licenseType] = {
'licenseUrl': item.licenseUrl,
'licenseType': String(licenseType)
};
}
}
return licenseExtMap;
}3.2 任务的优先级比单纯的追求做更多的事情更重要
最近看到有个说法：有些博主有空去研究效率工具的前提之一是"保持单身"。
原因是有女朋友或者结婚、有小孩后个人时间急剧减少，已经没有单身时有大把的个人时间花在折腾工具上。这似乎可以佐证为什么企业偏向招聘年轻人，因为他们皮实耐用，没有家庭需要照顾，可以花更多的精力在工作上。
当然也看到另一个角度的说法，有人认为结婚后的人会更注重有效率的工作，把精力花在真正重要的地方。因为精力的确已经不够了，在有限的时间精力里想要得到更多，就需要对爱好、工作目标等做最优的选择
四、Share
每周分享至少一篇有观点和思考的技术文章。
最好是自己写的文章。
Neuro 一个 AI Vtuber
这一篇不是技术文章，而是之前刷 B 站看到了这个 AI Vtuber，也就是所谓的人工智能虚拟 Vtuber，至于效果如何可以看下视频，我是觉得很惊艳。
这个 Vtuber 作者是 vedal，他写了一个对想要做类似的 AI 助手的一篇建议。
总体来看是比较概略性的，因为作者说自己是自学编程，需要从兴趣出发。当然也提到了 Python、OpenAI 等关键词。
个人博客的定位与信噪比
从信息消费者角度来看，如果一个博客老是在伤春悲秋而对我有用的内容非常少，除非我自己也是这方面的爱好者，想看一看不同的人的生活方式是怎样的，否则我是不会将其放到订阅列表的。
这种做法未免有些功利，然而就前文所说，一个中年人的时间总是有限的，其实没有那么多精力花在关注别人的事情上面。
不过作为自己写个人博客的话，似乎可以更自由一点，毕竟自己的博客自己做主。