Honorary course of data structure - first experiment - problem solving Report

1, Repeat count

subject

In a finite sequence of positive integers, some numbers will appear repeatedly. Please count the number of occurrences of each number, and then output the number and its number in the order of the first occurrence of the number in the sequence.

Input format:

In line 1, an integer N represents the number of integers, (1 ≤ N ≤ 50000).

In line 2, there are N positive integers, and each integer x satisfies 1 ≤ x ≤ 2000000000.

Output format:

A number of rows, two numbers separated by a space in each row. The first is the number appearing in the sequence, and the second is the number of times the number appears in the sequence.

Input sample:

  • 12
  • 8 2 8 2 2 11 1 1 8 1 13 13

Output example:

  • 8 3
  • 2 3
  • 11 1
  • 1 3
  • 13 2

Meaning:

Count the frequency of each element in the sequence and output it in turn according to the original relative order.

thinking

Solution 1:

  1. Statistical frequency:
    Since the number of integers is specified in the title, you can open up an array of corresponding size, read the subscript of the array each time, and exchange the corresponding element + 1 with space for time.

  2. Output according to the original relative order:
    We can use a container to save the element subscripts that have appeared before, and then output them in the original order. Since the subscript of the first in container needs the first out container, we choose the queue.

Solution 2:

  1. First, read all data without brain, and record the relative order of element values with queue, then sort the data, and finally output the number of this value.
  2. sort() sorting: an efficient standard sorting algorithm in STL, which can sort any linear storage container. The three parameters needed are: ① the starting iterator of the container; ② The end iterator of the container; ③ Sorting standard (binary predicate). The default is less, from small to large.
  3. lower_bound(): perform a binary search in [begin, end], and return the iterator of the first element position greater than or equal to the key. If all elements are less than the key, return the iterator of the end position.
  4. upper_bound(): perform a binary search in [begin, end], find the upper bound of the keyword, and return the iterator greater than the first element position of the key.
  5. It should be noted that due to the use of binary search, the objects to be searched should be orderly.

Reference code

Solution 1:

#include "iostream"
#include "queue"
using namespace std;

queue<int> q;

int Num;

int a[500000];//Global variables, which are all 0 initially
int main()
{
	cin>>Num;
	
	int index;
	for(int i=0;i<Num;i++)
	{
		cin>>index;
		if(!a[index])//If a[index] is zero, it means that the index appears for the first time and the index is put on the stack
			q.push(index);
		a[index]++;
	}

	while(q.size()!=1)//Due to the requirements of the output format, we stop the output when there is one element left in the queue
	{
		index=q.front();
		q.pop();
		cout<<index<<" "<<a[index]<<endl;
	}
	index=q.front();//There is no extra carriage return when the last element is output
	q.pop();
	cout<<index<<" "<<a[index];
}

Solution 2:

#include "iostream"
#include "algorithm"
#include "queue"
using namespace std;

int a[50001];
int N;

queue<int> q;

int main()
{
	cin>>N;

	for(int i=1;i<=N;i++)
	{
		cin>>a[i];
		if(find(a,a+i,a[i])==a+i)//To detect whether a[i] it exists before, this algorithm is traversal, and its efficiency is not high
			q.push(a[i]);
	}

	sort(a+1,a+N+1);

	int val;
	while(q.size()!=1)//Due to the requirements of output format, the output is stopped when there is one element left in the queue
	{
		val=q.front();
		q.pop();
		cout<<val<<" "<<upper_bound(a+1,a+N+1,val)-lower_bound(a+1,a+N+1,val)<<endl;
	}
	val=q.front();
	q.pop();
	cout<<val<<" "<<upper_bound(a+1,a+N+1,val)-lower_bound(a+1,a+N+1,val);
}

2, Counting game

subject

n people form a circle, number them successively from 1, and play the counting game. It is now designated to start counting from the first person. When counting to the m person, the person will go out of the circle, and then start counting again from the next person. It is still counting to the m person out of the circle. This is repeated until everyone goes out of the circle. When the total number of people is less than m, the number will be reported circularly. Please output the order of everyone out of the circle.

