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: Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

   bool isNumber(const char *s) {  
     int n = strlen(s);  
     int i = 0;  
     while(i<n && (s[i] == ' ' || s[i] == '\t'))i++;  
     if(i==n)return false;  
     int j = n-1;  
     while (j >= 0 && (s[j] == ' ' || s[j] == '\t'))j--;  
   
     s = s+i;  
     n = j-i+1;  
     if (n == 1)if(s[0] <='9' && s[0] >= '0')return true; else return false;  
   
     if (s[0] == '-' || s[0] == '+'){s++;n--;}  
     if (s[n-1] == '+' || s[n-1] == '-')return false;  
   
     bool res = true, dot = false, exp = false, number = false, sign = false;  
   
     for (i = 0; i < n; i++)  
     {  
       if(i==0 && (s[i] == '+' || s[i] == '-')){return false;}  
       else if ((s[i] == '+' || s[i] == '-') && s[i-1] != 'e') {return false;}  
       else if (s[i] == '+' || s[i] == '-')if(sign)return false; else sign = true;  
       else if(s[i] == '.'){  
         if (exp == true)return false;  
         if(dot == false)dot = true;  
         else return false;  
       }  
       else if (s[i] == 'e')  
       {  
         if (dot == true && number == false)return false;  
         if (i==0 || i== n-1 || exp == true)return false;  
         exp = true;  
       }  
       else if (s[i] < '0' || s[i] > '9'){return false;}  
       else number = true;  
     }  
   
     if(number == false)return false;  
   
     return res;  
   }  

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: Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

   int divide(int dividend, int divisor) {  
     long long x = abs((long long)divisor);  
     long long y = abs((long long)dividend);  
     long long res = 0, sum = x, negative = 0 , q = 1;  
   
     if (divisor < 0 && dividend < 0)negative = 0;  
     else if (divisor < 0 || dividend < 0)negative = 1;  
   
     if(x>y)return 0;  //y/x  
   
     while(sum)  
     {  
       if (sum << 1 <= y)  
       {  
         sum = sum<<1;  
         q = q<<1;  
       }  
       else  
       {  
         res += q;  
         if(y - sum < x) sum = 0;  
         else {  
           y = y - sum;  
           sum = x;  
           q = 1;  
         }  
       }  
     }  
     if(negative)  
       res = -res;  
   
     return (int)res;  
   }  

LeetCode: Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

   string longestPalindrome(string s) {  
     int n = s.length();  
     if(n<=1)return s;  
   
     int v[2][n];  
     int longest = 1, lindex = 0;  
   
     for (int i = 0; i < n; i++)v[1][i] = 1;  
   
     for (int i = 0; i < n-1; i++)  
       if(s[i] == s[i+1]){  
         lindex = i;  
         longest = 2;  
         v[0][i] = 1;  
       }  
       else v[0][i] = 0;  
   
     for ( int l = 3; l <= n; l++)  
     {  
       for (int i = 0; i+l-1 < n; i++)  
       {  
         int j = i+l-1;  
         if(v[l&1][i+1] && s[i] == s[j]){  
           lindex = i;  
           longest = l;  
           v[l&1][i] = 1;  
         }  
         else  
           v[l&1][i] = 0;  
       }  
     }  
   
     return s.substr(lindex, longest);  
   }  

LeetCode: ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

   #define tr(c,it) for(decltype((c).begin()) (it) = (c).begin(); (it) != (c).end(); (it)++)  
   
   string convert(string s, int nRows) {  
     int n = s.length();  
     vector<string> v(nRows);  
     int j = 0, increase = 1;  
     if(nRows == 1)return s;  
     for (int i = 0; i < n; i++)  
     {  
       if(increase)  
       {  
         v[j++] += s[i];  
         if(j == nRows){j -= 2;increase = 0;}  
       }  
       else  
       {  
         v[j--] += s[i];  
         if(j < 0){j += 2;increase = 1;}  
       }  
     }  
     string res;  
     tr(v, it)  
     {  
       res += *it;  
     }  
     return res;  
   }  

