Friday, September 19, 2014

[Leetcode] Longest Consecutive Sequence

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.
Your algorithm should run in O(n) complexity.
Analysis:
  1. Take [100, 4, 200, 1, 3, 2] as an example 
  2. First, for 100, we look for 101, 102 ... and 99, 98... in the array. If the number exist, add count and mark it as visited
  3. Next, if next number (4) was not visited, do the same as step 2
  4. Loop until end of the array




class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        map<int, bool> m;
        for(int i=0; i<num.size(); i++)
        {
            m[num[i]] = false;
        }
        
        int maxCount = 0;
        for(int i=0; i<num.size(); i++)
        {
            //the num was not visited
            if (m.find(num[i]) != m.end() && !m[num[i]])
            {
                int n = num[i]-1;
                int count = 1;
                while(m.find(n) != m.end() && !m[n])
                {
                    m[n] = true;
                    n--;
                    count++;
                }
                
                n = num[i] + 1;
                while(m.find(n) != m.end() && !m[n])
                {
                    m[n] = true;
                    n++;
                    count++;
                }
                
                maxCount = max(maxCount, count);
            }
        }
        
        return maxCount;
    }
};

[Leetcode] Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Analysis:
  •  DFS find all 'O' not surrounded by 'X' (at or connected to the edge of the board ) and changed to '#'
  •  Flip the remain 'O' into X
  •  Flip the '#' back to 'O'


class Solution {
public:

 void flipRegion(vector<vector<char>> &board, int i, int j)
 {
  if (board[i][j] == 'O')
  {
   board[i][j] = '#';
   if (i < board.size() - 1 && board[i+1][j] == 'O')
    flipRegion(board, i + 1, j);
   if (j < board[0].size() - 1 && board[i][j+1] == 'O')
    flipRegion(board, i, j + 1);
   if (i > 0 && board[i-1][j] == 'O')
    flipRegion(board, i - 1, j);
   //why should be 1 rather than 0 here? 
   if (j > 1 && board[i][j-1] == 'O')
    flipRegion(board, i, j - 1);
  }
 }


    void solve(vector<vector<char>> &board) {
        
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[i].size(); j++)
            {
                //if it is at the edge of the board
                if ((i == 0 || i == board.size()-1 || j == 0 || j == board[i].size() - 1)
                && (board[i][j] == 'O'))
                {
                    //board[i][j] = '#';
                    flipRegion(board, i, j);
                }
                    
            }
        }

        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[i].size(); j++)
            {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == '#')
                    board[i][j] = 'O';    
            }
        }
        
    }
};

[Leetcode] Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Analysis:
思路1:
顺序遍历,如果rating递增,则candy数量加一;否则等与1(注意,这个1可能不准确,所以我们需要逆序遍历)
逆序遍历,同顺序。和顺序的candy数比较,取较大的一个数。


思路2:
找到rating的谷底ratings[i-1] <= ratings[i] <= rating[i+1],谷底的candy数量必为1.然后设定谷底左右的candy数(分别+1)
使用两个dummy rating来处理第一个和最后一个rating的情况



class Solution {
public:
    int candy(vector<int> &ratings) {
        vector<int> candys(ratings.size(), 1);
        
        for(int i=1; i<ratings.size(); i++)
        {
            if (ratings[i] > ratings[i-1])
                candys[i] = candys[i-1] + 1;
        }
        
        for(int i=ratings.size() - 2; i>=0; i--)
        {
            if (ratings[i] > ratings[i+1])
            {
                candys[i] = max(candys[i], candys[i+1] + 1);
            }
        }
        
        int total = 0;
        for(int i=0; i<candys.size(); i++)
        {
            total += candys[i];
        }
        
        return total;
    }
};

[Leetcode] Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
Analysis:
  • example: gas: [1,2,3,4,5], cost [3,4,5,1,2]
  • Diff is [-2,-2,-2, 3, 3]
  • Diff accumulation from right to left is [0,2,4,6,3] and should choose the idx with max diff is the station to start
  • The accumulation is the remaining gas at station 5 when travel beginning from station i ( 1 <= i <= 5)
  • We should choose the idx with the max value as the start station.



class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        vector<int> diffs;
        for(int i=0; i<gas.size(); i++)
            diffs.push_back(gas[i] - cost[i]);
            
        int remainGas = 0;
        int idx = -1;
        int maxRemainGas = -1;
        for(int i = diffs.size() - 1; i >=0; i--)
        {
           remainGas += diffs[i];
           if (remainGas > maxRemainGas)
           {
               idx = i;
               maxRemainGas = remainGas;
           }
        }
        
        if (remainGas >= 0)
            return idx;
        else
            return -1;
    }
};

[Leetcode] Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Analysis:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL)
            return NULL;
            
        //use BFS to visit all nodes
        queue<UndirectedGraphNode*> q;
        //use hash table to marked as visited
        map<UndirectedGraphNode*, UndirectedGraphNode*> m;
        m[node] = new UndirectedGraphNode(node->label);
        q.push(node);
        while(!q.empty())
        {
            UndirectedGraphNode* t = q.front();
            q.pop();
            for(int i=0; i<t->neighbors.size(); i++)
            {
                UndirectedGraphNode* n = t->neighbors[i];
                //if not visited before, added to the hash table and queue
                if (m.find(n) == m.end())
                {
                    m[n] = new UndirectedGraphNode(n->label);
                    q.push(n);
                }
                
                m[t]->neighbors.push_back(m[n]);
            }
        }
        
        return m[node];
    }
};

[Leetcode] Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?



class Solution {
public:
    int singleNumber(int A[], int n) {
        int ret = A[0];
        for(int i=1; i<n; i++)
        {
            ret = ret ^ A[i];
        }
        return ret;
    }
};

[Leetcode] Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Analysis:
Count the numbers of each bit for all integers and the bit which is not times of 3 is the bit of the integer appears once.


class Solution {
public:
    int singleNumber(int A[], int n) {
        vector<int> nums(32,0);
        for(int i=0; i<n; i++)
        {
            int num = A[i];
            for(int j=0; j<32;j++)
            {
                nums[j] += (num >> j) & 0x1;
            }
        }
        
        int ret = 0;
        for(int i=0; i<32;i++)
        {
            if (nums[i] % 3)
                ret = ret | (0x1 << i);
        }       
        
        return ret;
    }
};