Frank's Weblog

一次令人自闭的算法作业

By Frank October 8, 2019

最近一次Data Structure & Algorithm课程的作业是要求实现Dijkstra算法，并且其中的排序部分要使用最小堆来实现。

Dijkstra的基本思路如下

1. 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
2.从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点。
3.更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
4.重复步骤(2)和(3)，直到遍历完所有顶点。

我们的作业要求是在步骤2中的“选出距离最短的顶点”要用堆来实现。也就是说，我们需要维护一个最小堆，里面包含有起点到各个尚未访问到的顶点的（目前为止的）最短距离。每一次更新各个顶点到起点的距离时，都要更新堆中所有顶点的值。这样，每次寻找距离最短的顶点时，直接取出堆的根即可，省去了每次都要遍历一遍来寻找最小值。

我们要求的实现逻辑是这样的：维护一个如下的routing table，其中存储了每个节点的id，是否已经访问过，到出发点的最短距离，和该节点在堆中对应的位置。每次访问图中的一个节点时，都要在routing table中更新该节点及其所有后继节点的距离和其他信息。

node	0	1	2
is_visited	true	true	false
cost	0	1	3
heap_position	0	1	2

我写完提交之后，被告知我的solution在小用例上部分正确，大用例上报vector越界的运行时错误。

纽约游记

By Frank October 8, 2019

自从8月中来到雪城之后，虽然同在纽约州，但是和纽约市还有近300mi的距离。安排好入学和生活上的事情之后，我终于在9月初如愿去了纽约。

我乘坐灰狗巴士从雪城出发，一共大约5小时的车程。灰狗的舒适程度比我预想的要好不少，车上有WiFi，电源插座和卫生间。在路上看到对面的高速公路上的一辆装着大型机械的卡车，挂着Oversize Load的旗子，和美卡里面的Heavy Cargo Mod一模一样，太帅了。

大约中午12点的时候巴士到达了Port Authority的巴士站。车站位于曼哈顿中城的正中心的地下，出门之后的斜前方就是纽约时报的总部。纽约时报的总部原本位于时报广场，后来才迁到这里。

New York State Fair 纽约州土味大集

By Frank September 15, 2019

在诸多人的安利下，趁着Labor Day的长周末去了趟New York State Fair。纽约的State Fair是全美国第一个大规模的农畜产品展，最早一届是在1841年，就是在雪城举办的。每年只开两周，今年是从八月22号开到九月3号，错过了只能再等下一年。

因为当天是本年度State Fair的倒数第三天，再加上是个周末，在高速上就开始堵车，堵了超过3mi的路程。路边有几个房车营地，里面停满了房车。恐怕真的有不少人是拖家带口开着房车过来的。

从10号门进入Fairground之后，首先看到的是一个牛棚。

我们在路上堵着的时候，同行的学长跟我说：

“我去年来的时候，他们在牛棚里搭了个摄像头在YouTube上直播。他也不说话，就播那个牛。”

“美国人真的是…他们就过来看看牛，看看猪赛跑，就觉得特别快乐。我去年来的时候，牛棚里边有一个看台，我去的时候就看见一个人坐在那看牛，等我下午走的时候他还在那看牛。”

初到雪城的一周

By Frank September 15, 2019

今天是我到达美国的整一个月，我终于把这篇鸽了好几周的文章写完了。

前文提到，经过近两年的准备和申请，我取得了雪城大学MSCE项目的录取。

8月14号，我从首都机场登上了飞往纽约的航班。经过13个小时的飞行，飞机在JFK机场停稳的时候已经将近3点了，飞往雪城的航班在两小时后起飞，于是只能在机场里一路狂奔，连一张照片都没来得及拍。幸运的是所有持F1签证的学生都被分流到一个单独的房间里，检查护照和I20等，平均每个人只用了不到一分钟。

美国的安检看起来很严格，和国内一样需要把液体和电子产品拿出来单独过机器，还需要脱掉鞋和外套。然而，如果注册了TSA Precheck，则不需要这一系列繁琐操作。总之不充值是不会变强的。

总而言之，一番折腾之后终于顺利到达了JetBlue的登机口。机型是巴航工业的E190，比320和737稍小一圈。

使用Time Machine迁移数据导致的OneDrive数据丢失问题

By Frank June 13, 2019

前一段时间，我将我使用的云存储从自托管的NextCloud切换到了OneDrive。就在前两天，我在使用Time Machine在两个macOS设备之间迁移数据时，OneDrive中大量的数据丢失，原本25G的数据仅剩下了3个G。

本文记录了该问题发生的过程，问题发生后的解决方案及可能导致这个问题的原因。

过程

我使用的macOS版本为10.14.5 (18F132) ，OneDrive客户端版本为19.062.0331.0010。

我的OneDrive上大约存储了23G的数据，为了节省硬盘空间，大部分的文件都使用文件随选释放了本地空间，只有少量数据存储在本地的磁盘上。

两天之前我购买了2019款MacBook Pro，并使用Time Machine迁移了旧设备的数据。迁移完成后，OneDrive一直处于正在同步状态，我认为是在进行重建索引一类的操作，所以没有特别在意。期间我收到了如下图所示的来自OneDrive的邮件，提示我从OneDrive删除了大量文件。

2019 Fall 美国CS Master申请总结

By Frank May 26, 2019

