leetcode Questions: Number of Islands

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.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Analysis:

This is a typical recursive problem which can be solved by either Depth First Search(DFS) or Breath First Search (BFS).

Briefly speaking, DFS is to search every possible directions(solutions) whenever meet the new one, BFS is to search and store every possible directions(solutions) using a queue usually, then search from the head of the queue each time.

In this problem, possible directions are left, right, top, bottom, with constrains that the new location is '1' and has not been visited before. Therefore, we can define a bool matrix (of same size) to store the status of each element in the grid, set it to false when it is not available(been visited).

Details can be found in the code below, which is pretty straightforward.

Code(C++, DFS):

class Solution {
public:

    void search(int i, int j, vector<vector<char>>& grid, vector<vector<bool>>& mark){
        mark[i][j] = false;
        
        if (i+1<grid.size() && grid[i+1][j]=='1' && mark[i+1][j]==true){
            search(i+1,j,grid,mark);
        }
        if (j+1<grid[0].size() && grid[i][j+1]=='1' && mark[i][j+1]==true){
            search(i,j+1,grid,mark);
        }
        if (i-1>=0 && grid[i-1][j]=='1' && mark[i-1][j]==true){
            search(i-1,j,grid,mark);
        }
        if (j-1>=0 && grid[i][j-1]=='1' && mark[i][j-1]==true){
            search(i,j-1,grid,mark);
        }
    }    

    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if (row==0) return 0;
        int col = grid[0].size();
        
        int res=0;
        
        vector<vector<bool> > mark(row, vector<bool>(col,true));
        
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (grid[i][j] == '1' && mark[i][j] == true){
                    search(i,j,grid,mark);
                    res+=1;
                }
            }
        }
        return res;
        
    }
};

Code(C++, BFS):

class Solution {
public:

    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if (row==0) return 0;
        int col = grid[0].size();
        
        int res=0;
        
        vector<vector<bool> > mark(row, vector<bool>(col,true));
        
        queue<int> q_row;
        queue<int> q_col;
        
        for (int i=0; i<row; i++){
            for (int j=0; j<col; j++){
                if (grid[i][j]=='1' && mark[i][j]){
                    q_row.push(i);
                    q_col.push(j);
                    mark[i][j] = false;
                    while (!q_row.empty()){
                        int ii = q_row.front();
                        int jj = q_col.front();
                        
                        if (ii+1<row && grid[ii+1][jj]=='1' && mark[ii+1][jj]){
                            q_row.push(ii+1);
                            q_col.push(jj);
                            mark[ii+1][jj] = false;
                        }
                        if (jj+1<col && grid[ii][jj+1]=='1' && mark[ii][jj+1]){
                            q_row.push(ii);
                            q_col.push(jj+1);
                            mark[ii][jj+1] = false;
                        }
                        if (ii-1 >=0 && grid[ii-1][jj]=='1' && mark[ii-1][jj]){
                            q_row.push(ii-1);
                            q_col.push(jj);
                            mark[ii-1][jj] = false;
                        }
                        if (jj-1>=0 && grid[ii][jj-1]=='1' && mark[ii][jj-1]){
                            q_row.push(ii);
                            q_col.push(jj-1);
                            mark[ii][jj-1] = false;
                        }
                        
                        q_row.pop();
                        q_col.pop();
                    }
                    res += 1;
                }
            }
        }
        return res;
    }
};

Code(Python, DFS):

class Solution:
    
    def search(self, i, j, grid, mark):
        mark[i][j] = False
        
        if i+1 < len(grid) and grid[i+1][j] == '1' and mark[i+1][j] == True:
            self.search(i+1,j,grid,mark)
            
        if j+1 < len(grid[0]) and grid[i][j+1] == '1' and mark[i][j+1] == True:
            self.search(i,j+1,grid,mark)
            
        if i-1 >= 0 and grid[i-1][j] == '1' and mark[i-1][j] == True:
            self.search(i-1,j,grid,mark)
            
        if j-1 >=0 and grid[i][j-1] == '1' and mark[i][j-1] == True:
            self.search(i,j-1,grid,mark)
    
    # @param {character[][]} grid
    # @return {integer}
    def numIslands(self, grid):
        row = len(grid)
        if row == 0:
            return 0
        col = len(grid[0])
        
        #mark = [x[:] for x in [[True]*col]*row]
        mark = [[True for x in range(col)] for x in range(row)]
        
        res  = 0
        for i in range(0,row):
            for j in range(0, col):
                if grid[i][j] == '1' and mark[i][j] == True:
                    self.search(i, j, grid,mark)
                    res += 1
        return res
        