Input format:

One line, two integers n and m. N represents the number of people in the game, M represents the number of circles, 1 ≤ n ≤ 50000, 1 ≤ m ≤ 100.

Output format:

One line, n integers separated by spaces, indicating the order in which everyone turns out.

Input sample:

  • 5 2

Output example:

  • 2 4 1 5 3

Meaning:

Classical Joseph Ring problem.

thinking

Because the algorithm needs to be efficient, the linked list structure is adopted. Construct a circular linked list with sentinel nodes, and remove one node every time when the circle is out, until all the nodes are removed.

Reference code

#include "iostream"
using namespace std;

struct cell
{
	int data;
	cell *next;
};

int N;
int M;

int main()
{
	cin>>N>>M;

	cell *head,*tmp,*tail;
	head=tail=new cell;//Create sentinel node

	for(int i=0;i<N;i++)//Build one-way linked list
	{
		tmp=new cell;
		tmp->data=i+1;

		tail->next=tmp;
		tmp->next=NULL;
		tail=tmp;
	}

	tail->next=head->next;//One way linked list ring

	tmp=head;//The following tmp is the node to be deleted (out of circle), and p is the precursor node of tmp
	cell *p=NULL;
	while(N!=1)//Due to format requirements, the output is stopped when N=1
	{
		for(int i=0;i<M;i++)//Find the node to delete
		{
			p=tmp;
			tmp=tmp->next;
		}

		cout<<tmp->data<<" ";//Output deleted nodes

		p->next=tmp->next;//Delete Vertex 
		//delete tmp;// I'm afraid to call delete timeout for many times, so I didn't write it
		tmp=p;//Reset tmp to previous position

		N--;//Number of people - 1
	}

	cout<<tmp->next->data<<endl;//Output the last node
	//Note that tmp refers to the predecessor of the last deleted node. The node to be deleted is the successor of the last deleted node, so tmp - > next - > data is deleted
}

3, Arithmetic expression calculation

subject

The arithmetic expression is given as infix and ends with = sign, including +, -, *, / and (,) separator. The range of operands is a non negative integer without positive and negative symbols, and is less than or equal to 109.

In the calculation process, if the divisor is 0, the result of the expression is "NaN"; If the intermediate result exceeds the 32-bit signed integer range, it is still calculated as an integer without special treatment. Enter to ensure that the expression is correct.

Input format:

One line, including one arithmetic expression. The length of arithmetic expression is less than or equal to 1000.

Output format:

One line, the value of the arithmetic expression.

Input sample:

  • (1+30)/3=

Output example:

  • 10

Meaning:

Calculate the value of infix expression. Special treatment is required when the divisor is 0.

