連續第三篇參賽記。

8月14日

昨天zTrix駕車帶cbmixx和我進行了San Francisco Bay Area一日遊，遊覽了Google HQ、Facebook、Stanford University、Twitter HQ和金門大橋，醒來疲憊不堪。到達San Francisco機場，zTrix和cbmixx要回北京，而我要去臺北，在登機口碰到ppwwyyxx。

8月15日

和ppwwyyxx抵達臺北。

Read More

8月5日

感謝贊助商安全寶給我們的支持，不然我們即使有決賽入場券也難以成行。去年參加DEFCON 21 CTF時，由於航班延誤到第二天，比賽前一天才到達Las Vegas，把大家都弄得疲憊不堪。吸取去年的教訓，今年我們決定提前兩天到。我和zTrix、cbmixx、DeadCat等同行，從北京出發，其他夥伴則從上海出發。巧的是和TombKeeper一個航班……

Read More

本學期期末參加了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