Algorithm(leetcode 算法题)

Lowest Common Ancestor of a Binary Tree

如题目名,是朴素经典的求两个树节点最小公共祖先的一道题目(换句话说懂就是懂,不懂就是不懂, 没错我就是不懂)。解法非常之多,大致分为在线算法和离线算法两类,常见包括 Tarjan、线段树、RMQ 等等

我自己挑了 RMQ 和 Tarjan 两种算法理解了下,RMQ 理解的很快不过 Tarjan 却看了好几天才在某个时刻灵机一动参透了其原理😂,之前一直对着伪代码一脸懵逼,理解了之后发现真的很简单……甚至不知道为什么之前一直没理解

Tarjan 涉及到之前仅模模糊糊有印象的并查集,这次为了 Tarjan 也一并理解了并查集的概念和基本用法,算有所收获吧,毕竟算法一直是弱项来着……

编码实现的时候稍微多想了点,想将基本的方法写成可以通用的而不仅仅只能查询两个节点的公共祖先,写着写着发现要用 Tarjan 实现似乎不太容易,RMQ 反而会很方便,所以最后还是写成了只能查询两个节点的形式

Tarjan 算法实现如下:

class TreeNode(object):
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

class Solution(object):
	def __init__(self):
		self.pre = {}
		self.nodeChildren = {}
			
	def merge(self, x, parent):
		self.nodeChildren[parent] += [x]
		self.nodeChildren[parent] += self.nodeChildren[x]
		for child in self.nodeChildren[parent]:
			self.pre[child] = parent
			
	def TarjanPrepared(self, root, queries, result):
		# queries prepared
		queryIndex, checked, queue = {}, {}, [root]
		for query in queries:
			for element in query:
				checked[element] = False
				result[element] = {}
				if element not in queryIndex:
					queryIndex[element] = [query]
				else:
					if query not in queryIndex[element]: 
						queryIndex[element].append(query)
		# pre prepared
		self.pre[root] = root
		while len(queue) != 0:
			cur = queue[0]
			self.nodeChildren[cur] = []
			if cur.left != None:
				queue.append(cur.left)
				self.pre[cur.left] = cur
			if cur.right != None:
				queue.append(cur.right)
				self.pre[cur.right] = cur
			queue.remove(cur)
		return queryIndex, checked
		
	def Tarjan(self, node, queryIndex, checked, result):
		if node.left != None:
			self.Tarjan(node.left, queryIndex, checked, result)
			self.merge(node.left, node)
			checked[node.left] = True
		if node.right != None:
			self.Tarjan(node.right, queryIndex, checked, result)
			self.merge(node.right, node)
			checked[node.right] = True
		checked[node] = True
		if node in queryIndex:
			for query in queryIndex[node]:
				queryWithoutNode = [x for x in query if x != node]
				if queryWithoutNode:
					findResult = self.pre[queryWithoutNode[0]]
					queryWithoutNode = queryWithoutNode[0]
				else:
					findResult = query[0]
					queryWithoutNode = query[0]
				if checked[queryWithoutNode]:
					result[node][queryWithoutNode] = findResult
											
	def lowestCommonAncestor(self, root, p, q):
		result = {}
		queryIndex, checked = self.TarjanPrepared(root, [[p,q]], result)
		self.Tarjan(root, queryIndex, checked, result)
		if q in result[p]:
			return result[p][q]
		elif p in result[q]:
			return result[q][p]

最终实现版本非常残忍的 TLE 了……难过到变形……😫

一开始以为是因为每次 merge 都要遍历部分树结构的原因,将原本的进队列改成了数组(nodeChildren 变量)后仍旧超时,还是卡死在 29/31 上了……emmmmm


Review(阅读并点评至少一篇技术文章)

How Distributed Ledger Technologies are set to disrupt the world’s monetary system

实不相瞒,这篇看的时候感觉非常吐血,乍看标题还以为会详细聊聊分布式账本技术,然而我又错了……(诶这既视感)

文章花了不小的篇幅介绍了 monetary system 的诞生、发展与现状,从当前主要流通的纸质货币存在的弊端引申到分布式账本引入的意义、难点等,对当前流通货币的依托价值与中央银行(Central Bank)、商业银行(Commercial Bank)之间关系的论述非常详细,还提及了通货膨胀/紧缩时期经济组织是如何通过控制货币印刷

