LeetCode: Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
   typedef vector<vector<bool> > vvb;  
   typedef vector<vector<char> > vvc;  
   
   bool backtrack(vvc &board, string &word, int i, int j, int x, int n, int row, int col, vvb &visited)  
   {  
     if(x == n && word[x] == board[i][j])return true;  
     if (word[x] != board[i][j]) return false;  
       
     bool left = false, right = false, up = false, down = false;  
     visited[i][j] = true;  
     if (j > 0 && visited[i][j-1] == false){  
       left = backtrack(board, word, i, j-1, x+1, n, row, col, visited);  
       if (left) return true;  
     }  
   
     if (j < col && visited[i][j+1] == false){  
       right = backtrack(board, word, i, j+1, x+1, n, row, col, visited);  
       if (right) return true;  
     }  
   
     if (i > 0 && visited[i-1][j] == false){  
       up = backtrack(board, word, i-1, j, x+1, n, row, col, visited);  
       if (up) return true;  
     }  
       
     if (i < row && visited[i+1][j] == false){  
       down = backtrack(board, word, i+1, j, x+1, n, row, col, visited);  
       if (down) return true;  
     }  
     visited[i][j] = false;  
     return false;  
   }  
   
   bool exist(vector<vector<char> > &board, string word) {  
     int n = word.length();  
     if(!n)return false;  
     int row = board.size();  
     if(!row) return false;  
     int col = board[0].size();  
     if(row*col < n)return false;  
   
     vvb visited(row, vector<bool>(col, false));   
     for (int i = 0; i < row; i++)  
     {  
       for(int j = 0; j < col; j++)  
       {  
         if(board[i][j] == word[0] && backtrack(board, word, i , j, 0,n-1, row-1, col-1, visited))return true;  
       }  
     }  
     return false;  
   } 

LeetCode: Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

 /**  
  * Definition for an interval.  
  * struct Interval {  
  *   int start;  
  *   int end;  
  *   Interval() : start(0), end(0) {}  
  *   Interval(int s, int e) : start(s), end(e) {}  
  * };  
  */  
   
   static bool compare(Interval x, Interval y)  
   {  
     return (x.start < y.start);  
   }  
   
   vector<Interval> merge(vector<Interval> &intervals) {  
     sort(intervals.begin(), intervals.end(), compare);  
   
     int n = intervals.size();  
     vector<Interval> res;  
   
     for (int i = 0; i< n; i++)  
     {  
       int j = i;  
       int greatest = intervals[i].end;  
       while (j<n-1 && intervals[j+1].start <= greatest){  
         j++;  
         if(intervals[j].end > greatest)greatest = intervals[j].end;  
       }  
       if(j == i)  
       {  
         res.push_back(intervals[i]);  
       }  
       else  
       {  
         Interval x(intervals[i].start, greatest);  
         res.push_back(x);  
         i = j;  
       }  
     }  
     return res;  
   }  

LeetCode: Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

   int maxProfit(vector<int> &prices) {  
     int n = prices.size();  
     if(n == 0)return 0;  
     vector<int> smallest(n, 0);  
     smallest[0] = INT_MAX;  
     int min = prices[0], profit = 0;  
       
     for (int i = 1; i <n; i++)  
     {  
       int t = prices[i];  
       smallest[i] = min;  
       if(prices[i] < min) min = prices[i];  
     }  
       
     for(int i = 1; i < n; i++)  
     {  
       int diff = prices[i] - smallest[i];   
       if(profit < diff) profit = diff;  
     }  
       
     return profit;  
   }  

LeetCode: Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

   typedef pair<int, int> ii;  
   
   bool compare(ii a, ii b)  
   {  
     return (a.second < b.second);  
   }  
   
   vector<int> twoSum(vector<int> &numbers, int target) {  
     int l = numbers.size();  
     vector < ii > num(l);  
     for(int i = 0;i<l; i++)  
     {  
       num[i].first = i;  
       num[i].second = numbers[i];  
     }  
       
     sort(num.begin(),num.end(),compare);  
     vector <int> v;  
     int i = 0, j = numbers.size()-1;  
     while(i<j)  
     {  
       int sum = num[i].second+num[j].second;  
       if(sum == target)  
       {  
         int small,big;  
         small = min(num[i].first, num[j].first);  
         big = max(num[i].first, num[j].first);  
         v.push_back(small+1);  
         v.push_back(big+1);  
         break;  
       }  
       else if(sum < target)i++;  
       else j--;  
     }  
     return v;  
   }  

LeetCode: Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

   bool isPalindrome(int x) {  
     int d = 0;  
     int n = x;  
     if(x<0)return false;  
     while(n)  
     {  
       d++;  
       n=n/10;  
     }  
     int i = d-1, j = 0;  
     while(i>j)  
     {  
       int pi = pow(10,i), pj = pow(10,j), pk = pow(10,j+1);  
       if(x/pi != (x%pk)/pj)return false;  
       x = x%pi;  
       i--;j++;  
     }  
     return true;  
   }  

