LeetCode solutions

Table of Contents

• 注记
  • 4-sum
  • Alien Dictionary
  • Basic Calculator
  • Best Time to Buy and Sell Stock IV
  • Closest Binary Search Tree Value II
  • Contains Duplicate III
  • Course Schedule
  • Dungeon Game
  • Expression Add Operators
  • Find Minimum in Rotated Sorted Array
  • Find Minimum in Rotated Sorted Array II
  • Find Peak Element
  • First Missing Possitive
  • Fraction to Recurring Decimal
  • Graph Valid Tree
  • Guess Number Higher or Lower II
  • Invert Binary Tree
  • Jump Game
  • Jump Game II
  • Lexicographical Numbers
  • Linked List Cycle II
  • Longest Palindromic Substring
  • Majority Element
  • Majority Element II
  • Maximum Gap
  • Maximum Subarray
  • Meeting Rooms II
  • Merge k Sorted Lists
  • Min Stack
  • Minimum Window Substring
  • Missing Number
  • N Queen
  • Number of 1 Bits
  • One Edit Distance
  • Palindrome Partitioning
  • Palindrome Partitioning II
  • Perfect Rectangle
  • Perfect Squares
  • Reconstruct Itinerary
  • Recover Binary Search Tree
  • Remove Nth Node From End of List
  • Regular Expression Matching
  • Remove Element
  • Remove Invalid Parentheses
  • Repeated DNA Sequences
  • Reverse Bits
  • Rotate Array
  • Same Tree
  • Set Matrix Zeroes
  • Search For a Range
  • Search Insert Position
  • Serialize and Deserialize Binary Tree
  • Shortest Palindrome
  • Single Number III
  • Smallest Good Base
  • Sort Colors
  • Sqrt(x)
  • Scramble String
  • Sort List
  • Strobogrammatic Number III
  • Sudoku Solver
  • Trapping Rain Water
  • Unique Binary Search Trees II
  • Wiggle Sort
  • Word Ladder
  • Verify Preorder Sequence in Binary Search Tree
  • Maximal Rectangle
    • 秋叶拓哉（iwi）、岩田阳一（wata）和北川宜稔（kita_masa）所著，巫泽俊（watashi）、庄俊元（navi）和李津羽（itsuhane）翻译的《挑战程序设计竞赛》
    • 潘宇超 2008
    • ACRush某TopCoder SRM
    • 栈维护histogram
    • 其他方法　
• 代码索引

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

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;

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;

// 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;
}

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

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)

#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;
  }
};

#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;
  }
};

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])

#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;
  }
};

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'))

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