Algorithm(leetcode 算法题)

这周出于各种各样的原因写了不少道题,最近写的题多了,略微能感觉到自己的数据结构和算法有进步了^-^(我觉得我还可以再抢救一下)

不过要达到 channel 里讨论的那样一小时写出来并 AC 果然还是办不到……思考和一点点的修正编码 bug、思路缺陷还是会花掉大量时间😢,果然还是基础不扎实吧 (抢救不过来了送火葬场吧)

Sudoku Solver

这应该是这周最难的一题,记得周二凌晨就开始看题写出了基本代码,但一步步修正花了很长时间

因为也玩过数独,所以编码的方案混合了自己玩的思路和算法的策略。这回解题的时候特意记录了一下自己的思路,大概是这样的:

graph LR
a("规模如何?") --> | 大 | b("其他")
b --> g("特定的寻找方案")
g --> e
a --> | 不大 | c("暴力搜索")
c --> d("能否优化暴力搜索空间?")
d --> | 检测顺序调整 | e("当前格可能性唯一优先")
e --> | 循环 | f("更新状态")
f --> e

总之就是基于 BFS 的解法暴力搜索,开始搜索前循环把能填的空格(具有唯一解)都给填了,如果没填完再考虑暴力搜索方案

到了最后还不知道为什么一模一样的示例输入本地运行能正确输出答案,上传 leetcode 却显示没有任何输出?

from copy import copy
from pprint import pprint
class Node (object):
	def __init__(self, pIndex, num, status, parent):
		self.pIndex = pIndex
		self.num = num
		self.status = status
		self.parent = parent
	
class Solution(object):
	def __init__(self):
			self.oneToNine = [str(x) for x in range(1, 10)]
			
	def bfsSearch(self, board, empty):
		stack, length = [Node(-1, -1, [[j for j in i] for i in board], None)], len(empty)
		while True:
			parent = stack[0]
			stack.remove(parent)
			if parent.pIndex >= length - 1:
				return parent.status
			point = empty[parent.pIndex + 1] #out of index
			total = parent.status[point[0]] + [x[point[1]] for x in parent.status] + [parent.status[x][y] for x in range(0,9) for y in range(0,9) if (x/3, y/3) == (point[0]/3, point[1]/3)]
			tmpList = [x for x in self.oneToNine if x not in total]
			for num in tmpList:
				status = [[j for j in i] for i in parent.status]
				status[point[0]][point[1]] = num
				stack.append(Node(parent.pIndex + 1, num, status, parent))
				
	def solveSudoku(self, board):
		empty, changed = [(i,j) for i in range(0,9) for j in range(0,9) if board[i][j] == '.'], False
		emptyCopy = [p for p in empty]
		while True:
			for point in empty:
				i, j = point
				total = board[i] + [x[j] for x in board] + [board[x][y] for x in range(0,9) for y in range(0,9) if (x/3, y/3) == (i/3, j/3)]
				availableHere = [x for x in self.oneToNine if x not in total]
				if len(availableHere) == 1:
					board[i][j] = availableHere[0]
					emptyCopy.remove(point)
			if len(emptyCopy) == 0 or len(empty) == len(emptyCopy):
				break
			else:
				empty = [p for p in emptyCopy]
		if len(emptyCopy) == 0:
			return board
		else:
			return self.bfsSearch(board, emptyCopy)

Shortest Path Visiting All Nodes

这道题很悲伤的也没能自己完整的想出解法来,最终还是参考了评论区的一种 java 解法用 python 实现了出来:

from math import pow
class Solution(object):
	def shortestPathLength(self, graph):
		if len(graph) == 1:
			return 0
		visited, queue, N = set(), [], len(graph)
		targetMaskValue = pow(2, N) - 1
		for i in range(0, N):
			bitMask = 1 << i
			queue.append((bitMask, i, 0))
			visited.add((bitMask, i))
		while len(queue) != 0:
			current = queue[0]
			queue.remove(current)
			linkedPoints = graph[current[1]]
			for point in linkedPoints:
				bitMask = 1 << point | current[0]
				if bitMask == targetMaskValue:
					return current[2] + 1
				if (bitMask, point) not in visited:
					queue.append((bitMask, point, current[2] + 1))
					visited.add((bitMask, point))

