chocoluffy

"""
When I want to loop over lines from stdin, I generally use sys.stdin instead. In that case you could ignore the count.
For a test case like the following, giving N integers and sum them up, then divide by K.

1 #test cases
3 2 #N  #K
4 5 7 #N integers 
"""

raw_input() # ignore the size

chocoluffy

"""
典型题：
- DFS的空间复杂度是O(N*M)，因为worst case是全部都为1，这个时候的stack number为
  O(N*M)，即便我们可以直接修改原grid而不额外引入复杂度，因为function call引入的
  复杂度是需要考虑进去的。

> 原本写有visited[N][M]的算法会给runtime error(recursion depth exceeds)，但是由
于可以直接修改参数grid，使得不需要extra的visited来记录哪些path是经过的。

仔细思考一下为什么这个修改会改善程序：

chocoluffy

OJ里用python的解法

在遇到runtime error的时候需要注意的地方：

• recursion function stack mem. 尽量少引入可能尺寸过大的全局变量。如果能够直接改动数据首选直接改动用作flag。
• 尽量避免O(n^2)复杂度的算法，在hackerrank上容易runtime error。
• 多使用python built-in的操作比如，set(), sorted()等等来加速，以及保持算法简洁。

String

将string的all chars转换为list

lst = list('hello') # return ['h', 'e'....]

chocoluffy

padding and index

usually we need to set base case. like for dp in strings, the base case is usually empty string. thus we enlarge the usual dp table by increasing the height and width by 1. but when we iterate the table, and refer to the original string, we need to reduce the index by 1 to match with original string index. 还是看情况的，主要依据是根据dp里和occurrence的联系来判断的，dp[i]如果和dp[i-1]等相关，则往往是在前面添加padding。如果dp[i]和dp[i+1]相关，则在后面添加padding。

dp table里index的含义

搞清楚index i，dp[i]表示的是，从开始到包含i这个位置的元素[:i+1]，还是直到i这个位置之前[:i]，还是指从后开始的。

chocoluffy

"""
Typical question convert:
- finding longest common suffix in all prefix pairs of two string.
=> "all prefix pairs" equals to a dp table, where dp[i][j] represent the prefix pair of s1[:i+1] and s2[:j+1]
=> given such dp table, to find the longest common suffix:
   constantly aligning with last elements and increment, till not match.
   LCSuffix[i][j] = LCSuffic[i-1][j-1] + 1 if s1[i] == s2[j]
"""
class Solution(object):
  def longest_common_substring(self, s1, s2):

chocoluffy

xrange or range

xrange提供的是iterator，对内存比较好。

Python 2：
for i in xrange(0,10,2):
  print(i)
  
Python 3
for i in range(0,10,2):
 print(i)

chocoluffy

// given an unordered array and a pivot value as the last element in the array, sort the array such that all elements smaller than pivot appear at the left of the pivot.

// use j to iterate the array, till meet k.
// < i left is elements smaller than pivot; 
//  [i, j) is pivots duplicate;
// (k, -1] is elements greater then pivot;
void partition(vector<int> A) {
  int i = 0, j = 0, k = A.size() - 1, pivot = A[A.size() - 1];
  while(j < k) {
    if (A[j] < pivot) {

chocoluffy

记录c++里引用数据结构的经典写法。

chocoluffy

Data Structure

stack

单调栈的使用：

• 找到每个元素下一个更大的元素。

palindrome

很多时候和prefix，suffix联系在一起。

chocoluffy

记录常见的STL数据结构的API，和使用方式。

vector

emplace_back(), similar to push_back(), but will auto call constructor(more convenient).