Bo2SS

"Containers" Why are there quotes around it? Please read on.

Course Content#

template name; // Custom types are also allowed, such as struct

Queue and Stack#

queue#

• 

• queue que;

• name.method()

  • que.push(5); // Enqueue
  • que.pop(); // Dequeue
  • que.front(); // Front element
  • que.size(); // Number of elements
  • que.empty(); // Is it empty?

stack#

• stack sta;
• name.method()
  • sta.push(5);
  • sta.pop();
  • sta.top(); // Top element, the only difference from queue
  • sta.size();
  • sta.empty();

Essence#

• Their underlying implementation is based on deque
  • double-ended queue
  • Reference deque-cppreference
• They are wrappers around deque, essentially adapters
  • deque is the real container

Vector and Priority Queue#

vector#

【Note: In C language, variable-length arrays cannot be defined, ❌ cannot define like this: int n; scanf("%d", &n); int num[n];】

• vector v;
• name.method()
  • v.push_back(5); // Add an element at the end O(1)
  • v.size(); // Number of elements
  • v.insert(1, 6); // Insert element O(N), using push_back is more efficient
• vector<vector > v2; // Dynamic two-dimensional array
  • Before C++11 standard, there must be a space between "> >", otherwise it may be misinterpreted as right shift operation
  • 
• Initialization, refer to Various Initialization and Assignment Methods of vector-CSDN
• cin to vector needs to initialize the vector with the size of space first

priority_queue#

• priority_queue que;
  • int can be followed by objects to sort
  • Reference C++ priority_queue (STL priority_queue) Usage Detailed Explanation-C Language Chinese Network
• name.method()
  • que.push(5);
  • que.pop();
  • que.top(); // Top element of the heap, default is largest number on top
  • que.size();
  • que.empty();
• Custom structure priority queue needs to overload the less than operator
  • bool operator <(const struct name &variable) {}
  • Note: Overloading the less than operator, for this container, if implemented as
    • a) <, it arranges from large to small, corresponding to a max heap
    • b) >, it arranges from small to large, corresponding to a min heap
    • A bit convoluted, see code demonstration for details-priority_queue
  • Note: All containers that need sorting structures overload the less than operator

Essence#

• The underlying implementation of vector is based on arrays
• The underlying implementation of priority_queue is based on heaps

String string#

Class

• string str;
• name.method()
  • str.size() // Equivalent to str.length()
  • str.find(s2, pos = 0); // Find s2 in str, default starts from the beginning (pos = 0), returns index if found
    • The underlying method implementation depends on the compiler
    • Check if found (no position)

if (str.find(s2) != string::npos) {
  // static const size_t npos = -1;
  // Found
} else {
  // Not found
}

• • str.insert(x, s2); // Insert s2 at index x
  • str.substr(2); // Substring from index 2 to the end
  • str.substr(2, len); // Note the second parameter is the length
  • str.replace(index, len, s2); // Also note the second parameter is the length
• Overloaded many operators
  • +
    • string a = string("123") + string("a");
    • += Use with caution
      • a += string("123") + string("456"); // "+=" has a priority just higher than ","
      • ❓ Imagine how many temporary variables are defined and how many times values are copied
  • ==, >=, <=, >, <
    • Judged by dictionary order
  • =
    • str = "123a"
    • Can be directly assigned, unlike C language which requires strcpy

Key-Value Pair map#

Mapping

• map<string, int> m; // "123" → 456
• Methods
  • []
    • Assignment, access
    • If the accessed key does not exist, it will automatically create one, assigning the default value of the type
    • There is an implicit cost, as the underlying structure is a red-black tree, with a lookup efficiency of O(logN)
  • insert, find, erase
  • count
    • Returns how many of a certain key
    • But there are no duplicates in the map, so it only returns 0 or 1
    • Can be used to check if a key exists
