本学期期末参加了ISC'14 Student Cluster Competition，6月20日到6月27日住在Leipzig Messe的Sachsenpark Hotel。

6月20日

从北京出发，在Frankfurt转机抵达Leipzig。Frughafen Leipzig竟然没免费WiFi……手机电也不足了，也不知道无线网怎么弄，给先到达的伙伴们打了三个电话，费了好大功夫坐S-bahn乘到Leipzig Messe。看到ISC'14广告牌很激动呢。

会场旁的Leipzig吉祥物，四只小狮子，好萌~ 吉祥物

Read More

You have solved 489/1771 problems. 主要追求两个目标：代码简短，时间空间复杂度低。

注记

4-sum

使用了multimap，时间复杂度，得到所有答案后不需要去重操作。

合法的四元组有三类：

• a<=b<c<=d，枚举c和d，判断是否存在和为target-c-d的二元组
• a<=b=c<=d，枚举b和d，判断是否存在target-b-b-d
• a=b=c<=d，枚举a，判断是否存在target-a-a-a

分别统计，小心实现可以保证不会产生相同的候选解，从而无需去重。

Alien Dictionary

对于每一对单词，可以确定去除最长公共前缀后的下一对字母的大小关系。两个单词的最长公共前缀等于夹在其中的(所有相邻单词对的最长公共前缀)的最小值。根据相邻单词对的信息即可推得所有任意单词对的信息。因此只需根据相邻单词对求出拓扑关系。

Basic Calculator

这是operator-precedence grammar，可以用operator-precedence parser计算。这类算法的一个特例是shunting-yard algorithm，适用于本题。 为了方便，我假设字串开头和末尾都有隐含的'\0'字符。使用的文法如下：

1
2
3
4
5

S := %x00 E %x00
E := E "+" E
E := E "-" E
E := ( E )
E := 1*DIGIT

参考http://www.scribd.com/doc/51358638/16/Operator-Precedence-Relations。

在比较两个操作符时，区分左手边和右手边，左手边用于先处理的操作符，右手边为新来的操作符。使用左手边操作符的in-stack precedence(isp)和右手边操作符的incoming precedence(icp)进行比较。立即数可以看作icp很大，因此shift后可以立刻reduce。

Best Time to Buy and Sell Stock IV

线性解法。见2015-03-27-leetcode-best-time-to-buy-and-sell-stock-iv。

Closest Binary Search Tree Value II

题意：求BST中与目标值最接近的k个节点。 BST中关键字小于等于目标值的所有节点可以用若干(不带右孩子的子树)表示。这些(不带右孩子的子树)在一条链上，可以用栈维护，得到用于计算前驱的的迭代器。求出目标值的k个前驱的时间复杂度为。 类似地，大于目标值的所有节点也可以组织成一个迭代器。 两个迭代器做合并操作，获得前k个最接近的值。

Contains Duplicate III

以为单位把元素分桶，若一个桶内包含两个元素，则它们的差一定小于等于；差小于等于的数对还可能出现在相邻两个桶之间。对于的各个元素，计算当前元素应放置的桶的编号，检查三个桶，判断之前个元素里是否有差值小于等于的元素。

Course Schedule

拓扑排序。入度减为0的顶点即成为候选，可以把入度向量组织成单链表，从而无需使用额外的队列或栈存储候选顶点，减小空间占用。

Dungeon Game

动态规划，对于每个格子记录从它出发顺利到达终点需要的最小血量。从递推至。

注意对于每个格子其实有进和出两个状态：进入该格子时(未考虑当前格子影响)；和离开该格子后(已考虑当前格子影响)。这两种方法都行，考虑到程序的结构可能有三部分：初始化边界条件、状态转移、根据状态表示答案，需要仔细斟酌以追求代码简短。这里两种方式并无明显代码长度差异。

Expression Add Operators

见2015-10-16-leetcode-expression-add-operators。

Find Minimum in Rotated Sorted Array

方法是二分，如果要写短可以采用下面的思路： 子数组中如果有相邻两个元素a[i]>a[i+1]，则a[i+1]是整个数组的最小值。 若子数组a[i..j]满足a[i]>a[j]，则存在i<=k<j使得a[k]>a[k+1]。 对于子数组a[l..h]判断a[l]>a[m]或a[m]>a[h]是否有一个成立，成立则可以去除一半候选元素，不然a[h]>a[l]为一个逆序对。