LeetCode: 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

   typedef vector<vector<int> > vvi;  
   typedef vector<int> vi;  
   
   #define tr(v, i) for(decltype((v).begin()) (i) = (v).begin(); (i) != (v).end(); (i)++)  
   
   vector<vector<int> > threeSum(vector<int> &num) {  
     set< vector<int> > S;  
     vvi V;  
   
     sort(num.begin(),num.end());  
   
     int n = num.size();  
   
     int i, j,k,sum;  
     for (k = 0; k<n-2; k++)  
     {  
       i = k+1; j = n-1;  
       while(j > i)  
       {  
         sum = num[i]+num[j]+num[k];  
         if(sum == 0)  
         {  
           vi v;  
           v.push_back(num[k]);  
           v.push_back(num[i]);  
           v.push_back(num[j]);  
           S.insert(v);  
           i++;  
           j--;  
         }  
         else if (sum > 0)  
         {  
           j--;  
         }  
         else i++;  
       }  
     }  
   
     tr (S,it)  
     {  
       V.push_back(*it);  
     }  
   
     return V;  
   
   }  

LeetCode: 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

   typedef vector< vector<int> > vvi;  
   typedef vector< int > vi;  
   
   #define tr(v, it) for(decltype((v).begin()) (it) = (v).begin(); (it) != (v).end(); (it)++)   
   
   vector<vector<int> > fourSum(vector<int> &num, int target) {  
     set < vector<int> > S;  
     vvi V;  
     sort(num.begin(),num.end());  
       
     int n = num.size();  
       
     for (int i = 0; i < n-3; i++)  
     {  
       for (int j = i+1; j <n-2; j++)  
       {  
         int k = j+1, l = n-1;  
         while(k<l)  
         {  
           int sum = num[i]+num[j]+num[k]+num[l];  
           if(sum == target)  
           {  
             vi v;  
             v.push_back(num[i]);  
             v.push_back(num[j]);  
             v.push_back(num[k]);  
             v.push_back(num[l]);  
             S.insert(v);  
             k++;  
             l--;  
           }  
           else if (sum<target)k++;  
           else l--;  
         }  
       }  
     }  
     tr(S,it)  
     {  
       V.push_back(*it);  
     }  
     return V;  
   }  

LeetCode: Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

   int removeDuplicates(int A[], int n) {  
     int i=0, j = 0;  
     while(j<n)  
     {  
       A[i++] = A[j];  
       int k = j+1;  
       while(k<n && A[k] == A[j])k++;  
       j = k;  
     }  
     return i;  
   }  

LeetCode: Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

   int removeElement(int A[], int n, int elem) {  
     int i = 0, j = n;  
     int cnt = n;  
     while(i<j)  
     {  
       if(A[i] == elem)  
       {  
         j--;cnt--;  
         swap(A[i], A[j]);  
       }  
       else i++;  
     }  
     return cnt;  
   }  

LeetCode: Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

   typedef vector< int > vi;  
   typedef vector< vector<int> > vvi;  

   #define tr(c,it) for(decltype((c).begin()) (it) = (c).begin(); (it) != (c).end(); (it)++)  

   static bool vviCompare(vi a, vi b)  
   {  
     return (a.size()<b.size());  
   }  

   static bool viCompare(int a, int b)  
   {  
     return (a<b);  
   }  

   vector<vector<int> > subsets(vector<int> &S) {  
     vvi res;  
     int n = S.size();  
     int total = 1<<n;  
     for(int i = 0; i <total; i++)  
     {  
       vi v;  
       for (int j = 0; j<31; j++)  
       {  
         if(i & 1<<j)  
         {  
           v.push_back(S[j]);  
         }  
       }  
       res.push_back(v);  
     }  
     std::sort(res.begin(), res.end(), vviCompare);  
     tr(res, it)  
     {  
       std::sort((*it).begin(),(*it).end(), viCompare);  
     }  
     return res;  
   }  

LeetCode: Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

   int removeDuplicates(int A[], int n) {  
     int i = 0, j = 0;  
     while(j<n)  
     {  
       A[i++] = A[j++];  
       if(j<n && A[j] == A[j-1])A[i++] = A[j++];  
       while(j<n && A[j] == A[j-1])j++;  
     }  
     return i;  
   }  

