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 […]

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 […]

Sort List Sort a linked list in O(n log n) time using constant space complexity. tag: list, sort 9/22/2015 update a cleaner solution /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class […]

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 […]

Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 tag: tree, […]

Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings. tag: string 好久没一遍AC了。 直接暴力搜就好。 遍历整个字符串数组，每次查看位于n位置的字符是否相等，如果有一个不等则返回，如果全相等则n++。 class Solution { public: string longestCommonPrefix(vector<string> &strs) { int n = 0; bool isFinish = false; if(strs.empty()){ return string(“”); } while(!isFinish){ char c; if(strs[0].size() == n){ isFinish […]

Roman to Integer Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. tag: math, string 9/28/2015 update class Solution { public: unordered_map<char, int> map; int romanToInt(string s) { map[‘I’] = 1; map[‘V’] = 5; map[‘X’] = 10; map[‘L’] […]

Integer to Roman Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. tag: string, math 9/28/2015 update class Solution { public: vector<string> roman = {“M”, “CM”, “D”, “CD”,”C”,”XC”,”L”,”XL” ,”X”,”IX”,”V”,”IV”,”I”}; vector<int> value = {1000, 900, 500, 400, 100, 90, […]

Container With Most Water Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a […]