Leetcode经典编程题解答 --基于牛客网C++编译器
熟悉一下牛客网的编译器，面试笔试肯定用的到~
不间断更新中。。
1、minimum-depth-of-binary-tree
Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
class Solution {
public:
int run(TreeNode *root) {
if(!root)
return 0;
if(!root->left && !root->right)
return 1;
else if(!root->left || !root->right)
return 1 + max(run(root->left), run(root->right));
else return 1 + min(run(root->left), run(root->right));
}
}; 注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
2、evaluate-reverse-polish-notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
class Solution {
public:
int evalRPN(vector<string> &tokens) {
if(tokens.size()==0)
return 0;
stack<string> s;
for(int i=0;i<tokens.size();i++)
{
if(tokens[i]!="+" && tokens[i]!="-" && tokens[i]!="*" && tokens[i]!="/")
s.push(tokens[i]);
else calculate(s, tokens[i]);
}
return stoi(s.top());
}
void calculate(stack<string> &s, string sign)
{
int num2 = stoi(s.top());
s.pop();
int num1 = stoi(s.top());
s.pop();
int num;
if(sign == "+")
num = num1 + num2;
if(sign == "-")
num = num1 - num2;
if(sign == "*")
num = num1 * num2;
if(sign == "/")
num = num1 / num2;
s.push(to_string(num));
}
}; 注：本题一点都没有考虑特殊情况，包括tokens里的逆波兰表达式非法，运算结果过大，除数为0等。
3、max-points-on-a-line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
4、sort-list
Sort a linked list in O(n log n) time using constant space complexity.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(!head || !head->next)
return head;
ListNode *slow = head, *fast = head, *ptr;
while(fast && fast->next)
{
ptr = slow;
slow = slow->next;
fast = fast->next->next;
}
ptr->next = nullptr;
ListNode *first = sortList(head);
ListNode *second = sortList(slow);
ListNode *result = merge(first, second);
return result;
}
ListNode * merge(ListNode *first, ListNode *second)
{
ListNode *m = new ListNode(0);
ListNode * p = m;
while(first || second)
{
int a = INT_MAX, b = INT_MAX;
if(first)
a = first->val;
if(second)
b = second->val;
if(a>b)
{
ListNode *cache = new ListNode(b);
p->next = cache;
second = second->next;
}
else
{
ListNode *cache = new ListNode(a);
p->next = cache;
first = first->next;
}
p = p->next;
}
return m->next;
}
}; 注：采用归并排序的方法。
5、max-points-on-a-line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
6、binary-tree-postorder-traversal
Given a binary tree, return the postorder traversal of its nodes' values.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
if(!root)
return {};
vector<int> output;
stack<TreeNode*> s;
s.push(root);
while(!s.empty())
{
TreeNode *p = s.top();
output.push_back(p->val);
s.pop();
if(p->left)
s.push(p->left);
if(p->right)
s.push(p->right);
}
reverse(output.begin(), output.end());
return output;
}
}; 注：无
7、binary-tree-preorder-traversal
Given a binary tree, return the preorder traversal of its nodes' values.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
if(!root)
return {};
vector<int> output;
stack<TreeNode*> s;
s.push(root);
while(!s.empty())
{
TreeNode *p = s.top();
output.push_back(p->val);
s.pop();
if(p->right)
s.push(p->right);
if(p->left)
s.push(p->left);
}
return output;
}
}; 注：用栈即可。
8、reorder-list
Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…
You must do this in-place without altering the nodes' values.
For example： Given{1,2,3,4}, reorder it to{1,4,2,3}.
用栈：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
stack<ListNode *> s;
ListNode *p = head;
while(p)
{
s.push(p);
p = p->next;
}
while(!s.empty())
{
if(s.top() == head)
{
head->next = nullptr;
return;
}
else if(s.top() == head->next)
{
head->next->next = nullptr;
return ;
}
else
{
ListNode *q = s.top();
ListNode *cache = head->next;
head->next = q;
q->next = cache;
s.pop();
head = head->next->next;
}
}
}
}; 原地：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
if(!head)
return;
ListNode *slow = head, *fast = head, *ptr;
while(fast && fast->next)
{
ptr = slow;
slow = slow->next;
fast = fast->next->next;
}
ptr->next = nullptr;
ListNode *first = head;
ListNode *second = reverse(slow);
if(first == second)
return ;
while(first->next)
{
ListNode *cache1 = first->next;
ListNode *cache2 = second->next;
first->next = second;
second->next = cache1;
first = first->next->next;
second = cache2;
}
first->next = second;
}
ListNode *reverse(ListNode *head)
{
ListNode *p = nullptr;
ListNode *q = head;
while(q)
{
ListNode *r = q->next;
q->next = p;
p = q;
q = r;
}
return p;
}
}; 注：原地修改需要找到中间结点然后断开，翻转后一段的链表，然后合并两个链表。
9、linked-list-cycle-ii
Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
Follow up:
Can you solve it without using extra space?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *m = hasCycle(head);
if(!m)
return m;
int num = 1;
ListNode *p = m;
while(p->next != m)
{
num++;
p = p->next;
}
ListNode *slow = head, *fast = head;
while(num)
{
fast = fast->next;
num--;
}
while(slow!=fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
ListNode *hasCycle(ListNode *head) {
if(!head)
return nullptr;
ListNode *slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return slow;
}
return nullptr;
}
}; 注：计算出环的长度L，然后让快指针先走L步。
10、linked-list-cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head)
return false;
ListNode *slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return true;
}
return false;
}
}; 注：使用快慢指针即可。
11、word-break-ii
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].
A solution is["cats and dog", "cat sand dog"].
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
12、word-break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s ="leetcode",
dict =["leet", "code"].
Return true because"leetcode"can be segmented as"leet code".
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
vector<int> cache(s.size()+1, -1);
return recurrent(cache, s, dict, 0);
}
bool recurrent(vector<int> &cache, string s, unordered_set<string> &dict, int k)
{
if(cache[k]!=-1)
return cache[k];
if(s.size()<1)
{
cache[k] = 1;
return true;
}
for(int i=0;i<s.size();i++)
{
if(dict.find(s.substr(0,i+1))!=dict.end())
if(recurrent(cache, s.substr(i+1), dict, k+i))
{
cache[k] = 1;
return true;
}
}
cache[k] = 0;
return false;
}
}; 注：记忆化搜索法。
13、copy-list-with-random-pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(!head)
return nullptr;
RandomListNode *m = new RandomListNode(0);
RandomListNode *q = m;
RandomListNode *p = head;
while(p)
{
RandomListNode *cache = new RandomListNode(p->label);
cache->next = p->next;
p->next = cache;
p = p->next->next;
}
p = head;
while(p)
{
if(p->random)
p->next->random = p->random->next;
p = p->next->next;
}
p = head;
while(p)
{
q->next = p->next;
p->next = p->next->next;
p = p->next;
q = q->next;
}
return m->next;
}
}; 注：首先复制当前节点并插入其下一个节点，再复制random指针，然后再断开链表。
14、single-number-ii
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
15、single-number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
class Solution {
public:
int singleNumber(int A[], int n) {
int num = 0;
for(int i=0;i<n;i++)
num^=A[i];
return num;
}
}; 注：异或即可。
XX、sort-list
Sort a linked list in O(n log n) time using constant space complexity.
1
注：无。
XX、sort-list
Sort a linked list in O(n log n) time using constant space complexity.
1
注：无。
XX、sort-list
Sort a linked list in O(n log n) time using constant space complexity.
1
注：无。
XX、sort-list
Sort a linked list in O(n log n) time using constant space complexity.
1
注：无。
XX、maximum-depth-of-binary-tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Sort a linked list in O(n log n) time using constant space complexity.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode *root) {
if(!root)
return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
}; 注：无。
XX、binary-tree-zigzag-level-order-traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree{3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7 return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
if(!root)
return {};
vector<vector<int> > output;
stack<TreeNode*> s1, s2;
s1.push(root);
bool flag = true;
while(!s1.empty() || !s2.empty())
{
vector<int> cache;
if(flag)
{
while(!s1.empty())
{
TreeNode *p = s1.top();
s1.pop();
cache.push_back(p->val);
if(p->left)
s2.push(p->left);
if(p->right)
s2.push(p->right);
}
flag = !flag;
}
else
{
while(!s2.empty())
{
TreeNode *p = s2.top();
s2.pop();
cache.push_back(p->val);
if(p->right)
s1.push(p->right);
if(p->left)
s1.push(p->left);
}
flag = !flag;
}
output.push_back(cache);
}
return output;
}
}; 注：无。
XX、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] ]
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
if(!root)
return {};
vector<vector<int> > output;
queue<TreeNode *> q;
q.push(root);
while(!q.empty())
{
int size = q.size();
vector<int> cache;
while(size--)
{
TreeNode *p = q.front();
q.pop();
cache.push_back(p->val);
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}
output.push_back(cache);
}
return output;
}
}; 注：无。
XX、symmetric-tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following is not:
1 / \ 2 2 \ \ 3 3
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if(!root)
return true;
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode *root1, TreeNode *root2)
{
if(!root1 && !root2)
return true;
if(!root1 || !root2)
return false;
if(root1->val == root2->val)
return isSymmetric(root1->left, root2->right) && isSymmetric(root1->right, root2->left);
return false;
}
}; 注：无。
XX、same-tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(!p && !q)
return true;
if(!p || !q)
return false;
if(p->val == q->val)
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
return false;
}
}; 注：无。
XX、recover-binary-search-tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n ) space is pretty straight forward. Could you devise a constant space solution?
1
注：无。
XX、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.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode *root) {
vector<int> cache;
inorder(cache, root);
for(int i=0;i<cache.size();i++)
{
if(i+1<cache.size() && cache[i]>=cache[i+1])
return false;
}
return true;
}
void inorder(vector<int>& cache, TreeNode *root)
{
if(root)
{
inorder(cache, root->left);
cache.push_back(root->val);
inorder(cache, root->right);
}
}
}; 注：无。
XX、recover-binary-search-tree
Sort a linked list in O(n log n) time using constant space complexity.
1
注：无。
XX、recover-binary-search-tree
Sort a linked list in O(n log n) time using constant space complexity.
1
注：无。
XX、binary-tree-inorder-traversal
Given a binary tree, return the inorder traversal of its nodes' values.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
if(!root)
return {};
vector<int> output;
stack<TreeNode*> s;
TreeNode *p = root;
while(p || !s.empty())
{
while(p)
{
s.push(p);
p = p->left;
}
p = s.top();
output.push_back(p->val);
s.pop();
p = p->right;
}
return output;
}
}; 注：无。
XX、substring-with-concatenation-of-all-words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S:"barfoothefoobarman"
L:["foo", "bar"]
You should return the indices:[0,9].
(order does not matter).
class Solution {
public:
vector<int> findSubstring(string S, vector<string> &L) {
if(L.size()==0 || S.size()==0)
return {};
vector<int> output;
map<string, int> hash;
int stride = L[0].size(), num = L.size();
for(int i=0;i<num;i++)
{
if(hash.find(L[i])==hash.end())
hash[L[i]] = 1;
else hash[L[i]]++;
}
for(int i=0;i+stride*num<=S.size();i++)
{
int j = 0, cache = i;
map<string, int> hash1(hash);
for(;j<num;j++)
{
cache = i + j * stride;
if(hash1.find(S.substr(cache, stride))==hash1.end() || hash1[S.substr(cache, stride)]==0)
break;
else hash1[S.substr(cache, stride)]--;
}
if(j==num)
output.push_back(i);
}
return output;
}
}; 注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
XX、divide-two-integers
Divide two integers without using multiplication, division and mod operator.
class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
int sign = 1;
long long a = dividend,b = divisor;
a = abs(a);
b = abs(b);
if(dividend>0 ^ divisor>0)
sign = -1;
return sign*recurrent(a, b, 0);
}
long long recurrent(long long dividend, long long divisor, long long k)
{
if(divisor>dividend)
return k;
long long temp = divisor, cache = divisor, num = 1;
while(dividend-temp>0)
{
cache = temp;
temp += temp;
if(dividend-temp>0)
num += num;
}
return recurrent(dividend-cache, divisor, k+num);
}
}; 注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
XX、implement-strstr
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
class Solution {
public:
char *strStr(char *haystack, char *needle) {
if(*haystack=='\0' && *needle=='\0')
return haystack;
while(*haystack!='\0')
{
if(isStr(haystack, needle))
return haystack;
haystack++;
}
return nullptr;
}
bool isStr(char *haystack, char *needle)
{
if(*needle=='\0')
return true;
if(*haystack=='\0')
return false;
if(*haystack == *needle)
return isStr(haystack+1, needle+1);
return false;
}
}; 注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
XX、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.
class Solution {
public:
int removeElement(int A[], int n, int elem) {
int left = 0;
for(int i=0;i<n;i++)
{
if(A[i]!=elem)
{
swap(A[i], A[left]);
++left;
}
}
return left;
}
}; 注：本题设计测试样例的人脑袋有坑，不用管它。
XX、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].
class Solution {
public:
int removeDuplicates(int A[], int n) {
if(n==0)
return 0;
int left = 1,temp = A[0];
for(int i=1;i<n;i++)
{
if(A[i]!=temp)
{
temp = A[i];
swap(A[left], A[i]);
left++;
}
}
return left;
}
}; 注：无。
XX、reverse-nodes-in-k-group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list:1->2->3->4->5
For k = 2, you should return:2->1->4->3->5
For k = 3, you should return:3->2->1->4->5
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if(k<=1)
return head;
ListNode *m = new ListNode(0);
ListNode *p = m;
while(head)
{
int sum = k-1;
ListNode *q = head;
while(q && sum)
{
--sum;
q = q->next;
}
if(sum || !q)
break;
ListNode *cache = q->next;
q->next = nullptr;
p->next = reverse(head);
while(sum!=k)
{
++sum;
p = p->next;
}
head = cache;
}
p->next = head;
return m->next;
}
ListNode *reverse(ListNode *head) {
ListNode *p = nullptr;
ListNode *q = head;
while(q)
{
ListNode *r = q->next;
q->next = p;
p = q;
q = r;
}
return p;
}
}; 注：无。
XX、swap-nodes-in-pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given1->2->3->4, you should return the list as2->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) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
ListNode *m = new ListNode(0);
ListNode *p = m;
while(head && head->next)
{
ListNode *q = head->next->next;
head->next->next = nullptr;
p->next = reverse(head);
p = p->next->next;
head = q;
}
p->next = head;
return m->next;
}
ListNode *reverse(ListNode *head) {
ListNode *p = nullptr;
ListNode *q = head;
while(q)
{
ListNode *r = q->next;
q->next = p;
p = q;
q = r;
}
return p;
}
}; 注：无。
XX、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) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if(lists.size()==0)
return nullptr;
ListNode *m = lists[0];
for(int i=1;i<lists.size();i++)
m = merge(m, lists[i]);
return m;
}
ListNode *merge(ListNode *l1, ListNode *l2)
{
ListNode * m = new ListNode(0);
ListNode * p = m;
while(l1 || l2)
{
int a = INT_MAX, b = INT_MAX;
if(l1)
a = l1->val;
if(l2)
b = l2->val;
if(a<b)
{
p->next = new ListNode(a);
l1 = l1->next;
}
else
{
p->next = new ListNode(b);
l2 = l2->next;
}
p = p->next;
}
return m->next;
}
}; 注：无。
XX、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:
"((()))", "(()())", "(())()", "()(())", "()()()"
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> output;
combination(output, "", n, n);
return output;
}
void combination(vector<string> &output, string cache, int left, int right)
{
if(left==0 && right==0)
{
output.push_back(cache);
return ;
}
if(left>0)
combination(output, cache+'(', left-1, right);
if(right>left)
combination(output, cache+')', left, right-1);
}
}; 注：无。
XX、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.
class Solution {
public:
bool isValid(string s) {
stack<char> stack1;
for(int i=0;i<s.size();i++)
{
if(!stack1.empty() && ((s[i]==')' && stack1.top()=='(') || (s[i]==']' && stack1.top()=='[') ||(s[i]=='}' && stack1.top()=='{')))
stack1.pop();
else stack1.push(s[i]);
}
if(stack1.empty())
return true;
return false;
}
}; 注：无。
XX、remove-nth-node-from-end-of-list
Given a linked list, remove the n th 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) {
ListNode *m = new ListNode(0);
m->next = head;
ListNode *slow = m, *fast = m;
while(n)
{
fast = fast->next;
n--;
}
while(fast->next)
{
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return m->next;
}
}; 注：设置快慢指针即可。
XX、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.
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> output;
string cache;
vector<string> dict = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
combinations(output, dict, digits, cache, 0);
return output;
}
void combinations(vector<string> &output, vector<string> &dict, string &digits, string cache, int k)
{
if(k==digits.size())
{
output.push_back(cache);
return ;
}
for(int i=0;i<dict[digits[k]-'0'-2].size();i++)
{
cache.push_back(dict[digits[k]-'0'-2][i]);
combinations(output, dict, digits, cache, k+1);
cache.pop_back();
}
}
}; 注：递归就行了。
XX、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) class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
if(num.size()<4)
return {};
vector<vector<int> > output;
sort(num.begin(), num.end());
for(int i=0;i<num.size();i++)
{
if(i!=0 && num[i]==num[i-1])
continue;
for(int j=i+1;j<num.size();j++)
{
if(j!=i+1 && num[j]==num[j-1])
continue;
int left = j+1, right = num.size()-1;
while(left<right)
{
int sum = num[i] + num[j] + num[left] + num[right];
if(sum == target)
{
vector<int> cache{num[i], num[j], num[left], num[right]};
output.push_back(cache);
right--;
left++;
while(left<right && num[right]==num[right+1])
right--;
while(left<right && num[left]==num[left-1])
left++;
}
else if(sum>target)
right--;
else left++;
}
}
}
return output;
}
}; 注：无。
XX、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) {
int temp = INT_MAX, output = 0;
sort(num.begin(), num.end());
for(int i=0;i<num.size();i++)
{
int left = i+1, right = num.size()-1;
while(left<right)
{
int sum = num[i] + num[left] + num[right];
if(abs(sum - target)<temp)
{
output = sum;
temp = abs(sum - target);
}
if(sum>target)
right--;
else left++;
}
}
return output;
}
}; 注：无。
XX、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.
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
if(num.size()<3)
return {};
sort(num.begin(), num.end());
vector<vector<int> > output;
for(int i=0;i<num.size()-2;i++)
{
int target = -num[i];
map<int, int> hash;
if(i>0 && (num[i] == num[i-1]))
continue;
for(int j = i+1;j<num.size();j++)
{
if(hash.find(target-num[j])==hash.end())
hash[num[j]] = 1;
else
{
if(hash[target-num[j]] == 1)
{
vector<int> cache{num[i], target-num[j], num[j]};
output.push_back(cache);
}
hash[target-num[j]]++;;
}
}
}
sort(output.begin(), output.end());
return output;
}
}; 注：第二层循环可以用双指针来做。
XX、longest-common-prefix
Write a function to find the longest common prefix string amongst an array of strings.
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
string output;
if(strs.size()==0)
return output;
string first = strs[0];
for(int i=0;i<first.size();i++)
{
char cache = first[i];
for(int j=1;j<strs.size();j++)
{
if(strs[j].size()<i || strs[j][i]!=cache)
return output;
}
output.push_back(cache);
}
return output;
}
}; 注：无。
XX、roman-to-integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
class Solution {
public:
int romanToInt(string s) {
map<char, int> dict{ {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
int sum = 0;
for(int i=0;i<s.size();i++)
{
if(i+1<s.size() && ((s[i]=='I' &&(s[i+1]=='V'||s[i+1]=='X')) || (s[i]=='X' &&(s[i+1]=='L'||s[i+1]=='C')) || (s[i]=='C' &&(s[i+1]=='D'||s[i+1]=='M'))))
{
sum += dict[s[i+1]] - dict[s[i]];
i++;
}
else sum += dict[s[i]];
}
return sum;
}
}; 注：无。
XX、integer-to-roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
class Solution {
public:
string intToRoman(int num) {
string res = "";
vector<int> val{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
vector<string> str{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
for (int i = 0; i < val.size(); ++i) {
while (num >= val[i]) {
num -= val[i];
res += str[i];
}
}
return res;
}
}; 注：无。
XX、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 container, such that the container contains the most water.
Note: You may not slant the container.
1
注：无。
XX、regular-expression-matching
Implement regular expression matching with support for'.'and'*'.
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if(*s == '\0' && *p == '\0')
return true;
if(*p !='\0' && *(p+1)=='*')
{
if(*s != '\0' && (*s == *p || *p=='.'))
return isMatch(s+1, p) || isMatch(s, p+2) || isMatch(s+1, p+2);
else return isMatch(s, p+2);
}
if(*s != '\0' && (*s == *p || *p=='.'))
return isMatch(s+1, p+1);
return false;
}
}; 注：先判断特殊情况。
139、palindrome-number
Determine whether an integer is a palindrome. Do this without extra space.
1
注：无。
140、string-to-integer-atoi
Sort a linked list in O(n log n) time using constant space complexity.
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
141、string-to-integer-atoi
Implement atoi to convert a string to an integer.
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
142、reverse-integer
Implement atoi to convert a string to an integer.
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
143、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) {
if(s.size()<=nRows ||s.size()==0 || nRows==1)
return s;
string output;
for(int i=0;i<nRows;i++)
{
int stride = 2*nRows-2;
int cache = i;
if(i==0 || i==nRows-1)
{
while(cache<s.size())
{
output += s[cache];
cache += stride;
}
}
else
{
while(cache<s.size())
{
output += s[cache];
cache += stride;
if(cache-2*i<s.size())
output += s[cache-2*i];
}
}
}
return output;
}
}; 注：找规律即可。
144、sort-list
Sort a linked list in O(n log n) time using constant space complexity.
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
145、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) {
if(!l1 && !l2)
return nullptr;
ListNode * m = new ListNode(0);
ListNode * p = m;
int carry = 0;
while(l1 || l2)
{
int a = 0, b = 0;
if(l1)
{
a = l1->val;
l1 = l1->next;
}
if(l2)
{
b = l2->val;
l2 = l2->next;
}
int sum = a + b + carry;
int result = sum%10;
carry = sum/10;
ListNode *cache = new ListNode(result);
p->next = cache;
p = p->next;
}
if(carry)
p->next = new ListNode(carry);
return m->next;
}
}; 注：使用a和b作为哨兵记录l1和l2节点的值。
146、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.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char,int> hash;
int left = 0, cache = 0, maximum = 0;
for(int i=0;i<s.size();i++)
{
if(hash.find(s[i])==hash.end() || hash[s[i]]<left)
{
hash[s[i]] = i;
cache ++;
}
else
{
left = hash[s[i]] + 1;
hash[s[i]] = i;
cache = i - left + 1;
}
maximum = max(maximum, cache);
}
return maximum;
}
}; 注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
147、median-of-two-sorted-arrays
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
1
注：本题需要注意找的是最小深度，只有左右节点全为空才是最小深度。
148、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
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
if(numbers.size()==0)
return {};
map<int,int> hash;
for(int i=0;i<numbers.size();i++)
{
if(hash.find(numbers[i])==hash.end())
hash[target-numbers[i]] = i+1;
else return {hash[numbers[i]], i+1};
}
return {};
}
}; 注：哈希表遍历一遍解决，需要注意这里的index是从1开始。
查看12道真题和解析