LeetCode: Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.

   void merge(int A[], int m, int B[], int n) {  
     int j = m+n-1, i = m-1,k;  
     if(n <= 0)return;  
     if(m<=0)  
     {  
       int k = 0;  
       while(k<n)  
       {  
         A[k] = B[k];  
         k++;  
       }  
       return;  
     }  
     while(i>=0)  
     {  
       A[j] = A[i];  
       i--;  
       j--;  
     }  
     i = j+1; j = 0, k = 0;  
     while(i<m+n && j<n)  
     {  
       if(A[i] <= B[j])  
       {  
         A[k++] = A[i++];  
       }  
       else A[k++] = B[j++];  
     }  
     while(j<n)  
     {  
       A[k++] = B[j++];  
     }  
   }  

LeetCode: Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

   #define tr(v, it) for(decltype((v).begin()) (it) = (v).begin(); (it) != (v).end(); (it)++)  

   typedef vector<vector<int> > vvi;  

   vector<vector<int> > subsetsWithDup(vector<int> &S) {  
     set< vector<int> > res;  
     vvi V;  
     int n = S.size();  
     if(n == 0)return V;  
     sort(S.begin(), S.end());  
     for (int i = 0; i < pow(2,n); i++)  
     {  
       vector<int> v;  
       for (int j = 0; j <32; j++)  
       {  
         if(i & (1<<j))v.push_back(S[j]);  
       }  
       res.insert(v);  
     }  
     tr(res, it)  
       V.push_back(*it);  
     return V;  
   }  

LeetCode: Pascal Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

    #define tr(v,it) for(decltype((v).begin()) it = (v).begin(); it != (v).end(); it++)


    vector<vector<int> > generate(int numRows) {  
     vector<vector<int> > v;  
     if (numRows<=0)return v;  
     v.push_back(vector<int> (1,1));  
     int i = 1;  
     while(i<numRows)  
     {  
       vector<int> x;  
       x.push_back(1);  
       int n = v[i-1].size();  
       tr(v[i-1], it)  
       {  
         int index = it - v[i-1].begin();  
         if(index < n-1){  
           x.push_back(*it + *(it+1));  
         }  
       }  
       x.push_back(1);  
       v.push_back(x);  
       i++;  
     }  
     return v;  
   }  

LeetCode: Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

   typedef vector<vector<int> > vvi;  
   typedef vector<int> vi;  
   #define INT_MAX 0x7FFFFFFF

  
   int minimumTotal(vector<vector<int> > &triangle) {  
     int n = triangle.size();  
     if(n==1)return triangle[0][0];  
     vi v(n,0);  
     for (int i = 0; i <n; i++)  
     {  
       v[i] = triangle[n-1][i];  
     }  
     for (int i = n-2; i>=0; i--)  
     {  
       for(int j = 0; j <= i; j++)  
       {  
         v[j] = triangle[i][j] + min(v[j], v[j+1]);  
       }  
     }  
     return v[0];  
   }  

LeetCode: Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

   struct node
   {
     int cost;
     string s;
   };

   struct mycompare{
     bool operator()(node &a, node &b) const
     {
        return (a.cost > b.cost);
     }
   };
   #define INT_MAX 0x7FFFFFFF

   bool canTrans(string a, string b){  
     int dif = 0;  
     for (int i = 0; i < a.length(); i++){  
       if (a[i] != b[i]){  
         dif++;  
         if (dif >= 2){  
           return false;  
         }  
       }  
     }  
     return true;  
   }



   int ladderLength(string start, string end, unordered_set<string> &dict) {  
     queue<string> wq;  
     queue<int> lq;  
     wq.push(start);  
     lq.push(1);  
     while (!wq.empty()){  
       string word(wq.front());  
       wq.pop();  
       int lev = lq.front();  
       lq.pop();  
       for (int i = 0; i < word.length(); i++){  
         char temp = word[i];  
         for (char c = 'a'; c <= 'z'; c++){  
           word[i] = c;  
           if (word == end){  
             return lev + 1;  
           }  
           if (dict.find(word) != dict.end()){  
             wq.push(word);  
             lq.push(lev + 1);  
             dict.erase(word);  
           }  
           word[i] = temp;  
         }  
       }  
     }  
     return 0;  
   }  

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.

  #define tr(c,it) for(decltype((c).begin()) (it) = (c).begin(); (it) != (c).end(); (it)++)


   int longestConsecutive(vector<int> &num) {  
     int res = 1,local = 1;  
     int n = num.size();  
     if(n==0)return 0;  
     sort(num.begin(),num.end());  
     set<int> s;  
     tr(num, it)  
     {  
       s.insert(*it);  
     }  
     num.clear();  
     n = 0;  
     tr(s, it)  
     {  
       num.push_back(*it);  
       n++;  
     }  
     for (int i = 1; i < n; i++)  
     {  
       if(num[i] == num[i-1]+1)  
       {  
         local++;  
         if(local > res)res = local;  
       }  
       else  
         local = 1;  
     }  
     return res;  
   }