GeeksforGeeks: Dynamic Programming | Set 28 (Minimum insertions to form a palindrome)

Minimum insertions to form a palindrome
ref: http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/
假设有minInsert(int begin, int end), s为string，返回 s[begin : end]所需的最少insertion
如果s[begin] == s[end], minInsert(begin, end) = minInsert(begin + 1, end - 1);
如果s[begin] != s[end], minInsert(begin, end) = min(minInsert(begin + 1, end), minInsert(begin, end - 1)) + 1;

以下是递归解法：

int minInsert(string s, int begin, int end) {
    if (begin == end) return 0;
    if (begin == end - 1) return (s[begin] == s[end])? 0 : 1;
    if (s[begin] == s[end]) {
        return minInsert(s,begin + 1,end - 1);
    }
    return 1 + min(minInsert(s,begin + 1,end),minInsert(s,begin,end - 1));
}

显而易见，有重复的子问题，所以可以用dp来解决

int minInsert(string s) {
    int n = s.length();
    vector<vector<int>> dp(n,vector<int>(n,0));
    for (int gap = 1; gap < n; gap++) {
        for (int begin = 0, end = gap; end < n; begin++,end++) {
            if (s[begin] == s[end]) {
                dp[begin][end] = dp[begin + 1][end - 1];    
            }else {
                dp[begin][end] = min(dp[begin + 1][end],dp[begin][end - 1]) + 1;    
            }
        }
    }
    
    return dp[0][n - 1];
}

GeeksforGeeks: Segment Tree | Set 1 (Sum of given range), Segment Tree | Set 2 (Range Minimum Query), Binary Indexed Tree

Segment Tree | Set 1 (Sum of given range)
ref: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
1维

void updateHelper(vector<int> &tree,int diff,int i,int start,int end,int index) {
    if (i < start || i > end) return;
    tree[index] += diff;
    if (start != end) {
        int mid = (start + end) / 2;
        updateHelper(tree,diff,i,start,mid,index * 2 + 1); 
        updateHelper(tree,diff,i,mid + 1,end,index * 2 + 2); 
    }
}

void update(vector<int> &nums, vector<int> &tree,int i,int newValue) {
    int diff = newValue - nums[i];
    nums[i] = newValue;
    updateHelper(tree,diff,i,0,nums.size() - 1,0);
}

int query(vector<int> &tree,int targetS, int targetE, int curS, int curE,int index) {
    if (curS >= targetS && curE <= targetE) {
        return tree[index];
    }
    if (curS > targetE || curE < targetS) {
        return 0;
    }
    int mid = (curS + curE) / 2;
    return query(tree,targetS,targetE,curS,mid,index * 2 + 1) + query(tree,targetS,targetE,mid + 1,curE,index * 2 + 2);
}

int query(vector<int> &nums,vector<int> &tree,int start,int end) {
    return query(tree,start,end,0,nums.size() - 1,0);
}

int buildTree(vector<int> &nums,vector<int> &tree,int start,int end,int i) {
    //cout << i << endl;
    if (start == end) {
        tree[i] = nums[start];
        return tree[i];    
    }
    int mid = (start + end) / 2;
    tree[i] = buildTree(nums,tree,start,mid,2 * i + 1)
                + buildTree(nums,tree,mid + 1,end,2 * i + 2);
    return tree[i];
}

void segmentTree(vector<int> &nums) {
    vector<int> tree(1000,0);
    buildTree(nums,tree,0,nums.size() - 1,0);
}

2维
2维的build tree单独搞不出来，最后只能用调用update，O( n^2 * lgn * lgn)

void updateY(vector<vector<int>> &tree,int y1,int cY1,int cY2,int x,int y,int diff) {
    if (y1 > cY2 || y1 < cY1) return;
    tree[x][y] += diff;
    if (cY1 == cY2) return;
    int mid = (cY1 + cY2) / 2;
    updateY(tree,y1,cY1,mid,x,y * 2 + 1,diff);
    updateY(tree,y1,mid + 1,cY2,x,y * 2 + 2,diff);
    
}

