# day22_0519

## choice question

1: simply select the best time O(n^2) average time O(n^2) worst time O(n^2)
2: Directly insert the best time O(n) average time O(n^2) worst time O(n^2)
3: Bubble sort best time O(n) average time O(n^2) worst time O(n^2)
4: Hill sort ＾ best time ＾ O(n) average time O(logn) worst time ＾ O(n^s) 1 < s < 2
5: Quicksort best time O(nlogn) average time O(nlogn) worst time O(n^2)
6: Heap sort best time O(nlogn) average time O(nlogn) worst time O(nlogn)
7: Merge sort △ best time O(nlogn) average time O(nlogn) worst time O(nlogn)

The most common operations of linear table are accessing any element with specified sequence number and performing insertion and deletion operations at the end;
To access anywhere, the most time-saving and labor-saving is the array, that is, the sequence table.
Moreover, the element is inserted and deleted at the last position, which does not involve the additional operation of displacement of other elements. The most involved is to expand the space.

For recursive programs, common optimization methods include tail recursion, iteration and loop
Tail recursion: in the process of each recursion, the state of the last calculation is maintained, that is, the "linear iterative process", that is, when the function returns, it calls itself. Tail recursion is different from ordinary recursion in the occupation of memory. Ordinary recursion creates stack accumulation and then calculates shrinkage; Tail recursion will only occupy a constant amount of memory, so that the recursion itself will only occupy one stack frame no matter how many times it is called, and there will be no stack overflow. During tail recursive calls, if optimized, the stack will not grow. Therefore, no matter how many calls, it will not lead to stack overflow.

End1 ￠ points to the head element and end2 ￠ points to the last position of the tail element. Because the circular queue is placed in one-dimensional array A[0... M-1], end1 points to the head element, that is, A[0], so end1 = = 0. When the queue is initialized, the queue entry operation is to store the data in array A, and then end2 increases automatically. You can know that the initial value of end2 # is 0. Therefore, it can be seen that the condition of the air force is end1 = = end2.
considering that the queue is full, because the queue can hold   M-1   elements at most, suppose that the queue is stored in M-1   areas with subscript 0   to subscript M-2   and the queue head is A[0] and the queue tail is A[M-2]. At this time, the queue is full, end1   points to the queue head element, so we can know that end1=0; End2 ， points to the last position of the tail element. It can be seen that end2=M-2+1=M-1. Therefore, we can see that the condition of full team is end1 = = (end2+1) mod m, choose A.

supplement: relevant conditions and formulas of circular queue

the queue head pointer is front, the queue tail pointer is rear, and QueueSize is the maximum length of the circular queue

## programming

```public class FightMonsters {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNextInt()){
int[] ar=new int[2];
for(int i=0;i<2;i++){
ar[i]=sc.nextInt();
}
int n=ar[0];//Number of monsters
int a=ar[1];//Initial capability value
int[] arr=new int[n];
for(int i=0;i<arr.length;i++){
arr[i]=sc.nextInt();
}
for(int i=0;i<arr.length;i++){
if(arr[i]>a){
//The monster's defense is greater than Xiaoyi's ability
int bi=arr[i];
a+=Divisor(bi,a);
}else{
a+=arr[i];
}
}
System.out.println(a);
}
}
public static int Divisor(int bi,int c){
int temp=0;
for(int i=c;i>0;i--){
if(bi%i==0&&c%i==0){
temp=i;
break;
}
}
return temp;
}
}```

Find the first character in the string that appears only once

Take out the current character, splice the string s before and after the current character, and judge whether s contains the current character. If not, it means that the current character meets the requirements, and the output ends; If the str string is traversed and the output - 1 is not found;

```public class FirstChar {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
boolean b=true;
for(int i=0;i<str.length();i++){
String  c=str.charAt(i)+"";
String s=str.substring(0,i).concat(str.substring(i+1,str.length()));
if(!s.contains(c)||s.equals("")){
b=false;
System.out.println(c);
break;
}
}
if(b){
System.out.println("-1");
}
}
}```

Tags: Java Algorithm

Posted by QuietWhistler on Fri, 20 May 2022 01:49:27 +0300