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) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (n <= 0) return head;
        
        ListNode Dummy(0);
        Dummy.next = head;
        
        ListNode *slower = &Dummy, *faster = &Dummy;
        
        while (n > 0)
        {
            faster = faster->next;
            --n;
        }
        
        while (faster->next)
        {
            faster = faster->next;
            slower = slower->next;
        }
        
        ListNode *del = slower->next;
        slower->next = slower->next->next;
        delete del;
        del = NULL;
        
        return Dummy.next;
    }
};

3Sum Closest

/*
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

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

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
*/

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (num.size() < 3) return INT_MIN;
         
        sort(num.begin(), num.end()); //nlogn
        
        int res = num[0] + num[1] + num[2]; //give an arbitrary sum to init.
        
        int prev = INT_MAX;
        
        for (int i = 0; i < num.size(); ++i) //n
        {
            int first = num[i];
             
            if (prev != INT_MAX && first == prev) continue;
             
            prev = first;
             
            int p1 = i + 1, p2 = num.size() - 1;
            
            while (p1 < p2) //n
            {
                int sum = num[p1] + num[p2] + first;
                
                if (sum > target)
                {
                    if (abs(sum - target) < abs(target - res)) res = sum;
                    int prev = num[p2];
                    while (num[p2] == prev) p2--; //avoid duplicate
                }
                else if (sum < target)
                {
                    if (abs(sum - target) < abs(target - res)) res = sum;
                    int prev = num[p1];
                    while (num[p1] == prev) p1++;
                }
                else
                {
                    return target;
                }
            }
        }
        return res;
    }
};

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)
*/

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vector<vector<int> > res;
        
        if (num.size() < 3) return res;
        
        sort(num.begin(), num.end()); //nlogn
        
        if (num.back() < 0 || num.front() > 0) return res;
        
        int prev = INT_MAX;
        for (int i = 0; i < num.size(); ++i) //n
        {
            int first = num[i];
            
            if (first == prev) continue;
            
            if (first > 0) break;
            
            prev = first;
            
            int p1 = i + 1, p2 = num.size() - 1;
            while (p1 < p2) //n
            {
                if (num[p1] + num[p2] > -first)
                {
                    int prev = num[p2];
                    while (num[p2] == prev) p2--; //avoid duplicate
                }
                else if (num[p1] + num[p2] < -first)
                {
                    int prev = num[p1];
                    while (num[p1] == prev) p1++;
                }
                else
                {
                    res.push_back(vector<int>{first, num[p1], num[p2]});
                    
                    int prev1 = num[p2];
                    while (num[p2] == prev1) p2--; //avoid duplicate
                    int prev2 = num[p1];
                    while (num[p1] == prev2) p1++;
                }
            }
        }
        return res;
    }
};

Integer to Roman

class Solution {
public:
    string intToRoman(int num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        
        string res;
        
        if (num < 1) return res;
        
        vector<int>  divider = {1, 5, 10, 50, 100, 500, 1000};
        vector<char> chars = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
        
        while (num != 0)
        {
            int i = num / divider.back();
            num = num % divider.back();
            
            if (i == 4)
            {
                 if (divider.back() == 100) res += "CD";
                 if (divider.back() == 10)  res += "XL";
                 if (divider.back() == 1)   res += "IV";
            }
            else
            {
                for (int t = 0; t < i; ++t)
                {
                    res += chars.back();
                }
            }
            
            if (divider.back() == 1000 && num >= 900)
            {
                res += "CM";
                num = num - 900;
            }
            if (divider.back() == 100 && num >= 90)
            {
                res += "XC";
                num = num - 90;
            }
            if (divider.back() == 10 && num >= 9)
            {
                res += "IX";
                num = num - 9;
            }
            divider.pop_back();
            chars.pop_back();
        }
        return res;
    }
};

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".
*/

