Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

class Solution {
public:
    int jump(vector<int>& nums) {
        int fartherest = 0;
        int lastFartherest = 0;
        int i=0;
        int count=0;
        while(i<=fartherest && i<nums.size())
        {
            if (i>lastFartherest){
                ++count;
                lastFartherest = fartherest;
            }
            fartherest = max(fartherest, i+nums[i]);
            ++i;
        }
        return count;
    }
};

35 Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int left=0,right = n-1;
        int res = 0;
        while(left<=right)
        {
            int mid = left+(right-left)/2;
            if (target == A[mid]){
                return mid;
            }
            else if (A[mid]<target){
                left = mid+1;
                res = left;
            }
            else{
                right = mid-1;
                res = mid;
            }
        }
        return res;
    }
};

112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root)
            return false;
        if (!root->left && !root->right)
            return root->val == sum;
        return hasPathSum(root->left, sum-root->val ) || hasPathSum(root->right, sum-root->val);
    }
};

129 Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int res = 0;
        int sum=0;
        help(root, res, sum);
        return sum;
    }
    void help(TreeNode *root, int res, int &sum)
    {
        if (!root)
            return;
        res = res*10 + root->val;
        if (!root->left && !root->right)
        {
            sum+= res;
            return;
        }
        if (root->left)
        {
            help(root->left, res, sum);
        }
        if (root->right)
        {
            help(root->right,res,sum);
        }
    }
};

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int sum=0;
        if (!root)
            return 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            TreeNode * tmp = q.front();
            q.pop();
            if (!tmp->left && !tmp->right)
            {
                sum+= tmp->val;
            }
            else
            {
                if (tmp->left)
                {
                    tmp->left->val += tmp->val*10;
                    q.push(tmp->left);
                }
                if (tmp->right)
                {
                    tmp->right->val += tmp->val*10;
                    q.push(tmp->right);
                }
            }
        }
        return sum;
    }
    
};

93 Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<int> ip;
        vector<string> res;
        help(s,ip,res,0);
        return res;
    }
    void help(string s, vector<int> & ip, vector<string> &res, int pos)
    {
        if (ip.size()==4 && pos == s.size())
        {
            string tmp;
            for (int i=0;i<ip.size();i++)
            {
                tmp+= to_string(ip[i])+".";
            }
            tmp.pop_back();
            res.push_back(tmp);
            return;
        }
        if (ip.size()==4 || pos>=s.size())
            return;
        for (int i=1;i<=3;i++)
        {
            string tmp = s.substr(pos,i);
            int val = stoi(tmp);
            if (isValid(tmp))
            {
                ip.push_back(val);
                help(s,ip,res,pos+i);
                ip.pop_back();
            }
        }
    }
    bool isValid(string s)
    {
        int i=0;
        if (s[0]=='0' && s.size()>1)
            return false;
        int val = stoi(s);
        if (val>=0 && val<=255)
            return true;
        return false;
    }

};

89 Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

class Solution {
public:
    vector<int> grayCode(int n) {
        if (n==0)
        {
            vector<int> res = vector<int>(1,0);
            return res;
        }
        vector<int> res = grayCode(n-1);
        int i = res.size()-1;
        for (;i>=0;i--)
        {
            int temp = res[i];
            temp = temp | (1<<(n-1));
            res.push_back(temp);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res = vector<int>(1,0);
        for (int i=1;i<=n;i++)
        {
            for (int j = res.size()-1;j>=0;j--)
            {
                int temp = res[j];
                temp = temp|(1<<(i-1));
                res.push_back(temp);
            }
        }
        return res;
    }
};

220 Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

class Solution {
public:
    int numIslands(vector<vector<char>> &grid) {
        int m = grid.size();
        if (m==0)
            return 0;
        int n = grid[0].size();
        if (n==0)
            return 0;
        int count = 0;
        for (int i=0;i<m;i++)
        {
            for (int j=0;j<n;j++)
            {
                if (grid[i][j]=='1')
                {
                    ++count;
                    dfs(grid,i,j,m,n);
                }
            }
        }
        return count;
    }
    void dfs(vector<vector<char>> &grid,int i, int j, int m, int n)
    {
        grid[i][j]='X';
        if (i-1>=0 && grid[i-1][j]=='1')
        {
            dfs(grid,i-1,j,m,n);
        }
        if (i+1<m && grid[i+1][j]=='1' )
        {
            dfs(grid,i+1,j,m,n);
        }
        if (j-1>=0 && grid[i][j-1]=='1')
        {
            dfs(grid,i,j-1,m,n);
        }
        if (j+1<n && grid[i][j+1]=='1')
        {
            dfs(grid,i,j+1,m,n);
        }
    }
};