Find Minimum in Rotated Sorted Array II

留意几个特殊情形：[1,0,1,1,1]、[1,1,1,0,1]。

对于子数组a[l..h]，令m=floor(l+h)/2(注意m可能等于l)。判断a[l]>a[m]或a[m]>a[h]是否有一个成立，成立则可以去除一半候选元素。 若两个条件均不满足则a[l]<=a[m]<=a[h]，若a[h]>a[l]则说明a[l]最小，否则a[l]=a[m]=a[h]，可以把范围缩小为a[l+1..h-1]。

另外一种方法是只判断a[m]与a[h]`的大小关系。

Find Peak Element

二分查找，把区间缩小为仍包含候选值的子区间。对于相邻两个元素、，若则及左边部分存在peak，否则及右边部分存在peak。不关心或是否满足peak条件，将区间折半。

1
2
3
4
5
6
7

int l = 0, h = a.size();
while (l < h-1) {
  int m = l+h >> 1;
  if (a[m-1] > a[m]) h = m;
  else l = m;
}
return l;

或者检查中间元素是否满足要求，可以提前退出循环。

1
2
3
4
5
6
7
8

int l = 0, h = a.size();
while (l < h-1) {
  int m = l+h >> 1;
  if (a[m-1] > a[m]) h = m;
  else if (m+1 == h || a[m] > a[m+1]) l = h = m;
  else l = m+1;
}
return l;

First Missing Possitive

空间复杂度。

Fraction to Recurring Decimal

注意INT_MIN/(-1)会溢出。

Graph Valid Tree

个节点的树的判定方式：

• 有条边且没有simple circle。可以用union-find algorithm判断。
• 联通且无simple circle。可以用graph traversal。

Guess Number Higher or Lower II

动态规划优化，。见张昆玮的分析：http://artofproblemsolving.com/community/c296841h1273742s3_leetcode_guess_number_higher_or_lower_ii。

Invert Binary Tree

选择一种binary tree traversal算法，节点访问改成交换左右孩子即可。 如果要O(1)空间的话，得借鉴Morris pre/in-order traversal的思路，该算法的核心是通过左子树最右节点的右孩子是否指向当前节点来判断当前节点被访问到的次数，从而决定当前应该进行的操作(探索左子树或访问当前节点)。但交换子树操作会弄乱左子树最右节点的位置，因此pre-order和in-order都行不通，但post-order可行。Morris post-order traversal(这个叫法也许不恰当)可以参考https://www.quora.com/What-is-a-good-way-to-implement-stackless-recursion-less-post-order-traversal-for-a-non-threaded-binary-tree-using-Morris-method的描述，pre/in-order的访问是针对一个节点进行的，但post-order则需要对当前节点左子树的右链进行，并且需要翻转两次以达到按post-order输出的效果。但这里只需要保证每个节点都被访问一次，不需要严格的post-order顺序，因此无需翻转操作。

Jump Game

空间复杂度。

Jump Game II

使用output-restricted queue优化的动态规划，注意到动态规划值的单增性可以用类似BFS的方式，空间复杂度。

Lexicographical Numbers

在trie中找1~n，存在迭代解法。

Linked List Cycle II

单链表找圈。Brent's cycle detection algorithm或Floyd's cycle detection algorithm。

如果只需要判断是否有圈，而不用指出圈的起点，可以使用pointer reversal。访问链表的过程中翻转链表，倘若访问到NULL，则说明无圈；若回到了起点，则说明有圈。如果有圈的话，算法执行完毕后，圈的方向会被反转，可以再执行一次翻转过程还原。下面是这个方法的实现：

1
2
3
4
5
6
7
8
9
10
11
12

// return true if a cycle is detected
bool pointerReversal(ListNode *head) {
  if (! head) return false;
  ListNode *x = head->next, *y, *z = head;
  while (x && x != head) {
    y = x->next;
    x->next = z;
    z = x;
    x = y;
  }
  return x == head;
}

Longest Palindromic Substring

线性时间求出以每个位置为中心的最长回文子串的Manacher's algorithm。http://www.csie.ntnu.edu.tw/~u91029/Palindrome.html提供的描述感觉最清晰。但实现我更喜欢我从某本stringology书上看到的。

Majority Element

Boyer-Moore majority vote algorithm http://www.cs.utexas.edu/~moore/best-ideas/mjrty/，思路是每次找到两个不同的元素并丢弃，这样做不会丢失解。容器里只剩下一种元素时，它就是majority。

Majority Element II

Boyer-Moore majority vote algorithm的扩展，找出所有出现次数大于的元素。方法是每次找出个互不相同的元素丢掉，最后剩下的元素是候选解。时间复杂度。

Maximum Gap

平均数原理，求出极差后，根据桶大小分成若干个桶，答案必为不同桶的两个元素之差。

Maximum Subarray

Kadane's algorithm

Meeting Rooms II

题意中两条线段冲突当且仅当它们的公共部分长度大于0。 这是interval graph，所求的是chromatic number，interval graph包含与perfect graph，因此chromatic number等于maximum clique顶点数，即最大线段相交数，可以把所有端点排序计算。 或者按起始端点排序后用贪心算法：维护若干线段集合，按起始端点总从小到大考虑每个线段，任选一个不冲突的集合加入，若无不冲突的集合则自成一个新集合。最后，集合数即为答案。实现时，每个集合用最大右端点值表示，所有集合组织为一个小根binary heap，若当前考虑线段的起始点小于根则压入一个新元素，否则修改根的值。

Merge k Sorted Lists

Tournament sort，可以用priority_queue实现。

Min Stack

使用两个栈，原栈S存放各个元素。每当新元素小于等于当前最小值时，就把新元素复制一份压入另一个栈S'。弹出时，若元素在S'中出现，则也从S'中弹出。

另一种方法是记录新元素与当前最小值的差值，每个元素需要多记录1个bit。可惜C++会Memory Limit Exceeded，感觉不合理。

Minimum Window Substring

尺取法

Missing Number

从左到右考虑每个元素，若不等于它的位置则把它交换到正确的位置并重复此过程。

N Queen

bitmask存储列，正反斜线控制的格子。

Number of 1 Bits

求popcount。__builtin_popcount()或者网上查找各种bit twiddling hacks。

One Edit Distance

编辑距离为1有三种可能：S比T多一个字符、T比S多一个字符、S与T长度相同且有一个位置不同。除去最长公共前缀和最长公共后缀，三种可能的检查方式可以统一为判断较长的串长度是否为1。

Palindrome Partitioning

f[i][j] = calc(f[ii][jj] : i <= ii <= jj <= j)形式的动态规划可以采用如下计算方式。

1
2
3
4

for (int i = n; --i >= 0; )
  for (int j = i; j < n; j++) {
    // calc [i,j]
  }

Palindrome Partitioning II

求原串的最少回文串划分。O(n^2)时间，可以优化到O(n)空间。

我没能找到比O(n^2)快的算法。相关的问题有检测一个串是否分割成k个回文串。k小于等于4时均有线性算法，参见Text Algorithms一书Theorem 8.17。k大于4时不确定。

Perfect Rectangle

使用unordered_map的解法：判断除了四个极点，每个小矩形的角是否被两个或四个矩形共享。

或者判断所有小矩形面积和等于四个极点围成的矩形的面积，并且小矩形没有重叠(用sweep line判断)。

Perfect Squares

https://leetcode.com/discuss/57477/sqrt-applying-fermats-theorm-brahmagupta-fibonacci-identity

由Lagrange's four-square theorem知答案为1~4，由Legendre's three-square theorem检查答案是否为4。若小于4，则再尺取法检查是否是perfect square或能表示为两个perfect squares之和，若不是则答案为3。

另有期望的算法，参见M. O. Rabin, J. O. Shallit, Randomized Algorithms in Number Theory, Communications on Pure and Applied Mathematics 39 (1986), no. S1, pp. S239–S256. doi:10.1002/cpa.3160390713

Reconstruct Itinerary

题目即lexicographically smallest Eulerian path。Eulerian path最简单的算法是Hierholzer's algorithm，有向图中仅有一个顶点出度=入度+1，记为源；一个顶点入度=出度+1，记为汇。任求一条源到汇的路径，之后把各个圈合并到路径上即可。本题要求字典序最小，对Hierholzer's algorithm稍加变形即可。

从源开始，贪心地选择序号最小的下一个顶点，删除这条边，重复此过程，即得到一条源到汇的路径。需要把圈添加到该路径上。若一个圈只包含路径上的一个顶点，那么在该顶点处添加圈即可。若一个圈包含路径上的多个顶点，那么应该把它放在离汇最近的顶点上，这样能保证字典序最小。

Recover Binary Search Tree

使用Morris in-order traversal找到邻接失序对。

如果交换的元素相邻，则有一个邻接失序对(如0 1 2 3 4 ->0 1 3 2 4)，否则有两个邻接失序对(如0 1 2 3 4 5 -> 0 4 2 3 1 5)。

Remove Nth Node From End of List

http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions

使用pointers-to-pointers很多时候能简化实现。

Regular Expression Matching

P为模式串，T为文本， f[i][j]表示P的前i个字符能否匹配T的前j个字符。 根据f[i-1][*]计算f[i][*]。 这个方法也可以看作构建了精简表示的Thompson's automaton，时间复杂度。

Remove Element

原地修改数组，我喜欢把这种操作称作deflate。

Remove Invalid Parentheses

最少移除个数很容易计算，把可以配对的左右括号全部抵消，剩余括号数即是(形如：)))...((()。难点在于输出所有不同答案，多数解法使用DFS枚举要删除哪些括号，枚举量大于答案个数。 有一个枚举量固定为答案个数的方法，找到残余串)))...(((中右括号与左括号的分割点。DFS分割点左半部分，保证到达残余串第个右括号时，至少有个右括号(原串的)被删除。分割点右半部分也如法炮制，两边合并即为答案。

Repeated DNA Sequences

可以用类似Rabin-Karp的rolling hash方法，求出所有长为10的子串的hash值，判断是否有重复。只有四个字符，长度为10，故可以使用polynomial hash code。 另外也可以用suffix tree/suffix array等方法，找longest common prefix大于等于10的两个后缀。注意不能重复输出字串。

Reverse Bits

Hacker's Delight (2nd) 7.1 Reversing Bits and Bytes。

Rotate Array

经典的三次reverse，或者拆成gcd(k,n)个置换群循环右移一格。

Same Tree

类似于same fringe problem，可以试验generator、co-routine、lazy evaluation、continuation等。如果要O(1)的空间复杂度可以用Morris in-order traversal等方法。

Set Matrix Zeroes

空间复杂度。使用两个标志表示第0行或第0列是否需要清零，之后用第0行表示各列是否需要清零，第0列表示各行是否需要清零。

Search For a Range

设序列用区间表示为[begin,end)。使用C++ STL风格的lower_bound、upper_bound。有几点好处：

• 循环内只有一次比较
• 循环退出后两个指针相等，且落在[begin,end]，都是迭代器的合法取值。某些binary search写法返回值可能为begin-1，某些容器不合法
• [lower_bound(a[],x), upper_bound(a[],x)给出了元素x所在的子区间

Search Insert Position

C++ <algorithm>的lower_bound。

Serialize and Deserialize Binary Tree

把NULL视作叶子，则pre/in/post-order traversal可以用于编码。若使用Morris traversal则额外空间为。解码时使用类似Schorr-Waite graph marking algorithm的edge crawling技巧即可做到额外空间。

Shortest Palindrome

找出原串的最长回文前缀，用Manacher's algorithm求解，把剩下部分复制一份、翻转后、接到左边，就得到了最短的回文串。求最长回文前缀的另一种方法是把原串以及翻转用特殊字符隔开，用Morris-Pratt algorithm求border，该值即为最长回文前缀长度。

Single Number III

所有数的xor等于两个出现一次的数的xor，不妨设为k，则k & -k为二进制表示上某个为1的数位。根据这个数位把所有元素划分成两份，每份只有一个出现一次的数。

Smallest Good Base

设，由得，由得，因此。枚举，唯一可能取值为，判断是否成立。

Sort Colors

Dutch national flag problem。如果不要求000111222，允许111000222111，那么有交换次数更少的Bentley-McIlroy算法http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem-3/

Sqrt(x)

Hacker's Delight (2nd) 11.1.1。 牛顿迭代法。46340 = floor(sqrt(INT_MAX))

Scramble String

我用了的空间和的时间，应该有更好的算法。但查阅了一些文献还没有找到。

Sort List

我用了较麻烦的natural merge sort。Quicksort实现会简单很多。

Strobogrammatic Number III

定义一个函数，用于计算小于给定数的strobogrammatic number个数，则用减法即可得到题目所求。下面考虑如何计算这个函数。 小于给定数high的strobogrammatic number分为两类：

• 位数不够的，可看作有若干前导0。容易求得。
• 位数相同。可以枚举与high的公共前缀的长度，再计算下一个数位小于high中对应数位的strobogrammatic number个数。由于位数为的strobogrammatic number只有个数位是独立的，枚举的公共前缀长度得小于。

Sudoku Solver

转化为exact cover problem，使用dancing links + Algorithm X求解。

Trapping Rain Water

两个指针夹逼，空间。

Unique Binary Search Trees II

类似动态规划的思想，子树可以复用。

Wiggle Sort

从左到右考虑每一对相邻元素，如果不满足大小关系则交换，交换不会影响之前一对元素的大小关系。

Word Ladder

基本方法是BFS或bidirectional BFS，相邻关系的确定有两种思路：枚举所有其他顶点判断是否相邻、枚举顶点的变异判断是否为顶点。对于第一种思路，还可以利用一个技巧：把所有字串都分为左右两半，若两个字串hamming distance为1，则左半部分相同或右半部分相同。

Verify Preorder Sequence in Binary Search Tree

对于前序序列中的递减连续段，它们形成了BST的某个左孩子链。

Maximal Rectangle

秋叶拓哉（iwi）、岩田阳一（wata）和北川宜稔（kita_masa）所著，巫泽俊（watashi）、庄俊元（navi）和李津羽（itsuhane）翻译的《挑战程序设计竞赛》

逐行扫描棋盘，对于每一行记录三个值：

• 表示第列上方连续为1的行数：h[j] = a[i][j] == 0 ? 0 : h[j]+1;
• 若，令为；若则设为
• 若，令为；若则设为

的计算方式是：

1
2
3
4
5
6
7

if a[i][j] == 0:
  l[j] = j
elif h[j] == 1:
  l[j] = j-(a[i][j]及左边连续的1的个数)+1
else
  # 下式中右边的l[j]是第i-1行计算得到的l[j]
  l[j] = min(l[j], j-(a[i][j]及左边连续的1的个数)+1)

的计算类似。对于每一列，是一个候选解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

class Solution {
public:
  int maximalRectangle(vector<vector<char> > &a) {
    if (a.empty()) return 0;
    int m = a.size(), n = a[0].size(), ans = 0;
    vector<int> h(n), l(n), r(n, n-1);
    REP(i, m) {
      int ll = -1;
      REP(j, n) {
        h[j] = a[i][j] == '1' ? h[j]+1 : 0;
        if (a[i][j] == '0') ll = j;
        l[j] = h[j] ? max(h[j] == 1 ? 0 : l[j], ll+1) : j;
      }
      int rr = n;
      ROF(j, 0, n) {
        if (a[i][j] == '0') rr = j;
        r[j] = h[j] ? min(h[j] == 1 ? n-1 : r[j], rr-1) : j;
        ans = max(ans, (r[j]-l[j]+1)*h[j]);
      }
    }
    return ans;
  }
};

潘宇超 2008

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

class Solution {
public:
  int maximalRectangle(vector<vector<char> > &a) {
    if (a.empty()) return 0;
    int m = a.size(), n = a[0].size(), ans = 0;
    vector<int> h(n), l(n), r(n, n-1);
    REP(i, m) {
      REP(j, n) {
        h[j] = a[i][j] == '1' ? h[j]+1 : 0;
        l[j] = j;
        while (l[j] && h[l[j]-1] >= h[j])
          l[j] = l[l[j]-1];
      }
      ROF(j, 0, n) {
        r[j] = j;
        while (r[j]+1 < n && h[j] <= h[r[j]+1])
          r[j] = r[r[j]+1];
        ans = max(ans, (r[j]-l[j]+1)*h[j]);
      }
    }
    return ans;
  }
};

ACRush某TopCoder SRM

逐行扫描棋盘，对于每一行记录：第列上方连续为1的行数。

对于每一行，从大到小排序，并计算候选解：

1
2
3
4

x = [0,0,...,0]
foreach j, h[j]: # 从大到小遍历h[j]
  x[j] = 1
  ans = max(ans, (max(k : x[j..k]都为1) - min(k : x[k..j]都为1)) * h[j])

上面伪代码可以在时间内求出。方法是把中设置为1的元素看成若干集合，相邻元素在同一个集合中。每次把某个中元素设为1可以看成新建了一个集合，若左边或右边的集合存在则合并。

不相交集合可以用union-find算法，但针对这种特殊情形存在的算法：每个集合(即某个1的连续段)左端和右端互指，其他元素的指针任意。新建集合时若左边或右边的集合存在，则更新它们两端的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP1(i, n) for (int i = 1; i <= (n); i++)

class Solution {
public:
  int maximalRectangle(vector<vector<char> > &a) {
    if (a.empty()) return 0;
    int m = a.size(), n = a[0].size(), ans = 0;
    vector<int> h(n), p(n), b(m+1), s(n);
    REP(i, m) {
      REP(j, n)
        h[j] = a[i][j] == '1' ? h[j]+1 : 0;
      fill(b.begin(), b.end(), 0);
      REP(j, n)
        b[h[j]]++;
      REP1(j, m)
        b[j] += b[j-1];
      REP(j, n)
        s[--b[h[j]]] = j;
      fill(p.begin(), p.end(), -1);
      ROF(j, 0, n) {
        int x = s[j], l = x, r = x;
        p[x] = x;
        if (x && p[x-1] != -1) {
          l = p[x-1];
          p[l] = x;
          p[x] = l;
        }
        if (x+1 < n && p[x+1] != -1) {
          l = p[x];
          r = p[x+1];
          p[l] = r;
          p[r] = l;
        }
        ans = max(ans, (r-l+1)*h[x]);
      }
    }
    return ans;
  }
};

栈维护histogram

逐行扫描棋盘，对于每一行记录：第列上方连续为1的行数。

对于每一行，维护一个以值为元素的栈，满足从栈底到栈顶值递增。从左到右枚举各列，在插入前维持栈性质，弹出元素后栈顶代表往左能“看到”的最远位置，插入。

其他方法　

枚举两列，求出夹在两列间的最大1子矩形。

令表示以原矩形最上角和两个端点的矩形内1的数目，枚举所有子矩形，用求出这个子矩形内1的数目，判断是否合法。

把0看成障碍点，求不包含障碍点的最大子矩形。 把障碍点按横座标排序。枚举障碍点作为候选子矩形的左端，向右扫描各个障碍点，维护纵座标和枚举点最近的上下个一个障碍点。枚举点、扫描线和上下障碍点确定了候选子矩形的边界。 若0的数目为，，最坏。

代码索引

1
2
3
4
5
6

copy($('td:has(.ac) ~ td:nth-child(3) a').map(function(_,e){
  var id = $(e).parent().prev().text();
  var h=e.href.replace(/htt.*problems/,'/leetcode');h=h.substr(0,h.length-1);
  var title=e.textContent, href=e.href, name=h.replace(/.*\//,'');
  return '|'+id+'|['+title+']('+href+')|['+name+'.cc]('+name+'.cc)|'
}).toArray().join('\n'))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

require 'mechanize'
agent = Mechanize.new
page = agent.get 'https://leetcode.com/accounts/login/'
doc = page.form_with {|form|
  form['login'] = 'MaskRay'
  form['password'] = getpass
}.submit.parser
total = doc.css('td:nth-child(3)').size
solved = doc.css('td:has(.ac)').size
puts "You have solved #{solved}/#{total} problems."
for a in doc.css('td:nth-child(3) a')
  id = a.parent.previous_element.text
  href = a['href']
  name = href.sub(/\/problems\/(.*)\//, '\1')
  title = a.text
  puts "|#{id}|[#{title}](#{href})|[#{name}.cc](#{name}.cc)|"
end

Suffix array是解决string search问题的一个工具，它是一个字串所有后缀的排序。

线性时间的构建算法主要有Kärkkäinen-Sanders(¹)、Ko-Aluru(²)、KSP三种，其中KSP算法使用了类似suffix tree的构建方式，Kärkkäinen-Sanders算法时间复杂度的递推式为，通常认为性能不如的Ko-Aluru。

按照³的注记，借鉴⁴对LMS substring递归排序使用的方法， 对原始的Ko-Aluru算法进行改动以简化内存使用和提升性能。 我的实现在字串和suffix array外仅使用两个数组：计数排序使用的桶和一个表示L/S类型的数组， 反映了Ko-Aluru算法能达到和⁵同等的精简内存占用。

Read More

CTF夺旗赛是计算机安全竞赛的一种形式。国内这一领域当前的规模最大的赛事BCTF“百度杯”全国网络安全技术对抗赛决赛刚刚落下帷幕。作为工作组的一名成员，想分享下自己的参与经历。

Read More

二月

一日回上海，回来又吃了顿海底捞~

TUNA技术沙龙，精心准备了一天的HTML幻灯片：A Pretty Printer Library in Haskell

幻灯片里的1958、555都有所指涉，1958为诞生年份，555为马路号码。到了Algebraic data type，连同后面的Tagged Union，也都有深意。

Read More

http://www.net9.org/StudentFestival/1001/是模仿东京大学设计的海报谜题：

前几关的解法可以参考http://ppwwyyxx.com/2013/Student-Festival-Puzzle/，下面以出题人角度给出其中的1001/key的题解。

1001/key下载

本题是一道crackme，直接运行程序会提示输入密码，如果密码输入错误就会显示meow。

Read More

RedTigers Hackit是关于PHP和SQL injection的wargame。

又开始做wargame了，这次的进步是用上了HTTPie，一个类似curl的工具，但语法比后者优雅一些。

Read More

这是学习 http://www.devttys0.com/2013/10/reverse-engineering-a-d-link-backdoor 动手实践时做的一些记录。

下载 ftp://ftp.dlink.eu/Products/dir/dir-100/driver_software/DIR-100_fw_reva_113_ALL_en_20110915.zip

1
2
3
4
5
6
7
8

% binwalk -e DIR100_v5.0.0EUb3_patch02.bix

DECIMAL         HEX             DESCRIPTION
-------------------------------------------------------------------------------------------------------------------
4               0x4             Realtek firmware header (ROME bootloader) image type: RUN, header version: 1, created: 9/17/2011, image size: 1690484 bytes, body checksum: 0xA, header checksum: 0x67
13046           0x32F6          mcrypt 2.2 encrypted data, algorithm: blowfish-256, mode: CBC, keymode: 8bit
403343          0x6278F         gzip compressed data, has CRC, extra field, last modified: Tue Jun  6 18:51:20 2028
646032          0x9DB90         Squashfs filesystem, big endian, version 2.0, size: 1041011 bytes, 528 inodes, blocksize: 65536 bytes, created: Thu Sep 15 17:11:28 2011

得到squashfs文件系统9DB90.squashfs。留着这个文件不动，还要准备另一个工具。

Read More

这个是学习编程时的一个耳熟能详的问题了：

n个人(编号为0,1,...,n-1)围成一个圈子，从0号开始依次报数，每数到第m个人，这个人就得自杀，之后从下个人开始继续报数，直到所有人都死亡为止。问最后一个死的人的编号(其实看到别人都死了之后最后剩下的人可以选择不自杀……)。

这个问题一般有两种问法：

• 给出自杀顺序。不少数据结构初学书都会以这个问题为习题考验读者对线性表的掌握。比较常见的解法是把所有存活的人组织成一个循环链表，这样做时间复杂度是O(n*m)的。另外可以使用order statistic tree(支持查询第k小的元素以及询问元素的排名)优化到O(n log n)。另外有篇1983年的论文An O(n log m) Algorithm for the Josephus Problem，但可惜我没找到下载链接。
• 求出最后一个人的编号。可以套用上一种问法的解法，但另外有更加高效的解法，下文展开讨论。

Read More

关于做题这回事，引用一下：

1
2

Chao Xu，Haskell用户.
acm算是用来训练秒面试题的一个方式。 像我这种非cs系学生全靠玩acm的训练秒各个公司。

深以为然。算法题带来的代码能力的效用实在是太大了，除了训练思维外对速度、准确性也有极大帮助。真切感受到解决一个大作业花了数小数编写，再花了更长的时间调试，和立刻写完、写完就对的差异。订阅过一些邮件列表，偶尔能看到一些非常苍白的问题的人，也能看到内容可能更空洞的回复。以及市面上很多浮夸的书。如果方法恰当潜心研习一段时间应该不会出现这样的问题呢。所以当我看到《编程之美》这个书名的时候，第一印象也是那类浮华的书，等待之前某次活动拿到一本看才发现不是，”编程“、”美“字样在我心目中的地位都被这些浮夸的事物玷污了。

我现在发现自己看过的东西拓扑顺序不太对了，简单说就是ld -la -lb -la，这可以算作一个tech joke吧。昨天经过fqj1994指导，今天终于把https开起来了，感觉又有所提高，好开心啊。

Read More