【C++】【LeetCode】2020.5.16~2020.6.30
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode* head = new ListNode();
ListNode* tmp = head;
while(l1 && l2)
{
if (l1->val < l2->val)
{
tmp->next = l1;
l1 = l1->next;
}
else
{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
while (l1)
{
tmp->next = l1;
l1 = l1->next;
tmp = tmp->next;
}
while (l2)
{
tmp->next = l2;
l2 = l2->next;
tmp = tmp->next;
}
return head->next;
}
};
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
class Solution {
public:
void DFS(int l, int r, string s, vector<string> &res)
{
if (l == 0 && r == 0)
{
res.push_back(s);
}
if (l > 0)
{
DFS(l - 1, r, s + "(", res);
}
if (r > 0 && l < r)
{
DFS(l, r - 1, s + ")", res);
}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
DFS(n, n, "", res);
return res;
}
};
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode* head = new ListNode();
ListNode* tmp = head;
while(l1 && l2)
{
if (l1->val < l2->val)
{
tmp->next = l1;
l1 = l1->next;
}
else
{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
while (l1)
{
tmp->next = l1;
l1 = l1->next;
tmp = tmp->next;
}
while (l2)
{
tmp->next = l2;
l2 = l2->next;
tmp = tmp->next;
}
return head->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0)
{
return NULL;
}
//0 1 2 3 4 5 6 7-> 0 2 4 6-> 0 4 -> 0
int step = 1;
while (step < lists.size())
{
for (int i = 0; i < lists.size();i += 2*step)
{
ListNode* left = lists[i];
ListNode* right = NULL;
if (i + step < lists.size())
{
right = lists[i + step];
}
lists[i] = mergeTwoLists(left, right);
}
step *= 2;
}
return lists[0];
}
};
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* pre = new ListNode();
ListNode* first = pre;
pre->next = head;
ListNode *l, *r, *end;
l = head;
while(l)
{
//pre -> l -> r -> end
//pre -> r -> l -> end
//pre = l, l = end
r = l->next;
if (!r) break;
end = r->next;
pre->next = r;
r->next = l;
l->next = end;
pre = l;
l = end;
}
return first->next;
}
};
25. 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.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
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
Note:
Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* res = new ListNode();
res->next = head;
ListNode* pre = res;
while (pre)
{
//先找到所有需要的节点
bool findNull = false;
vector< ListNode*> nodes;
ListNode* tmp = pre->next;
//pre->0->1->2->3->4->end
for (int i = 0; i < k + 1; ++i)
{
//end节点是可以空的
if (i == k)
{
nodes.push_back(tmp);
break;
}
//其他任意节点都不能空
if (!tmp)
{
findNull = true;
break;
}
else
{
nodes.push_back(tmp);
tmp = tmp->next;
}
}
if (findNull)
{
break;
}
//开始移动
//pre->0->1->2->3->4->end ==> pre->1 4->3->2->1->0 end
for (int i = nodes.size() - 2; i > 0; --i)
{
nodes[i]->next = nodes[i - 1];
}
//pre->0 4->3->2->1->0 end ==> pre->1 4->3->2->1->0->end
nodes[0]->next = nodes[nodes.size() - 1];
//pre->0 4->3->2->1->0->end ==> pre->4->3->2->1->0->end
pre->next = nodes[nodes.size() - 2];
//新的pre应该指向end前面
pre = nodes[0];
}
return res->next;
}
};
26. Remove Duplicates from Sorted Array
Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0)
{
return 0;
}
int idx = 1;
int tmpVal = nums[0];
for (int i = 1; i < nums.size(); ++i)
{
if (nums[i] != tmpVal)
{
nums[idx++] = nums[i];
tmpVal = nums[i];
}
}
return idx;
}
};
27. Remove Element
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example 1:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the order of those five elements can be arbitrary.
It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if (nums.size() == 0)
{
return 0;
}
int len = 0;
for (; len < nums.size(); ++len)
{
if (nums[len] == val)
{
int idx = -1;
for (int j = len + 1; j < nums.size(); ++j)
{
if (nums[j] != val)
{
idx = j;
break;
}
}
if (idx == -1)
{
break;
}
nums[len] = nums[idx];
nums[idx] = val;
}
}
return len;
}
};
28. Implement strStr()
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
//试了两种办法，一种是顺序遍历截取直接compare，耗时4ms
//另一种是使用kmp，跳跃compare，耗时8ms
class Solution {
public:
int strStr(string haystack, string needle) {
if (haystack == needle)
{
return 0;
}
if (haystack.size() < needle.size())
{
return -1;
}
for (int i = 0; i <= haystack.size() - needle.size(); ++i)
{
if (haystack.substr(i, needle.size()) == needle)
{
return i;
}
}
return -1;
}
void getNext(string& strs, vector<int> &next)
{
int i = 0;
int j = -1;
next[0] = -1;
while (i < strs.size())
{
if (j == -1 || strs[i] == strs[j])
{
next[++i] = ++j;
}
else j = next[j];
}
}
int strStr_KMP(string haystack, string needle) {
if (haystack == needle) return 0;
if (haystack.size() < needle.size()) return -1;
vector<int> next(needle.size() + 1, 0);
getNext(needle, next);
int i = 0, j = 0;
while (i < haystack.size() && j < int(needle.size()))
{
if (j == -1)
{
++i;
j = 0;
}
else if (haystack[i] == needle[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == needle.size())
{
return i - j;
}
return -1;
}
};
29. Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
Note:
Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.
class Solution {
public:
bool isValid(int val, int flag)
{
if (flag < 0)
{
return val >= INT_MIN;
}
return val <= INT_MAX;
}
int divide(int dividend, int divisor) {
int flag = ((dividend < 0) == (divisor < 0)) ? 1 : -1;
if (divisor == 0)
{
return flag == 1 ? INT_MAX : INT_MIN;
}
if (divisor == 1)
{
return dividend;
}
if (divisor == -1 && dividend == INT_MIN)
{
return INT_MAX;
}
long long divd = abs(dividend);
long long divs = abs(divisor);
int res = 0;
while (divd >= divs)
{
long tmp = divs;
int base = 1;
while (divd > (tmp << 1))
{
base = base << 1;
tmp = tmp << 1;
}
divd -= tmp;
res += base;
}
return flag * res;
}
};
30. Substring with Concatenation of All Words
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
class Solution {
public:
void findStr(const string& s, int index, vector<string>& words, vector<int> &res)
{
map<string, int> wordMap;
vector<int> wordCount(words.size(), 0);
int mapIndex = 0;
for (auto i : words)
{
if (wordMap.find(i) == wordMap.end())
wordMap[i] = mapIndex;
mapIndex++;
wordCount[wordMap[i]]++;
}
int len = words[0].size();
int strLen = len * words.size();
int start = index;
int matchCount = 0;
while (index + len <= s.size())
{
if (matchCount == mapIndex)
{
//a a b a[a b a] ==> a [a b a] (count+1)
//匹配到了,此时index后移，count变化
res.push_back(index);
const string& nowWord = s.substr(index, len);
index += len;
wordCount[wordMap[nowWord]]++;
matchCount--;
continue;
}
const string& nowWord = s.substr(start, len);
if (wordMap.find(nowWord) == wordMap.end())
{
//a a c b[a b a] ==> b [a b a]
//出现了一个不能匹配的单词，之前统计过得单词全部去除
while (index < start)
{
const string& tmpWord = s.substr(index, len);
index += len;
wordCount[wordMap[tmpWord]]++;
matchCount--;
}
//注意这里index和start相等，还要再跳一次
index += len; start = index;
continue;
}
if (wordCount[wordMap[nowWord]] < 1)
{
//a a a b[a b a] ==> a a b [a b a]
//可以匹配，但是次数不够，去除这个单词首次出现位置之前的所有统计
while (s.substr(index, len) != nowWord)
{
wordCount[wordMap[s.substr(index, len)]]++;
index += len;
matchCount--;
}
//注意这里找到了，再位移一次，但是不需要计数
index += len; start += len;
continue;
}
//最后就是常规情况，计数
wordCount[wordMap[nowWord]]--;
start += len;
matchCount++;
}
}
vector<int> findSubstring(string s, vector<string>& words) {
if (words.size() == 0
|| words[0].size() * words.size() > s.size())
{
return {};
}
vector<int> res;
for (int i = 0; i < words[0].size(); ++i)
{
findStr(s, i, words, res);
}
return res;
}
};