针对原基础 java 代码做了一点微小的优化:原作者的编码中每次将新的节点加入队列时并不检查它是否为目标结果,而是等按序出队列到了这个节点的时候才检查,而我在自己的实现当中将这部分检查挪到了节点入队列的时刻

因为使用的基本方法是 BFS,意味着如果图的结构复杂,在结果节点入队列和出队列之间会有一段间隔,这段间隔里队列入的节点都是无意义的,在入队列时就检查结果能省去这部分无用的队列操作

Coin Change

这道题在 leetcode 上运行出现了非常奇妙的现象,一模一样一个字符不差的代码,在 python2 下跑结果是这样的:

enter image description here
在 python3 下跑结果是这样的:

enter image description here

可以说是非常玄学了 (此处应有一声响亮的辣鸡 py3 我这辈子都不会从 2.7 升级的),我自己试着在平板下运行了下,py2 确实会略微比 py3 要快一些

具体原因还不清楚,将来有机会可能会借此深入探究一下 py2 与 py3 的区别?😂

import sys, time
from pprint import pprint
class Solution(object):
	def coinChange(self, coins, amount):
		coinsLen = len(coins)
		if coinsLen == 0:
			return -1
		dp = [0] * (amount + 1)
		for i in range(0, amount + 1):
			if i % coins[0] == 0:
				dp[i] = i // coins[0]
			else:
				dp[i] = sys.maxsize
		for i in range(1, coinsLen):
			if coins[i] <= amount:
				for j in range(coins[i], amount + 1):
					if (dp[j - coins[i]], dp[j]) == (sys.maxsize, sys.maxsize):
						dp[j] = sys.maxsize
					else:
						dp[j] = min(dp[j], dp[j - coins[i]] + 1)
		if dp[amount] == sys.maxsize:
			return -1
		else:
			return dp[amount]

Backspace String Compare

virtual weekly contest 里随机打开的一道题, 太简单就不放源代码了反正也没几行(做完了才发现是 Easy 级别的)……

一个基本的入栈出栈就能搞定,提交一次 AC


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

Consensus Mechanisms — As Detailed and Concise as possible!

标题含义是尽可能简洁的介绍一致性机制,一开始还以为测中心会更多的放在机制的原理乃至算法本质上,不过实际上并没有提到很多原理性的东西 (某种意义上确实够简洁🙄️)

正文按部就班的介绍了优秀一致性机制的必要点、不良一致性机制的危害以及 PoW 与几种常见的 PoS 类型,各个点基本都不深入,点到为止的感觉,感兴趣深入了解还是建议读点别的

看之前用平板做了个简单的手写笔记可以供作为阅读的提纲 (写字丑多多担待)

enter image description here


Technique(技术技巧)

这回分享的是 iPad 使用技巧……也许不算正经的技术技巧?凑合凑合吧啊哈哈哈哈😂

iOS 键盘分割

最近购入了新的苹果产品,于是开始关注起了 iPad 的使用技巧。在一个分享视频中发现了 iPad 虚拟键盘可以被分割为更适合打字的模式,我们原本默认的虚拟键盘是这样的:

enter image description here

凭空按键盘无论是拿着还是平放感觉都非常不顺手,毕竟按键大间距也大,但是调整成下图这样后双手握着平板打字应该就方便多了:

enter image description here

在虚拟键盘中间手势向两侧拉即可。日常手握 iPad 的小伙伴可以尝试下,虽然即使切分了我也还是不太习惯……不过我已经有键盘了日常基本也不用虚拟键盘了啊哈哈哈哈哈:


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

No, you don't need ML/AI. You need SQL

这是一篇从标题就很有意思的文章