void updateX(vector<vector<int>> &tree,int x1,int y1,int cX1,int cY1,int cX2,int cY2,int x,int y,int diff) {
    if (x1 > cX2 || x1 < cX1) return;
    updateY(tree,y1,cY1,cY2,x,y,diff);
    if (cX1 == cX2) return;
    int mid = (cX1 + cX2) / 2;
    updateX(tree,x1,y1,cX1,cY1,mid,cY2,2 * x + 1,y,diff);
    updateX(tree,x1,y1,mid + 1,cY1,cX2,cY2, 2 * x + 2,y,diff);
}


int getYSum(vector<vector<int>> &tree,int y1,int y2,int cY1,int cY2,int x,int y) {
    if (y1 <= cY1 && y2 >= cY2) {
        return tree[x][y];
    }
    if (y1 > cY2 || y2 < cY1) return 0;
    
    int mid = (cY1 + cY2) / 2;
    return getYSum(tree,y1,y2,cY1,mid,x,y * 2 + 1) + getYSum(tree,y1,y2,mid + 1,cY2,x,y * 2 + 2);
}

int getXSum(vector<vector<int>> &tree,int x1,int y1,int x2,int y2,int cX1,int cY1,int cX2,int cY2,int x,int y) {
    if (x1 <= cX1 && x2 >= cX2) {
        return getYSum(tree,y1,y2,cY1,cY2,x,y);
    }
    if (x1 > cX2 || x2 < cX1) return 0;
    
    int mid = (cX1 + cX2) / 2;
    return getXSum(tree,x1,y1,x2,y2,cX1,cY1,mid,cY2,2 * x + 1,y) + getXSum(tree,x1,y1,x2,y2,mid + 1,cY1,cX2,cY2, 2 * x + 2,y);
}

void twoDSegmentTree(vector<vector<int>> &matrix) {
    vector<vector<int>> tree(1000,vector<int>(1000,0));
    int m = matrix.size(),n = matrix[0].size();
    
    // build 2d segment tree
    for (int i = 0; i < m; i++) {
     for (int j = 0; j < n; j++) {
      updateX(tree,i,j,0,0,m - 1,n - 1,0,0,matrix[i][j]);
     }
    }
}

------------------------------------------------------------------------------------
Segment Tree | Set 2 (Range Minimum Query)
ref: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

int updateHelper(vector<int> &tree,int newValue,int i,int start,int end,int index) {
    if (i < start || i > end) return INT_MAX;
    if (start == end) {
        tree[index] = newValue;   
        return tree[index];
    }

    int mid = (start + end) / 2;
    tree[index] = min(updateHelper(tree,newValue,i,start,mid,index * 2 + 1),
                    updateHelper(tree,newValue,i,mid + 1,end,index * 2 + 2));
    
    return tree[index];
}

void update(vector<int> &nums, vector<int> &tree,int i,int newValue) {
    nums[i] = newValue;
    updateHelper(tree,newValue,i,0,nums.size() - 1,0);
}

int query(vector<int> &tree,int targetS, int targetE, int curS, int curE,int index) {
    if (curS >= targetS && curE <= targetE) {
        return tree[index];
    }
    if (curS > targetE || curE < targetS) {
        return INT_MAX;
    }
    int mid = (curS + curE) / 2;
    return min(query(tree,targetS,targetE,curS,mid,index * 2 + 1), query(tree,targetS,targetE,mid + 1,curE,index * 2 + 2));
}

int query(vector<int> &nums,vector<int> &tree,int start,int end) {
    return query(tree,start,end,0,nums.size() - 1,0);
}

int buildTree(vector<int> &nums,vector<int> &tree,int start,int end,int i) {
    if (start == end) {
        tree[i] = nums[start]; 
        return tree[i];
    }
    int mid = (start + end) / 2;
    tree[i] = min(buildTree(nums,tree,start,mid,2 * i + 1),
                buildTree(nums,tree,mid + 1,end,2 * i + 2));
    return tree[i];
}

void segmentTree(vector<int> &nums) {
    vector<int> tree(1000,0);
    buildTree(nums,tree,0,nums.size() - 1,0);
}

-----------------------------------------------------------------
Binary Indexed Tree
ref: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
http://www.hawstein.com/posts/binary-indexed-trees.html
http://algorithmsandme.in/2015/02/binary-indexed-trees/
1维

