[data structure and algorithm] stack and queue
Stack
What is a stack?
Stack is a kind of linear table.
It only allows the insertion and deletion of elements at the fixed end.
The one end for data insertion and deletion is called the top of the stack and the other end is called the bottom of the stack.
Therefore, the stack addition and deletion elements have what we often call last ...
Posted by beboo002 on Fri, 20 May 2022 00:43:56 +0300
CF 1405E Fixed Point Removal
CF 1405E Fixed Point Removal
Meaning:
Given the sequence \ (A \) with length \ (n \), the number of \ (A_i = i \) (i.e. the value is equal to its subscript) can be deleted in each operation, and then the remaining arrays are spliced together to ask how many can be deleted at most
\(q \) independent inquiries. Set the number of the first \ ...
Posted by bakigkgz on Thu, 19 May 2022 08:38:13 +0300
Data structure day 8 - two dimensional array and matrix multiplication, and transpose of compressed matrix
The first is matrix multiplication
#include<stdio.h>
#include<stdlib.h>
/**
*Dynamic two-dimensional array
*/
typedef struct TwoDArray{
int rows;
int columns;
int **elements;
} TwoDArray, *TwoDArrayPtr;
/**
*Static two-dimensional array
*/
typedef struct TwoDStaticArray{
int rows;
int columns;
int elements[4][5];
} ...
Posted by g00bster on Thu, 19 May 2022 00:09:30 +0300
Data Structure Chapter 6 Graph Study Notes
content
1. Figure
6.1 Definition of graph
6.2 Basic terminology of graphs
6.3 Graph storage structure
6.3.1 Lead matrix
6.3.2 Adjacency List
6.4 Traversal of graphs
6.4.1 Depth-First Search (DFS)
6.4.2 Breadth-First Search (BFS)
6.5 Applications of graphs
6.5.1 Minimum Spanning Tree
6.5.2 Shortest path
6.5.3 Topolog ...
Posted by Ramtree on Wed, 18 May 2022 01:04:31 +0300
P6186 bubble sort (tree array + thinking)
1. The number of exchanges in each round of bubble sorting is equal to N - x, and X is the number of numbers that meet the following conditions: there is no larger number in front of this number We say that this number does not participate in the exchange in the current round of bubble sorting
2. The total number of rounds of bubble sort exc ...
Posted by moboter on Tue, 17 May 2022 23:30:21 +0300
Interview question: How to design a blocking queue?
foreword
I was asked this question in the interview, and the answer was terrible, so I record it here.
The answer at that time was to use the while loop to judge whether it is empty when reading. If so, sleep for a period of time, and then judge again. If it is not empty, read and return. When inserting, use the while loop to judge whether it ...
Posted by Jude on Tue, 17 May 2022 18:42:01 +0300
Data structure and program design of leetcode in the direction of postgraduate entrance examination (miscellaneous articles such as number and stack, including train of thought solutions)
Digital problem
9. Number of palindromes
Algorithm idea: 1. First, judge whether x is a negative number. If it is a negative number, it directly returns false without conversion 2. Assign the palindrome number y according to the flashback until Y > = X. at this time, if x = = y | x = = Y / 10, it is the palindrome number, otherwise it ...
Posted by elwadhos on Tue, 17 May 2022 18:01:13 +0300
String reverse order - multiple methods
Reverse the order of strings, taking the string abcdef as an example
1. With additional arrays
#include <stdio.h>
#include <string.h>
int main() {
char str[] = "abcdef";
//Find the size of the string, including '\ 0'
int sz = strlen(str) + 1;
//Dynamic memory allocation, apply for a character array of sz size
...
Posted by zechdc on Tue, 17 May 2022 03:07:02 +0300
Detailed explanation of red and black trees
Red black tree
The concept of red black tree
Red black tree
, is a kind of
Binary search tree
, but
Add a storage bit on each node to represent the color of the node, which can be
Red
or
Black
. By limiting the coloring method of each node on any path from root to leaf, the red black tree ensures that no path will be two longer ...
Posted by Easter Bunny on Tue, 17 May 2022 02:24:17 +0300
Summary of UnionFind skills
What is joint search set
In computer science, the union query set is a tree data structure, which is used to deal with the merging and query of some Disjoint Sets. A union find algorithm defines two operations for this data structure:
Find: determines which subset the element belongs to. It can be used to determine whether two elements belong ...
Posted by Revan on Mon, 16 May 2022 04:03:36 +0300