所有总结题目 http://www.jianshu.com/p/55b90cfcb406
这里总结了频率4的题目：
2.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
分析
跟 Add Binary 很类似
代码
// Add Two Numbers
// 跟Add Binary 很类似
// 时间复杂度O(m+n)，空间复杂度O(1)
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode dummy(-1); // 头节点
int carry = 0;
ListNode *prev = &dummy;
for (ListNode *pa = l1, *pb = l2;
pa != nullptr || pb != nullptr;
pa = pa == nullptr ? nullptr : pa->next,
pb = pb == nullptr ? nullptr : pb->next,
prev = prev->next) {
const int ai = pa == nullptr ? 0 : pa->val;
const int bi = pb == nullptr ? 0 : pb->val;
const int value = (ai + bi + carry) % 10;
carry = (ai + bi + carry) / 10;
prev->next = new ListNode(value); // 尾插法
}
if (carry > 0)
prev->next = new ListNode(carry);
return dummy.next;
}
};
12.Integer to Roman
描述
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
代码
// Integer to Roman
// 时间复杂度O(num)，空间复杂度O(1)
class Solution {
public:
string intToRoman(int num) {
const int radix[] = {1000, 900, 500, 400, 100, 90,
50, 40, 10, 9, 5, 4, 1};
const string symbol[] = {"M", "CM", "D", "CD", "C", "XC",
"L", "XL", "X", "IX", "V", "IV", "I"};
string roman;
for (size_t i = 0; num > 0; ++i) {
int count = num / radix[i];
num %= radix[i];
for (; count > 0; --count) roman += symbol[i];
}
return roman;
}
};
13. Roman to Integer
描述
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
分析
从前往后扫描，用一个临时变量记录分段数字。
如果当前比前一个大，说明这一段的值应该是当前这个值减去上一个值。比如 IV = 5 – 1 ；否则，将当前值加入到结果中，然后开始下一段记录。比如 VI = 5 +1, II=1+1
代码
// Roman to Integer
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
inline int map(const char c) {
switch (c) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
int romanToInt(const string& s) {
int result = 0;
for (size_t i = 0; i < s.size(); i++) {
if (i > 0 && map(s[i]) > map(s[i - 1])) {
result += (map(s[i]) - 2 * map(s[i - 1]));
} else {
result += map(s[i]);
}
}
return result;
}
};
22. 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:
"((()))", "(()())", "(())()", "()(())", "()()()"
分析
小括号串是一个递归结构，跟单链表、二叉树等递归结构一样，首先想到用递归。
一步步构造字符串。当左括号出现次数 <n 时，就可以放置新的左括号。当右括号
出现次数小于左括号出现次数时，就可以放置新的右括号。
代码1
// Generate Parentheses
// 时间复杂度O(TODO)，空间复杂度O(n)
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string path;
if (n > 0) generate(n, path, result, 0, 0);
return result;
}
// l 表示 ( 出现的次数, r 表示 ) 出现的次数
void generate(int n, string& path, vector<string> &result, int l) {
if (l == n) {
string s(path);
result.push_back(s.append(n - r, ')'));
return;
}
path.push_back('(');
generate(n, path, result, l + 1, r);
path.pop_back();
if (l > r) {
path.push_back(')');
generate(n, path, result, l, r + 1);
path.pop_back();
}
}
};
代码2 （递归）
class Solution {
public:
vector<string> generateParenthesis (int n) {
if (n == 0) return vector<string> (1, "");
if (n == 1) return vector<string> (1, "()");
vector<string> result;
for (int i = 0; i < n; ++i)
for (auto inner : generateParenthesis (i))
for (auto outer : generateParenthesis (n - 1 - i))
result.push_back ("(" + inner + ")" + outer);
return result;
}
};
23. Merge k Sorted Lists
描述
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its
complexity.
代码
// Merge k Sorted Lists
// 时间复杂度O(n1+n2+...)，空间复杂度O(1)
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if(lists.empty()) {
return NULL;
}
int n = lists.size();
while(n > 1) {
int k = (n + 1) / 2;
for(int i = 0; i < n / 2; i++) {
//合并i和i + k的链表，并放到i位置
lists[i] = merge2List(lists[i], lists[i + k]);
}
//下个循环只需要处理前k个链表了
n = k;
}
return lists[0];
}
ListNode* merge2List(ListNode* n1, ListNode* n2) {
ListNode dummy(0);
ListNode* p = &dummy;
while(n1 && n2) {
if(n1->val < n2->val) {
p->next = n1;
n1 = n1->next;
} else {
p->next = n2;
n2 = n2->next;
}
p = p->next;
}
if(n1) {
p->next = n1;
} else if(n2) {
p->next = n2;
}
return dummy.next;
}
};
24. 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.
代码
// Swap Nodes in Pairs
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
if (head == NULl || head->next == NULL)
return head;
else if (head->next->next == NULL) {
ListNode* pNext = head->next;
pNext->next = head;
head->next = NULL;
return pNext;
} else {
ListNode* pNext = head->next;
ListNode* newHead = pNext->next;
pNext->next = head;
head->next = swapPairs(newHead);
return pNext;
}
}
};
27. 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.
代码
// Remove Element
// Time Complexity: O(n), Space Complexity: O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int target) {
int index = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != target) {
nums[index++] = nums[i];
}
}
return index;
}
};
46. Permutations（全排列）
描述
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3]have the following permutations:
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], and [3,2,1].
class Solution {
public:
bool next_perm(vector<int>& num) {
int i = num.size()-1, j = num.size()-1;
while(i-1 >= 0 && num[i] < num[i-1])i--;
if(i == 0)
return false;
i--;
while(num[j] < num[i])
j--;
std::swap(num[i], num[j]);
reverse(num.begin()+i+1, num.end());
return true;
}
vector<vector<int> > permute(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> > ans;
do {
ans.push_back(num);
} while(next_perm(num));
return ans;
}
};
49. Anagrams
描述
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
代码
class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
int i;
map<string,int> book;
vector<string> d,t;
for(i=0;i<strs.size();t.push_back(strs[i]),i++);
for(i=0;i<t.size();i++)
{
sort(t[i].begin(),t[i].end());
if(book.count(t[i])==0) book[t[i]]=0;
book[t[i]]++;
}
for(i=0;i<strs.size();i++)
if(book[t[i]]>=2) d.push_back(strs[i]);
return d;
}
};
67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example, a = "11" b = "1" Return "100".
分析: 我认为这道题所要注意的地方涵盖以下几个方面:
对字符串的操作.
对于加法，我们应该建立一个进位单位，保存进位数值.
我们还要考虑两个字符串如果不同长度会怎样.
int 类型和char类型的相互转换.
时间复杂度:其实这就是针对两个字符串加起来跑一遍，O(n) n代表长的那串字符串长度.
class Solution {
public:
string addBinary(string a, string b) {
int len1 = a.size();
int len2 = b.size();
if(len1 == 0)
return b;
if(len2 == 0)
return a;
string ret;
int carry = 0;
int index1 = len1-1;
int index2 = len2-1;
while(index1 >=0 && index2 >= 0)
{
int num = (a[index1]-'0')+(b[index2]-'0')+carry;
carry = num/2;
num = num%2;
index1--;
index2--;
ret.insert(ret.begin(),num+'0');
}
if(index1 < 0 && index2 < 0)
{
if(carry == 1)
{
ret.insert(ret.begin(),carry+'0');
return ret;
}
}
while(index1 >= 0)
{
int num = (a[index1]-'0')+carry;
carry = num/2;
num = num%2;
index1--;
ret.insert(ret.begin(),num+'0');
}
while(index2 >= 0)
{
int num = (b[index2]-'0')+carry;
carry = num/2;
num = num%2;
index2--;
ret.insert(ret.begin(),num+'0');
}
if(carry == 1)
ret.insert(ret.begin(),carry+'0');
return ret;
}
};
69. Sqrt(x)
描述
Implement int sqrt(int x) .
Compute and return the square root of x .
分析
二分查找
代码
// LeetCode, Sqrt(x)
// 二分查找
// 时间复杂度O(logn)，空间复杂度O(1)
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x / 2;
int last_mid; // 记录最近一次mid
if (x < 2) return x;
while(left <= right) {
const int mid = left + (right - left) / 2;
if(x / mid > mid) { // 不要用 x > mid * mid，会溢出
left = mid + 1;
last_mid = mid;
} else if (x / mid < mid) {
right = mid - 1;
} else {
return mid;
}
}
return last_mid;
}
};
77. Combinations
描述
Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n.
For example, If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
递归
// Combinations
// 深搜，递归
// 时间复杂度O(n!)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > result;
vector<int> path;
dfs(n, k, 1, 0, path, result);
return result;
}
private:
// start，开始的数, cur，已经选择的数目
static void dfs(int n, int k, int start, int cur,
vector<int> &path, vector<vector<int> > &result) {
if (cur == k) {
result.push_back(path);
}
for (int i = start; i <= n; ++i) {
path.push_back(i);
dfs(n, k, i + 1, cur + 1, path, result);
path.pop_back();
}
}
};
78. 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],
[]
]
递归
增量构造法
每个元素，都有两种选择，选或者不选。
代码
// Subsets
// 增量构造法，深搜，时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end()); // 输出要求有序
vector<vector<int> > result;
vector<int> path;
subsets(S, path, 0, result);
return result;
}
private:
static void subsets(const vector<int> &S, vector<int> &path, int step,
vector<vector<int> > &result) {
if (step == S.size()) {
result.push_back(path);
return;
}
// 不选S[step]
subsets(S, path, step + 1, result);
// 选S[step]
path.push_back(S[step]);
subsets(S, path, step + 1, result);
path.pop_back();
}
};
79. 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 neighbouring. 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 .
代码
//C++ DFS backtracking 的算法
class Solution {
public:
bool isOut(int r, int c, int rows, int cols){
return c<0 || c>=cols || r<0 || r>=rows;
}
bool DFS(vector<vector<char>> &board, int r, int c, string &word, int start){
if(start>=word.size())
return true;
if(isOut(r, c, board.size(), board[0].size())||word[start]!=board[r][c])
return false;
int dx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0};
char tmp=board[r][c];
board[r][c]='.';
for(int i=0; i<4; ++i){
if(DFS(board, r+dx[i], c+dy[i], word, start+1))
return true;
}
board[r][c]=tmp;
return false;
}
bool exist(vector<vector<char> > &board, string word) {
int rows=board.size(), cols=board[0].size();
for(int r=0; r<rows; ++r)
for(int c=0; c<cols; ++c){
if(board[r][c]==word[0])
if(DFS(board, r, c, word, 0))
return true;
}
return false;
}
};
102. Binary Tree Level Order Traversal、
描述
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree{3,9,20,#,#,15,7},
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/
2 3
/
4
5
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".
代码
// Binary Tree Level Order Traversal
// 递归版，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int>> result;
traverse(root, 1, result);
return result;
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result) {
if (!root) return;
if (level > result.size())
result.push_back(vector<int>());
result[level-1].push_back(root->val);
traverse(root->left, level+1, result);
traverse(root->right, level+1, result);
}
};
129. Sum Root to Leaf Numbers
描述
Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path1->2->3which represents the number123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/
2 3
The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.
Return the sum = 12 + 13 =25.
代码
// Sum root to leaf numbers
// 时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
int sumNumbers(TreeNode *root) {
return dfs(root, 0);
}
private:
int dfs(TreeNode *root, int sum) {
if (root == nullptr) return 0;
if (root->left == nullptr && root->right == nullptr)
return sum * 10 + root->val;
return dfs(root->left, sum * 10 + root->val) +
dfs(root->right, sum * 10 + root->val);
}
};
131. Palindrome Partitioning
描述
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s ="aab",
Return
[
["aa","b"],
["a","a","b"]
]
动态规划+递归实现
class Solution {
public:
//返回以s[i]开始的子串的所有拆分情况
vector<vector<string> > dfs(size_t start, vector<vector<bool> >& flag, string s) {
vector<vector<string> > res;
//到达末尾
if (start == s.length()) {
vector<string> tmp;
res.push_back(tmp);
}
else {
//分两部分
for (size_t i = start; i < s.length(); i++) {
//前半部分为回文
if (flag[start][i] == true) {
//递归计算后半部分
vector<vector<string> > tmp = dfs(i + 1, flag, s);
//将返回的结果插入前半部分，放入res中
for (size_t k = 0; k < tmp.size(); k++) {
tmp[k].insert(tmp[k].begin(), s.substr(start, i - start + 1));
res.push_back(tmp[k]);
}
}
}
}
return res;
}
vector<vector<string>> partition(string s) {
vector<bool> tmp(s.size(), false);
vector<vector<bool> > flag(s.size(), tmp);
vector<vector<string> > res;
//flag[i][j]为s[i..j]是否为回文串的标志，用动态规划
//flag[i][j] = true (当s[i]==s[j] 且 flag[i+1][j-1]为true)
for (int i = s.size() - 1; i >= 0; i--) {
for (size_t j = i; j < s.size(); j++) {
if (i == j) {
flag[i][j] = true;
}
else {
if (s[i] == s[j]) {
if (i + 1 == j || flag[i + 1][j - 1] == true)
flag[i][j] = true;
}
}
}
}
//递归找出拆分方法
res = dfs(0, flag, s);
return res;
}
};