class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        
    	if (nRows < 2) return s;
		
		int k = 2 * nRows - 2;
		
		int groups = s.size() / k;
		int last = s.size() % k;
		
		string res;
		for (int i = 0; i < nRows; ++i)
		{
			for (int j = 0; j < groups; ++j)
			{
				if (i == 0 || i == nRows - 1)
				{
					res += s[k * j + i];
				}
				else
				{
					res += s[k * j + i];
					res += s[k * j + k - i];
				}
			}
			if ((i == 0 && last >= 1) || (i == nRows - 1 && last >= nRows))
			{
				res += s[k * groups + i];
			}
			else
			{
				if (last > k - i)
				{
					res += s[k * groups + i];
					res += s[k * groups + k - i];
				}
				else if (last > i)
				{
					res += s[k * groups + i];
				}
			}
		}
		return res;
    }
};

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.
*/

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    	string res;
    	int d = s.size();
    	if (d == 0) return res;
        
		int starting = 0, longest = 0;		
		vector<vector<int> > DP(d, vector<int>());
        
		for (int i = 0; i < DP.size(); ++i)
        {
            DP[i].resize(d - i);
        }
		//base case
		for (int i = 0; i < d; ++i)
		{
			DP[i][0] = 1;
            if (i < d - 1) 
            {
                DP[i][1] = (s[i] == s[i + 1]) ? 2 : 1;
                if (DP[i][1] > longest) longest = DP[i][1], starting = i;
            }
            
		}
		
		for (int j = 2; j < d; ++j)
			for (int i = 0; i < d - j; ++i)
				{
					DP[i][j] = max(max((s[i] == s[i + j]) ? (2 + DP[i + 1][j - 2]) : DP[i + 1][j - 2], DP[i][j - 1]), DP[i + 1][j - 1]);
					if (DP[i][j] > longest) longest = DP[i][j], starting = i;
				b}
		
		return s.substr(starting, DP[0][d - 1]);
    }
};

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) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    	int carry = 0;
		
		ListNode Dummy(0);
		ListNode *prev = &Dummy;
		ListNode *head = Dummy.next;
		
		while (l1 || l2)
		{
            int val1 = 0, val2 = 0;
            
            if (l1)
            {
                val1 = l1->val;
                l1 = l1->next;
            }
            if (l2)
            {
                val2 = l2->val;
                l2 = l2->next;
            }
            
			head = new ListNode(0);
			
            head->val = val1 + val2 + carry;
			carry = (head->val) / 10;
			head->val = (head->val) % 10;
			
			prev->next = head;
			prev = head;
		}
		
		if (carry)
		{
			prev->next = new ListNode(carry);
		}
		
		return Dummy.next;
    }
};

added 9/9/2013

class Solution {
public:
    int carry;
    
    ListNode* helper(ListNode *l1, ListNode *l2, int carry)
    {
        if (not l1 && not l2) 
            return (carry) ? new ListNode(carry) : NULL;
        
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        ListNode* root = new ListNode(sum % 10);
        
        root->next = helper(l1 ? l1->next : NULL, l2 ? l2->next : NULL, sum / 10);
        return root;
    }
    
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return helper(l1, l2, 0);
    }
};

Multiply Strings

class Solution {
public:
    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        //compute progressively
        int s1 = num1.size();
        int s2 = num2.size();
        
        if (not s1 || not s2) return string();
        
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        if ((num1.back() - '0') * (num2.back() - '0') == 0) return string(1, '0');
        
        int carry = 0;
        int sum;
        string res(s1 + s2, '0');
        
        bool pop = true;
        for (int i = 0; i < s1; ++i)
        {
            for (int j = 0; j < s2; ++j)
            {
                sum = res[i + j] - '0' + (num1[i] - '0') * (num2[j] - '0') + carry;
                carry = sum / 10;
                res[i + j] = sum % 10 + '0';
            }
            if (carry)
            {
                if (i == s1 - 1) pop = false;
                res[s2 + i] = res[s2 + i] + carry;
                carry = 0;
            }
        }
        
        if (pop) res.pop_back();
        reverse(res.begin(), res.end());
        return res;
    }
};

Maximum Subarray

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (not A || n < 1) return 0;
        
        int res = INT_MIN, cur = 0;
        
        //assume if all negative then the maximum is zero (select nothing)
        for (int i = 0; i < n; ++i)
        {
            cur = cur + A[i];
            
            if (cur > res) res = cur;
            
            if (cur < 0) cur = 0;
        }
        
        return res;
    }
};

Jump Game

/*
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.
*/

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>
#include <climits>
#include <deque>

using namespace std;

/*
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.
*/

/*
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
*/


/*
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
*/
 
/*
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
 
For example,
Given n = 3,
 
You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]
*/
 
/*
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
 
You may assume that the intervals were initially sorted according to their start times.
 
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
 
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
*/
 
 
 
/*
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:
    bool canJump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        //greedy, only take the maximum
        
        if (not A || n <= 0) return false;
        if (n == 1) return true;
        
        int maxRight = 0;
        
        for (int i = 0; i <= maxRight; ++i)
        {
            if (i + A[i] > maxRight) maxRight = i + A[i];
            if (maxRight >= n - 1) return true;
        }
        return false;
    }
};
 
int main()
{
   Solution sol;
   int input[5] = {3,2,1,1,4};
   cout <<  sol.canJump(input, 5) << endl;
   return 0;
}