在微博上也关注了一些业界从事数据挖掘、机器学习以及人工智能相关研究开发的前辈们,当中不少人都吐槽过类似的问题,于是有了以下段子:

某企业老板:大牛你看我们这海量数据该用什么分析处理呢?kafka?hadoop?是不是应该用下最先进的机器学习算法?该放在哪家的云存储上呢balabalabala……
大牛:你们多少数据,每天多少访问量?
老板:1 个 G,每天几百次访问吧
大牛:😊写个 bash 脚本吧,我 U 盘借你存数据

😂基本上是对"大数据"概念滥用以及盲目追求高新技术引发的吐槽吧。专业与非专业的大家对**海量数据**的认知明显有差别,对机器学习、AI 一无所知但盲目追求时髦的大有人在,本文也是基于此与机器学习、AI和 SQL 相关的吐槽

一句经典吐槽:

Everybody and their mother that had a landing page with a “join the waitlist” field had ML/AI on that page. Heaven forbids you put up that initial page and there was no mention of AI.

作者在自己参与的类电商项目中仅用了基本的 SQL,从数据库中提取出客户的消费信息并制定简单的策略就达到了增长业务、挽留客户的目标,比使用 ML、AI 这些复杂而耗时的新技术或者在 Google 上打广告都要有效得多

作者一直以来使用的都是"老旧"的技术诸如 SQL、Bash 以及 CRON 等,而这些并不有趣的、"过时"的技术在他的场景下一直运行的很好

当然,作者并不是反 ML 或 AI 技术,在文末总结他也明确提到了这些吐槽都是针对**小规模**的线上销售,像亚马逊这样的大型科技企业才是这些复杂的高新技术的落地场所

Is there a real adoption trend in cryptocurrencies for e-commerce?

如题,主要加密货币在电子商务的应用潮流是否如我们所想般正在到来

作者认为最先拥抱加密货币体系的是 web 商务:零售商,尤其是小的在线零售服务,因为交易中较小面额的退款散钱等对他们来说非常麻烦

加密电子货币的优点显而易见,但它真的那么容易就能融入现有的各个产业中吗?作者的观点很明确:

what works in principle doesn’t necessarily cash out in the real world. As the saying goes, ‘In theory, theory and practice are the same. In practice, they’re not.’

作者通过拉面在监狱中作为"通行货币"的例子简单叙述了下成为通行货币的几大条件/特点:

  • 便携、可分割
  • 难以伪造
  • 易识别
  • 具备可替代性
  • 可长期存储和持有

基于此进一步分析,作者提到了一个很重要的观点:替换基础货币的**成本**问题。任何产业在发展过程中都会有所积累,这些积累既是沉淀也是包袱,货币的切换如果没有足够撼动这些包袱的利益,这个改革的开头将会变得非常困难。此外电子货币本身不具有实体,目前阶段的发展来看,其价值和偿债能力都还不稳定(抬头看看比特币从 2w 美元跌到 6k 的发展吧 hhhhh),很难作为通用的货币被大多数人所接受

当然我们都知道,技术的发展永远比想象中的要惊人和快速,电子加密货币的发展也不可小瞧


And......

此处是内心复杂的后记:

这周的 ARTS 来晚了不是一星半点,此时甚至想凑合凑合空掉一周算了……那当然是不可能的😂

这周突发事件很多,除了搬家后处理的一大堆杂事,非常重要的离职手续和入职等等,偏偏还是包括周末的最后三天,所以几乎是在接到消息的瞬间就推掉了原本计划好的所有行程开始忙了起来……

实际上并没有将 ARTS 都推到最后时刻才来做,第一道算法题上周二就动笔了,Review 和 Share 的文章也周三就看了,但题目小磕小碰不断一直不能 AC,同时 Review 的文章最后看下又觉得有点不值得推荐,犹豫了不少时间,甚至还紧急从备选库里拖了两篇出来看……结果还是拖到了周末🤦‍♀️

希望下次不会啦!也希望以后无论发生什么,ARTS 可以迟到但不能缺席😤


Written with StackEdit.