LeetCode: Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln;  
   
   ListNode *removeNthFromEnd(ListNode *head, int n) {  
     ln *dummy = new ln(0);  
     dummy->next = head;  
     ln *fast = dummy, *slow = dummy;  
     while(n--)  
     {  
       fast = fast->next;  
     }  
       
     while(fast->next)  
     {  
       fast = fast->next;  
       slow = slow->next;  
     }  
       
     slow->next = slow->next->next;  
       
     return dummy->next;  
   }  

LeetCode: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln;  
   
   ListNode *partition(ListNode *head, int x) {  
     ln *list1 = new ln(0);  
     ln *list2 = new ln(0);  
       
     ln *tmp = head, *newHead = NULL, *list2head = list2;  
     while(tmp)  
     {  
       if (tmp->val < x)  
       {  
         list1->next = tmp;  
         list1 = tmp;  
         if(!newHead) newHead = tmp;  
       }  
       else  
       {  
         list2->next = tmp;  
         list2 = tmp;  
       }  
       tmp = tmp->next;  
     }  
     if(!newHead) newHead = list2head->next;  
     list1->next = list2head->next;  
     list2->next = NULL;  
   
     return newHead;  
   }  

LeetCode: Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

   int lengthOfLongestSubstring(string s) {  
     int res = 0, start = 0;  
     int n = s.length();  
     vector<int> h(256, -1);  
   
     for (int i = 0; i < n; i++)  
     {  
       if (h[s[i]] != -1)  
       {  
         while(s[start] != s[i]){  
           h[s[start]] = -1;  
           start++;  
         }  
         start++;  
       }  
       else  
       {  
         if (res < i-start+1)res = i-start+1;  
         h[s[i]] = i;  
       }  
     }  
   
     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: Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
   typedef ListNode ln;  
   
   int count(ln *head)  
   {  
     int cnt = 0;  
     while(head){  
       head = head->next;  
       cnt++;  
     }  
     return cnt;  
   }  
   
   ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
     if(l1 == NULL && l2 == NULL)return NULL;  
     if(l1 == NULL)return l2;  
     if(l2 == NULL)return l1;  
   
     ln *head = NULL,*last;  
     int sum = 0, carry = 0;  
   
     while(l1 && l2)  
     {  
       sum = l1->val + l2->val + carry;  
       carry = sum/10;  
       sum = sum%10;  
       ln *n = new ln(sum);  
       if(!head){head = n; last = head;}  
       else  
       {  
         last->next = n;  
         last = n;  
       }  
   
       l1 = l1->next;  
       l2 = l2->next;  
     }  
   
     while(l1)  
     {  
       sum = l1->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l1 = l1->next;  
       last = last->next;  
     }  
   
     while(l2)  
     {  
       sum = l2->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l2 = l2->next;  
       last = last->next;  
     }  
   
     if (carry)last->next = new ln(carry);  
   
     return head;  
   }  

LeetCode: Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

   int reverse(int x) {  
     int sign = 1, res = 0;  
     if (x<0)sign = -1;  
     vector< int > v;  
     x=abs(x);  
   
     while(x)  
     {  
       v.push_back(x%10);  
       x = x/10;  
     }  
   
     for(decltype(v.begin()) it = v.begin(); it != v.end(); it++)  
     {  
       res = res*10 + (*it);  
     }  
   
     return (res*sign);  
   }  