thinking

  1. We need two stacks, one is the number stack, which is used to store the encountered numbers, and the other is the symbol stack, which is used to store the encountered symbols.

  2. Different from the original one digit calculation, the number in this question is not just one digit. When a numeric character is read, the numeric character can be read circularly, and the number greater than one digit can be calculated according to sum=sum*10+(now - '0').

  3. After solving for numbers greater than one digit, consider how to evaluate the expression. There are two ideas: ① first convert infix expression into suffix expression, and then calculate suffix expression (see the last part of this article for the relevant contents of suffix expression). ② Read and calculate. The second method is mainly introduced here.

  4. When reading a number, press it directly into the number stack. When encountering symbols, there are four situations: ① when encountering the left bracket, directly enter the stack (because the left bracket indicates that the number behind the current position should be calculated first, so no operation is required here); ② When ± * /, keep taking the stack top symbol. If the priority of the stack top symbol is greater than or equal to the priority of the current symbol, Then process the stack top symbol (because if the priority of the stack top symbol is not less than the current symbol, it means that the stack top symbol can be calculated at this time) (the specific process is to take two data of the digital stack, detect the symbol, do the corresponding operation, and then press the result into the digital stack); ③ When encountering the right bracket, continue to take the top symbol of the stack and process it until encountering the left bracket; ④ When encountering the end symbol (this topic is called equal sign), it is enough to continuously process the symbol at the top of the stack (because all the symbols that can be calculated have been calculated before, and the priority relationship of the symbols in the last symbol stack must comply with the normal operation).

  5. Problems needing attention
    When encountering four kinds of operators, you must cycle the operators with priority greater than or equal to those encountered earlier, and do not only deal with the operators with priority greater than them. Otherwise, there is a counter example: calculate 1-2-3. Due to the use of stack, the calculation order is in reverse order, so the calculation process of the program is 1-2-3 = 1 - (- 1) = 2, which is obviously wrong.

  6. For specific demonstration, calculate the value of 4-2 * 3 - (3-4-5) = because * is a special character, which is used in the demonstration × (replaced)

  • 4 -2 × 3 - (3-4-5) = 4 into digital stack (4)
  • 4 - 2 × 3 - (3-4-5) = detect the top of the symbol stack, - enter the symbol stack (-)
  • 4- 2 × 3 - (3-4-5) = 2 into the digital stack (4 2)
  • 4-2 × 3 - (3-4-5) = detect the top of the symbol stack × Enter symbol stack (- ×)
  • 4-2 × 3 - (3-4-5) = 3 into the digital stack (4 2 3)
  • 4-2 × 3 - (3-4-5) = detect the top of the symbol stack, × Priority is greater than -, process the multiplication sign (2,3 out of the digital stack, × Out of symbol stack, 2 × 3 into the number stack), at this time, the number stack (4, 6) and the symbol stack (-); Check the top of the symbol stack again, - the priority is equal to -, and deal with the minus sign. At this time, the number stack (- 2) and the symbol stack (); Current symbol into symbol stack (-)
  • 4-2 × 3 - (3-4-5) = the left bracket is directly put into the stack (-)
  • 4-2 × 3 - (3 - 4-5) = 3 into the digital stack (- 2, 3)
  • 4-2 × 3 - (3 - 4-5) = detect the top of the symbol stack, (priority is less than -, the current symbol enters the symbol stack (-)
  • 4-2 × 3 - (3 - 4 - 5) = 4 into digital stack (- 2, 3, 4)
  • 4-2 × 3 - (3-4 - 5) = detect the top of the symbol stack, - the priority is equal to -, and process the minus sign. At this time, the number stack (- 2 - 1) and the symbol stack (-); Current symbol into symbol stack (-)
  • 4-2 × 3 - (3-4-5) = 5 into the digital stack (- 2 - 1 5)
  • 4-2 × 3 - (3-4-5) = when encountering the right bracket, start to cycle the symbols until encountering the left bracket. After the first processing, the symbol stack (-), the number stack (- 2 - 6); The second processing encounters the most parenthesis, and the processing stops. At this time, the symbol stack (-) and the number stack (- 2, - 6)
  • When an equal sign is encountered, all symbols are processed, and the final number stack is (4).

Reference code

#include "iostream"
#include "map"
#include "stack"
using namespace std;

map<char,int> Pro;//Used to store symbol priorities

stack<int> Num;//Digital stack
stack<char> Oper;//Symbol stack

//Used to record variables larger than 1-bit integers
int Flag;//Some kind of sign
int s;//Final integer value

inline void Calculate(char oper)//Calculate according to the symbol and put the result on the stack
{
	int x,y;
	x=Num.top();
	Num.pop();
	y=Num.top();
	Num.pop();

	if(oper=='+')
		Num.push(y+x);
	else if(oper=='-')
		Num.push(y-x);
	else if(oper=='*')
		Num.push(y*x);
	else if(oper=='/')
	{
		if(!x)//Divisor is 0
		{
			cout<<"NaN";
			exit(0);
		}
		Num.push(y/x);
	}
}

int main()
{
	//Establish priority between symbols
	Pro.insert(make_pair('#',-1));
	Pro.insert(make_pair('(',0));
	Pro.insert(make_pair('+',1));
	Pro.insert(make_pair('-',1));
	Pro.insert(make_pair('*',2));
	Pro.insert(make_pair('/',2));

	Oper.push('#');// Stack symbol

	char ch;
	cin>>ch;

	while(ch!='=')
	{
		while(ch>='0'&&ch<='9')//Process integers greater than 1 bit
		{
			s=s*10+ch-'0';
			Flag=1;//Flag a number is detected at this time
			cin>>ch;
		}
		if(Flag)//The number is detected before. Press in the number, and the Flag and s are reset
		{
			Num.push(s);
			Flag=0;
			s=0;
		}
		if(ch=='=')//If the number is followed by '=', exit the loop directly
			break;

		if(ch=='(')//The left bracket has the lowest priority and is directly put on the stack
			Oper.push(ch);
		else if(ch==')')//The right bracket is detected, and the calculation is continued until the left bracket is encountered
		{
			char oper=Oper.top();
			while(oper!='(')
			{
				Oper.pop();

				Calculate(oper);

				oper=Oper.top();
			}
			Oper.pop();//Pop up left parenthesis
		}
		else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')//Four operators are detected to process all the previous symbols with priority no greater than ch
		{
			char oper=Oper.top();
			while(Pro[oper]>=Pro[ch])
			{
				Oper.pop();

				Calculate(oper);

				oper=Oper.top();
			}
			Oper.push(ch);//Press in current symbol
		}

		cin>>ch;
	}

	while(Oper.size()!=1)//Process the remaining symbols until the stack symbol '#' is encountered
	{
		char oper=Oper.top();
		Oper.pop();
		
		Calculate(oper);
		
	}

	cout<<Num.top();
}

4, Favorite sequence

subject

Xiao Tang has been studying the sequence. Take a sequence of N integers, and he assigns a favorite value to each integer in the sequence. The favorite value is also an integer, positive and negative. The larger it is, the more you like it. He wants to know how to take up to m numbers continuously from the sequence, and he gets the most favorite value. 1≤N≤500000，1≤m≤N.

Input format:

The first line is two integers N, m. Respectively represent the number of numbers in the sequence and the maximum number that can be taken.

The second line is N integers separated by spaces, and the i-th integer Li represents his favorite value for the i-th number. │Li│≤1000.

Output format:

One line and three numbers represent the maximum favorite value and the first interval to take the maximum favorite value.

Input sample:

  • 5 2
  • 1 4 5 2 3

Output example:

  • 9 2 3

Meaning:

Output the maximum value of the sum in an interval of up to m length.

thinking

This problem is a typical problem solved by monotone queue.

Monotone queue

Maintain a queue with correct interval and monotonically increasing. Each queue capital is the minimum value of the current interval.

  1. Monotonicity maintenance: compare the current element with the tail element. If the tail element is larger than the current element, the tail element will be out of the team; Repeat processing until the queue is empty or the tail element is smaller than the current element.
  2. Interval maintenance: if the position of the first element of the team is not in the interval (current element subscript - first element subscript > interval length), the first element of the team will be out of the team; Repeat processing.

Reference code

#include "iostream"
using namespace std;

struct Cell
{
	int data;//Record element value
	int num;//Record subscript
};

class MyDeque//Custom Dual Ended queue
{
	Cell a[500001];
	int Num;//The number of elements in the queue, which is used to assign values to num in the Cell
	int top;//Queue header pointer
	int rear;//End of queue pointer
public:
	MyDeque():top(0),rear(0),Num(0){}
	void push(int x)//Back end team
	{
		a[rear].data=x;
		a[rear].num=++Num;
		rear++;
	}
	int peek_backdata(){ return a[rear-1].data; }//View end of queue element values
	int peek_backnum(){ return a[rear-1].num; }//View end subscript
	void pop_back(){ rear--; }//Back end out of line
	int peek_frontdata(){ return a[top].data; }//View queue header element value
	int peek_frontnum(){ return a[top].num; }//View team leader subscript
	void pop_front(){ top++; }//Front end out of the team
	int empty(){ return top==rear; }//Judge team empty
};

int M,N;
int a[500001];//The sum of the first n items is actually stored. Since it is a global variable, a[0] is initially 0
MyDeque d;

int Max=-500000001;//Maximum value, initialized to minimum value at the beginning
int top=1;//Left interval
int rear=1;//Right interval

int main()
{
    cin>>N>>M;

	for(int i=1;i<=N;i++)
	{
		cin>>a[i];//Read data in sequence
		a[i]+=a[i-1];//Record the sum of the first n items to facilitate the sum in a certain interval in the future
	}
	
	for(int i=0;i<N;i++)
	{
		//If the queue is not empty, constantly detect the tail element and pop up nodes larger than the current element
		while(!d.empty()&&d.peek_backdata()>a[i])
			d.pop_back();
			
		d.push(a[i]);//Join the current element
		
		//The subscript of the detection team head element shall be maintained within the required interval
		while(d.peek_backnum()-d.peek_frontnum()>=M)
			d.pop_front();
		
		int tmp=a[i+1]-d.peek_frontdata();//Calculate the sum of elements in the current interval
		
		if(Max<tmp)//Judge whether to update the maximum value
		{
			Max=tmp;
			top=d.peek_frontnum();
			rear=d.peek_backnum();
		}
	}
	cout<<Max<<" "<<top<<" "<<rear;
}

summary

  1. One use of map -- processing priority. The usage of map here is similar to a special array. The subscript of the array can be any type of value, and the value of the array can also be any type of value.

  2. Related to the third question - infix expression to suffix expression
    Reference code:

    #include "iostream"
#include "vector"
#include "map"
#include "stack"
using namespace std;

vector<string> ans;//Save suffix expression
stack<char> Oper;//Symbol stack
map<char,int> pro;//Processing Priority 

inline string String(char c)//char type to string type
{
	string s(1,c);
	return s;
}


int main()
{
	//set priority
	pro.insert(make_pair('+',0));
	pro.insert(make_pair('-',0));
	pro.insert(make_pair('*',1));
	pro.insert(make_pair('/',1));
	pro.insert(make_pair('(',-1));

	char str[21];
	int i=0;
	cin>>str;
	int len=strlen(str);

	while(i<len)
	{
		int Flag=0;
		char tmp=str[i];
		string s;
		while(tmp>='0'&&tmp<='9')//Processing multi digit numbers
		{
			s=s+tmp;
			i++;
			tmp=str[i];
			Flag=1;
		}
		if(Flag)//Digital direct stack
			ans.push_back(s);
			
		//According to the operation order, the symbols are stacked in turn
		if(tmp=='(')
			Oper.push(tmp);
		else if(tmp==')')
		{
			char oper=Oper.top();
			while(oper!='(')
			{
				Oper.pop();
				ans.push_back(String(oper));
				oper=Oper.top();
			}
			Oper.pop();
		}
		else
		{
			char oper;
			while(!Oper.empty())
			{
				oper=Oper.top();
				if(pro[oper]>=pro[tmp])
				{
					Oper.pop();
					ans.push_back(String(oper));
				}
				else
					break;
			}
			Oper.push(tmp);
		}
		i++;
	}
	while(Oper.size()!=1)//Put the remaining symbols other than the equal sign on the stack
	{
		char oper=Oper.top();
		Oper.pop();
		ans.push_back(String(oper));
	}

	for(vector<string>::iterator it=ans.begin();it!=ans.end();it++)
		cout<<*it<<" ";
	cout<<endl;
	return 0;
}

Added by sureshp on Thu, 10 Feb 2022 00:46:15 +0200

Popular Keywords

©2024 Programming VIP