当前位置：网站首页>[brush questions] top101 must be brushed in the interview of niuke.com
[brush questions] top101 must be brushed in the interview of niuke.com
2022-07-06 08:24:00 【If you dare to fly, you will have the sky】
List of articles
- One 、 Linked list
- 1. Reverse a linked list 【 Simple 】
- 2. Reverse the specified interval in the linked list 【 secondary 】
- 3. Every node in the linked list k Turn over in groups 【 secondary 】
- 4. Merge two ordered linked lists 【 Simple 】
- 5. Merge k Sorted linked list 【 difficult 】
- 6. Judge whether there are links in the list 【 Simple 】
- 7. The entry node of a link in a list 【 secondary 】
- 8. Last in the list k Nodes 【 Simple 】
- 9. Delete the last of the linked list n Nodes 【 secondary 】
- 10. The first common node of two linked lists 【 Simple 】
- 11. " Add the linked list "【 secondary 】
- 12. The sort of single linked list 【 secondary 】
- 13. Determine whether a linked list is palindrome structure 【 Simple 】
- 14. Parity rearrangement of linked list 【 secondary 】
- 15. Delete duplicate elements in the ordered linked list -1【 Simple 】
- 16. Delete duplicate elements in the ordered linked list -2【 secondary 】
- Two 、 Binary search / Sort
- 3、 ... and 、 Binary tree
- 23. Preorder traversal of two tree 【 Simple 】
- 24. Middle order traversal of binary trees 【 secondary 】
- 25. Postorder traversal of binary trees 【 Simple 】
- 26. Sequence traversal of binary tree 【 secondary 】
- 27. Print binary trees in zigzag order 【 secondary 】
- 28. The maximum depth of a binary tree 【 Simple 】
- 29. The path of a value in a binary tree 【 Simple 】
- 30. Binary search tree and double linked list 【 secondary 】
- 31. Symmetric binary tree 【 Simple 】
- 32. Merge binary tree 【 Simple 】
- 33. Image of binary tree 【 Simple 】
- 34. Determine whether it is a binary search tree 【 secondary 】
- 35. Judge whether it is a complete binary tree 【 secondary 】
- 36. Judge whether it is a balanced binary tree 【 Simple 】
- 37. The nearest common ancestor of a binary search tree 【 Simple 】
- 38. Find the nearest common ancestor of two nodes in the binary tree
- Four 、 Pile up / Stack / queue
- 42. Queues are implemented with two stacks 【 Simple 】
- 43. contain min Function of the stack 【 Simple 】
- 44. Valid parenthesis sequence 【 Simple 】
- 45. Maximum sliding window 【 difficult 】
- 46. The smallest K Number 【 secondary 】
- 47. Search for the first K Large number
- 48. Median in data stream
- 49. Expression evaluation
- 5、 ... and 、 Hash
- 7、 ... and 、 Dynamic programming
- 62. Fibonacci sequence 【 introduction 】
- 63. Skip step 【 Simple 】
- 64. Minimum cost of climbing stairs 【 Simple 】
- 65. Longest common subsequence
- 66. The longest public substring
- 67. Number of different paths 【 Simple 】
- 68. The minimum path sum of matrices
- 69. Translate numbers into strings
- 71. Longest ascending subsequence
- 72. The maximum sum of successive subarrays
- 73. Longest text substring
- 74. The number string is converted into IP Address
- 8、 ... and 、 character string
- Nine 、 Double pointer
- 87. Merge two ordered arrays 【 Simple 】
- 88. Determine whether it is a palindrome string 【 introduction 】
- 89. Merge range 【 secondary 】
- 90. Minimum cover substring 【 difficult 】
- 91. Reverse string 【 introduction 】
- 92. Longest non repeating subarray 【 secondary 】
- 93. The container with the most water 【 secondary 】
- 94. The rain problem
- Ten 、 Greedy Algorithm
One 、 Linked list
struct ListNode {
int val;
struct ListNode* next;
ListNode(int x) :
val(x), next(nullptr) {
}
};
1. Reverse a linked list 【 Simple 】
Given the head node of a single linked list pHead, The length is n, After reversing the linked list , Return the header of the new linked list . requirement ： Spatial complexity O(1), Time complexity O(n).
class Solution {
public:
ListNode* ReverseList(ListNode* pHead)
{
ListNode* pre = nullptr;
ListNode* cur = pHead;
ListNode* nex = nullptr;
while (cur)
{
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
};
2. Reverse the specified interval in the linked list 【 secondary 】
Set the number of a node to size Linked list , hold m Position to n Interval reversal between positions , Return to header node , Time complexity required O(n), Spatial complexity O(1). Data range ： Chain length 0 < size ≤1000,0 < m ≤ n ≤ size, The value of each node in the linked list meets ∣val∣ ≤ 1000.
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n)
{
// Add a header
ListNode* res = new ListNode(-1);
res->next = head;
// Preorder node
ListNode* pre = res;
// Current node
ListNode* cur = head;
// find m Node is no.
for (int i = 1; i < m; i++)
{
pre = cur;
cur = cur->next;
}
// from m Node No. is reversed to n Node is no.
for (int i = m; i < n; i++)
{
ListNode* temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
// Return the linked list without the header
return res->next;
}
};
3. Every node in the linked list k Turn over in groups 【 secondary 】
Every node in the given linked list k Turn over in groups , Returns the flipped linked list . If the number of nodes in the linked list is not k Multiple , Leave the last remaining nodes as they are .
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k)
{
// Find the tail of each flip
ListNode* tail = head;
// Traverse k Second to tail
for (int i = 0; i < k; i++)
{
// If not enough k Time to the end of the list , Go straight back to , No flip
if (tail == nullptr)
{
return head;
}
tail = tail->next;
}
// The pre order and current node required for flipping
ListNode* pre = nullptr;
ListNode* cur = head;
// Before reaching the end of the current segment
while (cur != tail)
{
// Flip
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
// The current tail points to the next linked list to be flipped
head->next = reverseKGroup(tail, k);
return pre;
}
};
4. Merge two ordered linked lists 【 Simple 】
Enter two incremental linked lists , The length of a single linked list is n, Merge these two linked lists and make the nodes in the new linked list still be sorted incrementally . requirement ： Spatial complexity O(1), Time complexity O(n)
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == nullptr)
{
return pHead2;
}
if (pHead2 == nullptr)
{
return pHead1;
}
// Header
ListNode* result = new ListNode(-1);
ListNode* cur = result;
while (pHead1 && pHead2)
{
if (pHead1->val <= pHead1->val)
{
cur->next = pHead1;
pHead1 = pHead1->next;
}
else
{
cur->next = pHead2;
pHead2 = pHead2->next;
}
cur = cur->next;
}
if (pHead1)
{
cur->next = pHead1;
}
else
{
cur->next = pHead2;
}
return result->next;
}
};
5. Merge k Sorted linked list 【 difficult 】
Merge k An ascending linked list and return the result to its head node as an ascending linked list . The length of each linked list meets 1 ≤ len ≤ 200, requirement ： Time complexity O(nlogk)
class Solution {
public:
struct Compare
{
// Heavy load small top heap comparison mode
bool operator()(ListNode* a, ListNode* b)
{
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists)
{
// Small cap pile
priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
// Add all nodes to the small top heap
for (int i = 0; i < lists.size(); i++)
{
if (lists[i] != nullptr)
{
pq.push(lists[i]);
}
}
// Header
ListNode* res = new ListNode(-1);
ListNode* cur = res;
while (!pq.empty())
{
// Take the top of the pile
ListNode* temp = pq.top();
pq.pop();
cur->next = temp;
cur = cur->next;
// Take the next element after this node and add it to the small top heap
if (temp->next != nullptr)
{
pq.push(temp->next);
}
}
return res->next;
}
};
6. Judge whether there are links in the list 【 Simple 】
Judge whether there is a ring in a given linked list （ look for NULL）. If there is a ring, return true, Otherwise return to false. Double pointer Speed pointer ： Access a linked list in the same direction . Double pointer Collide with the pointer ： Scan in the opposite direction .
class Solution {
public:
bool hasCycle(ListNode* head)
{
// Quick pointer Move two steps
ListNode* fast = head;
// Slow pointer Move a step
ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
// There is a ring when you meet
if (fast == slow)
{
return true;
}
}
// acyclic , The fast pointer will arrive at the end of the list first
return false;
}
};
7. The entry node of a link in a list 【 secondary 】
Give a length of n Linked list , If it contains rings , Please find the entry node of the link of the list , otherwise , return NULL. requirement ： Spatial complexity O(1), Time complexity O(n)
Before the slow pointer enters the link , Quick, the pointer has entered the ring , And circulate inside , Only after the slow pointer enters the ring , The fast pointer catches up with the slow pointer , Suppose the fast pointer walks in the ring n circle , The slow pointer walked in the ring m circle , They just met , The distance before entering the ring is x, The distance from the ring entrance to the meeting point is y, The distance from the meeting point to the ring entrance is z. Come on, the pointer is gone x+n(y+z)+y Step , The slow pointer has gone x+m(y+z)+y, At this time, the multiple of the fast pointer is twice that of the slow pointer , be x+n(y+z)+y=2(x+m(y+z)+y), Now x+y=(n−2m)(y+z), Because the size of the ring is y+z, explain The distance from the chain header through the ring entrance to the meeting place is equal to the size of the integer multiple ring .
- Determine if the list has links , And find the node that meets .
- The slow pointer is at the encounter node , Quick pointer back to the chain header , The two pointers synchronously start to traverse the linked list one by one .
- The place where we meet again is the entrance of the ring .
class Solution {
public:
ListNode* hasCycle(ListNode* head)
{
// Quick pointer Move two steps
ListNode* fast = head;
// Slow pointer Move a step
ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
// There is a ring when you meet
if (fast == slow)
{
return slow;
}
}
// acyclic
return nullptr;
}
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* ptr1 = pHead;
ListNode* ptr2 = hasCycle(pHead);
if (!ptr2)
{
return nullptr;
}
while (ptr1 != ptr2)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr1;
}
};
8. Last in the list k Nodes 【 Simple 】
Enter a length of n The linked list of , Set the value of the element in the linked list to ai , Returns the penultimate... In the linked list k Nodes . If the length of the list is less than k, Please return a length of 0 The linked list of .
- Prepare a quick pointer , From the head of the chain , Go first on the list k Step
- Prepare the slow pointer to point to the original chain header , Represents the current element , Then the distance between the slow pointer and the fast pointer is always k
- The speed pointer moves synchronously , When the fast pointer reaches the end of the list , The slow pointer just counts down k The location of the elements
class Solution {
public:
ListNode* FindKthToTail(ListNode* pHead, int k)
{
// Quick pointer
ListNode* fast = pHead;
// Slow pointer
ListNode* slow = pHead;
// Go ahead k Step
for (int i = 0; i < k; i++)
{
if (fast != nullptr)
{
fast = fast->next;
}
// The linked list is too short , No penultimate k Nodes
else
{
return slow = nullptr;
}
}
// Fast and slow pointer synchronization , Go to the end first , The slow pointer points to the penultimate k individual
while (fast != nullptr)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
9. Delete the last of the linked list n Nodes 【 secondary 】
Given a linked list , Delete the last of the linked list n A node and returns the header pointer of the linked list . Title assurance n It must be effective .
- Add a header to the linked list , It is convenient to delete the first element .
- Prepare a quick pointer , Go first on the list n Step .
- Prepare the slow pointer to point to the original chain header , Represents the current element , The preamble node points to the added header , So the distance between the two pointers is always n.
- The speed pointer moves synchronously , When the fast pointer reaches the end of the list , The slow pointer just counts down n The location of the elements .
- Finally, point the pointer of the previous node of this node to the next node after this node , Delete this node .
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
// Add header
ListNode* res = new ListNode(-1);
res->next = head;
// Current node
ListNode* cur = head;
// Preorder node
ListNode* pre = res;
ListNode* fast = head;
// Go ahead n Step
while (n--)
{
fast = fast->next;
}
// Fast and slow pointer synchronization , The fast pointer reaches the end , Slow pointer to the penultimate n A place
while (fast != nullptr)
{
fast = fast->next;
pre = cur;
cur = cur->next;
}
// Delete the node at this location
pre->next = cur->next;
// Return to the U-turn node
return res->next;
}
};
10. The first common node of two linked lists 【 Simple 】
Enter two acyclic one-way linked lists , Find their first common node , If there is no public node, null is returned .
Give Way N1 and N2 Traverse together , When N1 Finish the linked list first 1, From the linked list 2 The head node of continues to traverse , Again , If N2 Finish the linked list first 2, From the linked list 1 The head node of continues to traverse . Because two pointers , The same speed , After walking the same length （ Linked list 1+ Linked list 2）, Whether the two linked lists have the same node or not , Can reach the end at the same time .
- When there are public nodes ,N1 and N2 Will meet , Because it's the same length , The speed must be , Will go to the same place , So when the two are equal , The first public node
- When there are no public nodes , here N1 and N2 Will come to the end , So they are all NULL, So it's equal .
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == nullptr || pHead2 == nullptr)
{
return nullptr;
}
ListNode* ptr1 = pHead1;
ListNode* ptr2 = pHead2;
while (ptr1 != ptr2)
{
if (ptr1 == nullptr)
{
ptr1 = pHead2;
}
else
{
ptr1 = ptr1->next;
}
if (ptr2 == nullptr)
{
ptr2 = pHead1;
}
else
{
ptr2 = ptr2->next;
}
}
return ptr1;
}
};
11. “ Add the linked list ”【 secondary 】
Suppose that the value of each node in the linked list is 0 - 9 Between , Then the whole list can represent an integer . Given two such linked lists , Please generate a linked list of results representing the added values of two integers .
- Any linked list is empty , Return to another linked list .
- Reverse the two linked lists to be added .
- Set the chain header of the return linked list , Set carry carry=0.
- Traverse the two linked lists from scratch , Until two linked list nodes are empty and carry Not for 1. Take out the non empty linked list node value every time , If it is empty, it is set to 0, Combine two numbers with carry Add up , Then check whether to carry , The result after rounding （ Yes 10 modulus ） Add a new linked list node , Connect after the return linked list , And continue to traverse back .
- Reverse the linked list of results before returning .
class Solution {
public:
// Reverse a linked list
ListNode* ReverseList(ListNode* pHead)
{
ListNode* pre = nullptr;
ListNode* cur = pHead;
ListNode* nex = nullptr;
while (cur)
{
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
ListNode* addInList(ListNode* head1, ListNode* head2)
{
// Any linked list is empty , Go back to the other
if (!head1)
{
return head2;
}
if (!head2)
{
return head1;
}
// Reverse two linked lists
head1 = ReverseList(head1);
head2 = ReverseList(head2);
// Add header
ListNode* res = new ListNode(-1);
ListNode* cur = res;
// Carry symbol
int carry = 0;
// A linked list is not empty or the carry is not zero
while (head1 || head2 || carry != 0)
{
// If the linked list is not empty, its value is taken
int val1 = (head1 == nullptr) ? 0 : head1->val;
int val2 = (head2 == nullptr) ? 0 : head2->val;
// Add up
int temp = val1 + val2 + carry;
// Get carry
carry = temp / 10;
// Get the bit result
temp %= 10;
// Additive elements
cur->next = new ListNode(temp);
cur = cur->next;
// Move next
if (head1 != nullptr)
{
head1 = head1->next;
}
if (head2 != nullptr)
{
head2 = head2->next;
}
}
// The result is reversed
return ReverseList(res->next);
}
};
12. The sort of single linked list 【 secondary 】
Given the number of nodes is n Unordered single linked list , Sort them in ascending order .
class Solution {
public:
// Merge the two ordered linked lists into an ordered linked list
ListNode* merge(ListNode* pHead1, ListNode* pHead2)
{
// Any linked list is empty , Go back to the other
if (pHead1 == nullptr)
{
return pHead2;
}
if (pHead2 == nullptr)
{
return pHead1;
}
// Add a header
ListNode* head = new ListNode(-1);
ListNode* cur = head;
// Neither of the two linked lists should be empty
while (pHead1 && pHead2)
{
// Nodes with smaller values
if (pHead1->val <= pHead2->val)
{
cur->next = pHead1;
pHead1 = pHead1->next;
}
else
{
cur->next = pHead2;
pHead2 = pHead2->next;
}
// Pointer backward
cur = cur->next;
}
// The remaining linked list is directly connected behind
if (pHead1)
{
cur->next = pHead1;
}
if (pHead2)
{
cur->next = pHead2;
}
// The return value removes the header
return head->next;
}
ListNode* sortInList(ListNode* head)
{
// The list is empty or has only one element , Direct is orderly
if (head == nullptr || head->next == nullptr)
{
return head;
}
ListNode* pre = nullptr;
ListNode* slow = head;
ListNode* fast = head;
// Find the midpoint of the linked list
while (fast && fast->next)
{
pre = pre->next;
slow = slow->next;
fast = fast->next->next;
}
// The linked list is disconnected from the midpoint
pre->next = nullptr;
// Sort in two sections , Merge the ordered two paragraphs
return merge(sortInList(head), sortInList(slow));
}
};
13. Determine whether a linked list is palindrome structure 【 Simple 】
Palindrome means that the positive and negative order of the string are completely consistent .
- Slow pointer goes one node at a time , Fast pointer goes two nodes at a time , When the fast pointer reaches the end of the list , The slow pointer just reached the midpoint of the linked list .
- From the midpoint , Start to reverse the second half of the linked list .
- Left and right hands , The left pointer traverses backward from the chain header , The right pointer traverses from the end of the linked list to the front after inversion , Compare the values encountered in turn .
class Solution {
public:
// Reverse a linked list
ListNode* reverse(ListNode* head)
{
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* nex = nullptr;
while (cur)
{
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
bool isPail(ListNode* head)
{
if (head == nullptr)
{
return true;
}
// Speed pointer
ListNode* fast = head;
ListNode* slow = head;
// Double pointer to find the midpoint
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
// Reverse at the midpoint
ListNode* ptr1 = reverse(slow);
ListNode* ptr2 = head;
while (ptr1 && ptr2)
{
if (ptr1->val != ptr2->val)
{
return false;
}
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return true;
}
};
14. Parity rearrangement of linked list 【 secondary 】
Given a single chain table , Please set a function , Put the odd and even nodes of the linked list together , Output after rearrangement . Note that it is the number of the node, not the value of the node .
- If the list is empty , No rearrangement .
- Use double pointer odd and even Traverse odd and even nodes respectively , And give a header to the even node linked list .
- The above process , Traverse two nodes at a time , And even rearwards , Therefore, each round of circulation even Check whether the last two elements are NULL, If the above connection process is not carried out for re-entry cycle .
- Connect the even node head after the last odd node , Then return to the head .
class Solution {
public:
ListNode* oddEvenList(ListNode* head)
{
// Linked list is empty.
if (head == nullptr)
{
return head;
}
// Even pointer
ListNode* even = head->next;
// Odd pointer
ListNode* odd = head;
// Even sequence header
ListNode* evenhead = even;
while (even && even->next)
{
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
// A whole with an even subscript is followed by an odd subscript
odd->next = evenhead;
return head;
}
};
15. Delete duplicate elements in the ordered linked list -1【 Simple 】
Delete the duplicate elements in the given linked list （ The elements in the linked list are ordered from small to large ）, Make all elements in the linked list appear only once 
- Empty linked list is returned directly without processing .
- Use a pointer to traverse the linked list , If the current node of the pointer has the same value as the next node , Let's skip the next node , The current node is directly connected to the next node .
- If the value of the current node is different from that of the next node , Continue to traverse back .
- Two node values are used each time during the cycle , To check whether two consecutive nodes are empty .
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
// Empty list
if (head == nullptr)
{
return nullptr;
}
// Traversal pointer
ListNode* cur = head;
// The current and next bits of the pointer are not empty
while (cur && cur->next)
{
// If the current is equal to the next bit, the next bit is ignored
if (cur->val == cur->next->val)
{
cur->next = cur->next->next;
}
// Otherwise, the pointer traverses normally
else
{
cur = cur->next;
}
}
return head;
}
};
16. Delete duplicate elements in the ordered linked list -2【 secondary 】
Give a linked list in ascending order , Delete all duplicate elements in the linked list , Only keep the elements that appear only once in the original linked list .
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
// Empty list
if (head == nullptr)
{
return nullptr;
}
// Add header
ListNode* res = new ListNode(-1);
res->next = head;
ListNode* cur = res;
while (cur->next && cur->next->next)
{
// Two adjacent nodes with the same value are encountered
if (cur->next->val == cur->next->next->val)
{
int temp = cur->next->val;
// Skip all the same
while (cur->next != nullptr && cur->next->val == temp)
{
cur->next = cur->next->next;
}
}
else
{
cur = cur->next;
}
}
// Remove the header when returning
return res->next;
}
};
Two 、 Binary search / Sort
17. Two points search
Given an element in ascending order 、 An integer array without duplicate numbers nums And a target value target , Write a function search nums Medium target, If the target value has a return subscript （ Subscript from 0 Start ）, Otherwise return to -1
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target)
{
int low = 0;
int high = nums.size() - 1;
while (high >= low)
{
int mid = (low + high) / 2;
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] > target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
};
18. Binary search two-dimensional array
In a two-dimensional array array in （ Each one-dimensional array has the same length ）, Each row is sorted in ascending order from left to right , Each column is sorted in ascending order from top to bottom . Please complete a function , Enter such a two-dimensional array and an integer , Determine whether the array contains the integer .
- First, get the two side lengths of the matrix , Judge special cases .
- First, take the lower left corner as the starting point , If it is smaller than the target element , Then move to the right to find the big , If it is larger than the target element , Then move up to find the small .
- If you move to the matrix boundary, you can't find it , It indicates that there is no target value in the matrix .
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool Find(int target, vector<vector<int> > array)
{
if (array.size() == 0)
{
return false;
}
if (array[0].size() == 0)
{
return false;
}
// That's ok
int n = array.size();
// Column
int m = array[0].size();
// Start from the element in the bottom left corner and go right or up
for (int i = n - 1, j = 0; i >= 0 && j < m; )
{
// Large element , Go up
if (array[i][j] > target)
{
i--;
}
// The elements are smaller , Go to the right
else if (array[i][j] < target)
{
j++;
}
else
{
return true;
}
}
return false;
}
};
19. Looking for peaks
Given a length of n Array of nums, Please find the peak and return its index . The array may contain multiple peaks , under these circumstances , Just return to any location . The peak element refers to the element whose value is strictly greater than the left and right adjacent values , Strictly greater than means that there can be no equal to . hypothesis nums[-1] = nums[n] = −∞.
- Binary search starts from the beginning and end of the array , Take the middle value every time , Until they meet .
- If the element with the middle value is larger than the element to its right , That means right is down , We don't have to meet peaks , Then shrink the range to the left .
- If the middle value is less than the element on the right , It means that the right side is upward , There must be a crest up , Let's shrink the range to the right .
- The point where the last interval meets at the end must be the crest .
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
// Dichotomy
while (left < right) {
int mid = (left + right) / 2;
// On the right is down , There may not be a slope peak
if (nums[mid] > nums[mid + 1])
right = mid;
// On the right is up , You'll find the crest
else
left = mid + 1;
}
// One of the peaks
return right;
}
};
20. Reverse pairs in arrays
21. Minimum number of rotation array
There is a length of n Non descending array of , such as [1,2,3,4,5], Rotate it , That is, move the first elements of an array to the end of the array , Into a rotating array , For example, it became [3,4,5,1,2], perhaps [4,5,1,2,3] In this way . Excuse me, , Given such a rotation array , Find the minimum value in the array .
22. Compare version number
The version number consists of the revision number , There is a between the revision number and the revision number "." Connect .1 A revision number may consist of multiple digits , The revision number may contain a leading 0, And it's legal . for example ,1.02.11,0.1,0.2 Are legal version numbers . Each version number contains at least 1 Revision number . The revision number is numbered from left to right , Subscript from 0 Start , The leftmost revision number is subscript 0, The next revision number is subscript 1, And so on .
Compare the rules ：
One . When comparing version numbers , Please compare their revision numbers from left to right . When comparing revision numbers , Just compare integer values after ignoring any leading zeros . such as "0.1" and "0.01" The version number of is equal
Two . If the version number does not specify a revision number at a subscript , Then the amendment number shall be deemed to be 0. for example ,“1.1" The version number of is less than "1.1.1”. because "1.1" The version number of is equivalent to "1.1.0", The first 3 The subscript of the digit revision number is 0, Less than 1
3、 ... and . version1 > version2 return 1, If version1 < version2 return -1, Or return to 0.
#include <iostream>
#include <string>
using namespace std;
struct ListNode
{
int val;
struct ListNode* next;
ListNode(int x) :
val(x), next(nullptr) {
}
};
class Solution {
public:
int compare(string version1, string version2)
{
int n1 = version1.size();
int n2 = version2.size();
int i = 0, j = 0;
// Until the end of all strings
while (i < n1 || j < n2)
{
long long num1 = 0;
// From the next “.” Front intercept number
while (i < n1 && version1[i] != '.')
{
num1 = num1 * 10 + (version1[i] - '0');
i++;
}
// skip “.”
i++;
long long num2 = 0;
// From the next “.” Front intercept number
while (j < n2 && version2[j] != '.')
{
num2 = num2 * 10 + (version2[j] - '0');
j++;
}
// skip “.”
j++;
// Compare the numbers
if (num1 > num2)
{
return 1;
}
if (num1 < num2)
{
return -1;
}
}
// Same version number
return 0;
}
};
3、 ... and 、 Binary tree
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
}
};
23. Preorder traversal of two tree 【 Simple 】
// recursive
class Solution {
public:
void preorder(vector<int>& res, TreeNode* root)
{
// If an empty node is encountered, it returns
if (root == nullptr)
{
return;
}
// The root node
res.push_back(root->val);
// The left subtree
preorder(res, root->left);
// Right subtree
preorder(res, root->right);
}
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> res;
// Recursive preamble traversal
preorder(res, root);
return res;
}
};
Non recursive version of binary tree preorder traversal
- Priority to determine whether the tree is empty , Empty tree does not traverse .
- Prepare auxiliary stack , First record the root node .
- Pop up one element from the stack at a time , Visit , Then verify whether the left and right child nodes of the node exist , Add the stored words to the stack , Join the right node first .
// Non recursive
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> res;
// Empty tree
if (root == nullptr)
{
return res;
}
// Auxiliary stack
stack<TreeNode*> s;
// The root node is advanced
s.push(root);
// Until there are no nodes in the stack
while (!s.empty())
{
// Every time the top of the stack is accessed
TreeNode* node = s.top();
s.pop();
res.push_back(node->val);
// If there are right child nodes on the right side, they will be put into the stack
if (node->right)
{
s.push(node->right);
}
// If there are left child nodes on the left side of the stack
if (node->left)
{
s.push(node->left);
}
}
return res;
}
};
24. Middle order traversal of binary trees 【 secondary 】
// recursive
class Solution {
public:
void inorder(vector<int>& res, TreeNode* root) {
// If an empty node is encountered, it returns
if (root == nullptr)
{
return;
}
// The left subtree
inorder(res, root->left);
// The root node
res.push_back(root->val);
// Right subtree
inorder(res, root->right);
}
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> res;
// Recursive middle order traversal
inorder(res, root);
return res;
}
};
A non recursive version of the middle order traversal of a binary tree
- Priority to determine whether the tree is empty , Empty tree does not traverse .
- Prepare auxiliary stack , When the binary tree node is empty and there is no node in the stack , We'll stop visiting .
- Start at the root node , Each time you enter the left most node of the subtree , We keep adding it to the stack , Used to save the parent question .
- Reach the far left rear , Can start accessing , If it has a right node , Then add the right side to the stack , After that, the access of the right subtree is also given priority to the leftmost .
// Non recursive
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> res;
// Auxiliary stack
stack<TreeNode*> s;
// When the tree node is not empty or there are nodes in the stack
while (root != nullptr || !s.empty())
{
// Every time the leftmost node is found
while (root != nullptr)
{
s.push(root);
root = root->left;
}
// Access the node
TreeNode* node = s.top();
s.pop();
res.push_back(node->val);
// Enter the right node
root = node->right;
}
return res;
}
};
25. Postorder traversal of binary trees 【 Simple 】
class Solution {
public:
void postorder(vector<int>& res, TreeNode* root)
{
// If an empty node is encountered, it returns
if (root == nullptr)
{
return;
}
// The left subtree
postorder(res, root->left);
// Right subtree
postorder(res, root->right);
// The root node
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> res;
// Recursive postorder traversal
postorder(res, root);
return res;
}
};
The non recursive version of post order traversal of binary tree
- Open up an auxiliary stack , Used to record the child nodes to be accessed , Open up a preamble pointer pre.
- Start at the root node , Each time you enter the left most node of the subtree , We keep adding it to the stack , Used to save the parent question .
- Pop up a stack element , As the root of the subtree , Judge whether there is a node on the right side of the root or whether it has been accessed , If there is no right node or Have been interviewed , You can access this root , And mark the preamble node as the root .
- If not visited , Then this root must be put in the stack , Enter the right subtree and continue to visit , Only when the right subtree ends and returns here can we continue to access the root .
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> res;
// Auxiliary stack
stack<TreeNode*> s;
TreeNode* pre = nullptr;
while (root != nullptr || !s.empty())
{
// Find the leftmost node first every time
while (root != nullptr)
{
s.push(root);
root = root->left;
}
// Pop up the top of the stack
TreeNode* node = s.top();
s.pop();
// If the right side of the element is not or has been accessed
if (node->right == nullptr || node->right == pre)
{
// Access the middle node
res.push_back(node->val);
// And recorded as having visited
pre = node;
}
else
{
// The node is stacked
s.push(node);
// First visit the right
root = node->right;
}
}
return res;
}
};
26. Sequence traversal of binary tree 【 secondary 】
class Solution {
public:
vector<vector<int>> preorderTraversal(TreeNode* root)
{
vector<vector<int>> res;
// Empty tree
if (root == nullptr)
{
return res;
}
// Secondary queue
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int size = q.size();
// Record a layer of the binary tree
vector<int> temp;
for (int i = 0; i < size; i++)
{
TreeNode* node = q.front();
q.pop();
temp.push_back(node->val);
// If left and right children exist , Then save the left and right children as the next level
if (node->left != nullptr)
{
q.push(node->left);
}
if (node->right != nullptr)
{
q.push(node->right);
}
}
res.push_back(temp);
}
return res;
}
};
27. Print binary trees in zigzag order 【 secondary 】
Given a binary tree , Returns the zigzag of the binary tree , That is, the first floor is from left to right , The next floor is from right to left , All the time .
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>> res;
// Empty tree
if (pRoot == nullptr)
{
return res;
}
// Secondary queue
queue<TreeNode*> q;
q.push(pRoot);
// Sign a
bool flag = false;
while (!q.empty())
{
// Record a row of a binary tree
vector<int> temp;
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode* node = q.front();
q.pop();
temp.push_back(node->val);
if (node->left != nullptr)
{
q.push(node->left);
}
if (node->right != nullptr)
{
q.push(node->right);
}
}
if (flag)
{
reverse(temp.begin(), temp.end());
}
// The flag bit is reversed
flag = !flag;
res.push_back(temp);
}
return res;
}
};
28. The maximum depth of a binary tree 【 Simple 】
Find the maximum depth of a given binary tree , Depth refers to the number of nodes on the path from the root node of the tree to any leaf node . The maximum depth is the maximum depth of all leaf nodes .（ notes ： A leaf node is a node that has no children ）
// recursive
class Solution {
public:
int maxDepth(TreeNode* root)
{
// Empty nodes have no depth
if(root == nullptr)
{
return 0;
}
// Returns the subtree depth +1
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
// Level traversal
class Solution {
public:
int maxDepth(TreeNode* root)
{
// Empty tree
if (root == NULL)
{
return 0;
}
// Secondary queue
queue<TreeNode*> q;
// Root in line
q.push(root);
// Record the depth
int res = 0;
// Level traversal
while (!q.empty())
{
// Record how many nodes there are in the current layer
int n = q.size();
// Traverse this layer , Go on to the next floor
for (int i = 0; i < n; i++)
{
TreeNode* node = q.front();
q.pop();
// Add the left and right nodes of the next layer
if (node->left)
{
q.push(node->left);
}
if (node->right)
{
q.push(node->right);
}
}
// depth +1
res++;
}
return res;
}
};
29. The path of a value in a binary tree 【 Simple 】
Given a binary tree root And a value sum , To determine if there is From the root node to the leaf node The sum of the node values of is equal to sum The path of .
1. The problem path is defined as the node passing from the root node of the tree to the leaf node
2. A leaf node is a node that has no children
3. Path can only be from parent node to child node , Cannot from child node to parent node
4. The total number of nodes is n
// Stack + Depth-first search
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum)
{
// Empty tree
if (root == nullptr)
{
return false;
}
// Auxiliary stack
stack<pair<TreeNode*, int>> s;
// Root node stack
s.push({
root, root->val });
while (!s.empty())
{
auto temp = s.top();
s.pop();
// Leaf node and path sum equals sum
if (temp.first->left == nullptr && temp.first->right == nullptr && temp.second == sum)
{
return true;
}
// Left node in stack
if (temp.first->left != nullptr)
{
s.push({
temp.first->left, temp.second + temp.first->left->val });
}
// Right node in the stack
if (temp.first->right != nullptr)
{
s.push({
temp.first->right, temp.second + temp.first->right->val });
}
}
return false;
}
};
30. Binary search tree and double linked list 【 secondary 】
Enter a binary search tree , The binary search tree is transformed into a sorted double linked list , namely ： Binary search tree is transformed into a bidirectional linked list with increasing order . It is required that no new nodes can be created , You can only adjust the direction of the node pointer in the tree . As shown in the figure below ：
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
// Empty tree
if (pRootOfTree == nullptr)
{
return nullptr;
}
// Auxiliary stack
stack<TreeNode*> s;
TreeNode* head = nullptr;
TreeNode* pre = nullptr;
// Is it the first time to the left
bool isFirst = true;
while (pRootOfTree != nullptr || !s.empty())
{
// Until there is no left node
while (pRootOfTree != nullptr)
{
s.push(pRootOfTree);
pRootOfTree = pRootOfTree->left;
}
pRootOfTree = s.top();
s.pop();
// First place
if (isFirst)
{
head = pRootOfTree;
pre = head;
isFirst = false;
}
else
{
pre->right = pRootOfTree;
pRootOfTree->left = pre;
pre = pRootOfTree;
}
pRootOfTree = pRootOfTree->right;
}
return head;
}
};
31. Symmetric binary tree 【 Simple 】
Given a binary tree , Judge whether it is symmetrical . Must contain empty nodes ！
// Level traversal
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
// Empty tree
if (pRoot == nullptr)
{
return true;
}
// Secondary queue
queue<TreeNode*> q1;
queue<TreeNode*> q2;
q1.push(pRoot->left);
q2.push(pRoot->right);
while (!q1.empty() && !q2.empty())
{
// Pop up nodes from the left and right respectively
TreeNode* left = q1.front();
q1.pop();
TreeNode* right = q2.front();
q2.pop();
// Are empty and temporarily symmetric
if (left == nullptr && right == nullptr)
{
continue;
}
// If one is empty or the numbers are not equal, it will be asymmetric
if (left == nullptr || right == nullptr || left->val != right->val)
{
return false;
}
// Join the queue from left to right
q1.push(left->left);
q1.push(left->right);
// Join the queue from right to left
q2.push(right->right);
q2.push(right->left);
}
// They are all symmetrical after inspection
return true;
}
};
32. Merge binary tree 【 Simple 】
Two binary trees are known , Merge them into a binary tree . The consolidation rule is ： All existing nodes , Just add up the node values , Otherwise, the empty position will be replaced by the node of another tree . for example ：
// Level traversal
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2)
{
// Empty tree
if (t1 == nullptr)
{
return t2;
}
if (t2 == nullptr)
{
return t1;
}
// Merge the root node
TreeNode* head = new TreeNode(t1->val + t2->val);
// The secondary queue of the merged tree
queue<TreeNode*> q;
// Auxiliary queue of two trees to be merged
queue<TreeNode*> q1;
queue<TreeNode*> q2;
q.push(head);
q1.push(t1);
q2.push(t2);
while (!q1.empty() && !q2.empty())
{
TreeNode* node = q.front(), * node1 = q1.front(), * node2 = q2.front();
q.pop();
q1.pop();
q2.pop();
TreeNode* left1 = node1->left, * left2 = node2->left, * right1 = node1->right, * right2 = node2->right;
// The left node
if (left1 || left2)
{
// Both left nodes exist
if (left1 && left2)
{
TreeNode* left = new TreeNode(left1->val + left2->val);
node->left = left;
// New nodes are queued
q.push(left);
q1.push(left1);
q2.push(left2);
}
// There is only one left node
else if (left1)
{
node->left = left1;
}
else if (left2)
{
node->left = left2;
}
}
// Right node
if (right1 || right2)
{
// Right nodes exist
if (right1 && right2)
{
TreeNode* right = new TreeNode(right1->val + right2->val);
node->right = right;
// New nodes are queued
q.push(right);
q1.push(right1);
q2.push(right2);
}
// There is only one right node
else if (right1)
{
node->right = right1;
}
else
{
node->right = right2;
}
}
}
return head;
}
};
33. Image of binary tree 【 Simple 】
Operate a given binary tree , Transform it into a mirror image of the source binary tree .
- Check the empty tree first .
- Use the stack to help traverse the binary tree , The root node is advanced .
- During the traversal process, one element in the stack will pop up each time , Then the left and right nodes of the node are stacked respectively .
- At the same time, we exchange the values of the two child nodes on the stack , Because the child nodes have been put on the stack and then exchanged , I'm not afraid that there will be no exchange in the future .
// Stack
class Solution {
public:
TreeNode* Mirror(TreeNode* pRoot)
{
// Empty tree
if (pRoot == nullptr)
{
return nullptr;
}
// Auxiliary stack
stack<TreeNode*> s;
// The root node is advanced
s.push(pRoot);
while (!s.empty())
{
TreeNode* node = s.top();
s.pop();
// Left and right nodes are stacked
if (node->left != nullptr)
{
s.push(node->left);
}
if (node->right != nullptr)
{
s.push(node->right);
}
// Exchange left and right
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
}
return pRoot;
}
};
34. Determine whether it is a binary search tree 【 secondary 】
The binary search tree satisfies that all nodes on the left subtree of each node are strictly smaller than the current node, and all nodes on the right subtree are strictly larger than the current node .
// In the sequence traversal
class Solution {
public:
bool isValidBST(TreeNode* root)
{
// Set stack for traversal
stack<TreeNode*> s;
TreeNode* head = root;
// Record the result of sequence traversal
vector<int> res;
while (head != nullptr || !s.empty())
{
// Until there is no left node
while (head != nullptr)
{
s.push(head);
head = head->left;
}
head = s.top();
s.pop();
// Access to the node
res.push_back(head->val);
head = head->right;
}
// Traverse the middle order result
for (int i = 1; i < res.size(); i++)
{
// Once there is a descending order , It's not a search tree
if (res[i - 1] > res[i])
{
return false;
}
}
return true;
}
};
35. Judge whether it is a complete binary tree 【 secondary 】
The definition of a complete binary tree ： If the depth of the binary tree is h, In addition to h Out of layer , The number of nodes in other layers reaches the maximum , The first h All leaf nodes of the layer are continuously concentrated on the far left , This is a completely binary tree .
// Level traversal
class Solution {
public:
bool isCompleteTree(TreeNode* root)
{
// Empty tree
if (root == nullptr)
{
return true;
}
// Secondary queue
queue<TreeNode*> q;
// The root node accesses
q.push(root);
// Define a marker bit that appears for the first time
bool flag = false;
// Level traversal
while (!q.empty())
{
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode* cur = q.front();
q.pop();
// The tag encounters an empty node for the first time
if (cur == nullptr)
{
flag = true;
}
else
{
// An empty node has been encountered , There are leaf nodes for subsequent visits
if (flag)
{
return false;
}
q.push(cur->left);
q.push(cur->right);
}
}
}
return true;
}
};
36. Judge whether it is a balanced binary tree 【 Simple 】
Balanced binary tree has the following properties ： It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, And both the left and right subtrees are a balanced binary tree .
class Solution {
public:
// Calculate the depth of the binary tree
int deep(TreeNode* root)
{
// Empty tree
if (root == nullptr)
{
return 0;
}
// Left subtree depth
int left = deep(root->left);
// Right subtree depth
int right = deep(root->right);
// Maximum depth of subtree +1
return max(left, right) + 1;
}
bool IsBalanced_Solution(TreeNode* pRoot)
{
// Empty tree
if (pRoot == nullptr)
{
return true;
}
int left = deep(pRoot->left);
int right = deep(pRoot->right);
// The absolute value of the balance factor is greater than 1
if (abs(left - right) > 1)
{
return false;
}
// The left and right subtrees must also be balanced
return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}
};
37. The nearest common ancestor of a binary search tree 【 Simple 】
Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree . Common ancestor definition ： For a tree T Two nodes of p、q, The nearest common ancestor node x, Satisfy x yes p and q Our ancestors and x As deep as possible . ad locum , A node can also be its own ancestor .
Title assurance ：p、q For different nodes and all exist in a given binary search tree .
class Solution {
public:
// Find the path from the root node to the target node
vector<int> getPath(TreeNode* root, int target)
{
vector<int> path;
TreeNode* node = root;
// The node value of binary sort tree is unique , You can directly compare
while (node->val != target)
{
path.push_back(node->val);
// Small The left subtree
if (target < node->val)
{
node = node->left;
}
// Big Right subtree
else
{
node = node->right;
}
}
path.push_back(node->val);
return path;
}
int lowestCommonAncestor(TreeNode* root, int p, int q)
{
// Find the path from the root node to two nodes
vector<int> path_p = getPath(root, p);
vector<int> path_q = getPath(root, q);
int res;
// Compare two paths , The last same node is the nearest common ancestor
for (int i = 0; i < path_p.size() && i < path_q.size(); i++)
{
if (path_p[i] == path_q[i])
{
res = path_p[i];
}
else
{
break;
}
}
return res;
}
};
38. Find the nearest common ancestor of two nodes in the binary tree
Given a binary tree （ Make sure it's not empty ） And the two nodes on the tree val value o1 and o2, Please find o1 and o2 The nearest common ancestor node of . This question guarantees ： The values of each node in the binary tree are different .
class Solution {
public:
// Whether to find tar The mark of a
bool flag = false;
// Find the path from the root node to the target node
void dfs(TreeNode* root, vector<int>& path, int tar)
{
if (flag || root == nullptr)
{
return;
}
path.push_back(root->val);
// The values of each node in the binary tree are different , You can directly compare... With values
if (root->val == tar)
{
flag = true;
return;
}
dfs(root->left, path, tar);
dfs(root->right, path, tar);
if (flag)
{
return;
}
// This subtree has no , to flash back
path.pop_back();
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2)
{
vector<int> path1;
vector<int> path2;
dfs(root, path1, o1);
// Reset flag bit
flag = false;
dfs(root, path2, o2);
int res;
// Recent public ancestor ： Last same node
for (int i = 0; i < path1.size() && i < path2.size(); i++)
{
if (path1[i] == path2[i])
{
res = path1[i];
}
else
{
break;
}
}
return res;
}
};
Four 、 Pile up / Stack / queue
42. Queues are implemented with two stacks 【 Simple 】
Implement a queue with two stacks , Insert data at the end of the queue 、 The function of deleting data at the head of the queue . The elements in the queue are int type , Ensure that the operation is legal , Guarantee pop There are already elements in the queue during operation .
class Solution
{
public:
// When you enter the queue, you will normally enter the stack
void push(int node)
{
stack1.push(node);
}
int pop()
{
// Pop up the contents of the first stack and put them into the second stack
while (!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
// The second top of the stack is the element that comes in first , That is, the head of the team
int res = stack2.top();
stack2.pop();
// Then put the elements of the second stack back to the first stack
while (!stack2.empty())
{
stack1.push(stack2.top());
stack2.pop();
}
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};
43. contain min Function of the stack 【 Simple 】
Defines the data structure of the stack , Please implement a in this type that can get the minimum elements in the stack min function , Input operation is guaranteed pop、top and min Function operation , There must be elements in the stack .
- Use a stack to record the elements entering the stack , Go ahead normally push、pop、top operation .
- Use another stack to record every push Minimum value entered .
- Every time push Element is compared with the top element of the second stack , If it's smaller , Then enter the second stack , If it is larger , Then the top element of the second stack is put on the stack again , Because even if you add an element , It's still the minimum . therefore , Every time you access the minimum value, you access the top of the second stack .
class Solution {
public:
// For stack push And pop
stack<int> s1;
// Used to store minimum values
stack<int> s2;
void push(int value)
{
s1.push(value);
// The stack is empty or the new element is small , The stack
if (s2.empty() || s2.top() > value)
{
s2.push(value);
}
// ** The minimum value is added to the top of the stack repeatedly **
else
{
s2.push(s2.top());
}
}
void pop()
{
s1.pop();
s2.pop();
}
int top()
{
return s1.top();
}
int min()
{
return s2.top();
}
};
44. Valid parenthesis sequence 【 Simple 】
Give an example that contains only characters ’(’ , ‘)’ , ‘{’ , ‘}’ , ‘[’ and ‘]’ , String , Determine whether the given string is a legal sequence of parentheses . Parentheses must be closed in the correct order ,"()“ and ”()[]{}“ Are legal sequences of parentheses , but ”(]“ and ”([)]" illegal .
Ideas ： The matching rule of brackets should conform to the principle of first in, last out , The earliest left parenthesis , It also corresponds to the latest right parenthesis , So you can use the stack . When encountering the left parenthesis, add the corresponding matching right parenthesis to the stack , If the follow-up is legal , The order of the right parenthesis is the order of the pop-up in the stack .
class Solution {
public:
bool isValid(string s)
{
// Auxiliary stack
stack<char> st;
// Traversal string
for (int i = 0; i < s.length(); i++)
{
// Encountered left parenthesis
if (s[i] == '(')
{
// Expect to encounter the right parenthesis
st.push(')');
}
// Encountered left bracket
else if (s[i] == '[')
{
// Expect to encounter the right bracket
st.push(']');
}
// Encountered left brace
else if (s[i] == '{')
{
// Expect to encounter right parentheses
st.push('}');
}
// The stack is empty
else if (st.empty())
{
// You must have an open parenthesis to encounter a right parenthesis
return false;
}
// Right parenthesis encountered
else if (st.top() == s[i])
{
// If it matches, it pops up
st.pop();
}
}
// Whether there are elements in the stack
return st.empty();
}
};
45. Maximum sliding window 【 difficult 】
Given a length of n Array of nums And the size of the sliding window size , Find out the maximum value of the values in all sliding windows .
// Violence law
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> res;
// The length of the window > The length of the array || The length of the window <= 0
if (size > num.size() || size <= 0)
{
return res;
}
for (int i = 0; i <= num.size() - size; i++)
{
int max = 0;
for (int j = i; j < i + size; j++)
{
if (num[j] > max)
{
max = num[j];
}
}
res.push_back(max);
}
return res;
}
};
46. The smallest K Number 【 secondary 】
Given a length of n An array of possible duplicate values , Find the smallest one without weight removal k Number . For example, an array element is 4,5,1,6,2,7,3,8 this 8 A digital , The smallest 4 The number is 1,2,3,4（ In any order ）.
Ideas ： Build a capacity of k Priority queue of large root heap . Go through the elements , If the queue size <k, Just join the team , otherwise , Compare the current element with the team top element , If the top element is big , Out of the line , Queue the current element .
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
vector<int> ret;
if (k == 0 || k > input.size())
{
return ret;
}
// Priority queue Big pile top
priority_queue<int, vector<int>> pq;
for (const int val : input)
{
if (pq.size() < k)
{
pq.push(val);
}
else
{
// The current number is larger than the number at the top of the heap
if (val < pq.top())
{
pq.pop();
pq.push(val);
}
}
}
while (!pq.empty())
{
ret.push_back(pq.top());
pq.pop();
}
return ret;
}
};
47. Search for the first K Large number
There is an array of integers , Please follow the idea of quick sort , Find the number... In the array k Large number . Given an array of integers a , And given its size n And what you're looking for k , Please go back to k Large number ( Including elements of repetition , You don't have to remove the weight ), Make sure the answer exists .
Ideas ： Quick sort , Each move , You can find a benchmark element , Then move the larger one to the left , Those smaller than it move to the right , Thus, the whole array is divided into two parts , Then sort the left side and the right side in the same way , Continuously divide the left and right sub segments , Until the whole array is in order . This is also the idea of partition , Divide the array into sub segments , Divide and rule .
class Solution {
public:
// Conventional fast platoon Division , But this time the big number is on the left
int partion(vector<int>& a, int low, int high)
{
// The benchmark
int temp = a[low];
while (low < high)
{
// Less than the benchmark is on the right
while (low < high && a[high] <= temp)
{
high--;
}
if (low == high)
{
break;
}
else
{
a[low] = a[high];
}
// Larger than the benchmark is on the left
while (low < high && a[low] >= temp)
{
low++;
}
if (low == high)
{
break;
}
else
{
a[high] = a[low];
}
}
// The end condition ：low=high
a[low] = temp;
return low;
}
int quickSort(vector<int>& a, int low, int high, int K)
{
// Quick line up
int p = partion(a, low, high);
// The first K Big
if (K == p - low + 1)
{
return a[p];
}
// The first K Big on the left
else if (p - low + 1 > K)
{
return quickSort(a, low, p - 1, K);
}
// The first K Big on the right
else
{
// Subtract the number of larger numbers on the left ！
return quickSort(a, p + 1, high, K - (p - low + 1));
}
}
int findKth(vector<int> a, int n, int K)
{
return quickSort(a, 0, n - 1, K);
}
};
48. Median in data stream
How to get the median in a data stream ？ If you read an odd number of values from the data stream , So the median is the number in the middle after all the numbers are sorted . If even numbers are read from the data stream , Then the median is the average of the middle two numbers after all the numbers are sorted . We use Insert() Method to read the data stream , Use GetMedian() Method to get the median of the currently read data .
Ideas ： Insert a data into an ordered array every time , So you can sort by inserting .
class Solution {
public:
#define SCD static_cast<double>
vector<int> vec;
void Insert(int num)
{
if (vec.empty())
{
vec.push_back(num);
}
else
{
// from vecector Containers [begin, end) Look up in the middle , first ≥num The location of , Returns if it does not exist end
auto it = lower_bound(vec.begin(), vec.end(), num);
vec.insert(it, num);
}
}
double GetMedian()
{
int size = vec.size();
// The length is odd
if (size & 1)
{
return SCD(vec[size >> 1]);
}
// The length is even
else
{
return SCD(vec[size >> 1] + vec[(size - 1) >> 1]) / 2;
}
}
};
49. Expression evaluation
Please write an integer calculator , Supports addition, subtraction, multiplication and parentheses .
5、 ... and 、 Hash
50. Sum of two numbers
Give an integer array numbers And a target value target, Please find two subscripts in the array that add up to the target value , The returned subscripts are arranged in ascending order .（ notes ： The index of the returned array is from 1 From the beginning , Guarantee target It must be in the array 2 Add the two numbers to get ）
- Build a hash table , among key The value is the value that occurred during the traversal of the array ,value The value is its corresponding subscript , Because what we finally want to return is the subscript .
- Iterate through each element of the array , If the result of subtracting the element from the target value exists in the hash table , It shows that it appeared when we traversed earlier , According to the subscript of the record , You can get the result .
- If the result of subtraction is not in the hash table , It indicates that there is no other value corresponding to it in the previously traversed element , Let's add it to the hash table , Wait for the next value that matches it to appear .
- Note that the final result is the subscript value plus 1.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target)
{
vector<int> res;
// Hashtable ( value , Subscript )
unordered_map<int, int> hash;
// Look up... In the hash table target-numbers[i]
for (int i = 0; i < numbers.size(); i++)
{
int temp = target - numbers[i];
// Not found in hash table , Record in the hash table
if (hash.find(temp) == hash.end())
{
hash[numbers[i]] = i;
}
// Found in hash table
else
{
res.push_back(hash[temp] + 1);
res.push_back(i + 1);
break;
}
}
return res;
}
};
51. A number that appears more than half the times in an array
Give a length of n Array of , There is a number in an array that appears more than half the length of the array , Please find out the number .
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
sort(numbers.begin(), numbers.end());
int cond = numbers[numbers.size() / 2];
int cnt = 0;
for (const int k : numbers)
{
if (cond == k)
{
++cnt;
}
}
if (cnt > numbers.size() / 2)
{
return cond;
}
return 0;
}
};
52. Two numbers that appear only once in the array
An integer array appears only once except for two numbers , The other numbers have all appeared twice . Please write a program to find out these two numbers that only appear once .
// Hashtable
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> FindNumsAppearOnce(vector<int>& array)
{
unordered_map<int, int> mp;
vector<int> res;
// Count the frequency of each number
for (int i = 0; i < array.size(); i++)
{
mp[array[i]]++;
}
// Find the frequency is 1 Two numbers of
for (int i = 0; i < array.size(); i++)
{
if (mp[array[i]] == 1)
{
res.push_back(array[i]);
}
}
// Sorting order
if (res[0] < res[1])
{
return res;
}
else
{
return {
res[1], res[0] };
}
}
};
The XOR operation satisfies the exchange rate , And the XOR of the same number will be cancelled out , such as ：a⊕b⊕c⊕b⊕c=a, And any number is the same as 0 XOR is still the original number , Put it in this topic and all the number XOR operations will get a⊕b, That is, we get the exclusive or sum of two numbers that only appear once . But we want to separate them to get the result , Consider splitting the array into two parts , Part of it is a⊕d⊕c⊕d⊕c=a, The other part is b⊕x⊕y⊕x⊕y=b The style of , How to divide ？ Because the two numbers are different , Let's take the first of two numbers as 1 To divide the above two arrays , The same number will naturally be divided to the other side , and a And b Will just be separated .
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> FindNumsAppearOnce(vector<int>& array)
{
vector<int> res(2, 0);
// a⊕b
int temp = 0;
for (int i = 0; i < array.size(); i++)
{
temp ^= array[i];
}
int k = 1;
// Find the first different bit of two numbers
while ((k & temp) == 0)
{
k <<= 1;
}
for (int i = 0; i < array.size(); i++)
{
// Classify each number
if ((k & array[i]) == 0)
{
res[0] ^= array[i];
}
else
{
res[1] ^= array[i];
}
}
// Sorting order
if (res[0] < res[1])
{
return res;
}
else
{
return {
res[1], res[0] };
}
}
};
53. Missing first positive integer
Given an array of unsorted integers nums, Please find the smallest positive integer that doesn't appear in it .
Ideas ：n An array of lengths , No repetition , If the array is full 1～n, So missing n+1, If the array is not filled 1～n, What is missing is 1～n Number in . So just numbers 1～n A number appears in , We can mark the value of the corresponding subscript , Finally, the unmarked subscript is the missing value .
specific working means ：
// In situ hash
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int minNumberDisappeared(vector<int>& nums)
{
int n = nums.size();
// Negative elements are all recorded as n+1
for (int i = 0; i < n; i++)
{
if (nums[i] <= 0)
{
nums[i] = n + 1;
}
}
for (int i = 0; i < n; i++)
{
if (abs(nums[i]) <= n)
{
// The subscript of this number is marked negative
nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]);
}
}
// Find the subscript of the first element that is not negative
for (int i = 0; i < n; i++)
{
if (nums[i] > 0)
{
return i + 1;
}
}
return n + 1;
}
};
54. Sum of three numbers
Give a n Array of elements S,S Is there an element in a,b,c Satisfy a+b+c=0？ Find the array S All triples that meet the conditions in .
7、 ... and 、 Dynamic programming
62. Fibonacci sequence 【 introduction 】
We all know the Fibonacci series , Now you need to enter a positive integer n , Please output the number of Fibonacci series n term .
class Solution {
public:
int dp[50] = {
0 };
int Fibonacci(int n)
{
dp[1] = 1, dp[2] = 1;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
63. Skip step 【 Simple 】
A frog can jump up at a time 1 Stepped steps , You can jump on it 2 level . Ask the frog to jump on one n How many jumps are there in the steps , Different results are calculated according to different order .
Ideas ： Converse thinking . If I start from No n Step by step , There are two possibilities for the next step , One goes to the third n-1 A stair , One is to go to the n-2 A stair . therefore f[n] = f[n-1] + f[n-2]. Then the initial conditions ,f[0] = f[1] = 1.
class Solution {
public:
int dp[50] = {
0 };
int jumpFloor(int number)
{
dp[0] = 1, dp[1] = 1;
for (int i = 2; i <= number; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[number];
}
};
64. Minimum cost of climbing stairs 【 Simple 】
Given an array of integers cost , among cost[i] It's from the stairs i The cost of climbing a step up , Subscript from 0 Start . Once you pay this fee , You can choose to climb up one or two steps . You can choose from the subscript to 0 Or subscript 1 The steps began to climb the stairs . Please calculate and return the minimum cost to reach the top of the stairs .
- You can use an array to record every time you climb to the i Minimum cost of stairs , Then the state will be transferred once every step is added , The final result .
- 【 The initial state 】 Because it can be directly from the 0 Grade or grade 1 The steps begin , Therefore, the cost of these two levels is directly 0.
- 【 State shift 】 One step at a time , There are only two cases , Or it takes a step up the front step , Or two steps up the first two steps , Because of the cost on the front steps, we all got , Therefore, the minimum value can be updated every time , The transfer equation is ：dp[i] = min(dp[i−1]+cost[i−1], dp[i−2]+cost[i−2])
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
// dp[i] It means to climb to the first i The minimum cost of stairs
vector<int> dp(cost.size() + 1, 0);
// Choose the smallest plan each time
for (int i = 2; i <= cost.size(); i++)
{
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};
65. Longest common subsequence
Given two strings str1 and str2, Output the longest common subsequence of two strings . If the longest common subsequence is empty , Then return to "-1". Data given so far , There will only be one longest common subsequence . Be careful ： Subsequence is not a substring , Substring requires that all characters must be continuous , Subsequences do not require continuity , Only the relative position is required to remain unchanged .
66. The longest public substring
Given two strings str1 and str2 , The longest common substring of output two strings is guaranteed str1 and str2 The longest common substring of exists and is unique .
67. Number of different paths 【 Simple 】
A robot is in m×n The upper left corner of the size map （ The starting point ）. The robot can move down or right at a time . The robot will reach the lower right corner of the map （ End ）. How many different paths can you take from the beginning to the end ？
class Solution {
public:
int uniquePaths(int m, int n)
{
// dp[i][j] The size is i*j The number of paths to the matrix
vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// Only 1 when , There is only one path
if (i == 1)
{
dp[i][j] = 1;
continue;
}
// Only 1 At the time of listing , There is only one path
if (j == 1)
{
dp[i][j] = 1;
continue;
}
// The number of paths is equal to the number of paths in the left grid plus the number of paths in the upper grid
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
};
68. The minimum path sum of matrices
Given a n * m Matrix a, Starting from the upper left corner, you can only go right or down at a time , Finally reach the lower right corner , All the numbers on the path add up to the path and , Output the smallest of all paths and .
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int minPathSum(vector<vector<int> >& matrix)
{
// Column
int n = matrix.size();
// That's ok
int m = matrix[0].size();
// dp[i][j] Express with current i,j The shortest path length with the position as the end point
vector<vector<int> > dp(n, vector<int>(m, 0));
dp[0][0] = matrix[0][0];
// Process the first column
for (int i = 1; i < n; i++)
{
dp[i][0] = matrix[i][0] + dp[i - 1][0];
}
// Deal with the first line
for (int j = 1; j < m; j++)
{
dp[0][j] = matrix[0][j] + dp[0][j - 1];
}
// Others follow the formula
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
dp[i][j] = matrix[i][j] + (dp[i - 1][j] > dp[i][j - 1] ? dp[i][j - 1] : dp[i - 1][j]);
}
}
return dp[n - 1][m - 1];
}
};
69. Translate numbers into strings
There is a way to code letters into numbers ：‘a’->1, ‘b->2’, … , ‘z->26’. We encode a string into a string of numbers , Then consider reverse compiling into a string . Because there is no delimiter , Encoding numbers into letters may have a variety of compilation results , for example 11 It can be seen as two ‘a’ It can also be seen as a ‘k’ . but 10 Can only be ‘j’ , because 0 Can't compile into any results . Now give a string of numbers , Returns the number of possible decoding results .
Ideas ： For ordinary numbers 1-9, There is only one decoding method , But for 11-19,21-26, There are two alternative decoding schemes , Therefore, we use dynamic programming to accumulate the two schemes .
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// For ordinary numbers 1-9, There is only one decoding method , But for 11-19,21-26, There are two alternative decoding schemes .
class Solution {
public:
int solve(string nums)
{
int len = nums.size();
// Empty string With '0' The starting number string
if (len == 0 || nums[0] == '0')
{
return 0;
}
// dp[i] Used to store to i Number of decoding schemes for bit numbers
vector<int> dp(len, 0);
// The number of decoding methods at the end of the first digit must be 1
dp[0] = 1;
for (int i = 1; i < len; i++)
{
if (nums[i] == '0')
{
if (nums[i - 1] == '1' || nums[i - 1] == '2')
{
// The number string is in 10 perhaps 20 At the beginning
if (i == 1)
{
dp[i] = 1;
}
// There is 10 perhaps 20, The current decoding number is equal to the decoding number of two backward steps
else
{
dp[i] = dp[i - 2];
}
}
}
else if (nums[i - 1] == '1' || (nums[i - 1] == '2' && nums[i] >= '1' && nums[i] <= '6'))
{
// The number string is not 10 perhaps 20 The situation of
if (i == 1)
{
dp[i] = 2;
}
else
{
dp[i] = dp[i - 1] + dp[i - 2];
}
}
else
{
dp[i] = dp[i - 1];
}
}
return dp[len - 1];
}
};
71. Longest ascending subsequence
Given a length of n Array of arr, Find the length of its longest strictly ascending subsequence . So called subsequences , It refers to deleting some numbers from an array （ It's also possible to delete ） after , New array formed . for example [1,5,3,7,3] Array , Its subsequences are ：[1,3,3]、[7] etc. . but [1,6]、[1,3,5] Is not its subsequence .
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int LIS(vector<int>& arr)
{
// Dynamic programming auxiliary array for setting the length and size of the array
vector<int> dp(arr.size(), 1);
int res = 0;
for (int i = 1; i < arr.size(); i++)
{
for (int j = 0; j < i; j++)
{
// Probably j Not the biggest thing you need , Therefore need dp[i] < dp[j] + 1
if (arr[i] > arr[j] && dp[i] < dp[j] + 1)
{
// i Point to j It's a little big , Theoretically dp To add 1
dp[i] = dp[j] + 1;
// Find the maximum length
res = max(res, dp[i]);
}
}
}
return res;
}
};
72. The maximum sum of successive subarrays
Enter a length of n Integer array array, One or more consecutive integers in an array form a subarray , The minimum length of the subarray is 1. Find the maximum sum of all subarrays .
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array)
{
// Record to subscript i The largest continuous subarray up to and
vector<int> dp(array.size(), 0);
dp[0] = array[0];
int maxsum = dp[0];
for (int i = 1; i < array.size(); i++)
{
// State shift ： Continuous subarray and maximum
dp[i] = max(dp[i - 1] + array[i], array[i]);
// Maintenance maximum
maxsum = max(maxsum, dp[i]);
}
return maxsum;
}
};
73. Longest text substring
For length is n A string of A（ Only numbers , Case letters ）, Please design an efficient algorithm , Calculate the length of the longest palindrome substring .
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int fun(string& s, int begin, int end)
{
// Each center point starts to expand
while (begin >= 0 && end < s.length() && s[begin] == s[end])
{
begin--;
end++;
}
// Return length
return end - begin - 1;
}
int getLongestPalindrome(string A)
{
int maxlen = 1;
// Center on each point
for (int i = 0; i < A.length() - 1; i++)
{
// Divide odd length and even length to extend to both sides
maxlen = max(maxlen, max(fun(A, i, i), fun(A, i, i + 1)));
}
return maxlen;
}
};
74. The number string is converted into IP Address
Now there is a string that contains only numbers , Convert the string to IP The form of address , Return to all possible situations .
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<string> restoreIpAddresses(string s)
{
vector<string> res;
int n = s.length();
// Traverse IP Possible location of the point
// The position of the first point
for (int i = 1; i < 4 && i < n - 2; i++)
{
// The position of the second point
for (int j = i + 1; j < i + 4 && j < n - 1; j++)
{
// The position of the third point
for (int k = j + 1; k < j + 4 && k < n; k++)
{
// The remaining number in the last paragraph cannot exceed 3
if (n - k >= 4)
{
continue;
}
// Segment from the position of the point
string a = s.substr(0, i);
string b = s.substr(i, j - i);
string c = s.substr(j, k - j);
string d = s.substr(k);
// IP Each number is not greater than 255
if (stoi(a) > 255 || stoi(b) > 255 || stoi(c) > 255 || stoi(d) > 255)
{
continue;
}
// Exclude leading 0 The situation of
if ((a.length() != 1 && a[0] == '0') || (b.length() != 1 && b[0] == '0') || (c.length() != 1 && c[0] == '0') || (d.length() != 1 && d[0] == '0'))
{
continue;
}
// assemble IP Address
string temp = a + "." + b + "." + c + "." + d;
res.push_back(temp);
}
}
}
return res;
}
};
8、 ... and 、 character string
83. String deformation
For a length of n character string , We need to deform it . First of all, the string contains some spaces , It's like "Hello World" equally , Then what we need to do is reverse order the words separated by spaces in this string , Invert the case of each character at the same time . such as "Hello World" After deformation, it becomes "wORLD hELLO".
- Traversal string , Encountered lowercase letters , Convert to uppercase , Encountered a capital letter , Convert to lowercase , When encountering spaces, it is normal and unchanged .
- Invert the entire string for the first time , In this way, there are basic words in reverse order , But the characters of each word are also inverse .
- Traverse the string again , Take each space as the boundary , Reverse each word back to normal .
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
string trans(string s, int n)
{
if (n == 0)
{
return s;
}
string res;
// toggle case
for (int i = 0; i < n; i++)
{
if (s[i] >= 'A' && s[i] <= 'Z')
{
res += s[i] - 'A' + 'a';
}
else if (s[i] >= 'a' && s[i] <= 'z')
{
res += s[i] - 'a' + 'A';
}
// Spaces are copied directly
else
{
res += s[i];
}
}
// Flip the entire string
reverse(res.begin(), res.end());
// Bounded by spaces , Double flip
for (int i = 0; i < n; i++)
{
int j = i;
while (j < n && res[j] != ' ')
{
j++;
}
reverse(res.begin() + i, res.begin() + j);
i = j;
}
return res;
}
};
84. The longest common prefix
Give you a size of n Array of strings strs , It includes n A string , Write a function to find the longest common prefix in the string array , Return this public prefix .
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{
int n = strs.size();
// Empty string array
if (n == 0)
{
return "";
}
// Based on the first string
for (int i = 0; i < strs[0].length(); i++)
{
char temp = strs[0][i];
// Traverse the subsequent string
for (int j = 1; j < n; j++)
{
if (i == strs[j].length() || strs[j][i] != temp)
{
return strs[0].substr(0, i);
}
}
}
// This string has the longest prefix
return strs[0];
}
};
85. verification IP Address
IPv4 The address is represented by a decimal number , Each address contains 4 A decimal number , Its scope is 0 - 255, use (“.”) Division . meanwhile ,IPv4 The number in the address will not be 0 start .
IPv6 Address by 8 Group 16 A decimal number to represent . These groups of numbers go through ":" Division . and , You can add some to 0 Number at the beginning , Letters can be capitalized , It can also be lowercase . namely , Ignore 0 start , Ignore case .
However , We can't because the value of a group is 0, Use an empty group , So much so that (::) The situation of . such as , 2001:0db8:85a3::8A2E:0370:7334 It's invalid IPv6 Address . meanwhile , stay IPv6 In the address , Redundant 0 It's not allowed . such as , 02001:0db8:85a3:0000:0000:8a2e:0370:7334 It's invalid .
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
// String segmentation “.”“:”
vector<string> split(string s, string spliter)
{
vector<string> res;
int i;
// Split string
// Find success , Returns the position of the first character found according to the search rule ; If the search fails , return string::npos
while ((i = s.find(spliter)) && i != s.npos)
{
res.push_back(s.substr(0, i));
s = s.substr(i + 1);
}
res.push_back(s);
return res;
}
bool isIPv4(string IP)
{
vector<string> s = split(IP, ".");
// IPv4 Must be 4 Group
if (s.size() != 4)
{
return false;
}
for (int i = 0; i < s.size(); i++)
{
// Each group cannot be defaulted
if (s[i].size() == 0)
{
return false;
}
// The number of digits is 1-3, Cannot have prefix zero
if (s[i].size() < 0 || s[i].size() > 3 || (s[i][0] == '0' && s[i].size() != 1))
{
return false;
}
// Each character must be a number
for (int j = 0; j < s[i].size(); j++)
{
if (!isdigit(s[i][j]))
{
return false;
}
}
// Each group in 0-255 Between
int num = stoi(s[i]);
if (num < 0 || num > 255)
{
return false;
}
}
return true;
}
bool isIPv6(string IP)
{
vector<string> s = split(IP, ":");
// IPv6 Must be 8 Group
if (s.size() != 8)
{
return false;
}
for (int i = 0; i < s.size(); i++)
{
// The number of digits is 1-4
if (s[i].size() == 0 || s[i].size() > 4)
{
return false;
}
for (int j = 0; j < s[i].size(); j++) {
// Each character must be a number ,a-f,A-F
if (!(isdigit(s[i][j]) || (s[i][j] >= 'a' && s[i][j] <= 'f') || (s[i][j] >= 'A' && s[i][j] <= 'F')))
{
return false;
}
}
}
return true;
}
string solve(string IP)
{
if (IP.size() == 0)
{
return "Neither";
}
if (isIPv4(IP))
{
return "IPv4";
}
else if (isIPv6(IP))
{
return "IPv6";
}
return "Neither";
}
};
// Regular expressions
#include <iostream>
#include <regex>
#include <string>
using namespace std;
class Solution {
public:
string solve(string IP)
{
// IPv4 4 Group 0-255 No prefix 0
// 172.16.254.01
regex ipv4("(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])");
// IPv6 8 Group 0-9、a-f、A-F , The number must be 1-4 individual
// 2001:db8:85a3:0:0:8A2E:0370:7334
regex ipv6("([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}");
if (regex_match(IP, ipv4))
{
return "IPv4";
}
else if (regex_match(IP, ipv6))
{
return "IPv6";
}
else
{
return "Neither";
}
}
};
86. Add big numbers
Read in two numbers as a string , Write a function to calculate their sum , Returns... As a string .
- If one of the strings is empty , Return directly to another , No need to add .
- Swap the position of two strings , We are s Is a long string ,t Is a shorter string , The result is also recorded in a long string .
- Traverse the string from back to front s, Take out characters and turn them into numbers every time , Plus the carry system , Convert subscript to string t The corresponding subscript from back to front , If the subscript is non negative, you need to add a string t The number converted from the corresponding character in .
- Integer division carries , The modular algorithm removes ten digits , Put the calculated result into the corresponding position of the longer array .
- If the traversal ends , The carry value also has , It needs to be directly in the string s Add a character before ‘1’.
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string solve(string s, string t)
{
// An empty string
if (s.empty())
{
return t;
}
if (t.empty())
{
return s;
}
// s Store long strings ,t Store shorter strings
if (s.length() < t.length())
{
swap(s, t);
}
// Carry mark
int carry = 0;
// Traverse the long string from back to front
for (int i = s.length() - 1; i >= 0; i--)
{
// Turn numbers + carry
int temp = s[i] - '0' + carry;
// Shorter strings correspond to subscripts from back to front
int j = i - s.length() + t.length();
// Shorter strings also
if (j >= 0)
{
// Turn numbers + Add up
temp += t[j] - '0';
}
// Carry
carry = temp / 10;
// Go to ten
temp = temp % 10;
// Modify the result
s[i] = temp + '0';
}
// The last carry
if (carry == 1)
s = '1' + s;
return s;
}
};
Nine 、 Double pointer
87. Merge two ordered arrays 【 Simple 】
Give an ordered array of integers A And an ordered array of integers B , Please array B Merge into array A in , Into an ordered ascending array . Guarantee A The array has enough space to store B Elements of array , A and B The initial number of elements in are m and n,A The array space size of is m+n
class Solution {
public:
void merge(int A[], int m, int B[], int n)
{
// Pointing to the array A Ending
int i = m - 1;
// Pointing to the array B Ending
int j = n - 1;
// Pointing to the array A The end of space
int k = m + n - 1;
// Start with the two largest elements of the array , Until an array is traversed
while (i >= 0 && j >= 0)
{
// Put the larger element last
if (A[i] > B[j])
{
A[k--] = A[i--];
}
else
{
A[k--] = B[j--];
}
}
// Array A I'll go through it first , Array B First half part , Add to array A front
// Array B I'll go through it first , Array A First half part , Never mind
if (i < 0)
{
while (j >= 0)
{
A[k--] = B[j--];
}
}
}
};
88. Determine whether it is a palindrome string 【 introduction 】
Given a length of n String , Please write a function to judge whether the string is palindrome . If it is a palindrome, please return true, Otherwise return to false. String palindrome means that the positive order of the string is consistent with its reverse order character by character .
class Solution {
public:
bool judge(string str)
{
// Head pointer
int left = 0;
// Tail pointer
int right = str.length() - 1;
// Head and tail to the middle
while (left < right)
{
// Compare whether it is the same
if (str[left] != str[right])
{
return false;
}
left++;
right--;
}
return true;
}
};
89. Merge range 【 secondary 】
Give a set of intervals , Please merge all overlapping intervals . Please make sure that the merged intervals are arranged in ascending order according to the starting point of the interval .
- Since the overlapping intervals are required to be arranged in ascending order according to the starting position , Let's sort all the intervals first according to the starting position . Use sort Function to sort , Overloaded comparison mode is comparison interval Structural start Variable .
- The first interval after sorting must be the interval with the lowest starting point , We count it into the return array res, Then traverse the subsequent interval .
- During subsequent traversal , If the starting point value is less than res The end value of the last interval in , That must be overlap , Take the maximum end value of both to update res The last interval in .
- If the starting point value is greater than res The end value of the last interval in , There must be no overlap , There will be no overlapping interval at the end in the future , Because the starting point behind will only be bigger , So you can add it res.
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {
}
Interval(int s, int e) : start(s), end(e) {
}
};
class Solution {
public:
// Overload comparison
static bool cmp(Interval& a, Interval& b) {
return a.start < b.start;
}
vector<Interval> merge(vector<Interval>& intervals)
{
vector<Interval> res;
// A special case
if (intervals.size() == 0)
{
return res;
}
// Sort by the beginning of the interval
sort(intervals.begin(), intervals.end(), cmp);
// Put in the first interval
res.push_back(intervals[0]);
// Traverse the subsequent interval
for (int i = 1; i < intervals.size(); i++)
{
// The intervals overlap , Update end
if (intervals[i].start <= res.back().end)
{
res.back().end = max(res.back().end, intervals[i].end);
}
// The intervals do not overlap , Directly to join
else
{
res.push_back(intervals[i]);
}
}
return res;
}
};
90. Minimum cover substring 【 difficult 】
Give me two strings s and t, Ask for in s Find out the shortest inclusion in t Consecutive substrings of all characters in . Title Guarantee string s and t It only contains upper and lower case English letters , There may be many substrings that meet the conditions , But the topic guarantees that the shortest substring satisfying the condition is unique . If s It does not contain t Substrings of all characters in , Returns an empty string .
// Hashtable + The sliding window
class Solution {
public:
// Check whether there is less than in the hash table 0 Of
bool check(unordered_map<char, int>& hash)
{
for (auto iter = hash.begin(); iter != hash.end(); iter++)
{
if (iter->second < 0)
{
return false;
}
}
return true;
}
string minWindow(string S, string T)
{
int cnt = S.length() + 1;
// character string T Hashtable
unordered_map<char, int> hash;
for (int i = 0; i < T.length(); i++)
{
hash[T[i]] -= 1;
}
// The sliding window
int slow = 0, fast = 0;
// Record the left and right intervals
int left = -1, right = -1;
for (; fast < S.length(); fast++)
{
// Target character
char c = S[fast];
// There is... In the hash table
if (hash.count(c))
{
hash[c]++;
}
// No less than 0 The instructions of all cover
while (check(hash))
{
int res = fast - slow + 1;
// Take the optimal solution <=
if (res <= cnt)
{
cnt = res;
left = slow;
right = fast;
}
// Target character
char c = S[slow];
if (hash.count(c))
{
hash[c]--;
}
// The window shrinks
slow++;
}
}
// What can't be found
if (left == -1)
{
return "";
}
return S.substr(left, right - left + 1);
}
};
91. Reverse string 【 introduction 】
Write a program , Accept a string , Then output the inverted string of the string .（ The string length does not exceed 1000）
class Solution {
public:
string solve(string str) {
// Left and right hands
int left = 0;
int right = str.length() - 1;
// The two hands lean towards the middle
while (left < right)
{
// Swap characters on both sides
swap(str[left], str[right]);
left++;
right--;
}
return str;
}
};
92. Longest non repeating subarray 【 secondary 】
Given a length of n Array of arr, return arr The length of the longest non repeating element subarray of , No repetition means that all numbers are different . Subarray is continuous , such as [1,3,5,7,9] The subarrays of are [1,3],[3,5,7] wait , however [1,3,7] It's not a subarray .
- Build a hash table , Used to count the number of occurrences of array elements .
- The left and right bounds of the window start from the beginning of the array , Every time the window moves to the right first , And count the frequency of elements entering the window .
- Once the occurrence frequency of the right boundary element is greater than 1, You need to move the left boundary to the right until there is no repetition in the window , When removing the element on the left from the window, you need to reduce its frequency in the hash table 1, Ensure that the frequencies in the hash table are the frequencies in the window .
- Each cycle , Maintain the maximum window length .
// Hashtable + The sliding window
class Solution {
public:
int maxLength(vector<int>& arr)
{
// Hashtable Record the non repeated numbers in the window
unordered_map<int, int> mp;
// Window size
int res = 0;
for (int left = 0, right = 0; right < arr.size(); right++)
{
// Move window right The hash table counts the number of occurrences
mp[arr[right]]++;
// There is a repetition in the window
while (mp[arr[right]] > 1)
{
// Window left At the same time, subtract the number of occurrences of this number in the hash table
mp[arr[left++]]--;
}
// Maintain the maximum length of subarray
res = max(res, right - left + 1);
}
return res;
}
};
93. The container with the most water 【 secondary 】
Given an array height, The length is n, Each number represents the height of a point in the coordinate axis ,height[i] In the first i The height of the point , Excuse me, , Choose from 2 Height and x How much water can the container composed of shafts hold at most . When n Less than 2 when , Deemed not to form a container , Please return 0.
// Double pointer + Greedy Algorithm
class Solution {
public:
int maxArea(vector<int>& height)
{
// Cannot form a container
if (height.size() < 2)
{
return 0;
}
// Maximum volume
int res = 0;
// Double pointer left and right
int left = 0;
int right = height.size() - 1;
// Traverse all arrays together
while (left < right)
{
// Calculate the regional water capacity
int capacity = min(height[left], height[right]) * (right - left);
// Maintenance maximum
res = max(res, capacity);
// Give priority to shorter edges
if (height[left] < height[right])
{
left++;
}
else
{
right--;
}
}
return res;
}
};
94. The rain problem
Given an array of integers arr, It is known that all values are nonnegative , Think of this array as a column height map , Calculate columns arranged in this way , How much rain can be received after rain , The height of the area outside the array is treated as 0.
class Solution {
public:
long long maxWater(vector<int>& arr)
{
// An empty array
if (arr.size() == 0)
{
return 0;
}
// Left and right hands
int left = 0;
int right = arr.size() - 1;
// The boundary height of the middle area
int maxL = 0;
int maxR = 0;
long long res = 0;
while (left < right)
{
// Maintain the maximum boundary in the middle every time
maxL = max(maxL, arr[left]);
maxR = max(maxR, arr[right]);
// The shorter boundary determines the amount of water in the grid
if (maxR > maxL)
{
res += maxL - arr[left++];
}
else
{
res += maxR - arr[right--];
}
}
return res;
}
};
Ten 、 Greedy Algorithm
95. The problem of dividing candy
A group of children play games , Now please give out candy according to the score of the game , Requirements are as follows ：
1. No matter how much each child scores , At least one candy .
2. Between any two adjacent children , Children who score more must take more candy .( If the same, there is no such restriction )
Given an array arrarr Represents the score array , Please return the minimum number of sweets needed .
- Use an auxiliary array to record the candy distributed by children in each position , All initialized to 1.
- Traversing the array from left to right , If the right element is larger than the adjacent left element , It means increasing , The number of sweets is the previous one plus 1, Otherwise keep 1 unchanged .
- Traverse the array from right to left , If the left element is larger than the adjacent right element , It means that the decreasing part in the original array , If the left gets less candy in the last round , Then it is updated to the number of candies on the right +1, Otherwise, it will remain unchanged .
- Accumulate and sum the elements in the auxiliary array .
class Solution {
public:
int candy(vector<int>& arr)
{
// The number of sweets per location is initialized to 1
vector<int> nums(arr.size(), 1);
// Traverse from left to right
for (int i = 1; i < arr.size(); i++)
{
// If the score increases , Add one... At a time
if (arr[i] > arr[i - 1])
{
nums[i] = nums[i - 1] + 1;
}
}
// Record the total number of sweets
int res = nums[arr.size() - 1];
// Traverse from right to left
for (int i = arr.size() - 2; i >= 0; i--)
{
// If the score on the left is higher , But the number of sweets is smaller
if (arr[i] > arr[i + 1] && nums[i] <= nums[i + 1])
{
nums[i] = nums[i + 1] + 1;
}
// Cumulative sum
res += nums[i];
}
return res;
}
};
96. Host scheduling
- Use the auxiliary array to obtain the start time and end time of individual activities , Then sort the start time and end time respectively , It is convenient to judge whether it intersects later .
- Traverse n An activity , If the start time of an activity is greater than the end time of the previous activity , The current host is enough , The end time of the activity will be one later .
- If the end time of the previous activity is later than the start time of the current activity , You need to add a host .
class Solution {
public:
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
{
// Activity start time
vector<int> start;
// End time
vector<int> end;
for (int i = 0; i < n; i++)
{
start.push_back(startEnd[i][0]);
end.push_back(startEnd[i][1]);
}
// Sort the start and end times respectively
sort(start.begin(), start.end());
sort(end.begin(), end.end());
// The number of hosts
int res = 0;
int j = 0;
for (int i = 0; i < n; i++)
{
// The newly started program is longer than the end time of the previous round , The host remains the same
if (start[i] >= end[j])
{
j++;
}
else
{
// Moderator added
res++;
}
}
return res;
}
};
边栏推荐
- synchronized 解决共享带来的问题
- Use br to back up tidb cluster data to S3 compatible storage
- logback1.3. X configuration details and Practice
- 备份与恢复 CR 介绍
- vulnhub hackme: 1
- Personalized online cloud database hybrid optimization system | SIGMOD 2022 selected papers interpretation
- Nacos Development Manual
- Easy to use tcp-udp_ Debug tool download and use
- LDAP Application Section (4) Jenkins Access
- wincc7.5下载安装教程（Win10系统）
猜你喜欢
让学指针变得更简单（三）
将 NFT 设置为 ENS 个人资料头像的分步指南
【MySQL】数据库的存储过程与存储函数通关教程（完整版）
C language - bit segment
Résumé des diagrammes de description des broches de la série ESP
好用的TCP-UDP_debug工具下载和使用
【MySQL】日志
synchronized 解决共享带来的问题
"Designer universe" Guangdong responds to the opinions of the national development and Reform Commission. Primary school students incarnate as small community designers | national economic and Informa
IOT -- interpreting the four tier architecture of the Internet of things
随机推荐
Easy to use tcp-udp_ Debug tool download and use
Leetcode question brushing (5.28) hash table
Analysis of Top1 accuracy and top5 accuracy examples
Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
[Yugong series] February 2022 U3D full stack class 011 unity section 1 mind map
Let the bullets fly for a while
Step by step guide to setting NFT as an ens profile Avatar
Migrate data from a tidb cluster to another tidb cluster
PHP - Common magic method (nanny level teaching)
C language - bit segment
[research materials] 2021 China online high growth white paper - Download attached
使用 BR 备份 TiDB 集群数据到兼容 S3 的存储
Leetcode skimming (5.29) hash table
PLT in Matplotlib tight_ layout()
让学指针变得更简单（三）
Wireshark grabs packets to understand its word TCP segment
Migrate data from CSV files to tidb
Leetcode question brushing (5.31) string
A Closer Look at How Fine-tuning Changes BERT
Erc20 token agreement