LeetCode: String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

   int atoi(const char *str) {  
     if(!str)return 0;  
       
     int sign = 1, i = 0,prev;  
     long long res = 0;  
       
     while(str[i] == ' ' || str[i] == '\t')i++;  
       
     if(str[i] == '-'){sign = -1;i++;}  
     else if (str[i] == '+')i++;  
       
     while(str[i])  
     {  
       int x = str[i]-48;  
       if(x<0 || x>9 )return (res*sign);prev = res;  
       res = (res<<3) + (res<<1) + x;  
       if(res > 2147483647){if(sign == -1)return -2147483648; else return 2147483647;}   
       i++;  
     }  
     return ((int)res*sign);  
   }  

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: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

   string longestCommonPrefix(vector<string> &strs) {  
     int n = strs.size();  
     if (n == 0){string s; return s;}  
     if (n == 1){return strs[0];}  
     int length = 0;  
     int x = strs[0].length();  
     string res = strs[0];  
     for (int i = 1; i < n; i++)  
     {  
       int y = strs[i].length();  
       if(y < x)x = y;  
     }  
     bool success;  
     for (int i = 0; i < x; i++)  
     {  
       for (int j = 1; j<n; j++)  
       {  
         success = false;  
         if(strs[0][i] != strs[j][i])  
         {  
           break;  
         }  
         else  
           success = true;  
       }  
       if(success)length++;  
       else break;  
     }  
     return res.substr(0,length);  
   }  

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: Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

   typedef vector<string> vs;  
   
   void letterCombinationsUtil(string digits, vs &res, vs &list, int cur, int n, string &s)  
   {  
     if(cur == n)  
     {  
       res.push_back(s);  
       return;  
     }  
     string &str = list[digits[cur] - '0'];  
     int x = str.length();  
     for (int i = 0; i < x; i++)  
     {  
       s[cur] = str[i];  
       letterCombinationsUtil(digits, res, list, cur+1, n, s);  
     }  
   }  
   
   vector<string> letterCombinations(string digits) {  
     vector<string> list = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};   
     vector<string> res;  
     int n = digits.length();  
     if(n == 0){res.push_back("");return res;}  
     string s;  
     for (int i = 0; i <n; i++)s += '0';  
     letterCombinationsUtil(digits, res, list, 0, n, s);  
     return res;  
   }  

LeetCode: Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

   bool isValid(string s) {  
     stack<char> S;  
     int n = s.length();  
   
     for(int i = 0; i < n; i++)  
     {  
       if(s[i] == '(' || s[i] == '{' || s[i] == '[')S.push(s[i]);  
       else if (s[i] == ')' || s[i] == '}' || s[i] == ']')  
       {  
         if(S.empty())return false;  
         char t = S.top();  
         S.pop();  
         if((s[i] == ')' && t!= '(') ||  
           (s[i] == '}' && t!= '{') ||  
           (s[i] == ']' && t!= '[') )return false;  
       }  
     }  
     if(!S.empty())return false;  
     return true;  
   }  

LeetCode: Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

   void generateParenthesisRecurse(string &s, int x, int y, int n, vector<string> &v)  
   {  
     if(y>x)return;  
     if (x+y == n)  
     {  
       if(x==y)  
         v.push_back(s);  
       return;  
     }  
     s[x+y] = '(';  
     generateParenthesisRecurse(s, x+1, y, n, v);  
     s[x+y] = ')';  
     generateParenthesisRecurse(s, x, y+1, n, v);  
   }  
   
   vector<string> generateParenthesis(int n) {  
     vector<string> V;  
     string s;  
     for (int i = 0; i<n*2; i++)s+='(';  
     generateParenthesisRecurse(s, 0, 0, n*2, V);  
     return V;  
   }  

LeetCode: Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   
   #define tr(c,it) for(decltype((c).begin()) (it) = (c).begin(); (it) != (c).end(); (it)++)  
    
   typedef ListNode ln;   
   
   struct compare{  
     bool operator() (ListNode *a, ListNode *b) const  
     {  
       return (a->val > b->val);  
     }  
   };  
   
   ListNode *mergeKLists(vector<ListNode *> &lists) {  
     int n = lists.size();  
     if(n<1)return NULL;  
     vector<ListNode *> Cur;  
     ListNode *head = NULL, *last = NULL;  
     priority_queue<ListNode *,vector<ListNode *>, compare > pq;  
     tr(lists,it)  
     {  
       int i = it - lists.begin();  
       Cur.push_back(*it);  
       if(*it)  
         pq.push(*it);  
     }  
     while(!pq.empty())  
     {  
       ln *min = pq.top();  
       pq.pop();  
       if(!head)  
       {  
         head = min;  
         last = min;  
       }  
       else  
       {  
         last->next = min;  
         last = min;  
       }  
       if(last->next)  
         pq.push(last->next);  
     }  
     return head;  
   }  