• The underlying implementation is a red-black tree【RBTree】
  • An ordered structure, map defaults to ascending order
  • If the key corresponds to a custom structure, the < operator needs to be overloaded
• Extensions
  • multimap
    • Can have multiple duplicate keys
  • unordered_map ❗ appeared in C++11
    • Unordered
    • The underlying implementation is a hash table, with lookup and insertion efficiency of O(1)
    • Custom structures need to manually implement hash functions
      • Reference Custom Hash Functions and Comparison Rules for C++ STL Unordered Containers-C Language Chinese Network

Set set#

• Can be used for deduplication and sorting
• The underlying structure is the same as map, a red-black tree, and may also need to overload "<" when necessary
• Extensions
  • multiset
  • unordered_set ❗ C++11

Pair pair#

• Pair
• pair<int, int>
  • pair.first First element
  • pair.second Second element
• make_pair can quickly create a temporary pair

Code Demonstration#

queue#

• 

• Two types of data queues

• que.empty() and que.size() are both O(1), with a data field stored in the background

• Default generated constructor

Output

stack#

• 

• Difference from queue: name, header file, top() method

Output

vector#

• 

• More advanced than arrays, commonly used in leetcode

• Three insertion methods

Output

priority_queue#

• 

• Remember to overload the less than operator for custom structure queues

• ❗ The overloaded operator is less than, but it outputs from large to small!

Output

• 

• In the second part, it implements sorting from large to small, but the overloaded operator is less than, and it also implements the less than operator

map#

• 

• For custom structures, map needs to overload <, unordered_map needs to define a hash function

• For non-existent keys, accessing them will automatically create them and assign the default value of the type

Output

Exercise Questions#

HZOJ-383: Weekend Dance Party#

Sample Input

3 5 6

Sample Output

1 1
2 2
3 3
1 4
2 5
3 1

• Idea
  • Queue
  • Dequeue, put at the back of the queue
• Code
  • 
  • Basic operations of the queue

HZOJ-378: String Parenthesis Matching 2#

Sample Input

a(cc[])bbb()@

Sample Output

YES