从经济学的角度来看货币之所以能流通是因为大家普遍认可它的价值,它的根本价值又来源于能够兑换黄金(也包括别的贵金属)等抵押品(Collateral),黄金数量是有限的,但各国的纸币还在源源不断的印刷,而人们已经对纸币非常习惯以至于很少能意识到这背后的兑换关系

The money we were using every day to buy goods and services suddently lost its collateral backing and became officially just a convention. As we were used to paper money anyway, we did not perceive really that anything had changed.

电子加密货币难以取代现有货币体系的原因之一就是它与"抵押品"之间难以构建稳定的代偿关系,这里涉及到发币权、匿名交易与国际政治等

此外作者认为虽然比特币等加密货币仍难以取代现有货币体系,但美元与加密货币之间不一定是相互竞争的关系,加密货币可以

这篇文章与其说是技术更应该说是经济学主题的,感兴趣的可以细读一下做个笔记,毕竟文章比较长


Technique(技术技巧)

最近不是在看资料文档就是在做题,实际操作少得几乎可以忽略不计,根本没学到什么崭新的技术技巧Orz,只能开始往前追溯一些了……

交换文件

记得有一次 CentOS 的虚拟机上磁盘被没清理掉的 docker 文件数据占满了一时半会清不掉,但又急着要下载一个临时占内存很大的包……束手无策时发现了这个技巧,所以简单分享一下

一般来说我们可以创建两种:

  • 交换分区
  • 交换文件

创建交换文件较容易,所以当时我选择的是创建交换文件,基本上有三个备选命令,任选一条即可(/swapfile 是文件名和所在的路径):

fallocate -l 2G /swapfile

这条命令可能会失败,我操作时显示错误 fallocate operation not supported,说明有的系统不支持。失败了可以换下一条

truncate -s 2G /swapfile

这条命令创建文件的速度挺快,我是用这条成功的。不过可能会提示文件有很多漏洞从而无法使用,不行还是换下一条

dd if=/dev/zero of=/swapfile

最后这一条创建的速度据说较慢


Share(分享有观点和思考的技术文章)

这回分享的是专栏里推荐的 97 things every programmer should know 中的 1-4

(个人感觉有点不符合 Share 这栏的宗旨,不过这篇的 97 条原则也算观点的一种吧)

Act with Prudence「审慎的行动」

这一则的重点就在标题中:审慎,这没什么可多说的,都是些老生常谈的话题了:

  • 一切操作小心为上
  • 为求快速迭代欠下的技术债迟早要还,越早越好
  • 计划看起来再怎么舒适,压力迟早会到来

Apply Functional Programming Principles「运用函数式编程原则」

如今面向对象编程(OOP)广泛流行,互联网行业主流的语言、主流的开发模式似乎都围绕着这一原则进行。不从事科学计算等相关工作的编程人员几乎不会去刻意的钻研函数式编程,以至于错过了其中不少优秀的思想,如文中提到的

Ask "What Would the User Do?" (You Are not the User)「考虑用户会怎么做,(你并不是用户)」

这是非常老生常谈的话题了,开篇第一句直指重点:

We all tend to assume that other people think like us. But they don't.

人确实容易习惯于以自己的观点来揣摩他人的想法,即所谓"以己度人",这是用户调研这一工作存在的根本原因,某种意义上也是产品经理一类的岗位诞生的缘由

此外这篇还提到了一个很重要的点:用户自身未必知道自己的真实需求是什么,因此**观察用户并不等于询问用户**,所以最终还是要落实到切实观察用户真实的行为上

Automate Your Coding Standard「代码标准化流程自动化」

这也算是个老生常谈的话题了,在一个团队内大家各有不同的代码风格,一开始订好的代码规范最后总会不知不觉失去意义——没人按规范来,原因很多:

  • 不重视
  • 不认可
  • 赶时间

......

所以理论上能根治这一问题的方法就是将代码的 format 自动化,最好是直接加到构建流程中,这样无论开发人员重不重视、是不是因为赶时间忘记,最后一切都会在构建阶段被修正,线上的的代码还是能保持住规范的可读性


Written with StackEdit.