Algorithm(leetcode 算法题)

Max Points on a Line

本周题目虽然评级为 Hard 而且 AC 率看起来非常低(才 15 % 左右),但意外的感觉还蛮简单,思路很快就有了,编码实现过程也挺顺利

一天接近十二小时上班忙到变形,时间严重不足,睡前看题目几分钟理解题意,躺床上想思路,上班公交车上编码实现,最后周末花了点时间解决了边界问题……时间果然都靠挤牛奶啊

基本的思路是计算通过每个点的最长直线,最后再进行比较。计算单个点最长直线的过程中采用合并直线的方法,一旦确定新的点在直线上就加入该直线的数组,后面迭代再遇上该直线上的点可以引用相同的数组而无需重新计算。由于斜率和任意一个点能够确定一条直线,所以用了斜率作为存储的 key

这题主要有两个坑在意料之外:

  • 存在重复的点,需要列入计算范围:比如 [[0, 0], [0, 0]] 相当于两个点……然而题目完全没提及这个

  • python 除法精度不足:斜率的计算涉及到了除法,由于精度不足的关系出现了错误的斜率相等……最后用了乘以 10000 扩大斜率这种的比较笨的方法……(毕竟实际上只有一个 testcase 没过啊哈哈)

精度差

完整的 AC 代码如下,beat 67% 左右:

class Point(object):
  def __init__(self, a=0, b=0):
    self.x = a
    self.y = b

class Solution(object):
  def maxPoints(self, points):
    pointCount, newPoints = {}, []
    for p in points:
      if p.x in pointCount:
        if p.y in pointCount[p.x]:
          pointCount[p.x][p.y] += 1
        else:
          pointCount[p.x][p.y] = 1
          newPoints.append(p)
      else:
        pointCount[p.x] = {p.y: 1}
        newPoints.append(p)
    lines, length = {}, len(newPoints)
    if length == 0:
      return 0
    elif length == 1:
      return pointCount[newPoints[0].x][newPoints[0].y]
    for point in newPoints:
      remainPoints = [p for p in newPoints]
      remainPoints.remove(point)
      lines[point] = {}
      while True:
        cur = remainPoints[0]
        if cur.x - point.x == 0:
            slope = 'nil'
        else:
            slope = (cur.y - point.y) * 10000.0 / (cur.x - point.x)
        if cur in lines:
          lines[point][slope] = lines[cur][slope]
          tmpForRemove = [p for p in lines[cur][slope]]
          tmpForRemove.remove(point)
          for p in tmpForRemove:
            remainPoints.remove(p)
          if len(remainPoints) == 0:
              break
        else:
          if slope in lines[point]:
            lines[point][slope].append(cur)
          else:
            lines[point][slope] = [point, cur]
          remainPoints.remove(cur)
          if len(remainPoints) == 0:
              break
      maxCount = 2
      for p in newPoints:
        linesLen = []
        for slope in lines[p]:
          linesLen.append(sum([pointCount[point.x][point.y] for point in lines[p][slope]]))
        maxCount = max(maxCount, max(linesLen))
    return maxCount

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

Crypto Network Effects

这篇文章不长,没有目录提纲,虽然内容并不复杂,然而我由于对加密货币基本原理和体系的不熟悉,第一遍读的时候很多句子都没理解(当然在看第二遍的时候也没怎么能理解)……

文章首先简单介绍了一个概念:

网络效应(Network Effects)是网络价值随着网络中节点数量增长而出现的新性质。不同的协议会催生不同的网络效应

这里认为基本上网络效应🈷越大,加密货币的实际价值越大

基于这一概念,将当前加密货币相关的协议大致分为两组,每一组协议针对优化的维度(或者说是关注的侧重点?)不同:

graph LR
a("加密协议") --> b("实用协议")
a --> c("价值存储协议")
b --> |"关心"|e["图灵完备性、富状态集"]
c --> |"关心"|f["审查判断力、去中心化、安全"]
  • 价值存储协议:比特币
  • 实用协议:智能合约平台,如以太币

