Minimum Path Sum -- Leetcode

Question:

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.

Answer:

class Solution {

public:

    int minPathSum(vector<vector<int> > &grid) {

        int m=grid.size();

        int n=grid[0].size();

        if(m==0||n==0) return -1;

        

        int dp[m][n];

        memset(dp,0,sizeof(dp));

        dp[0][0]=grid[0][0];

        for(int i=1;i<m;++i){

            dp[i][0]=dp[i-1][0]+grid[i][0];

        }

        for(int j=1;j<n;++j){

            dp[0][j]=dp[0][j-1]+grid[0][j];

        }

        for(int i=1;i<m;++i){

            for(int j=1;j<n;++j){

                dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);

            }

        }

        return dp[m-1][n-1];

    }

};

Integer to Roman -- Leetcode

Question:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Answer:
Using greedy algorithm. Simple solution is to list all elements, then num minus the largest element every time on each digit position.

class Solution {
public:
    string intToRoman(int num) {
        string str;  
        string symbol[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};  
        int value[]=    {1000, 900, 500, 400, 100,  90,  50,  40,  10, 9,  5,  4,  1};  
        for(int i=0;num!=0;++i) {
            while(num>=value[i]) {
             
                num-=value[i];
                str+=symbol[i];
            }
        }
        return str;
    }
};

Unique path -- leetcode

Question:

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Answer:

1.DP, using Recursion (Time limit expired)

int uniquePaths(int m,int n){

        if(m==1 || n==1) return 1;

        else return uniquePaths(m-1)+ uniquePaths(n-1);

}

2.DP, look up the recursion table directly.

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> >table(m,vector<int>(n,1));
    
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                table[i][j]=table[i-1][j]+table[i][j-1];
            }
        }
        return table[m-1][n-1];
    }
};

3.DP, Similar to 2, be more space efficient.
          int uniquePath(int m,int n){

                 vector<int> table(n,1);
                for(int i=1;i<m;++i){
                      for( int j=1;j<n;++j){
                           table[j]+= table[j-1];
                       }
                }
                return table[n-1];
           }

Climbing stairs--leetcode

Question:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Answer:

class Solution {
public:
    int climbStairs(int n) {
        if(n==0) return 0;
        int fn_2 = 1, fn_1=2, fn;
        if(n==1) return fn_2;
        if(n==2) return fn_1;
                                              //if(n>=3)
        for(int i=3;i<=n;++i){
            fn = fn_1 + fn_2;
            fn_2 = fn_1;
            fn_1 = fn;
        }
        return fn_1;
    }

};

Graph BFS + DFS traverse

BFS: Using queue
DFS: Using recursion, also can use stack.

Answer:
C++ code:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class UndirectedGraphNode {
 public:
int label;
    bool visited;
vector<UndirectedGraphNode *> neighbors;

    UndirectedGraphNode(int x){
label=x;
visited = false;
}
    ~UndirectedGraphNode(){
}  
};

void concat(UndirectedGraphNode *p, UndirectedGraphNode *q){
p->neighbors.push_back(q);
q->neighbors.push_back(p);
}

vector<int> BFS (UndirectedGraphNode* node){
        queue<UndirectedGraphNode*> que;
        vector<int>  res;
        que.push(node);
node->visited=true;
int currnum=1;
int nextnum=0;

        while(!que.empty()){
             UndirectedGraphNode* cur = que.front();
             que.pop();
             res.push_back(cur->label);     //Only when poping an Node from the queue, add its label to the res.
         currnum--;

             for(int i=0; i < cur->neighbors.size();++i){
                   UndirectedGraphNode* nb= cur->neighbors[i];
                   if(!nb->visited){
                         que.push(nb);
                         nb->visited=true;
                   nextnum++;
                   }
              }

 if(currnum==0){
res.push_back(0);             //'0' is a symbol, means '\n', this level ends.
               std::swap(currnum,nextnum);
          }
         }
         return res;
}

vector<int> DFS(UndirectedGraphNode *node){
node->visited=true;
vector<int> res;
res.insert(res.begin(),node->label);              //recursion base case, no "unvisited" neighbor, only itself.

for(int i=0; i< node->neighbors.size();++i){
UndirectedGraphNode *nb=node->neighbors[i];
if(!nb->visited){
                 vector<int> subres=DFS(nb);                //recursion case, adding subres in preorder order.
                 nb->visited=true;
                 res.insert(res.end(),subres.begin(),subres.end());
}
}
return res;
}

int main(){

UndirectedGraphNode *a= new UndirectedGraphNode(1);
UndirectedGraphNode *b= new UndirectedGraphNode(2);
UndirectedGraphNode *c= new UndirectedGraphNode(3);
UndirectedGraphNode *d= new UndirectedGraphNode(4);
UndirectedGraphNode *e= new UndirectedGraphNode(5);
UndirectedGraphNode *f= new UndirectedGraphNode(6);
//Create graph.
concat(a,b);
concat(b,c);
concat(a,c);
concat(b,d);
concat(d,e);
concat(c,f);

vector<int> result;
//BFS
result= BFS(a);
cout<<"BFS:";
for(int i=0;i<result.size();i++){
cout<<result[i]<<" ";
}
/* 
//DFS
result= DFS(a);
cout<<"DFS:";
for(int i=0;i<result.size();i++){
cout<<result[i]<<" ";
}
*/
getchar();
return 0;
}

Graph BFS traverse

Using BFS method to traverse a graph.

Answer:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     bool visited;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x), visited(false) {};
 * }
**/

class Solution{
public:
vector<UndirectedGraphNode *>  bfs (UndirectedGraphNode* node){
        queue<UndirectedGraphNode*> que;
        vector<UndirectedGraphNode*>  res;
        que.push(node);
        while(!que.empty()){
             UnidirectedGraphNode *cur = que.top();
             que.pop();
             res.push_back(cur);

             for(int i=0; i < cur->neighbors.size();++i){
                   UndirectedGraphNode* nb= cur->neighbor[i];
                   if(!nb->visited){
                         que.push(nb);
                         nb->visited=true;
                   }
              }
         }
         return res;
}
};

Word Break--Leetcode

Question:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Answer:

class Solution {

public:

    bool wordBreak(string s, unordered_set<string> &dict) {

    vector<bool> wordB(s.length() + 1);

    wordB[0] = true;

    for (int i = 1; i < s.length() + 1; i++) {

        for (int j = i - 1; j >= 0; j--) {

            if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) {

                wordB[i] = true;

                break;

            }

        }

    }  

    return wordB[s.length()];

    }

};