void update(vector<int> &bit,int idx,int diff) {
    while (idx < bit.size()) {
  bit[idx] += diff;
  idx += idx & (-idx);
 }
}

int get(vector<int> &bit,int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += bit[idx];
        idx -= idx & (-idx);
    }
    
    return sum;
}

vector<int> buildTree(vector<int> &nums) {
    vector<int> bit(nums.size() + 1,0);
    for (int i = 0; i < nums.size(); i++) {
        update(bit,i + 1,nums[i]);
    }
    
    return bit;
    
}

void biTree(vector<int> &nums) {
    vector<int> bit = buildTree(nums);
}

2维bit

#1 每个row的sum，再做一个bit，就成了2维的了
求[i][j]的值需要从[0][i] 到 [i][j]

#2 如果求[x1,y1]到[x2,y2]的矩阵的值，则要做一些矩阵减法

void update(vector<vector<int>> &bit, int row,int col,int diff) {
    while (row < bit.size()) {
        int idx = col;
        while (idx < bit[0].size()) {
            bit[row][idx] += diff;
            idx += idx & (-idx);
        }
        row += row & (-row);
    }
}

int read(vector<vector<int>> &bit, int row,int col) {
 int sum = 0;
 while (row > 0) {
  int idx = col;
  while (idx > 0) {
   sum += bit[row][idx];
   idx -= idx & (-idx); 
  }
  row -= row & (-row);
 }
 
 return sum;
}

vector<vector<int>> buildBit(vector<vector<int>> &matrix) {
    vector<vector<int>> bit(matrix.size() + 1,vector<int>(matrix[0].size() + 1,0));
    
    for (int row = 0; row < matrix.size(); row++) {
        for (int col = 0; col < matrix[0].size(); col++) {
            update(bit,row + 1,col + 1,matrix[row][col]);
        }
    }
    return bit;
}

void twoDBit(vector<vector<int> > &matrix) {
    vector<vector<int>> bit = buildBit(matrix);
    
}

Day 120, Longest Increasing Subsequence, Longest Common Substring Show result, Longest Increasing Continuous subsequence II

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Have you met this question in a real interview?

Yes

Example

For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What's the definition of longest increasing subsequence?

    * The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.  

    * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

---------------------------------------------------------------------
O(n^2)

class Solution {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        // write your code here
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size(),1);
        int longest = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]) {
                    dp[i] = max(dp[i],dp[j] + 1);
                }
                longest = max(longest,dp[i]);
            }
        }
        
        return longest;
    }
};

geeksforgeeks,O(n lg n)

Longest Common Substring Show result 

Given two strings, find the longest common substring.

Return the length of it.

Have you met this question in a real interview? 

Yes

Example

Given A = "ABCD", B = "CBCE", return 2.

Note

The characters in substring should occur continuously in original string. This is different with subsequence.

Challenge

O(n x m) time and memory.

---------------------------------------------------
画个2d矩阵就明白了

class Solution {
public:    
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int m = A.length(), n = B.length();
        vector<vector<int> > dp(m + 1,vector<int>(n + 1,0));
        int longest = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    longest = max(longest,dp[i][j]);
                }
            }
        }
        
        return longest;
    }
};

线性额外空间

class Solution {
public:    
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int m = A.length(), n = B.length();
        vector<int> dp(n + 1,0);
        int longest = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (A[i - 1] == B[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    longest = max(longest,dp[j]);
                }else {
                    dp[j] = 0;
                }
            }
        }
        
        return longest;
    }
};

Longest Increasing Continuous subsequence II

Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

Have you met this question in a real interview? 

Yes

Example

Given a matrix:

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

return 25

Challenge

O(nm) time and memory.

--------------------------------------------------
以每一点为path的起始，它所得到最长递增数列都是恒定的
所以用memoization即可

class Solution {
public:
    /**
     * @param A an integer matrix
     * @return  an integer
     */
    int dfs(vector<vector<int>>& A,vector<vector<int>> &dp,int row,int col) {
        if (dp[row][col] != 0) return dp[row][col];

        if (row + 1 < A.size() && A[row + 1][col] > A[row][col]) {
            dp[row][col] = max(dp[row][col],dfs(A,dp,row + 1,col));
        }
        if (row - 1 >= 0 && A[row - 1][col] > A[row][col]) {
            dp[row][col] = max(dp[row][col],dfs(A,dp,row - 1,col));
        }
        if (col - 1 >= 0 && A[row][col - 1] > A[row][col]) {
            dp[row][col] = max(dp[row][col],dfs(A,dp,row,col - 1));
        }
        if (col + 1 < A[0].size() && A[row][col + 1] > A[row][col]) {
            dp[row][col] = max(dp[row][col],dfs(A,dp,row,col + 1));
        }
        
        dp[row][col]++;
        return dp[row][col];
    }
     