作者认为比特币将来很有希望成为广泛使用的电子货币,如今已经有业界相关人士给出了比特币与黄金大致的对应估值。而且比特币作为正常运转了这么多年的加密协议,将来的生命周期还是相当可观的

the future life expectancy of a technological system is proportional to its current age, so that every additional period of survival implies a longer remaining life expectancy.

文章后面提到了一个经典的认识误区:由于比特币较广为人知工作的特性,我们经常倾向于将比特币类比于技术公司,而作者认为比特币协议的地位应该类似于网络(Network),将来有机会成为基本标准体系中的一员


Technique(技术技巧)

拯救误操作 chmod -x

来源:微博(@蛋疼的axb,微博技术专家)

在微博上看到这条介绍了一个挺棒的操作,思路非常赞,同一条微博下面的评论里也提供了不少出色的思路,在此记录一下:

  • 问题描述
    • Linux 服务器上的 /bin/sbin/usr/bin 等目录下所有的文件都被执行了 chmod -x(换言之失去了所有基本命令的执行权)
    • 当前 bash 窗口保持打开,拥有 sudo 权限
  • 尝试思路:
    1. 确认常规命令 chmodcplscdcatless 等命令都没有执行权
    2. 远程下载命令,curlwgetrsyncnc 等都没有权限
  • 解决方案:
    1. 通过在另一台机器上 man builtin 确认到有 echoforwhileread 等内建命令可以用,通过这些内建命令实现 lscat 的功能
    2. for i in /usr/local/bin/*; do echo $i; done(相当于实现了 ls 这里)操作后发现 /usr/local/bin 下有 scp 可以使用,因此可以通过另一台能够 public key 登陆的机器下载文件
    3. echo 'rsa key' > tmp.rsa 生成 rsa 文件,但 scp 命令不能直接食用这个 key 文件,因为要求权限为 600
    4. 在正常机器上找到一个默认有 600 权限的文件路径,在异常机器上将 key 文件导入这个路径
    5. scp -i xxx.file [email protected]:/bin/chmod chmod
    6. 最后 ./chmod +x /bin/chmod && chmod +x /bin/* 彻底解决

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

Our reactions to Microsoft buying GitHub

这篇文章如标题所言,分享一下大家对 Microsoft 收购 GitHub 的反应,并从多个角度分析这件事背后的意义

一直以来大家对 Microsoft 抱有偏见以至于听到这个名字就想离开,但是这么多年来 Microsoft 在改变,我们也看到 vscode 这样在 Github 上受到开发者喜爱的产品,可以认为 Microsoft 确实是在改变的,这不是门面工程也不是幌子

之前在 Reddit 上GitHub 即将上任的 CEO 开了个话题邀请大家随意吐槽和提问, 从他的个人经历和回复来看,他对 GitHub 了解,想必不仅是对未来几年而是能考虑到下一个十年的发展

虽然很多证据证明 Microsoft 的可信,但开发者们多还是希望 GitHub 能从四巨头手中保持独立性,不过这很难,因为 GitHub 唯一的盈利途径是企业版,理论上难以支撑越来越多的开源项目。就访谈者个人的意见而言,他认为如果无论如何 GitHub 要被收购,Microsoft 也许是最好的选择:Amazon 规模已经够大,Facebook 还没有云 ,Google 掌握太多信息以至于让人难以交付信任,而且之前它已经对 GitLab 投资了 20 个亿,综合来看有着一定历史的 Azure 或许是最好的选择

说到对独立性的关注,关注的焦点其实还是在于与开发者们的社区关系会不会变化,Microsoft 会不会对社区的建设横插一脚等等,在 Reddit上也看到了很多相关提问

整个访谈还是比较流畅连贯的,由一个个问题深入分析、交换意见乃至进一步引入下一个问题等,还分享了一些推友们的看法并加以分析,推荐大家读一读


Comment(来自别人的评价与相关讨论)