Code(Python, BFS):

class Solution:
    # @param {character[][]} grid
    # @return {integer}
    def numIslands(self, grid):
        row = len(grid)
        if row == 0:
            return 0
        col = len(grid[0])
        
        #mark = [x[:] for x in [[True]*col]*row]
        mark = [[True for x in range(col)] for x in range(row)]
        
        res  = 0
        
        q = []
        
        for i in range(0,row):
            for j in range(0, col):
                if grid[i][j] == '1' and mark[i][j] == True:
                    q.append([i,j])
                    mark[i][j] = False
                    while q:
                        ii = q[0][0]
                        jj = q[0][1]
                        q.pop(0)
                        
                        if ii+1 < len(grid) and grid[ii+1][jj] == '1' and mark[ii+1][jj] == True:
                            q.append([ii+1, jj])
                            mark[ii+1][jj] = False
                
                        if jj+1 < len(grid[0]) and grid[ii][jj+1] == '1' and mark[ii][jj+1] == True:
                            q.append([ii, jj+1])
                            mark[ii][jj+1] = False
                
                        if ii-1 >= 0 and grid[ii-1][jj] == '1' and mark[ii-1][jj] == True:
                            q.append([ii-1, jj])
                            mark[ii-1][jj] = False
                
                        if jj-1 >=0 and grid[ii][jj-1] == '1' and mark[ii][jj-1] == True:
                            q.append([ii, jj-1])
                            mark[ii][jj-1] = False
                    res += 1        
                        
        return res
        

leetcode Question: Binary Tree Right Side View

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Analysis:

Note that in this problem, it is NOT to print out the right most sub tree.
It is to print out the most right element in each level.
Therefore the problem becomes pretty straightforward, which easily reminds us one of the basic tree operations:  level order traversal.

Similar to my previous post (here), we can use two queues to do the level order traversal. The only difference is in this question, we only need to store the 'last' element in each level and save it to the result vector. Implementation details can be seen in the following code.

Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> p, q;
        vector<int> res;
        if (!root) return res;
        
        p.push(root);
        while (1){
            int last;
            while (!p.empty()){
                TreeNode* cur = p.front();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
                last = cur->val;
                p.pop();
            }
            res.push_back(last);
            p=q;
            while (!q.empty()){q.pop();}
            if (p.empty()) return res;
        }
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def rightSideView(self, root):
        res = []
        if not root:
            return res
        p = []
        q = []
        p.append(root)
        while True:
            last = root.val
            while p:
                if p[0].left:
                    q.append(p[0].left)
                if p[0].right:
                    q.append(p[0].right)
                last = p[0].val
                p.pop(0);
            res.append(last)
            p = q
            q = []
            if not p:
                return res

leetcode Question: House Robber

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Analysis:

In this problem, it is usually hard for beginers to remind the "dynamic programming” (a.k.a. DP) approach. In order to better illustrate this specific problem, I tried to draw a figure below to help us understand the problem.  I personally used to look for the “state” in the problem at first, and then look for the “transition” between the states, then it is often just several lines of code that can solve the DP problem.

In this problem, every time the robber is in front of a house with his bag of money can be viewed as a “state”, note that at this time,  money bag has the money robber robbed in previous houses. Now, “actions” that robber can take are only two: rob or skip this house. However, this action is related to some “previous history” which is required by the problem: no adjacent houses is allowed to break. Considering the robber following certain path to get the max monry, In other words, for current house we have to choose if we rob or skip.  if we skip, we could have the amount of money from the path connected with previous house (which means we also robbed previous house). If we robber current house, then we cannot take the path connected to previous house, but the 2nd previous is OK.

For those who are familiar with a little DP, the description can be easily extracted as the following:

Given an array of non-negative integers, find the maximum sum of a subset, such that no element is adjacent to the other.

Starting from the above description, we can see that:
1. This problem requires the max sum.
2. Original index of any two elements in the subset cannot be adjacent.

