所有总结题目 http://www.jianshu.com/p/55b90cfcb406
这里总结了频率5的题目：
1. 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
分析
方法1：暴力，复杂度O(n^2)O(n2)，会超时
方法2：hash。用一个哈希表，存储每个数对应的下标，复杂度O(n).
方法3：先排序，然后左右夹逼，排序O(n\log n)O(nlogn)，左右夹逼O(n)，最终O(n\log n)O(nlogn)。但是注意，这题需要返回的是下标，而不是数字本身，因此这个方法行不通。
// Two Sum
// 方法2：hash。用一个哈希表，存储每个数对应的下标
// Time Complexity: O(n)，Space Complexity: O(n)
class Solution {
public:
vector twoSum(vector &nums, int target) {
unordered_mapmy_map;
vector result;
for (int i = 0; i < nums.size(); i++) {
my_map[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++) {
auto iter = my_map.find(target-nums[i]);
if (iter != my_map.end() && iter->second > i) {
result.push_back(i + 1);
result.push_back(iter->second + 1); break;
}
}
return result;
}
};
8. 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.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
分析
细节题。注意几个测试用例：
• 不规则输入，但是有效，"-3924x8fc"， " + 413",
• 无效格式，" ++c", " ++1"
• 溢出数据，"2147483648"
代码
// String to Integer (atoi)
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
int myAtoi(const string &str) {
int num = 0;
int sign = 1;
const int n = str.length();
if (n == 0) return 0;
int i = 0;
while (str[i] == ' ' && i < n) i++;
if (str[i] == '+') {
i++;
} else if (str[i] == '-') {
sign = -1;
i++;
}
for (; i < n; i++) {
if (str[i] < '0' || str[i] > '9')
break;
if (num > INT_MAX / 10 ||
(num == INT_MAX / 10 &&
(str[i] - '0') > INT_MAX % 10)) {
return sign == -1 ? INT_MIN : INT_MAX;
}
num = num * 10 + str[i] - '0';
}
return num * sign;
}
};
20. 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.
分析
无
代码
// Valid Parentheses
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
bool isValid (string const& s) {
string left = "([{";
string right = ")]}";
stack<char> stk;
for (auto c : s) {
if (left.find(c) != string::npos) {
stk.push (c);
} else {
if (stk.empty () || stk.top () != left[right.find(c)])
return false;
else
stk.pop ();
}
}
return stk.empty();
}
};
15. 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 \leq b \leq ca≤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)
分析
先排序，然后左右夹逼，复杂度 O(n^2)O(n2)。
这个方法可以推广到k-sum，先排序，然后做k-2次循环，在最内层循环左右夹逼，时间复杂度是 O(\max\{n \log n, n^{k-1}\})O(max{nlogn,nk−1})。
代码
// 3Sum
// 先排序，然后左右夹逼，注意跳过重复的数
// Time Complexity: O(n^2)，Space Complexity: O(1)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if (nums.size() < 3) return result;
sort(nums.begin(), nums.end());
const int target = 0;
auto last = nums.end();
for (auto i = nums.begin(); i < last-2; ++i) {
if (i > nums.begin() && *i == *(i-1)) continue;
auto j = i+1;
auto k = last-1;
while (j < k) {
if (*i + *j + *k < target) {
++j;
while(*j == *(j - 1) && j < k) ++j;
} else if (*i + *j + *k > target) {
--k;
while(*k == *(k + 1) && j < k) --k;
} else {
result.push_back({ *i, *j, *k });
++j;
--k;
while(*j == *(j - 1) && j < k) ++j;
while(*k == *(k + 1) && j < k) --k;
}
}
}
return result;
}
};
21. Merge Two Sorted Lists
描述
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.
分析
无
代码
// Merge Two Sorted Lists
// 时间复杂度O(min(m,n))，空间复杂度O(1)
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
ListNode dummy(-1);
ListNode *p = &dummy;
for (; l1 != nullptr && l2 != nullptr; p = p->next) {
if (l1->val > l2->val) { p->next = l2; l2 = l2->next; }
else { p->next = l1; l1 = l1->next; }
}
p->next = l1 != nullptr ? l1 : l2;
return dummy.next;
}
};
28. Implement strStr()
描述
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
分析
暴力算法的复杂度是 O(m*n)，代码如下。更高效的的算法有KMP算法、Boyer-Mooer算法和Rabin-Karp算法。面试中暴力算法足够了，一定要写得没有BUG。
暴力匹配
// Implement strStr()// 暴力解法，时间复杂度O(N*M)，空间复杂度O(1)
class Solution {
public:
int strStr(const string& haystack, const string& needle) {
if (needle.empty()) return 0;
const int N = haystack.size() - needle.size() + 1;
for (int i = 0; i < N; i++) {
int j = i;
int k = 0;
while (j < haystack.size() && k < needle.size() && haystack[j] == needle[k]) {
j++;
k++;
}
if (k == needle.size()) return i;
}
return -1;
}
};
KMP
// Implement strStr()// KMP，时间复杂度O(N+M)，空间复杂度O(M)class Solution {public:
int strStr(const string& haystack, const string& needle) {
return kmp(haystack.c_str(), needle.c_str());
}private:
/*
* @brief 计算部分匹配表，即next数组.
* @param[in] pattern 模式串
* @param[out] next next数组
* @return 无
*/
static void compute_prefix(const char *pattern, int next[]) {
int i;
int j = -1;
const int m = strlen(pattern);
next[0] = j;
for (i = 1; i < m; i++) {
while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];
if (pattern[i] == pattern[j + 1]) j++;
next[i] = j;
}
}
/*
* @brief KMP算法.
*
* @param[in] text 文本
* @param[in] pattern 模式串
* @return 成功则返回第一次匹配的位置，失败则返回-1
*/
static int kmp(const char *text, const char *pattern) {
int i;
int j = -1;
const int n = strlen(text);
const int m = strlen(pattern);
if (n == 0 && m == 0) return 0; /* "","" */
if (m == 0) return 0; /* "a","" */
int *next = (int*)malloc(sizeof(int) * m);
compute_prefix(pattern, next);
for (i = 0; i < n; i++) {
while (j > -1 && pattern[j + 1] != text[i]) j = next[j];
if (text[i] == pattern[j + 1]) j++;
if (j == m - 1) {
free(next);
return i-j;
}
}
free(next);
return -1;
}
};
50. Pow(x,n)
描述
Implement pow(x, n).
分析
二分法，x^n = x^{n/2} \times x^{n/2} \times x^{n\%2}xn=xn/2×xn/2×xn%2
代码
// Pow(x, n)
// 二分法，$x^n = x^{n/2} * x^{n/2} * x^{n\%2}$
// 时间复杂度O(logn)，空间复杂度O(1)
class Solution {public:
double myPow(double x, int n) {
if (n < 0) return 1.0 / power(x, -n);
else return power(x, n);
}private:
double power(double x, int n) {
if (n == 0) return 1;
double v = power(x, n / 2);
if (n % 2 == 0) return v * v;
else return v * v * x;
}
};
56. 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]
分析
复用一下Insert Intervals的解法即可，创建一个新的interval集合，然后每次从旧的里面取一个interval出来，然后插入到新的集合中。
代码
// Merge Interval
// 复用一下Insert Intervals的解法即可
// 时间复杂度O(n1+n2+...)，空间复杂度O(1)
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> result;
for (int i = 0; i < intervals.size(); i++) {
insert(result, intervals[i]);
}
return result;
}
private:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval>::iterator it = intervals.begin();
while (it != intervals.end()) {
if (newInterval.end < it->start) {
intervals.insert(it, newInterval);
return intervals;
} else if (newInterval.start > it->end) {
it++;
continue;
} else {
newInterval.start = min(newInterval.start, it->start);
newInterval.end = max(newInterval.end, it->end);
it = intervals.erase(it);
}
}
intervals.insert(intervals.end(), newInterval);
return intervals;
}
};
57. Insert Interval
描述
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].
分析
无
代码
// Insert Interval
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval>::iterator it = intervals.begin();
while (it != intervals.end()) {
if (newInterval.end < it->start) {
intervals.insert(it, newInterval);
return intervals;
} else if (newInterval.start > it->end) {
it++;
continue;
} else {
newInterval.start = min(newInterval.start, it->start);
newInterval.end = max(newInterval.end, it->end);
it = intervals.erase(it);
}
}
intervals.insert(intervals.end(), newInterval);
return intervals;
}
};
65. 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.
分析
细节实现题。
本题的功能与标准库中的strtod()功能类似。
有限自动机
// Valid Number
// @author 龚陆安 (http://weibo.com/luangong)
// finite automata，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
bool isNumber(const string& s) {
enum InputType {
INVALID, // 0
SPACE, // 1
SIGN, // 2
DIGIT, // 3
DOT, // 4
EXPONENT, // 5
NUM_INPUTS // 6
};
const int transitionTable[][NUM_INPUTS] = {
-1, 0, 3, 1, 2, -1, // next states for state 0
-1, 8, -1, 1, 4, 5, // next states for state 1
-1, -1, -1, 4, -1, -1, // next states for state 2
-1, -1, -1, 1, 2, -1, // next states for state 3
-1, 8, -1, 4, -1, 5, // next states for state 4
-1, -1, 6, 7, -1, -1, // next states for state 5
-1, -1, -1, 7, -1, -1, // next states for state 6
-1, 8, -1, 7, -1, -1, // next states for state 7
-1, 8, -1, -1, -1, -1, // next states for state 8
};
int state = 0;
for (auto ch : s) {
InputType inputType = INVALID;
if (isspace(ch))
inputType = SPACE;
else if (ch == '+' || ch == '-')
inputType = SIGN;
else if (isdigit(ch))
inputType = DIGIT;
else if (ch == '.')
inputType = DOT;
else if (ch == 'e' || ch == 'E')
inputType = EXPONENT;
// Get next state from current state and input symbol
state = transitionTable[state][inputType];
// Invalid input
if (state == -1) return false;
}
// If the current state belongs to one of the accepting (final) states,
// then the number is valid
return state == 1 || state == 4 || state == 7 || state == 8;
}
};
73. Set Matrix Zeroes
描述
Given a m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
分析
O(m+n)空间的方法很简单，设置两个bool数组，记录每行和每列是否存在0。
想要常数空间，可以复用第一行和第一列。
代码1
// Set Matrix Zeroes
// 时间复杂度O(m*n)，空间复杂度O(m+n)
class Solution {public:
void setZeroes(vector<vector<int> > &matrix) {
const size_t m = matrix.size();
const size_t n = matrix[0].size();
vector<bool> row(m, false); // 标记该行是否存在0
vector<bool> col(n, false); // 标记该列是否存在0
for (size_t i = 0; i < m; ++i) {
for (size_t j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
row[i] = col[j] = true;
}
}
}
for (size_t i = 0; i < m; ++i) {
if (row[i])
fill(&matrix[i][0], &matrix[i][0] + n, 0);
}
for (size_t j = 0; j < n; ++j) {
if (col[j]) {
for (size_t i = 0; i < m; ++i) {
matrix[i][j] = 0;
}
}
}
}
};
代码2
// Set Matrix Zeroes// 时间复杂度O(m*n)，空间复杂度O(1)
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
const size_t m = matrix.size();
const size_t n = matrix[0].size();
bool row_has_zero = false; // 第一行是否存在 0
bool col_has_zero = false; // 第一列是否存在 0
for (size_t i = 0; i < n; i++)
if (matrix[0][i] == 0) {
row_has_zero = true;
break;
}
for (size_t i = 0; i < m; i++)
if (matrix[i][0] == 0) {
col_has_zero = true;
break;
}
for (size_t i = 1; i < m; i++)
for (size_t j = 1; j < n; j++)
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
for (size_t i = 1; i < m; i++)
for (size_t j = 1; j < n; j++)
if (matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
if (row_has_zero)
for (size_t i = 0; i < n; i++)
matrix[0][i] = 0;
if (col_has_zero)
for (size_t i = 0; i < m; i++)
matrix[i][0] = 0;
}
};
88. Merge Two Sorted Arrays
描述
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 to hold additional elements from
B. The number of elements initialized in A and B are m and n respectively.
代码
// Merge Sorted Array
// 时间复杂度O(m+n)，空间复杂度O(1)
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int ia = m - 1, ib = n - 1, icur = m + n - 1;
while (ia >= 0 && ib >= 0) {
A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
}
While (ib >= 0) {
A[icur--] = B[ib--];
}
}
};
98. Validate Binary Search Tree
描述
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
代码
// Validate Binary Search Tree
// 时间复杂度O(n)，空间复杂度O(\logn)
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
bool isValidBST(TreeNode* root, long long lower, long long upper) {
if (root == nullptr) return true;
return root->val > lower && root->val < upper
&& isValidBST(root->left, lower, root->val)
&& isValidBST(root->right, root->val, upper);
}
};
125. Valid Palindrome
描述
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.
Note: Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
分析
无
代码
// Valid Palindrome
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
bool isPalindrome(string s) {
transform(s.begin(), s.end(), s.begin(), ::tolower);
auto left = s.begin(), right = prev(s.end());
while (left < right) {
if (!::isalnum(*left)) ++left;
else if (!::isalnum(*right)) --right;
else if (*left != *right) return false;
else { left++, right--; }
}
return true;
}
};
127. Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- 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.
思路：1. 广度优先遍历搜索到的一定是最短路径(广搜是dijstra的特例).
2. 一次广搜到结果后即可返回
设置visited防止回搜
代码：
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
if(dict.empty() || start == end)
return 0;
queue<string>strq;
queue<int>depq;
strq.push(start);
depq.push(1);
string cur, nxt;
int depth;
unordered_set<string> visited;
while(!strq.empty())
{
nxt = cur = strq.front();
strq.pop();
depth = depq.front();
depq.pop();
if(cur == end)
return depth;
for(int i = 0; i < cur.length(); ++i)
{
for(char ch = 'a'; ch<='z'; ++ch)
{
if(ch!=cur[i])
{
nxt[i] = ch;
if(dict.find(nxt)!=dict.end() && visited.find(nxt)==visited.end())
{
visited.insert(nxt);
strq.push(nxt);
depq.push(depth+1);
}
nxt = cur;
}
}
}
}
return 0;
}
};
5. 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.
O(n^2)方法
/**思路：
* 从回文串的对称点开始，依次向左向右比较，不相同的时候停止遍历，直到找出最大的长度的回文子串。
* （1）回文子串长度为奇数：对称点只有一个字符
* （2）回文子串长度为偶数：对称点有两个字符
* 时间复杂度为O(n^2):对称点的数量为O(n),每次查找的时间也为O(n),所有总时间复杂度为O(n^2) */
class Solution {
public:
string longestPalindrome(string s) {
//字符串的长度
int len = s.size();
if (len == 0) return s;
//保留最长回文串
string resultStr = "";
//回文子串长度为奇数,：对称点只有一个字符的情况
for (int i=0; i<len; ++i){
// i 为对称点
int left = i;//左
int right = i;//右
//向左向右遍历，直到发现不相同的时候停止
while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){
--left;
++right;
}
//比较，更新最长回文串
if (right - left + 1 > resultStr.size()){
resultStr = s.substr(left, right - left + 1);
}
}
//回文子串长度为偶数：对称点有两个字符
for (int i = 0; i < len - 1; ++i){
if (s[i] == s[i+1]){//两个对称点相同，才有继续遍历的意义
int left = i;
int right = i+1;
//向左向右遍历，直到发现不相同的时候停止
while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){
--left;
++right;
}
//比较，更新最长回文串
if (right - left + 1 > resultStr.size()){
resultStr = s.substr(left, right - left + 1);
}
}
}
return resultStr;
}
};
Manacher 算法， 复杂度 O(n)
// Transform S into T
// For example, S = "abba", T = "^#a#b#b#a#$"
// ^ and $ signs are sentinels appended to each string
// to avoid bound checking
string preProcess(string s)
{
int n = s.length();
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; ++i)
ret += "#" + s.substr(i, 1);
ret += "#$";
return ret;
}
string longestPalindromeManacher(string s)
{
string T = preProcess(s);
int n = T.length();
vector<int> p(n, 0);
int C = 0, R = 0;
for (int i = 1; i < n-1; ++i){
int i_mirror = 2*C-i;
p[i] = (i < R) ? min(R-i, p[i_mirror]) : 0;
// attempt to expand palindrome centered at i
while(T[i + 1 + p[i]] == T[i - 1 - p[i]])
++ p[i];
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome,
if(p[i] + i > R) {
C = i;
R = i + p[i];
}
}
// Find the maximum element in p
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n-1; ++i) {
if(p[i] > maxLen){
maxLen = p[i];
centerIndex = i;
}
}
return s.substr((centerIndex - 1 - maxLen)/2 , maxLen);
}
