1. Quick sort review
Basic idea:
1. Select any element in the current sorting sequence, call it the benchmark element or fulcrum, move all elements equal to the benchmark element to the front of the benchmark element, and move all elements greater than the benchmark element to the back of the benchmark element, so that the position of the benchmark element is exactly the final position of sorting, and divide the current sorting sequence into two sequences.
2. The above process is called one quick sort, that is, one division of quick sort
3. Next, repeat the above sorting operation for the two subsequences respectively (if the subsequence length is greater than 1) until all elements are moved to the final position where they should be after sorting.
The reason why the efficiency is high: each element movement is jumping, not like bubble sorting, and can only be carried out between adjacent elements. The interval of element movement is large, so the total comparison and movement times are reduced
Specific steps:
1. Suppose sequence a, set two variables i and j. to point to the first element and the tail element respectively, and set the first element pointed to by i as the reference element
2. Execute i + + repeatedly until i points to the element > = base element, or i points to the tail
3. Repeat J –, until the pointing element < base element, or j points to the head
4. If i < j at this time, exchange the elements pointed to by i and j. (large elements are behind)
5. After the first exchange, repeat steps 1 and 2 until I > = J
6. At this time, I > = j, and then exchange the position between the reference element and the element pointed to by j. so far, the first division of the original sequence is completed
7. Next, repeat the above operation for the subsequence with a length greater than 1 in the subsequence before and after the reference element.
Step analysis:
The operation of each subsequence is divided again, so this algorithm has the property of recursion.
The reference element of each division process can still be set as the first element of the subsequence
#include<iostream>
#include <vector>
using namespace std;
//Quick sort
void Quicksort(vector<int>& a, int s, int t)
{
int i, j;
if (s < t)
{
//[1] Set two variables i and j. to point to the first element and the tail element respectively, and set the first element pointed to by i as the reference element
i = s;
j = t + 1;
while (1)
{
do i++;
while (!(a[s] <= a[i] || i == t)); //[2] Repeat the i + + operation until i points to the element > = base element, or i points to the tail
do j--;
while (!(a[s] >= a[j] || j == s)); //[3] Repeat J -- until the pointing element is < the reference element, or j points to the head
if (i < j) //[5] If i < j at this time, exchange the elements pointed to by i and j. (large element behind)
{
swap(a[j], a[i]);
}
else break; //[5] After the first exchange, repeat steps 1 and 2 until I > = J
}
//[6] At this time, I > = j, and then exchange the position between the reference element and the element pointed to by j. so far, the first division of the original sequence is completed
swap(a[s], a[j]);
//[7] Next, repeat the above operation for the subsequence with a length greater than 1 in the subsequence before and after the reference element.
Quicksort(a, s, j - 1); //First half sequence
Quicksort(a, j + 1, t); //Second half sequence
}
}
void show_sort_result(vector<int> a, int k)
{
for (int f = 0;f < k;f++)
{
cout << a[f] << " ";
}
printf("\n");
}
int main()
{
vector<int> a = { 98,76,109,34,67,190,80,12,14,89,1 };
printf("Quick sort\n");
Quicksort(a,0,a.size() - 1);
show_sort_result(a, a.size() - 1);
return 0;
}
2. Review of linked list
Linked list definition
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) {}
};
203. Remove linked list elements
Do not use virtual header nodes
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//Delete header node
while(head != nullptr && head->val == val)
{
ListNode* temp = head;
head = head->next;
delete(temp);
}
//Delete non header node
ListNode* cur = head;
while(cur != nullptr && cur->next != nullptr)
{
if(cur->next->val == val)
{
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete(temp);
}
else
{
cur = cur->next;
}
}
return head;
}
};
Use virtual header node:
Note that if a pointer is used, no delete dummy will cause memory leakage.
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while(cur->next != nullptr)
{
if(cur->next->val == val)
{
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
}
else
{
cur = cur->next;
}
}
ListNode* ret = dummyHead->next;
delete dummyHead;
return ret;
}
};
707. Design linked list
Pay attention to the use of virtual head nodes.
class MyLinkedList {
public:
//Defines the structure of the linked list
struct ListNode {
int val;
ListNode* next;
ListNode(int val) : val(val) , next(nullptr) {}
};
private:
//Defines the virtual header node of the linked list
ListNode* _dummyHead;
int _size;
public:
/** Initialize your data structure here. */
MyLinkedList() {
_dummyHead = new ListNode(0);
_size = 0; //Record the number of elements that already exist in the linked list
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
if(index < 0 || index > _size -1)
return -1;
ListNode* cur = _dummyHead->next;
while(index--){
cur = cur->next;
}
return (cur->val);
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
ListNode* cur = _dummyHead; //Note cur from_ dummy starts to prevent the linked list from being empty at the beginning
while(cur->next != nullptr){
cur = cur->next;
}
//Cur - > next is empty
cur->next = newNode;
_size++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if(index > _size) return ;
if(index < 0)
{
addAtHead(val);
return ;
}
ListNode* newNode = new ListNode(val);
ListNode* cur = _dummyHead;
while(index--){
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if(index >= _size || index < 0)
{
return ;
}
ListNode* cur = _dummyHead;
while(index--)
cur = cur->next;
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
_size--;
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
206. Reverse linked list
Note the condition of the while loop and that the final return is pre.
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = nullptr;
while(cur != nullptr)
{
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
142. Circular linked list II
Mathematical derivation:
When meeting:
Number of slow nodes: x+y
Number of nodes passed by fast: x+y+n(y+z)
And there are:
(x+y)*2 = x+y+n(y+z)
When n= 1, x = z:
Namely:
Start a pointer from the beginning node and start a pointer from the meeting node. These two pointers only go to one node at a time. Then when the two pointers meet, they are the nodes of the ring entrance.
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != nullptr && fast->next != nullptr)
{
slow = slow->next;
fast = fast->next->next;
//Fast and slow pointers meet
if(fast == slow)
{
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1 != index2)
{
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return nullptr;
}
};
3. Dichotomy review
Dichotomy variants need to be brushed again for incomplete order
4. Hash review
242. Valid acronyms
https://leetcode-cn.com/problems/valid-anagram/
349. The intersection of two arrays. Pay attention to the use of set. I'm still not familiar with it
https://leetcode-cn.com/problems/intersection-of-two-arrays/
202. Happy number
https://leetcode-cn.com/problems/happy-number/
1. Sum of two numbers. Pay attention to the use of map. You are not very familiar with it. You should be familiar with the insert operation of map
https://leetcode-cn.com/problems/two-sum/submissions/
454. Add four numbers II. Note that count adds all frequencies on the value.
https://leetcode-cn.com/problems/4sum-ii/submissions/
383. Ransom letter, pay attention to which one is added and which one is deducted in the map. If a letter that does not exist in magazine appears in ransomNote, it fails.
https://leetcode-cn.com/problems/ransom-note/
5. Double pointer review
15. Sum of three
https://leetcode-cn.com/problems/3sum/
There are three points to note:
1. For the first time, if the same adjacent element is encountered in the outer for loop, continue
2. For the second de duplication, after finding a triplet every time, it should also be de duplicated until it no longer conforms to left < right
3. After finding an answer, the double pointer shrinks at the same time
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> result;
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] > 0) break;
//For the first time, if the same adjacent element is encountered in the outer for loop, continue
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1;
int right = nums.size() - 1;
while(left < right) //Cannot take=
{
int tmp_sum = nums[i] + nums[left] + nums[right];
if(tmp_sum > 0) right--;
else if(tmp_sum < 0) left++;
else {
result.emplace_back(vector<int>{nums[i],nums[left],nums[right]});
//For the second de duplication, after finding a triplet every time, it should also be de duplicated until it no longer conforms to left < right
while(left < right && nums[right - 1] == nums[right]) right--;
while(left < right && nums[left] == nums[left + 1]) left++;
//After finding an answer, the double pointer shrinks at the same time
left++;
right--;
}
}
}
return result;
}
};
18. Sum of four numbers
https://leetcode-cn.com/problems/4sum/
Points needing attention:
It is divided into three layers of nesting, which is one more layer of circulation than the previous question. So there is one more weight removal in the outermost layer.
If the pruning operation is wrong, you can't prune.
Sum of three:
for{
prune;
duplicate removal;
while(Go again)；
}
Sum of four numbers:
for
{
duplicate removal;
for{
duplicate removal;
while(Go again)；
}
}
27. Remove elements
https://leetcode-cn.com/problems/remove-element/
The point is that fast moves backward all the time (whether the element = = val or not). If it is not equal to, slow also needs to go. When num [fast] = val, slow doesn't go, fast goes.
Then go to the next num [fast]= val, moves the pointed element forward.
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for(int fast = 0; fast < nums.size(); fast++)
{
if(nums[fast] != val)
{
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
344. Reverse the string, which is simple. The double pointer is close to the middle from both sides, and swap at any time
https://leetcode-cn.com/problems/reverse-string/
Sword finger Offer 05 Replace spaces first calculate the expanded size, and then replace spaces from back to front. This is done for array filling questions.
https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
class Solution {
public:
string replaceSpace(string s) {
int count = 0; //Record the number of spaces
int old_size = s.size();
for(int i = 0; i < old_size; i++)
{
if(s[i] == ' ') count++;
}
//Extended s
s.resize(old_size + count * 2);
int new_size = s.size();
//Define two pointers to two positions
int new_index = new_size - 1;
int old_index = old_size - 1;
while(old_index < new_index)
{
if(s[old_index] != ' ')
{
s[new_index] = s[old_index];
}
else
{
s[new_index] = '0';
new_index--;
s[new_index] = '2';
new_index--;
s[new_index] = '%';
}
new_index--;
old_index--;
}
return s;
}
};
151. Turn over the words in the string. This problem needs to be done several more times..
https://leetcode-cn.com/problems/reverse-words-in-a-string/
This problem is a little more complicated in dealing with spaces;
Idea:
1. Remove extra spaces
2. Invert the entire string
3. Invert each word
For example:
"the sky is blue" => "the sky is blue" => "eulb si yks eht" => "blue is sky the"
1. Remove extra spaces and use double pointers
void removeExtraSpaces(string& s)
{
//Define speed pointer
int slow = 0;
int fast = 0;
//Remove spaces before strings
while(s.size() > 0 && fast < s.size() && s[fast] == ' ') fast++;
//Remove the white space in the middle of the string
while(fast < s.size())
{
if(fast > 1 && s[fast] == ' ' && s[fast - 1] == ' ')
{
fast++;
continue;
}
else
{
s[slow] = s[fast];
slow++;
fast++;
}
}
//Remove the spaces at the end of the string and resize the string
if(slow > 1 && s[slow - 1] == ' ')
{
s.resize(slow - 1);
}
else
{
s.resize(slow);
}
}
2. Inverts the string, using double pointers
void reverse(string& s,int left,int right)
{
while(left <= right)
{
swap(s[left],s[right]);
left++;
right--;
}
}
3. Invert each word in the string
string reverseWords(string s) {
removeExtraSpaces(s);
reverse(s,0,s.size() - 1);
int fast = 0;
int slow = 0;
while(fast < s.size())
{
//If you traverse to the middle of the string, one word ends
if(s[fast] == ' ')
{
reverse(s,slow,fast - 1);
//Skip spaces
slow = fast + 1;
}
//If you traverse to the end of the last word (there is no space at this time)
if(fast == s.size() -1)
{
reverse(s,slow,fast);
}
fast++;
}
return s;
}