Labels

Sunday, April 16, 2017

Minimum Path Sum in C++ using tabulation (Dynamic Programming)

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<int>> v(row, vector<int>(col,0));
        v[0][0] = grid[0][0];
        for (int i = 1; i< row; i++) 
            v[i][0] = grid[i][0] + v[i-1][0];
        for (int i = 1; i< col; i++) 
            v[0][i] = grid[0][i] + v[0][i-1];
        for (int i = 1; i<row; i++) {
            for (int j = 1; j < col; j++) {
                v[i][j] = grid[i][j] + min (v[i-1][j], v[i][j-1]);
            }
        }
        return v[row-1][col-1];    
    }
};

Coin Change problem in C++ using tabulation method dynamic programming

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> v(n+1, vector<int>(amount+1, 0));
        for (int i = 0; i<=n; i++)
            v[i][0] = 0;
        for (int i = 0; i<= amount; i++)
            v[0][i] = INT_MAX;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j>=coins[i-1] && v[i][j-coins[i-1]] < INT_MAX)
                    v[i][j] = min(v[i-1][j], v[i][j-coins[i-1]]+1);
                else
                    v[i][j] = v[i-1][j];
            }
        }
        return (v[n][amount]<INT_MAX)?v[n][amount]:-1;
    }
};

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        vector<vector<int>> v (len1+1, vector<int>(len2+1, 0));
        if (len1 == 0) return len2;
        if (len2 == 0) return len1;
        for (int i = 0; i< len1+1; i++) {
            for (int j = 0; j< len2+1; j++) {
                if (i == 0) v[i][j] = j;
                else if (j == 0) v[i][j] = i;
                else if (word1[i-1] == word2[j-1]) v[i][j] = v[i-1][j-1];
                else v[i][j] = 1+ min(min(v[i-1][j], v[i][j-1]), v[i-1][j-1]);
            }
        }
        return v[len1][len2];
    }
};

Longest Consecutive Sequence c++

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int max = 0;
        int cnt = 0;
        if (nums.size() == 0 ) return 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i< nums.size(); i++) {
            if (nums[i]+1 == nums[i+1]) {
                cnt++;
            } else if (nums[i+1] > nums[i]){
                if (cnt>max) max = cnt;
                cnt = 0;
            }
        }
        if (cnt>max) max = cnt;
        return max+1;
    }
};

Longest Substring Without Repeating Characters C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

   void util (string &s, int & max, int start, int end) {
        vector<int> arr(256,-1);
        int cnt = 0;
        int i;
        if (start >= end) return;
       
        for (i = start; i<end; i++) {
            if (arr[s[i]] == -1) {
                cnt++;
                arr[s[i]] = i;
            } else {
                break;
            }
        }
       
        if (cnt>max) max = cnt;
        arr.clear();
        if (i<end)
        util (s, max, arr[s[i]]+1, end);
       
    }
    int lengthOfLongestSubstring(string s) {
        int max = 0;
        util(s, max, 0, s.size());
        return max;
    }
int main() {
string s = "";
cout <<lengthOfLongestSubstring(s);
return 0;
}

Longest increasing sub-sequence in C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 0, max = 0;
        int n = nums.size();
        vector<int> L(n,1);
        for (int i = 0; i< n; i++) {
            for (int j = i+1; j<n; j++) {
                if (nums[j]>nums[i] && L[j]<L[i]+1) {
                    L[j] = L[i]+1;
                }
            }
        }
        for (int i = 0; i<n; i++) {
            if (max<L[i]) max = L[i];
        }
        return max;
    }
};

Thursday, March 16, 2017

Implement Text Editor with Gap Buffer

Implement Text Editor with Gap Buffer

Gap Buffer is a data structure which can be used to implement text editor. The advantage is that insertion/deletion can be very efficient and the data structure is simple. The disadvantage is when cursor changes its location frequently or the gap is frequently full, there will be a lot of copying operation, which is costly. The following gives more details about gap buffer.

  • Basically gap buffer can be implemented as an array (or a dynamic array) with some pointers to differentiate three regions: the segment before the gap, the gap, the segment after the gap.
| the front segment  |   the gap  |  the back segment  |
  • The location of the cursor in the text editor decides the border between the front segment and the gap. A example is given here:
We had a [            ] big day
  • As the above example, "We had a" is the front segment, "[   ]" is the gap buffer and "big day" is in the back segment. 
  • When insertion, new text is filled in the gap buffer, the start pointer of the gap buffer also moves accordingly. If the gap is full, we need to create new gap buffer and we may also need to move all the content in the back segment backwards.
  • When deletion,  we only need to move the start pointer of the gap buffer forwards if we are deleting the text in the front segment or  the end pointer of the gap buffer backwards if we are deleting the text in the back segment.
  • If we move the cursor, for example, the cursor is between "We" and "had" now:  "We [     ] had a big day". We need to copy the "had a" which was originally in the front segment to the back segment.