So, from the two observation, we have some further observations:
1. Order is not important. (because we need the sum)
2. For each element (say ith element) in the original array,  i-1 element cannot be included (neither does the i+1 th element).
3. Since all numbers are non-negative, the max sum before ith element (say S[i]), is max(S[i-2], S[i-3]).  
    Why not considering S[i-4] S[i-5]... but just the last 2 and last 3 elements?  
    Because S[i-2] = max(S[i-4], S[i-5]) + A[i-2], all numbers are >=0
    So S[i-2] >= S[i-5]
4. Therefore, we can write down the DP transition function:

S[i] = max(S[i-2], S[i-3]) + A[i]

The initialization of this problem is pretty straightforward, we use S[i] denote the max sum before A[i+1],  so S[1] = A[0], S[2] = A[1].    The final results is max(S[N], S[N-1]), N is the number of elements in A. 

Code (C++):

class Solution {

public:

int rob(vector<int>& nums) {

int len = nums.size();

if (len==0) return 0;

if (len == 1) return nums[0];

vector<int> s(len+1,0);

s[1] = nums[0];

s[2] = nums[1];

for (int i=3;i<=len;i++){

s[i] = max(s[i-2],s[i-3]) + nums[i-1];

}

return max(s[len-1],s[len]);

}

};

Code (Python):

class Solution:

# @param {integer[]} nums

# @return {integer}

def rob(self, nums):

n = len(nums)

if n==0:

return 0;

if n == 1:

return nums[0]

s = [0]*(n+1)

s[1] = nums[0]

s[2] = nums[1]

for i in range(3,n+1):

s[i] = (max(s[i-2],s[i-3]) + nums[i-1])

return max(s[n],s[n-1])

leetcode Questions: Reverse Bits

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Analysis:

This is a very basic bit manipulation problem.

Some experience about the basic bit operation (not the STL in C++):
1. mask is a very good tool
2. bit shifting operations (<<, >>) are very inportant
3. loop is usually enough
4. be careful with the data type.


In this problem, the first task is to get the binary bits from uint number n.
Let's say n = 43261596,  the binary format is: 00000010100101000001111010011100
In order to get the binary bits, mask is used here.
The idea of using mask to check 1 bit each time, using AND operation.

Mask moves 1 bit each time using << operation.
Mask can be computed and saved before to speed up the reverse function.

E.g.
iteration 1:  mask = 0000...00001,  then mask & n  = 0
iteration 2:  mask = 0000...00010, then mask & n  = 0
iteration 3:  mask = 0000...00100,  then mask & n  = 1
iteration 4:  mask = 0000...01000, then mask & n  = 1
...
iteration 32:  mask = 1000...00000, then mask & n  = 0

In this way, binary bits can be obtained from 32 iterations.
Reverse thus becomes pretty easy when using this looping.


The next step is to convert bits back into integer. Bit shift is all we need. "<< " shifts 1 bit left. (Remember if you shift left on an unsigned int by K bits, this is equivalent to multiplying by 2^K.)
In this problem, we check the original int from the lowest bit to highest, so the first bit in the original int is the highest bit in the result int. By shifting the final int 1 bit each time, the final int after 31 (32-1) times shifting, it becomes the reverse int of the original int.  32 is the length of the int data type in this problem.

Code(C++):

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        uint32_t mask = 1;
        for (int i=0;i<32;i++){
            if (n&mask) res = res + 1;
            if (i!=31) res <<= 1;
            mask <<= 1;
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        res = 0
        mask = 1
        for i in range(0,32):
            if n & mask:
                res += 1
            if i != 31:
                res <<= 1
            mask <<= 1
        return res
        

leetcode Question: Number of 1 Bits

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Analysis:

This is a very basic bit manipulation problem.
In order to count the number of 1 in the bit string, we can use a mask to check if the last bit is 1 or 0.
Cut the last bit (shift 1 bit right) and iterate this operation can achieve the final task.

mask = 1, binary of which is 0000...000001 (length meets with uint32)
shift operation:   >>1.

Note that << shifts left and adds 0s at the right end
>> shifts right and adds 0s at the left (when data is unsigned int)

Code(C++):

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res=0;
        while (n){
            if (n&1){
                res++;
            }
            n = n>>1;
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        res = 0
        while n:
            if n&1:
                res += 1
            n = n >> 1
        return res