2019Fall的申请季基本结束了。对于各位CS玩家来说，今年申请季非常惨烈。在此记录一下我在这个申请季中的一些感想和踩过的一些坑。如果你也是一名在准备申请美国CS master的准留学生，希望这篇文章能够或多或少给你一些启发。

我的申请结果如下：

AD

Syracuse CE, WPI CS, Stevens CS, BU MET CS

REJ

USC CS General, NYU CS, UCI MCS, UCD CS, NEU CS, Rutgers CS, Stony Brook CS, UCSC CS, Syracuse CS

前期准备

前期的准备基本在于标准化成绩，GPA，各种竞赛实习，选校等等。

我从2017年暑假开始准备托福起一共考了三次，分别是100->101->108。总体来说还算顺利。相比之下，GRE考试就艰难了很多。我一共考了4次GRE，分数分别为153+160，153+166，149+162和150+164，呈现出非常迷的波动。然而AW则非常稳定，每一次都是3.5。

我从2018年寒假开始学习GRE，背单词，刷题，从零开始准备到首考大约经过了3个月的时间。4月份首考GRE出现了严重翻车：我理解错了一道数学题的意思，结果在一个题上卡了太长时间导致数学没有做完，只得了160。当时的情况在这篇文章中有记录：https://nyan.im/posts/3362.html。

动态规划算法

By Frank May 7, 2019

动态规划是一种分治(Divide&Conquer)的思想。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。

适用于动态规划的问题，需要满足最优子结构和无后效性两种情况。

最优子结构性即如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
无后效性即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

动态规划最重要的两个要点在于找到状态和状态转移方程，也就是递推关系。

如果不记录每一步的结果，动态规划的时间复杂度与Brute Force无异。动态规划实质上是一种以空间换时间的方法，通过存储过程中每一步骤的状态来降低时间复杂度。

举个栗子

我们以Leetcode的Climbing Stairs题目为例：

当前位置为第i级台阶时，有两种途径到达当前的状态：

从第i-1级台阶走一步而来
从第i-2级台阶走两步而来

因此，到达第i级台阶的途径为到达第i-1级台阶和到达第i-2级台阶的途径数量之和。我们可以得出如下的状态转移方程：

Leetcode笔记

By Frank April 5, 2019

最近开始刷leetcode，在这里记录一下做题的过程，不定期更新。

GitHub：https://github.com/frankgx97/leetcode

Two Sum(Easy)

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

解法1：暴力搜索

题目本身很简单，使用两个for循环遍历即可。需要注意的是同一元素不能使用两次，因此在遍历时，内层循环需要直接从外层循环+1处开始，而不是从头开始。

Solution：https://github.com/frankgx97/leetcode/blob/master/TwoSum.py

解法2：哈希表

新建一个哈希表（Python中使用字典即可），遍历数组，以数组中的值为哈希表的键，以数组中的键为哈希表的值，将数组中的内容存入哈希表。

在遍历的同时检查(target-当前遍历到的值)是否存在哈希表的键中，如果存在则返回哈希表中的值和当前遍历到的键。这样复杂度由O(n^2)降低至O(n)。

Solution：https://github.com/frankgx97/leetcode/blob/master/TwoSum(Hashmap).py

基于Docker的GitLab配置

By Frank March 17, 2019

我原来使用的Git托管软件是Gogs，近期我迁移到了GitLab。GitLab除了Git托管之外，还包括CI/CD，Registry，Pages等一系列功能。Omnibus Installer使GitLab的安装和配置简化了很多，但是要使用更多的功能，仍然需要手工配置一些服务。

本文记述了使用Docker部署GitLab后开启CI/CD，Registry，Pages等功能的步骤和配置。

硬件需求

官方给出的硬件需求是1Core CPU+ 512MB RAM + 1.5GB SWAP是运行GitLab的最低要求。我使用的是Digital Ocean的5$/月的1C1G实例，开启了4G的Swap。

GitLab本体

Omnibus包包含了GitLab依赖一系列的软件和组件，如ruby, rails, Sidekiq, PostgreSQL等。在Docker中，这些服务都运行在同一个容器中。容器中已经包含了nginx，无需手动配置nginx反向代理。使用如下的compose文件启动GitLab。

web:
  image: 'gitlab/gitlab-ce:latest'
  restart: always
  hostname: 'git.example.com.'
  environment:
    GITLAB_OMNIBUS_CONFIG: |
      external_url 'https://git.example.com'
  ports:
    - '80:80'
    - '443:443'
    - '22:22'
  volumes:
    - './data/config:/etc/gitlab'
    - './data/logs:/var/log/gitlab'
    - './data/data:/var/opt/gitlab'

当external_url参数被设置为以https://打头时，GitLab默认使用Let’s Encrypt签发证书。当http及https被暴露到标准端口时，Let’s Encrypt会通过http challenge方式执行自动签发。

当容器启动后，GitLab的基本功能就可以使用了。

从Gogs迁移项目至GitLab

By Frank March 11, 2019

我以前使用的代码托管系统是Gogs，近期我切换到了更知名的代码托管系统GitLab。因此，我需要将原来托管在Gogs实例上的项目迁移到GitLab实例。

GitLab中提供了一些迁移工具，其支持的平台如下图：

其中，Gitea是Gogs的一个分支版本，我试着通过Gitea选项从Gogs导入项目，虽然GitLab能够正常列出Gogs上的项目列表，但是在导入时则会引发500错误。

经阅读文档得知，Gogs和GitLab均提供了操作代码仓库的API。因此，我可以编写一个Python脚本来迁移项目。