    int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {
        // Write your code here
        if (A.size() == 0) return 0;
        int m = A.size(), n = A[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        int longest = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == 0) {
                    dp[i][j] = dfs(A,dp,i,j);
                }
                longest = max(longest,dp[i][j]);
            }
        }
        
        return longest;
    }
};

遍历，所有点按高度排序

struct Dot {
        int row;
        int col;
        int height;
        Dot(int x,int y,int h):row(x),col(y),height(h) {
        }
    };

class Solution {
public:
    static bool cmp(const Dot &d1,const Dot &d2) {
        return d1.height < d2.height;
    }

    /**
     * @param A an integer matrix
     * @return  an integer
     */
    int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {
        // Write your code here
        if (A.size() == 0) return 0;
        int m = A.size(), n = A[0].size();
        vector<vector<int>> len(m,vector<int>(n,0));
        vector<Dot> dots;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Dot d(i,j,A[i][j]);
                dots.push_back(d);
            }
        }
        
        sort(dots.begin(),dots.end(),cmp);
        int longest = 0;
        for (int i = 0; i < dots.size(); i++) {
            if (dots[i].row + 1 < m && A[dots[i].row + 1][dots[i].col] > dots[i].height
                && len[dots[i].row + 1][dots[i].col] < len[dots[i].row][dots[i].col] + 1) {
                len[dots[i].row + 1][dots[i].col] = len[dots[i].row][dots[i].col] + 1;
            }
            
            if (dots[i].col + 1 < n && A[dots[i].row][dots[i].col + 1] > dots[i].height
                && len[dots[i].row][dots[i].col + 1] < len[dots[i].row][dots[i].col] + 1) {
                len[dots[i].row][dots[i].col + 1] = len[dots[i].row][dots[i].col] + 1;
            }
            
            if (dots[i].row - 1 >= 0 && A[dots[i].row - 1][dots[i].col] > dots[i].height
                && len[dots[i].row - 1][dots[i].col] < len[dots[i].row][dots[i].col] + 1) {
                len[dots[i].row - 1][dots[i].col] = len[dots[i].row][dots[i].col] + 1;
            }
            
            if (dots[i].col - 1 >= 0 && A[dots[i].row][dots[i].col - 1] > dots[i].height
                && len[dots[i].row][dots[i].col - 1] < len[dots[i].row][dots[i].col] + 1) {
                len[dots[i].row][dots[i].col - 1] = len[dots[i].row][dots[i].col] + 1;
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                longest = max(longest,len[i][j]);
            }
        }
        
        return longest + 1;
    }
};

GeeksforGeeks: Diameter of a Binary Tree， Inorder Successor in Binary Search Tree

Diameter of a Binary Tree
http://www.geeksforgeeks.org/diameter-of-a-binary-tree/

在返回想要的值的同时，传入pointer计算树的高度

int helper(TreeNode *root, int *height) {
    if (root == NULL) {
        *height = 0;
        return 0;
    }
    int lh = 0, rh = 0;
    int leftD = helper(root->left,&lh);
    int rightD = helper(root->right,&rh);
    
    *height = max(lh,rh) + 1;
    return max(lh + rh + 1,max(leftD,rightD));
}

int getDiameter(TreeNode *root) {
    int longest = 0;
    helper(root,longest);
    
    return longest;
}

--------------------------------------
Inorder Successor in Binary Search Tree
写法1：http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
写法2：
同样的写法可以用来计算floor function

TreeNode *myFloor(TreeNode *root,int key) {
    if (root == NULL) return NULL;
    
    if (key >= root->val) {
        return myFloor(root->right,key);    
    }else {
        TreeNode *right = myFloor(root->left,key);
        if (right == NULL) return root;
        else return right;
    }
}