PAT exam summary (exam experience)

大家好,又见面了,我是你们的朋友全栈君.

pat试题总结

A summary of the traversal problem

1. dfs中,If it is a graph with cycles,要设置visitedArrays prevent looping,同时在dfsbefore the function exitsvisitedThe array is set accordinglyfalse,Otherwise, other paths cannot traverse the node;
2. 在问题中,如果要求“Select several elements from a sequence to satisfy the condition”,可以考虑dfs,如1103 Integer Factorization (30分)和7-1 Forever (20分);
3. 在写dfs前,List all variables that need to be set,然后在dfs边界上,Modifications to the values ​​of these variables are considered one by one,You can avoid missing changes to a variable;
4. Think carefully before you start writing code“What is determined by what”可以省去debugtime mindset,如1131 Subway Map (30分)A line can be determined by using two neighbors as keys,But investigate“Which line both neighbors belong to”Can't figure out the line;又如1018 Public Bike Management (30分),Number of departuressendand recovery numbersbackdoes not satisfy the optimal substructure,Choosing a path by a greedy algorithm will not work.

字符串处理总结

1. 字符串处理中,注意利用sscanf,The numbers in the string can be read in the format,如 sscanf(s, “The root is %d”, &root)提取int型变量root;
2. When there are many illegal situations,Not to judge illegal situations one by one,Instead, only legal cases are allowed to pass,Such as judging whether it is a legal number：Only one decimal point is possible、several digits、There can only be one negative sign and it appears in the header.
3. Familiar with the conversion of numbers and strings.

Summary of math problems

1. in math problems,常用的函数如下：

//辗转相除法求最大公因数
int gcd(int a, int b) { 
   
	return b == 0 ? a: gcd(b, a % b);
}

复制

//A sieve lists the prime numbers
bool prime[100];
void getPime() { 
   
	fill(prime + 2, prime + 100, true);
	for(int i = 2; i < 100; i++) { 
   
		if(prime[i]) { 
   
			int factor = 2;
			while(i * factor < 100) { 
   
				prime[i * factor] = false;
			}
			++factor;
		}
	}
}

复制

//判断素数的函数
bool isPrime(int num) { 
   
	int n = sqrt(num);
	for(int i = 0; i <= n; i++) { 
   
		if(num % i == 0)
			return false;
	}
	return true;
}

复制

1. in some processing,Negative signs can be considered、The decimal point is handled separately,It can effectively simplify the judgment conditions;
2. 进制转换,Mainly use the remainder method of division and base multiplication.
3. When there is no good way,Try to find regular simplification solutions.

A summary of the sorting problem

1. Memorize the writing of various sorting codes. 插入排序：Inserts the head element from the unordered subarray into the ordered subarray each time; 冒泡排序：The cursor scans from front to back,If the two elements before and after are in reverse order,则交换; 选择排序：Choose the smallest one from the unordered part at a time,Swap with the elements after the ordered part; 快速排序：Selects an element in the array as pivot,Hide it to the far left,两个游标left, right根据pivotThe size keeps swapping elements,When two cursors meet,leftIt is indicatedpivot应该放的位置; 堆排序：先自底向上建堆,Each time an element is taken from the top of the heap,Top with the element at the end of the array,Then filter down the top element of the heap;
2. 对时间的处理,You can first convert the time into seconds,Convert back to hours, minutes and seconds if necessary.
3. Eliminate invalid data if necessary,Find results from valid data;
4. When a question has multiple queries,Process the data first,Results can be returned directly when processing a query.If every query is sorted once,可能会超时;
5. Read the sorting criteria carefully,Avoid omissions or mistakes.

Summary of tree problems

1. Memorize the code for constructing the tree given two sequences as well1119 Pre- and Post-order Traversals (30分)Preorder and postorder are not uniquely constructed;
2. 熟记AVL树左旋、Right-handed spelling,Note that the height of the child node and the parent node needs to be updated after the rotation,Pay attention to the timing of updating the altitude;
3. Write the template code first,Then modify as needed;
4. Consider the logical inconsistency between the implemented code and the description of the problem,如1135 Is It A Red-Black Tree (30分)要求的是”The number of black nodes from each node to the leaf node is the same“,Not just root node to leaf node.

A summary of the simulation problem

1. Choose the data structure appropriately,如1129 Recommendation System The number of occurrences of data is constantly changing,At the same time, it is required to be ordered according to the number of occurrences,So consider the red-black tree implementationset;
2. 充分考虑、Simplify the conditions to be met by the simulated event,如1128 N Queens Puzzle (20分)中,”Two queens cannot be on the same diagonal“,It shows that the slope of the line connecting the two queens cannot be 1;
3. When the simulated event has a timeline,Consider setting a variable to simulate the passage of time.

发布者：全栈程序员栈长,转载请注明出处：https://javaforall.cn/128736.html原文链接：https://javaforall.cn