• Idea
  • Character stack
  • Matching: YES, such as ( [ ] )
  • Not matching: NO
    • Parentheses are mismatched, such as ( [ ) ]
    • Encountered a right parenthesis when the stack is empty, such as ( ) )
    • The string ends, but the stack is still not empty, such as ( ( { } )
  • Note: Cannot simply use three variables to record counts, as parentheses have order issues, for example ([)]
• Code
  • 
  • Note the three mismatching cases
  • When matching, pop the left parenthesis from the stack

HZOJ-376: Machine Translation#

Sample Input

3 7
1 2 1 5 4 4 1

Sample Output

5

• Idea
  • Queue
  • Use a marking array to record words
    • mark[x] = 1, 0
    • Data is not large (article length does not exceed 1000), no need to use map, set, etc.
• Code
  • 
  • The key is to store words in the queue and mark words in the array
  • Note the case when memory is full

HZOJ-379: Warehouse Log#

Sample Input

13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2

Sample Output

2
4
4
1
0

• Idea
  • 0, 1, 2: Inbound, Outbound, Query
  • Last in first out: Requires a goods stack
  • Query function (output maximum value): Also requires a stack to record the maximum value [Key]
  • Note: Each piece of goods is different, so the problem is simplified
• Code
  • 
  • There are two stacks!
    • For this problem, the goods stack can be omitted, just to aid understanding
    • Because this problem does not need to care about what the goods are when they are popped, while the max stack records the maximum value each time it is stored, it will repeat!

HZOJ-382: Counting Numbers#

Sample Input

7 3

Sample Output

4

• Idea
  • Josephus problem
  • 【Essence】 Queue: Safe people throw to the back, unsafe people pop out
  • End condition: When the size of the queue is 1
• Code
  • 
  • The push i is the number
  • Does pop have no return value?
    • Here, in the mentioned container, pop and push have no return value
    • See pop-cppreference

HZOJ-384: Knock Seven#

Sample Input

4 3 6

Sample Output

3

• Idea
  • Similar to the previous question, pay attention to details
  • The difference is
    • Input: The x-th person starts counting from t
    • Judgment condition: Contains 7 or multiples of 7
    • Counting does not reset, continues to +1
• Code

HZOJ-385: Harbor#

Sample Input

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

Sample Output

3
3
3
4

• Idea
  • Input: Arrival time, number of people, nationality of each person
  • Queue +【marking array/map】+ Variable for the number of countries
    • Can store either ships or people in the queue
      • Because the number of people on the ship is not fixed, storing people is more convenient
    • First reduce people based on time, then add people
    • Country count: If a new one arrives, +1; if the last one leaves, -1
• Code
  • 
  • The key is the queue used, the marking array, and the variable counting the number of countries
  • Is it a bit like a sliding window? A little bit, but generally in a sliding window, the data is already fixed
  • Directly copy data input, output format is a bit strange? It should be the newline character issue
  • Line 33 quickly defines a structure: (struct name){..., ...}
    • Not adding parentheses () is also fine, but adding parentheses may be clearer

HZOJ-569: Solution Simulator#

Sample Input

100 100
2
P 100 0
Z

Sample Output

200 50.00000
100 100.00000

• Idea
  • Undo operation: Use a stack! Store the mass and concentration after each operation [or] the mass of salt and total mass
  • Review of chemistry knowledge
    • Solution composition: Salt + Water
    • Concentration: Salt / (Salt + Water)
    • Mass: Salt + Water
• Code
  • 
  • Storing the mass of salt and total mass makes calculations easier to understand
    • Store as double type, pay attention to conversion during output
  • Undo operation: subtract first then pop

LC-232: Implement Queue Using Stacks#

• Idea
  • Two stacks to implement a queue
  • Have a process in mind 👇
  • 
• Code

class MyQueue {
public:
    // Declare stacks here, otherwise they are not easy to call
    stack<int> s1, s2;
    /** Initialize your data structure here. */
    MyQueue() {
        // No need to worry
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // First transfer all elements from s1 stack to s2 stack
        while (!s1.empty()) {
            // Push first then pop, the order cannot be reversed
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // At this point, get the value to pop
        s2.pop();          // Pop from stack
        // Transfer back
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        // Transfer to s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // Temporary variable t stores the value, needs to be returned after putting back
        // Transfer back
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();  // Just check s1
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

• • After each operation, the value is always stored in s1
  • Stack declaration position: Place it in the global scope of the class so that it can be accessed by other functions
    • Can it be used if placed in the initialization function MyQueue() with this?
    • ❌ No, this refers to the entire class, pay attention when learning classes later
  • 【Advanced】 Can you implement a queue with an amortized time complexity of O(1) for each operation? In other words, the total time complexity for executing n operations is O(n), even if one of the operations may take a longer time.
    • Key: When pop transfers elements from s1 to s2, do not transfer back
    • This way, the order of s2 is the order of the queue's dequeue
    • Each time pop only transfers elements from s1 to s2 when s2 is empty, otherwise just pop from s2
    • Reference Implement Queue Using Stacks - Official Solution-Method Two

LC-225: Implement Stack Using Queues#

• Idea
  • Actually, only one queue is needed
    • When transferring elements, just put them at the back
      • ① Can adjust the order when pushing
      • ② Can also operate when popping
    • Control the boundary of the transfer using queue.size()
• Code

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
        // Move all previous elements to the back
        for (int i = 1; i < que.size(); i++) {
            que.push(que.front());
            que.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int t = que.front();
        que.pop();
        return t;
    }
    
    /** Get the top element. */
    int top() {
        return que.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

• • After pushing complex operations, other operations can be used like a stack

Additional Knowledge Points#

• Quickly define a structure: (struct name){..., ...}

Points to Consider#

Tips#

Course Notes#