LeetCode: Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   
   ListNode *swapPairs(ListNode *head) {  
     if(!head || !head->next)return head;  
     ListNode *nxt=head->next, *cur = head, *prev = NULL;  
     ListNode *res = head->next;  
     while(cur && nxt)  
     {  
       cur->next = nxt->next;  
       nxt->next = cur;  
       if(prev)  
         prev->next = nxt;  
       prev = cur;  
       cur = cur->next;  
         
       if(cur)nxt = cur->next;  
     }  
     return res;  
   }  

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: Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

   void ComputPrefix(char* pattern,int pre[], int n)  
   {  
     memset(pre, 0, n);  
     int len = 0;  
     pre[len] = 0;  
     int i = 1;  
     while(i<n)  
     {  
       if(pattern[i] == pattern[len])  
       {  
         len++;  
         pre[i]=len;  
         i++;  
       }  
       else  
       {  
         if(len>0)  
         {  
           len = pre[len-1];  
         }  
         else  
         {  
           pre[i] = 0;  
           i++;  
         }  
       }  
     }  
   }  

   char *KMP(char *haystack, char *needle)  
   {  
     int n = strlen(needle);  
     int m = strlen(haystack);  
     if(n==0)return haystack;  
     int *pre = new int[n];  
     ComputPrefix(needle, pre,n);  
     int i = 0, j = 0;  
     for (; i < m;)  
     {  
       if(haystack[i] == needle[j])  
       {  
         if(j == n-1)  
         {  
           return (&haystack[i-n+1]);  
         }  
         j++;  
         i++;  
       }  
       else  
       {  
         if(j > 0)  
           j = pre[j-1];  
         else  
         {  
           i++;  
         }  
       }  
     }  
     return NULL;  
   }  

   char *strStr(char *haystack, char *needle) {  
     return KMP(haystack,needle);  
   }  

LeetCode: Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

   string StringPrep(string s)  
   {  
     string res;  
     int d = s.length();  
     for(int i = 0; i<d;)  
     {  
       char c = s[i];  
       int j = i+1;  
       while(j<d && s[j] == s[i])j++;  
       res += j-i + '0';  
       res += s[i];  
       i += j-i;  
     }  
     return res;  
   }  

   string countAndSay(int n) {  
     string s = "1";  
     for (int i = 1; i <n; i++)  
     {  
       s = StringPrep(s);  
     }  
     return s;  
   }  

LeetCode: Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

   void reverse(string &s)  
   {  
     int i = 0, j = s.length()-1;  
     while(i<j)  
     {  
       swap(s[i],s[j]);  
       i++;  
       j--;  
     }  
   }  

   string add(string str1, string str2)  
   {  
     string s;  
     int n1 = str1.length(), n2 = str2.length();  
     int i =0, j =0, carry = 0;  
     while(i<n1 && j<n2)  
     {  
       int sum = (str1[i] - '0') + (str2[j] - '0') +carry;  
       s += sum%10 + '0';  
       carry = sum/10;  
       i++; j++;  
     }  
     while(i<n1)  
     {  
       int sum = (str1[i] - '0') +carry;  
       s += sum%10 + '0';  
       carry = sum/10;  
       i++;  
     }  
     while(j<n2)  
     {  
       int sum = (str2[j] - '0') +carry;  
       s += sum%10 + '0';  
       carry = sum/10;  
       j++;  
     }  
     if(carry)  
     {  
       s += carry + '0';  
     }  
     return s;  
   }  

   string multiply(string num1, string num2) {  
     string s, res="0";  
     int n1 = num1.length();  
     int n2 = num2.length();  
     int carry = 0;  
     reverse(num1);  
     reverse(num2);  
     for(int i = 0; i <n2; i++)  
     {  
       carry = 0;  
       s = "";  
       for (int k = 0; k<i; k++)s += '0';  
       for (int j = 0; j <n1; j++)  
       {  
         int m = (num2[i] - '0') * (num1[j] - '0') + carry;  
         s += m%10 + '0';  
         carry = m/10;  
       }  
       while(carry){  
         s += carry%10 + '0';  
         carry = carry/10;  
       }  
       res = add(res,s);  
     }  
     reverse(res);  
     int n = res.length()-1;  
     int i = 0;  
     while(i<n && res[i] == '0')i++;  
     res = res.substr(i);  
     return res;  
   }