PTA exercise 2-6 calculate the free falling distance of an object (5 points)
An object falls freely from an altitude of 100 meters. Write a program to find the vertical distance it falls in the first 3 seconds. Let the gravitational acceleration be 10 m / S2.
Input format:
This topic is not entered.
Output format:
Output in the following format
height = Vertical distance value
Keep 2 decimal places for the result.
#include<stdio.h>
int main(){
float height,i,j;//Look at the questions! 2 decimal places!
height = 0.5*10*9;
printf("height = %.2f",height);//Look at the questions! 2 decimal places!
}
Exercise 2-12 output Fahrenheit Celsius temperature conversion table (15 points)
Enter two positive integers lower and upper (lower ≤ upper ≤ 100), please output a Fahrenheit Celsius temperature conversion table with a value range of [lower, upper] and an increase of 2 degrees Fahrenheit each time.
Calculation formula of temperature conversion: C=5 × (F − 32) / 9, where: C represents Celsius temperature and F represents Fahrenheit temperature.
Input format:
Enter 2 integers in one line to represent the values of lower and upper respectively, separated by spaces.
Output format:
The first line outputs: "fahr celsius"
Then, each line outputs a Fahrenheit temperature fahr (integer) and a celsius temperature celsius (occupy 6 characters wide, align to the right, and keep 1 decimal place)// It means celsius
If the input range is illegal, "Invalid." will be output.
Input example 1:
32 35
Output example 1:
fahr celsius 32 0.0 34 1.1
Input example 2:
40 30
Output example 2:
Invalid.
#include<stdio.h>
int main(){
int a,b,F,i;
float C;
scanf("%d %d",&a,&b);
if(a>b||a>100||b>100) printf("Invalid.");
else{
printf("fahr celsius\\n");//How can fahr celsius write in for with only one line? Remember to wrap when the output is complete.
for(i=a;i<=b;i=i+2){
C=5*(i*1.0-32)/9;//Convert i to float
printf("%d%6.1f\\n",i,C);//More than thirty degrees Fahrenheit is degrees Celsius, and one decimal place is degrees Celsius.
}
}
}
PTA exercise 2-13 find the sum of the first N items in the nth sequence (15 points)
This problem requires writing a program to calculate the sum of the first N items of sequence 1 + 1 / 2 + 1 / 3 +.
Input format:
The input gives a positive integer N in one line.
Output format:
In one line, output the value S of the partial sum in the format of "sum = S", accurate to 6 decimal places. Ensure that the calculation results do not exceed the double precision range.
Input example:
6
Output example:
sum = 2.450000
#include<stdio.h>
int main(){
int n;
double sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
sum+=(1.0/i);//1/i is not a fraction (decimal). 1.0/i is!!!
}
printf("sum = %.6lf",sum);
}
PTA exercise 5-2 using functions to sum odd numbers (15 points)
This problem requires the implementation of a function to calculate the sum of all odd numbers in N integers, and realize a function to judge parity at the same time.
Function interface definition:
int even( int n ); int OddSum( int List[], int N );
The function even will return the corresponding value according to the parity of the parameter n passed in by the user: 1 when n is an even number, otherwise 0. The function OddSum is responsible for calculating and returning the sum of all odd numbers in the passed in n integers List [].
Example of referee test procedure:
#include <stdio.h>
#define MAXN 10
int even( int n );int OddSum( int List[], int N );
int main(){
int List[MAXN], N, i;
scanf("%d", &N);
printf("Sum of ( ");
for ( i=0; i<N; i++ ) {
scanf("%d", &List[i]);
if ( even(List[i])==0 )
printf("%d ", List[i]);
}
printf(") = %d\\n", OddSum(List, N));
return 0;
}
/* Your code will be embedded here */
Input example:
6 2 -3 7 88 0 15
Output example:
Sum of ( -3 7 15 ) = 19
int even( int n ){
if(n%2==0) return 1;
else
return 0;
}
int OddSum( int List[], int N )
{
int i,sum=0;
for(i=0;i<N;i++)
if(even(List[i])==0)
sum+=List[i];
return sum;
}
PTA exercise 5-4 using functions to sum primes (20 points)
This problem requires the realization of a simple function to judge prime numbers and a function to calculate the sum of prime numbers in a given interval by using this function.
A prime number is a positive integer that can only be divided by 1 and itself. Note: 1 is not prime, 2 is prime.
Function interface definition:
int prime( int p );int PrimeSum( int m, int n );
The function prime returns 1 when the parameter p passed in by the user is a prime number, otherwise it returns 0; The function PrimeSum returns the sum of all primes in the interval [m, n]. Ensure that the parameter m ≤ n passed in by the user.
Example of referee test procedure:
#include <stdio.h>
#include <math.h>
int prime( int p );
int PrimeSum( int m, int n );
int main(){
int m, n, p;
scanf("%d %d", &m, &n);
printf("Sum of ( ");
for( p=m; p<=n; p++ ) {
if( prime(p) != 0 )
printf("%d ", p);
}
printf(") = %d\\n", PrimeSum(m, n));
return 0;
}
/* Your code will be embedded here */
Input example:
-1 10
Output example:
Sum of ( 2 3 5 7 ) = 17
int prime( int p )
{
int i=2,c;
if (p <= 1 )
{
c=0;
}
else if (p == 2)
{
c=1;
}
else
{
for(i=2;i<p;i++)
{if(p % i==0)
{c=0;
break;}//Remember to break when it's over
else {c=1;}
}
}
return c;
}
int PrimeSum( int m, int n )
{int sum=0,i;
for(i=m;i<=n;i++)
if (prime(i)==1)
sum+=i;
return sum;}
PTA exercise 2-15 finding the sum of the first N items of simple interleaved sequence (15 points)
This problem requires writing a program to calculate the sum of the first N items of sequence 1 - 1 / 4 + 1 / 7 - 1 / 10 +.
Input format:
The input gives a positive integer N in one line.
Output format:
In one line, output the value S of the partial sum in the format of "sum = S", accurate to three decimal places. Ensure that the calculation results do not exceed the double precision range.
Input example:
10
Output example:
sum = 0.819
#include<stdio.h>
int main(){
float ans=0,z=1;
int m=1,n,f=1;
scanf("%d",&n);//Why do you always forget to add &
for(int i=0;i<n;i++)
{
ans=ans+f*(z/m);
f*=(-1);
m+=3;
}
printf("sum = %.3f",ans);
}
PTA exercise 2-15 finding the sum of the first N items of simple interleaved sequence (15 points)
This problem requires writing a program to calculate the sum of the first N items of sequence 1 - 1 / 4 + 1 / 7 - 1 / 10 +.
Input format:
The input gives a positive integer N in one line.
Output format:
In one line, output the value S of the partial sum in the format of "sum = S", accurate to three decimal places. Ensure that the calculation results do not exceed the double precision range.
Input example:
10
Output example:
sum = 0.819
#include<stdio.h>
int main(){
float ans=0,z=1;
int m=1,n,f=1;
scanf("%d",&n);//Why do you always forget to add &
for(int i=0;i<n;i++)
{
ans=ans+f*(z/m);
f*=(-1);
m+=3;
}
printf("sum = %.3f",ans);
}
PTA exercise 2-18 finding the number of combinations (15 points)
This problem requires the preparation of procedures, according to the formula Cnm=m!(n−m)!n! Calculate the combination number of M elements (m ≤ n) taken from n different elements.
It is recommended to define and call the function fact(n) to calculate n!, Where the type of n is int and the function type is double.
Input format:
The input gives two positive integers m and n (m ≤ n) on one line, separated by spaces.
Output format:
Output according to the format "result = calculation result of combination number". The title ensures that the result is within the range of double type.
Input example:
2 7
Output example:
result = 21
#include<stdio.h>
double fact (int);
int main ()
{
int m,n,i;
double ans=1;
scanf("%d %d",&m,&n);
ans=fact(n)/fact(m)/fact(n-m);//Directly insert the formula given by the topic
printf("result = %.0lf",ans);
}
double fact (int n)
{ double ans=1;
for(int i=n;i>=1;i--) ans*=i;
return ans;
}
PTA exercise 5-6 using function to output daffodils (20 points)
Narcissus number refers to an n-bit positive integer (n ≥ 3), and the sum of the N powers of the numbers in each bit is equal to itself. For example: 153 = 1 ^ 3 + 5 ^ 3 + 3 ^ 3. This problem requires writing two functions, one to judge whether a given integer is the number of daffodils, and the other to print out all the daffodils in a given interval (m,n) from small to large.
Function interface definition:
int narcissistic( int number ); void PrintN( int m, int n );
The narcissistic function determines whether number is the number of daffodils. If yes, it returns 1, otherwise it returns 0.
The function PrintN prints the number of all daffodils in the interval (m, n), and each number occupies one line. Ensure 100 ≤ m ≤ n ≤ 10000.
Example of referee test procedure:
#include <stdio.h>
int narcissistic( int number );void PrintN( int m, int n );
int main(){
int m, n;
scanf("%d %d", &m, &n);
if ( narcissistic(m) ) printf("%d is a narcissistic number\\n", m);
PrintN(m, n);
if ( narcissistic(n) ) printf("%d is a narcissistic number\\n", n);
return 0;
}
/* Your code will be embedded here */
Input example:
153 400
Output example:
153 is a narcissistic number 370 371
int narcissistic( int number )
{int d=number,num=number,a=0,b=1,i,j,c=0;
while(d)
{d/=10;
c++;
}
for(i=0;i<c;i++)
{int m=1,o;
o=num%10;
for(j=0;j<c;j++)
m*=o;
num/=10;
a+=m;
}//Three times
return (a==number)? 1:0;
}
void PrintN (int m, int n)
{int i;
for(++m;m<=n;m++)
{if(narcissistic(m)==1)
printf("%d\\n",m);
}
}
C language classic example: insert a number in a certain array.
#include<stdio.h>
void insert(int a[],int l)
{ int c;
for(int i=0;i<11;i++)
{
if(a[i]>=l){
c=i;
for(int j=11;j>i;j--) a[j]=a[j-1];
break;
a[c]=l;
}else a[10]=l;
}
}
int main()
{
int i,j,l,p,a[11]={0,1,2,3,4,5,6,7,8,9};
scanf("%d",&l);
for (i=0;i<10;i++)
printf("%d ",a[i]);
printf("\\n");
insert(a,l);
for (i=0;i<11;i++)
printf("%d ",a[i]);
return 0;
}
Input example 1:
6
Output example 1:
0 1 2 3 4 5 6 6 7 8 9
Input example 2:
110
Output example 2:
0 1 2 3 4 5 6 7 8 9 110
PTA exercise 5-7 using function to approximate cosine function (15 points)
This problem requires the realization of a function. Use the following formula to find the approximate value of cos(x) until the absolute value of the last term is less than e:
cos(x)=x0/0!−x2/2!+x4/4!−x6/6!+⋯
Function interface definition:
double funcos( double e, double x );
The parameters passed in by the user are the upper error limit e and the independent variable x; The funcos function shall return the approximate value of cos(x) calculated by the given formula and meeting the error requirements. The input and output are within the double precision range.
Example of referee test procedure:
#include <stdio.h>#include <math.h>
double funcos( double e, double x );
int main(){
double e, x;
scanf("%lf %lf", &e, &x);
printf("cos(%.2f) = %.6f\\n", x, funcos(e, x));
return 0;
}
/* Your code will be embedded here */
Input example:
0.01 -3.14
Output example:
cos(-3.14) = -0.999899
double funcos( double e, double x )
{ double n1=1,n2=1,n3=1,c=1,p,sum=1;
for(p=2;n1>e;p+=2)
{n2=n2*x*x;
n3=n3*p*(p-1);
c*=(-1);
sum=sum+c*n2/n3 ;
n1=n2/n3;
}
return sum;
}
PTA exercise 6-2 finding the sum of special a string sequences using functions (20 points)
Given two positive integers a and n that are not more than 9, it is required to write a function to find the sum of a+aa+aaa + +... + aa * a (n a).
Function interface definition:
int fn( int a, int n );int SumA( int a, int n );
The function fn must return a number composed of n a; SumA returns the required sum.
Example of referee test procedure:
#include <stdio.h>
int fn( int a, int n );int SumA( int a, int n );
int main(){
int a, n;
scanf("%d %d", &a, &n);
printf("fn(%d, %d) = %d\\n", a, n, fn(a,n));
printf("s = %d\\n", SumA(a,n));
return 0;
}
/* Your code will be embedded here */
Input example:
2 3
Output example:
fn(2, 3) = 222 s = 246
int fn( int a, int n )
{int i,c=a;
for(i=1;i<n;i++) a=a*10+c;
return a;
}
int SumA( int a, int n )
{
int i;
int sum=0;
for(i=1;i<=n;i++){
sum=sum+fn(a,i);//Recursive thought
}
return sum;
}
PTA exercise 6-3 using functions to output perfects within a specified range (20 points)
This problem requires to realize a simple function for calculating the sum of integer factors, and use it to realize another function to output all completions between two positive integers m and n (0 < m ≤ n ≤ 10000). The so-called perfect number is that the number is exactly equal to the sum of factors other than yourself. For example, 6 = 1 + 2 + 3, where 1, 2 and 3 are factors of 6.
Function interface definition:
int factorsum( int number ); void PrintPN( int m, int n );
The function factorsum must return the sum of the factors of int number; The function PrintPN shall output the factorization of the factor accumulation form of each perfection within the given range [m, n] line by line. Each perfection occupies one line. The format is "perfection = factor 1 + factor 2 +... + factor k", in which the perfections and factors are given in increasing order. If there is No perfect number in a given interval, a line of "No perfect number" is output.
Example of referee test procedure:
#include <stdio.h>
int factorsum( int number );void PrintPN( int m, int n );
int main(){
int m, n;
scanf("%d %d", &m, &n);
if ( factorsum(m) == m ) printf("%d is a perfect number\\n", m);
if ( factorsum(n) == n ) printf("%d is a perfect number\\n", n);
PrintPN(m, n);
return 0;
}
/* Your code will be embedded here */
Input example 1:
6 30
Output example 1:
6 is a perfect number 6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14
Input example 2:
7 25
Output example 2:
No perfect number
int factorsum(int number) {
int i,sum=0;
for(i=1;i<number;i++)
{if(number%i==0) sum+=i;}
return sum;
}
void PrintPN(int m, int n) {
int i,j,k,flag=0;
for(i=m;i<=n;i++)
{
if(i==factorsum(i))
{flag=1;
printf("%d = 1",i);
for(j=2;j<i;j++)
{if(i%j==0)
printf(" + %d",j);//The plus sign must precede
}
printf("\\n");
}
}
if(flag==0)
printf("No perfect number") ;
}
PTA exercise 6-4 use function to output Fibonacci number within specified range (20 points)
This problem requires to realize a simple function for calculating Fibonacci number, and use it to realize another function to output all Fibonacci numbers between two positive integers m and n (0 < m ≤ n ≤ 10000). The so-called Fibonacci sequence is a sequence that satisfies that any number is the sum of the first two terms (the first two terms are defined as 1).
Function interface definition:
int fib( int n ); void PrintFN( int m, int n );
The function fib must return the number of Fibonacci of the nth item; The PrintFN function outputs all Fibonacci numbers in the given range [m, n] in one line. There is a space between adjacent numbers, and there must be no redundant space at the end of the line. If there is No Fibonacci number in a given interval, a line of "No Fibonacci number" is output.
Example of referee test procedure:
#include <stdio.h>
int fib( int n );
void PrintFN( int m, int n );
int main(){
int m, n, t;
scanf("%d %d %d", &m, &n, &t);
printf("fib(%d) = %d\\n", t, fib(t));
PrintFN(m, n);
return 0;
}
/*Your code will be embedded here*/
Input example 1:
20 100 7
Output example 1:
fib(7) = 13 21 34 55 89
Input example 2:
2000 2500 8
Output example 2:
fib(8) = 21 No Fibonacci number
int fib(int n)
{
int n1=1,n2=1,ans;
if(n<3) return 1;
else{for(int i=3;i<=n;i++){
ans=n1+n2;
n1=n2;
n2=ans;}
return ans;
}
}
void PrintFN(int m,int n)
{ int stage[10000],count=0,i=1;
while(fib(i)<m) i++;
while(fib(i)<=n)
stage[count++]= fib(i++);
if(count==0) puts ("No Fibonacci number");
else {for(int j=0;j<count-1;j++) printf("%d ",stage[j]);
printf("%d",stage[count-1]);
}
}
PTA exercise 6-5 verifying Goldbach's conjecture with function (20 points)
This problem requires to realize a simple function to judge prime numbers, and use this function to verify Goldbach's conjecture: any even number not less than 6 can be expressed as the sum of two odd prime numbers. A prime number is a positive integer that can only be divided by 1 and itself. Note: 1 is not prime, 2 is prime.
Function interface definition:
int prime( int p ); void Goldbach( int n );
The function prime returns 1 when the parameter p passed in by the user is a prime number, otherwise it returns 0; The function Goldbach outputs the prime decomposition of N in the format "n=p+q", where p ≤ q are prime numbers. Because such decomposition is not unique (for example, 24 can be decomposed into 5 + 19 and 7 + 17), it is required to output the solution with the smallest P among all solutions.
Example of referee test procedure:
#include <stdio.h>#include <math.h>
int prime( int p );void Goldbach( int n );
int main(){
int m, n, i, cnt;
scanf("%d %d", &m, &n);
if ( prime(m) != 0 ) printf("%d is a prime number\\n", m);
if ( m < 6 ) m = 6;
if ( m%2 ) m++;
cnt = 0;
for( i=m; i<=n; i+=2 ) {
Goldbach(i);
cnt++;
if ( cnt%5 ) printf(", ");
else printf("\\n");
}
return 0;
}
/* Your code will be embedded here */
Input example:
89 100
Output example:
89 is a prime number 90=7+83, 92=3+89, 94=5+89, 96=7+89, 98=19+79 100=3+97,
int prime( int p )
{int ans=1;
if(p<2) ans= 0;
else if(p==2) ans=1;
else
{
for(int i=2;i<=sqrt(p);i++)
{
if(p%i==0){
ans=0;
break;
}
}
}
return ans;
}
void Goldbach( int n )
{
int a;
if(n%2==0&&n>=6)
{for(a=2;a<=n/2;a++)
if(prime(a)&&prime(n-a))
{printf("%d=%d+%d",n,a,n-a);
break;}
}
}
Introduction to programming -- C language final exam (rolling Division)
Input format:
Enter a fraction in one line. The numerator and denominator are separated by a slash "/". For example, 12 / 34 means 12 / 34. Both numerator and denominator are positive integers (excluding 0).
(rolling Division)
//Reduced minimal fraction
//First find the maximum common divisor, and then divide the numerator and denominator by the maximum common divisor at the same time;
#include <stdio.h>
int main()
{
int a,b,n1,n2;
scanf("%d/%d",&n1,&n2);
/*If n1 < n2, exchange the values of n1 and n2
if(n1<n2)
{
int t=n1;
n1=n2;
n2=t;
}*/
a=n1;b=n2;//Save first and divide last without defining redundant variables
while(n2!=0)
{int t=n1%n2;
n1=n2;
n2=t;
}
printf("%d/%d",a/n1,b/n1);
}
PTA exercise 10-7 decimal conversion to binary (15 points)
This problem requires the implementation of a function to convert the positive integer n into binary and output it.
Function interface definition:
void dectobin( int n );
The function dectobin should print binary n in one line. Recursive implementation is recommended.
Example of referee test procedure:
#include <stdio.h>
void dectobin( int n );
int main(){
int n;
scanf("%d", &n);
dectobin(n);
return 0;
}
/* Your code will be embedded here */
Input example:
10
Output example:
1010
void dectobin(int n) {
int a[1000], i = 0;
while (n / 2 != 0)
{
a[i++] = n % 2;
n /= 2;
}//3 / 2 = 1, 1 / 2 = 0, 1 will not be output, so a[i]=n manual output is required;
a[i] = n;
for (int j = i;j >= 0;j--)
printf("%d", a[j]);
}
PTA exercise 8-8 moving letters (10 points)
This problem requires writing a function to move the first three characters of the input string to the last.
Function interface definition:
void Shift( char s[] );
char s [] is the string passed in by the user, and its length shall not be less than 3; The Shift function must still store the converted String in s [].
Example of referee test procedure:
#include <stdio.h>#include <string.h>
#define MAXS 10
void Shift( char s[] );
void GetString( char s[] ); /* Implementation details are not shown here */
int main(){
char s[MAXS];
GetString(s);
Shift(s);
printf("%s\\n", s);
return 0;
}
/* Your code will be embedded here */
Input example:
abcdef
Output example:
defabc
void Shift( char s[] )
{ int a[10000],i,n=strlen(s),j;
for(i=0;i<3;i++)
{int k=s[0];
for(j=1;j<n;j++)
s[j-1]=s[j];
s[n-1]=k;
}
}
PTA exercise 8-1 splitting integer and decimal parts of real numbers (15 points)
This problem requires a simple function to split the integer and decimal parts of real numbers.
Function interface definition:
void splitfloat( float x, int *intpart, float *fracpart );
Where x is the split real number (0 ≤ x < 10000), * intpart and * fracpart are the integer part and decimal part of the real number X.
Example of referee test procedure:
#include <stdio.h>
void splitfloat( float x, int *intpart, float *fracpart );
int main(){
float x, fracpart;
int intpart;
scanf("%f", &x);
splitfloat(x, &intpart, &fracpart);
printf("The integer part is %d\\n", intpart);
printf("The fractional part is %g\\n", fracpart);
return 0;
}
/* Your code will be embedded here */
Input example:
2.718
Output example:
The integer part is 2 The fractional part is 0.718
Function interface definition:
//Where x is the split real number (0 ≤ x < 10000), * intpart and * fracpart are the integer part and decimal part of the real number X.
void splitfloat( float x, int *intpart, float *fracpart ){
*intpart = (int)x;
*fracpart = x- (*intpart);
}
PTA exercise 8-3 array cycle right (20 points)
This problem requires a simple function to rotate the array to the right: an array a contains n (> 0) integers, and each integer is rotated to the right by M (≥ 0) positions, that is, the data in a is transformed from (a0a1 * an − 1) to (an − m * an − 1a0a1 * an − m − 1) (the last m numbers are cycled to the top m positions).
Function interface definition:
int ArrayShift( int a[], int n, int m );
Where a [] is the array passed in by the user; n is the size of the array; m is the number of bits shifted to the right. The ArrayShift function must move the loop to the right, and the array still exists in a [].
Example of referee test procedure:
#include <stdio.h>#define MAXN 10
int ArrayShift( int a[], int n, int m );
int main(){
int a[MAXN], n, m;
int i;
scanf("%d %d", &n, &m);
for ( i = 0; i < n; i++ ) scanf("%d", &a[i]);
ArrayShift(a, n, m);
for ( i = 0; i < n; i++ ) {
if (i != 0) printf(" ");
printf("%d", a[i]);
}
printf("\\n");
return 0;
}
/*Your code will be embedded here*/
Input example:
6 2 1 2 3 4 5 6
Output example:
5 6 1 2 3 4
int ArrayShift( int a[], int n, int m )
{
for (int i=0;i<m;i++)
{int k=a[n-1];
for (int j=n-1;j>=1;j--)//The subscript of a[10] is 0123456789, and a[10] does not exist.
a[j]=a[j-1];
a[0]=k;
}
}
PTA exercise 8-4 count off (20 points)
The counting game is like this: n people form a circle and number them from 1 to N in order. Start counting from the first person, and those who report to m (< n) quit the circle; The next person starts counting from 1, and the person who reports to m quits the circle. Go on like this until you leave the last person.
This problem requires writing a function to give everyone's exit sequence number.
Function interface definition:
void CountOff( int n, int m, int out[] );
Where n is the initial number; m is the exit bit specified by the game (guaranteed to be a positive integer less than n). The function CountOff stores everyone's exit order number in the array out []. Because the C language array subscript starts from 0, the person at position i is the out[i-1] who exits.
Example of referee test procedure:
#include <stdio.h>#define MAXN 20
void CountOff( int n, int m, int out[] );
int main(){
int out[MAXN], n, m;
int i;
scanf("%d %d", &n, &m);
CountOff( n, m, out );
for ( i = 0; i < n; i++ )
printf("%d ", out[i]);
printf("\\n");
return 0;
}
/* Your code will be embedded here */
Input example:
11 3
Output example:
4 10 1 7 5 2 11 9 3 6 8
void CountOff( int n, int m, int out[] )
{
int a[MAXN],i,j=0,p=0,count=0;
for(i=0;i<n;i++) a[i]=i+1;
i=0;
while(count<n)
{
if(a[i]!=0) p++;
if(p==m){
j++;
out[i]=j;
p=0;
a[i]=0;
count++;
}
i++;
if(i==n) i=0;
}
}
PTA exercise 8-5 using function to copy part of string (20 points)
This problem requires writing a function to copy all characters from the m character in the input string t to the string s.
Function interface definition:
void strmcpy( char *t, int m, char *s );
The function strmcpy copies all characters from the m-th character in the input string char *t to the string char *s. If M exceeds the length of the input string, the resulting string should be an empty string.
Example of referee test procedure:
#include <stdio.h>
#define MAXN 20
void strmcpy( char *t, int m, char *s );
void ReadString( char s[] ); /* It is realized by the referee, and the table is omitted */
int main(){
char t[MAXN], s[MAXN];
int m;
scanf("%d\\n", &m);
ReadString(t);
strmcpy( t, m, s );
printf("%s\\n", s);
return 0;
}
/* Your code will be embedded here */
Input example:
7 happy new year
Output example:
new year
#include<string.h>
void strmcpy( char *t, int m, char *s )
{
int n,i,j=0,k;
meset(char *s,0,strlen(s));
//for(i=0;i<strlen(s);i++) s[i]=0;
n=strlen(t);
if(m>n) *s=NULL;
else {for(i=m-1;i<=n;i++)
s[j++]=t[i];
}
}
PTA exercise 8-6 delete characters (20 points)
This problem requires a simple function to delete the specified characters in the string.
Function interface definition:
void delchar( char *str, char c );
Where char *str is the incoming string and c is the character to be deleted. The function delchar deletes all c characters that appear in the string str.
Example of referee test procedure:
#include <stdio.h>#define MAXN 20 void delchar( char *str, char c ); void ReadString( char s[] ); /* It is realized by the referee, and the table is omitted */
int main(){
char str[MAXN], c;
scanf("%c\\n", &c);
ReadString(str);
delchar(str, c);
printf("%s\\n", str);
return 0;
}
/* Your code will be embedded here */
Input example:
a happy new year
Output example:
hppy new yer
void delchar( char *str, char c ){
int n=strlen(str);
for(int i=0;i<n;i++)
{while(str[i]==c) {for(int j=i;j<n;j++)
str[j]=str[j+1];
}
}
}
/*Why use while:
while()
{
.....
}
If the expression in the brackets after while is true, execute the statement in {}, and then judge whether the expression in () after while is true. If it is true, execute the statement in {} again until the condition in () is false.
if()
{
.......
}
Statement A
.........
If it is true in if, execute the statement in {} and execute the following statement A after execution. If false, execute statement A directly
for(i=0;i<10;i++)
{
.......
}
Statement A
......
Indicates that the statements in {} are executed from i=0 to I < 10.
i=0 Is initialization, and I < 10 is the execution condition. Only when this condition is met can it be executed. If not, skip and execute statement A and subsequent statements;
for Statement can realize the function of while statement,
for example
Int i=0；
while(i<10)
{
...........
i++;//Similar statements must appear, otherwise the exit condition cannot be met
....
}
for(;;)
{
}
Just in this way, the following statement will always be executed. Of course, you can also use break; To exit
for(;;)
{
........
if(i>10)
{
break;
}
i++;
........
} */
PTA exercise 8-8 judging palindrome string (20 points)
This question requires writing a function to judge whether a given string of characters is a "palindrome". The so-called "palindrome" refers to a string that is read in sequence and read backwards. For example, "XYZYX" and "xyzzyx" are palindromes.
Function interface definition:
bool palindrome( char *s );
The function palindrome determines whether the input string char *s is a palindrome. If yes, it returns true; otherwise, it returns false.
Example of referee test procedure:
#include <stdio.h>#include <string.h>
#define MAXN 20typedef enum {false, true} bool;
bool palindrome( char *s );
int main(){
char s[MAXN];
scanf("%s", s);
if ( palindrome(s)==true )
printf("Yes\\n");
else
printf("No\\n");
printf("%s\\n", s);
return 0;
}
/* Your code will be embedded here */
Input example 1:
thisistrueurtsisiht
Output example 1:
Yes thisistrueurtsisiht
Input example 2:
thisisnottrue
Output example 2:
Nothisisnottrue
bool palindrome( char *s )
{
int i,len=strlen(s),ans=true;
if(len%2==0)
{ for(i=0;i<(len/2);i++)
if(s[i]!=s[len-1-i]) ans = false;}
else{for(i=0;i<len/2;i++)
if(s[i]!=s[len-1-i]) ans = false;}
return ans;
}
//Very concise, ha ha!
PTA exercise 9-2 calculate the product of two complex numbers (15 points)
This problem requires a simple function to calculate the product of complex numbers.
Function interface definition:
struct complex multiply(struct complex x, struct complex y);
Where struct complex is a complex structure, which is defined as follows:
struct complex{
int real;
int imag;
};
Example of referee test procedure:
#include <stdio.h>
struct complex{
int real;
int imag;
};
struct complex multiply(struct complex x, struct complex y);
int main(){
struct complex product, x, y;
scanf("%d%d%d%d", &x.real, &x.imag, &y.real, &y.imag);
product = multiply(x, y);
printf("(%d+%di) * (%d+%di) = %d + %di\\n",
x.real, x.imag, y.real, y.imag, product.real, product.imag);
return 0;
}
/* Your code will be embedded here */
Input example:
3 4 5 6
Output example:
(3+4i) * (5+6i) = -9 + 38i
struct complex multiply(struct complex x, struct complex y)
{ struct complex product;//struct complex is equivalent to int
product.real=x.real*y.real-x.imag*y.imag;
product.imag=x.real*y.imag+x.imag*y.real;
return product;
}
PTA exercises 9-6 student scores by grade (20 points)
This problem requires a simple function to set the grade according to students' grades and count the number of failed students.
Function interface definition:
int set_grade( struct student *p, int n );
Where p is the pointer to the structure array of student information, which is defined as:
struct student{
int num;
char name[20];
int score;
char grade;
};
n is the number of array elements. Student number num, name and score are all stored. set_ The grade function needs to set the grade according to the student's score. Grade setting: 85-100 is A, 70-84 is B, 60-69 is C, and 0-59 is D. At the same time, set_grade also needs to return the number of failed students.
Example of referee test procedure:
#include <stdio.h>#define MAXN 10
struct student{
int num;
char name[20];
int score;
char grade;
};
int set_grade( struct student *p, int n );
int main(){ struct student stu[MAXN], *ptr;//The number of students is defined here;
int n, i, count;
ptr = stu;
scanf("%d\\n", &n);
for(i = 0; i < n; i++){
scanf("%d%s%d", &stu[i].num, stu[i].name, &stu[i].score);
}
count = set_grade(ptr, n);
printf("The count for failed (<60): %d\\n", count);
printf("The grades:\\n");
for(i = 0; i < n; i++)
printf("%d %s %c\\n", stu[i].num, stu[i].name, stu[i].grade);
return 0;
}
/* Your code will be embedded here */
Input example:
10 31001 annie 85 31002 bonny 75 31003 carol 70 31004 dan 84 31005 susan 90 31006 paul 69 31007 pam 60 31008 apple 50 31009 nancy 100 31010 bob 78
Output example:
The count for failed (<60): 1 The grades: 31001 annie A 31002 bonny B 31003 carol B 31004 dan B 31005 susan A 31006 paul C 31007 pam C 31008 apple D 31009 nancy A 31010 bob B
int set_grade( struct student *p, int n )
{
int c=0;
for(int i=0;i<n;i++)
{
if(p[i].score>=85&&p[i].score<=100) p[i].grade='A';
else if(p[i].score>=70&&p[i].score<=84) p[i].grade='B';
else if(p[i].score>=60&&p[i].score<=69) p[i].grade='C';
else if(p[i].score>=0&&p[i].score<=59) {p[i].grade='D';
c++;}
}
return c;
}
PTA exercise 10-1 calculate the sum of 1 to n using recursive functions (10 points)
This problem requires a simple function to recursively calculate the sum of 1 + 2 + 3 +... + n.
Function interface definition:
int sum( int n );
The function returns the sum of 1 + 2 + 3 +... + n for the incoming positive integer n; Returns 0 if n is not a positive integer. The problem is to ensure that the input and output are within the long integer range. It is recommended to try to write recursive functions.
Example of referee test procedure:
#include <stdio.h>
int sum( int n );
int main(){
int n;
scanf("%d", &n);
printf ("%d\\n", sum(n));
return 0;
}
/* Your code will be embedded here */
Input example 1:
10
Output example 1:
55
Input example 2:
0
Output example 2:
0
int sum( int n )
{ int ans;
if(n==1)
{
ans=1;
}else if(n<=0){
ans=0;
}else {ans = n+sum(n-1);}
return ans;
}
//Small recursion is simple.
PTA exercise 10-1 judge the three digits that meet the conditions (15 points)
This problem requires the implementation of a function to count the number of complete square numbers (such as 144 and 676) with the same two digits in the three digits in a given interval.
Function interface definition:
int search( int n );
The passed in parameter int n is a three digit positive integer (the highest digit is not 0). The function search returns the number of all qualified numbers in the [101, n] interval.
Example of referee test procedure:
#include <stdio.h>#include <math.h>
int search( int n );
int main(){
int number;
scanf("%d",&number);
printf("count=%d\\n",search(number));
return 0;
}
int search( int n )
{
int i;
int a,b,c;
int temp=0;
for(i=101;i<=n;i++)
{
a=i%10;
c=i/100;
b=i/10-10*c;
if((a==b)||(a==c)||(b==c))
{
for(int j=10;j<=i/2;j++)
if(j*j==i) temp++;//To accumulate numbers, temp=1 is wrong.
//int t=sqrt(i);
//if(t*t==i) temp++; it's fine too
}
}
return temp;
}
PTA exercise 10-3 recursive realization of exponential function (15 points)
This problem requires a function to calculate xn (n ≥ 1).
Function interface definition:
double calc_pow( double x, int n );
Function calc_pow should return the value of x to the nth power. Recursive implementation is recommended. The problem ensures that the results are within the double precision range.
Example of referee test procedure:
#include <stdio.h>
double calc_pow( double x, int n );
int main(){
double x;
int n;
scanf("%lf %d", &x, &n);
printf("%.0f\\n", calc_pow(x, n));
return 0;
}
/* Your code will be embedded here */
Input example:
2 3
Output example:
8
double calc_pow( double x, int n )
{ int ans=0;
if(n==1) ans=x;
else ans=x*calc_pow(x,n-1);
return ans;
}
PTA exercise 10-4 recursively finding the partial sum of simple alternating power series (15 points)
This problem requires a function to calculate the partial sum of the following simple interleaved power series:
f(x,n)=x−x2+x3−x4+⋯+(−1)n−1xn
Function interface definition:
double fn( double x, int n );
The title ensures that the incoming n is a positive integer, and the input and output are within the double precision range. The function fn should return the partial sum of the above series. It is recommended to try recursive implementation.
Example of referee test procedure:
#include <stdio.h>
double fn( double x, int n );
int main(){
double x;
int n;
scanf("%lf %d", &x, &n);
printf("%.2f\\n", fn(x,n));
return 0;
}
/* Your code will be embedded here */
Input example:
0.5 12
Output example:
0.33
double fn(double x, int n)
{
double ans = 0;
if(n==1){ans=x;}
else{ans=pow(-1,n-1)*pow(x,n)+fn(x,n-1);}
return ans;
}
PTA exercise 10-8 recursive sequential output of integers (15 points)
This problem requires the implementation of a function to output an integer in bit order.
Function interface definition:
void printdigits( int n );
The function printdigits should print each digit of n in order from high to low, with each digit occupying one line.
Example of referee test procedure:
#include <stdio.h>
void printdigits( int n );
int main(){
int n;
scanf("%d", &n);
printdigits(n);
return 0;
}
/* Your code will be embedded here */
Input example:
12345
Output example:
1 2 3 4 5
void printdigits(int n)
{
if (n < 10) printf("%d\\n", n);
else {
printdigits(n / 10);
printf("%d\\n", n % 10); //123456-12345-1234-123-12-1 then output 1-1 12% 10-2 123% 10-3 Output 1 2 3 4 5 6
}
}//If switching 123456 outputs 6 5 4 3 2 1
PTA exercise 11-1 output month English name (15 points)
This problem requires the implementation of the function, which can return the English name of a given month.
Function interface definition:
char *getmonth( int n );
The function getmonth should return a string header pointer that stores the English name of the month corresponding to n. If the passed in parameter n is not a number representing the month, a NULL pointer NULL is returned.
Example of referee test procedure:
#include <stdio.h>
char *getmonth( int n );
int main(){
int n;
char *s;
scanf("%d", &n);
s = getmonth(n);
if ( s==NULL ) printf("wrong input!\\n");
else printf("%s\\n", s);
return 0;
}
/* Your code will be embedded here */
Input example 1:
5
Output example 1:
May
Input example 2:
15
Output example 2:
wrong input!
char *getmonth( int n )
{
static char month[100][100]={"January","February","March","April","May","June","July","August","September","October","November","December"};
if(n>0&&n<13)
return &month[n-1][0];
else return NULL;
}
PTA exercise 11-2 find week (15 points)
This problem requires the implementation of the function. You can find the week according to the following table and return the corresponding serial number.
Serial number week 0 Sunday 1 Monday 2 Tuesday 3 Wednesday 4 Thursday 5 Friday 6 Saturday
Function interface definition:
int getindex( char *s );
The function getindex should return the string s ordinal. If the passed in parameter s is not a string representing the week, - 1 is returned.
Example of referee test procedure:
#include <stdio.h>#include <string.h>
#define MAXS 80
int getindex( char *s );
int main(){
int n;
char s[MAXS];
scanf("%s", s);
n = getindex(s);
if ( n==-1 ) printf("wrong input!\\n");
else printf("%d\\n", n);
return 0;
}
/* Your code will be embedded here */
Input example 1:
Tuesday
Output example 1:
2
Input example 2:
today
Output example 2:
wrong input!
int getindex( char *s )
{
int ans;
char *day[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
for (int i=0;i<=6;i++)
if(strcmp (s,day[i])==0) {ans=i;
break;}
else ans=-1;
return ans;
}
PTA exercise 11-3 calculate the longest string length (15 points)
This problem requires the implementation of a function to calculate the length of the longest string in the pointer array s with n elements.
Function interface definition:
int max_len( char *s[], int n );
Where n strings are stored in s [] and the function max_len should return the length of the longest string.
Example of referee test procedure:
#include <stdio.h>#include <string.h>#include <stdlib.h>
#define MAXN 10#define MAXS 20
int max_len( char *s[], int n );
int main(){
int i, n;
char *string[MAXN] = {NULL};
scanf("%d", &n);
for(i = 0; i < n; i++) {
string[i] = (char *)malloc(sizeof(char)*MAXS);
scanf("%s", string[i]);
}
printf("%d\\n", max_len(string, n));
return 0;
}
/* Your code will be embedded here */
Input example:
4 blue yellow red green
Output example:
6
int max_len( char *s[], int n ){
int max=0;
for(int i=0;i<n;i++)
{
if(strlen(s[max])<strlen(s[i])) max=i;//If i is incremented by max=0, i and i+1 do not have to be compared
}
return strlen(s[max]);
}
PTA exercise 11-4 string connection (15 points)
This problem requires the implementation of a function to connect two strings.
Function interface definition:
char *str_cat( char *s, char *t );
Function str_cat should copy string t to the end of string s and return the first address of string s.
Example of referee test procedure:
#include <stdio.h>#include <string.h>
#define MAXS 10
char *str_cat( char *s, char *t );
int main(){
char *p;
char str1[MAXS+MAXS] = {'\\0'}, str2[MAXS] = {'\\0'};
scanf("%s%s", str1, str2);
p = str_cat(str1, str2);
printf("%s\\n%s\\n", p, str1);
return 0;
}
/* Your code will be embedded here */
Input example:
abc def
Output example:
abcdef abcdef
char *str_cat( char *s, char *t ){
int len1=strlen(s),len2=strlen(t);
for(int i=0;i<len2;i++)
{
s[len1+i]=t[i];
}
return s;
}
/*
/*Function str_cat should copy string t to the end of string s and return the first address of string s.*/
char *str_cat( char *s, char *t )
{
char *p;
p=strcat(s,t);//The function strcat connects two strings into one string
return p;
}*/
Exercise 11-6 finding substrings (20 points)
This problem requires a simple function to find a string.
Function interface definition:
char *search( char *s, char *t );
The function search finds the substring t in the string s and returns the first address of the substring t in S. NULL if not found.
Example of referee test procedure:
#include <stdio.h>#define MAXS 30
char *search(char *s, char *t);void ReadString( char s[] ); /* Provided by the referee, details are not shown in the table */
int main(){
char s[MAXS], t[MAXS], *pos;
ReadString(s);
ReadString(t);
pos = search(s, t);
if ( pos != NULL )
printf("%d\\n", pos - s);
else
printf("-1\\n");
return 0;
}
/* Your code will be embedded here */
Input example 1:
The C Programming Language ram
Output example 1:
10
Input example 2:
The C Programming Languagebored
Output example 2:
-1
#include <string.h>
char *search( char *s, char *t )
{
int k=0,j,i;
char*p=NULL;
for(i=0;i<strlen(s);i++){
j=i;
while (s[j]==t[k]) {k++;j++;}
if(k>=strlen(t)) return &s[i];
k=0;//Prevent the existence of multiple t?????
}
return p;
}
PTA exercise 11-7 linked list of odd value nodes (20 points)
This problem requires two functions to store the read data as a single linked list and re form a new linked list of odd nodes in the linked list. The linked list node is defined as follows:
struct ListNode {
int data;
ListNode *next;
};
Function interface definition:
struct ListNode *readlist();struct ListNode *getodd( struct ListNode **L );
The function readlist reads a series of positive integers from the standard input, and establishes a single linked list according to the reading order. When reading − 1, it indicates the end of input, and the function should return a pointer to the single chain header node.
The function getodd separates the nodes with odd values in the single linked list L and reconstitutes a new linked list. Return the pointer to the header node of the new chain. At the same time, change the address stored in L to the header node address of the chain after deleting the odd value node (so pass in the pointer of L).
Example of referee test procedure:
#include <stdio.h>#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *readlist();struct ListNode *getodd( struct ListNode **L );void printlist( struct ListNode *L ){
struct ListNode *p = L;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}
int main(){
struct ListNode *L, *Odd;
L = readlist();
Odd = getodd(&L);
printlist(Odd);
printlist(L);
return 0;
}
/* Your code will be embedded here */
Input example:
1 2 2 3 4 5 6 7 -1
Output example:
1 3 5 7 2 2 4 6
struct ListNode *readlist()
{
struct ListNode *head=NULL,*tail=head,*p;
int n=1;
while(n!=-1){
scanf("%d",&n);
if(n!=-1){
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->data=n;
if(head==NULL) head=p;//Double equal
else tail->next=p;//tailnext
tail=p;
}
}
return head;//Remember to return
}
struct ListNode *getodd( struct ListNode **L )
{
struct ListNode *h1=NULL,*h2=NULL,*tail1=h1,*tail2=h2,*p;
int a;
while(*L){//Use while
a=(*L)->data;//brackets
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->next=NULL;
p->data=a;//Bring up the sentence in if and else
if(a%2){
//p->data=a;
if(h1==NULL) h1=p;
else tail1->next=p;
tail1=p;
}
else
{
// p->data=a;
if(h2==NULL) h2=p;
else tail2->next=p;
tail2=p;
}
(*L)=(*L)->next;
}
*L=h2;
return h1;
}
Niuke Tiba - algorithm Title Description
Write a program, accept a string, and then output the inverted string. (string length no more than 1000)
Example 1
input
"abcd"
Return value
"dcba"
void swap(int x,int y){
int temp=x;
x=y;
y=temp;
}
char* solve(char* str ) {
int i=0,j=strlen(str)-1;
while(i<j) swap(str[i++],str[j--]);
return str;
}
Niuke Tiba - algorithm Title Description
Given a string, write a function to determine whether the string is a palindrome. Return true if palindrome, false otherwise.
Example 1
input
"absba"
Return value
true
Example 2
input
"ranko"
Return value
false
Example 3
input
"yamatomaya"
Return value
false
Example 4
input
"a"
Return value
true
remarks:
The string length is no more than 1000000 and consists of lowercase letters only
#include <stdbool.h>
bool judge(char* str ) {
int i=0,j=strlen(str)-1;
while(i<j) if(str[i++]!=str[j--]) return false;
return true;
}//Only return once, so use! =, And else cannot be used.
LeetCode interview question 17.16 massagist
A famous masseur will receive a steady stream of appointment requests. Each appointment can be answered or not. There is a break between each appointment service, so she can't accept adjacent appointments. Given an appointment request sequence, find the optimal appointment set for the masseur (the longest total appointment time) and return the total minutes.
Note: this question is slightly changed from the original question
Example 1:
Input: [1,2,3,1] Output: 4 Explanation: select appointment No. 1 and appointment No. 3, and the total time is = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1] Output: 12 Explanation: select appointment No. 1, No. 3 and No. 5, and the total time is = 2 + 9 + 1 = 12.
Example 3:
Input: [2,1,4,5,3,1,1,3 ]Output: 12 Explanation: select appointment No. 1, No. 3, No. 5 and No. 8. The total time is = 2 + 4 + 3 + 3 = 12.
/*Problem solving ideas
int massage(int* nums, int numsSize){//numsSize Array size. Finally, you need to return the array size numsize
int t1=0,t2=0;
for(int i=0;i<numsSize;i++){
int t=fmax(t1+nums[i],t2);
t1=t2;
t2=t;
}
return t2;
}//**Suppose you accept the appointment for the I time, and the value is larger than the last time, and then take the larger value and save it. If you accept an appointment for the i-th time, the I + 1st time must not accept an appointment. If you do not accept an appointment for the i-th time, you may accept an appointment for the I + 1st time, or you may not accept an appointment for two consecutive times. Select the maximum value and save it, and finally return the result of the last comparison**//
LeetCode 1480. Dynamic sum of one-dimensional arrays
Give you an array nums. The calculation formula of array "dynamic sum" is: runningsum [i] = sum (Num [0]... Num [i]).
Please return the dynamic and of nums.
Example 1:
Input: nums = [1,2,3,4] Output:[1,3,6,10] Explanation: the dynamic and calculation process is [1, 1+2, 1+2+3, 1+2+3+4] .
Example 2:
Input: nums = [1,1,1,1,1] Output:[1,2,3,4,5] Explanation: the dynamic and calculation process is [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] .
Example 3:
Input: nums = [3,1,2,10,1] Output:[3,4,6,16,17]
Tips:
1 <= nums.length <= 1000 -10^6 <= nums[i] <= 10^6
int* runningSum(int* nums, int numsSize, int* returnSize){//Returns the size of the array
if( numsSize==0){
*returnSize = 0;
return NULL;
}
for(int i=1;i<numsSize;i++){
nums[i]+=nums[i-1];
}
*returnSize= numsSize;
return nums;
}
Sword finger Offer 24 Reverse linked list
Define a function, input the head node of a linked list, invert the linked list and output the head node of the inverted linked list.
Example:
input: 1->2->3->4->5->NULL output: 5->4->3->2->1->NULL
Limitations:
0 <= Number of nodes <= 5000
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* pre=NULL;//After the rotation, the first head - > next = null
struct ListNode* cur=head;
while(cur!=NULL){
struct ListNode* next=cur->next;
cur->next=pre;//Not pre = cur - > next!!! Make next point to pre!!
pre=cur;
cur=next;
}
return pre;//At this time, cur is NULL, and the title requires the return value to start with 5
}//The animation is very clear
```java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
PTA experiment 11-2-1 establishing student information link list (20 points)
This problem requires a simple function to organize the input student scores into a one-way linked list.
Function interface definition:
void input();
The function uses scanf to obtain student information from the input and organize it into a one-way linked list. The linked list node structure is defined as follows:
struct stud_node {
int num; /*Student number*/
char name[20]; /*full name*/
int score; /*achievement*/
struct stud_node *next; /*Pointer to the next node*/
};
The head and tail pointers of the one-way linked list are saved in the global variables head and tail.
Enter the information (student number, name, grade) of several students. It ends when the student number is 0.
Example of referee test procedure:
#include <stdio.h>#include <stdlib.h>#include <string.h>
struct stud_node {
int num;
char name[20];
int score;
struct stud_node *next;
};struct stud_node *head, *tail;
void input();
int main(){
struct stud_node *p;
head = tail = NULL;
input();
for ( p = head; p != NULL; p = p->next )
printf("%d %s %d\\n", p->num, p->name, p->score);
return 0;
}
/* Your code will be embedded here */
Input example:
1 zhang 78 2 wang 80 3 li 75 4 zhao 85 0
Output example:
1 zhang 78 2 wang 80 3 li 75 4 zhao 85
void input(){
int number;
struct stud_node *p;
scanf("%d",&number);
while(number!=0){//To use number, you cannot directly use p - > num;
p=(struct stud_node *)malloc(sizeof(struct stud_node));//Remember to add struct. This sentence should be written in while. You need to apply for new space every time
p->num=number;
if(head==NULL) head=p;//Double equals!!
else tail->next=p;//This completes the conversion of the next node
tail=p;
tail->next=NULL;
//scanf("%s %d %d",&p->name,&p->num,number); Why is it wrong to write in one line???
scanf("%s %d",&p->name,&p->score);
scanf("%d",&number);
}
}
PTA experiment 11-2-2 student achievement linked list processing (20 points)
This problem requires the realization of two functions: one is to organize the input student scores into a one-way linked list; Another student node whose score is lower than a certain score line is deleted from the linked list.
Function interface definition:
struct stud_node *createlist(); struct stud_node *deletelist( struct stud_node *head, int min_score );
The function createlist uses scanf to obtain student information from the input, organize it into a one-way linked list, and return the chain header pointer. The linked list node structure is defined as follows:
struct stud_node {
int num; /*Student number*/
char name[20]; /*full name*/
int score; /*achievement*/
struct stud_node *next; /*Pointer to the next node*/
};
Enter the information (student number, name, grade) of several students. It ends when the student number is 0.
The function deletelist deletes a list with a head pointer from the linked list_ Score and return the head pointer of the result linked list.
Example of referee test procedure:
#include <stdio.h>#include <stdlib.h>
struct stud_node {
int num;
char name[20];
int score;
struct stud_node *next;
};
struct stud_node *createlist();struct stud_node *deletelist( struct stud_node *head, int min_score );
int main(){
int min_score;
struct stud_node *p, *head = NULL;
head = createlist();
scanf("%d", &min_score);
head = deletelist(head, min_score);
for ( p = head; p != NULL; p = p->next )
printf("%d %s %d\\n", p->num, p->name, p->score);
return 0;
}
/* Your code will be embedded here */
Input example:
1 zhang 78 2 wang 80 3 li 75 4 zhao 85 0 80
Output example:
2 wang 80 4 zhao 85
struct stud_node* createlist() {
int number;
scanf("%d", &number);
struct stud_node* p,*head, * tail = head = NULL;
while (number != 0) {
p = (struct stud_node*)malloc(sizeof(struct stud_node));
p->num = number;
if (head == NULL) head = p;
else tail->next = p;
tail=p;
tail->next = NULL;
scanf("%s %d", &p->name, &p->score);
scanf("%d", &number);
}
return head;
}//See details https://blog.csdn.net/qq_53749266/article/details/115046995
/*Defined in the outside world is the global variable!!
struct stud_node {
int num;
char name[20];
int score;
struct stud_node *next;
};
struct stud_node *head, *tail;
*/
struct stud_node *deletelist(struct stud_node *head,int min_score)
{
struct stud_node *p,*tail;
//if(head==NULL) return NULL; Put it below to prevent deletion!!
while(head!=NULL&&head->score<min_score) {//If there is no head==NULL in front, write head here= NULL!!!
p=head;
head=head->next;
free(p);
}
if(head==NULL) return NULL;
p=head;
tail=p->next;
while(tail){
if(tail->score<min_score){
p->next=tail->next;//Connect the previous section with the next section. Use p. the head is always there.
free(tail);
}else p=tail;//P forward, always make p less than tail.
tail=tail->next;
}
return head;
}
Experiment 11-2-3 reverse order data establishment linked list (20 points)
This problem requires the implementation of a function to establish a linked list in the reverse order of the input data.
Function interface definition:
struct ListNode *createlist();
The function createlist uses scanf to obtain a series of positive integers from the input. When it reads − 1, it indicates the end of the input. Create a linked list according to the reverse order of the input data and return the chain header pointer. The linked list node structure is defined as follows:
struct ListNode {
int data;
struct ListNode *next;
};
Example of referee test procedure:
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist();
int main(){
struct ListNode *p, *head = NULL;
head = createlist();
for ( p = head; p != NULL; p = p->next )
printf("%d ", p->data);
printf("\\n");
return 0;
}
/* Your code will be embedded here */
Input example:
1 2 3 4 5 6 7 -1
Output example:
7 6 5 4 3 2 1
struct ListNode *createlist(){
int number;
scanf("%d",&number);
struct ListNode *p,*head=NULL;//head must be NULL at first!
while(number!=-1){
p=(struct ListNode *)malloc(sizeof(struct ListNode ));
p->data=number;
if(head==NULL)
{
head=p;
head->next=NULL;
}
else
p->next=head;//Always point from the first to the next
head=p;//Head back
scanf("%d",&number);
}
return head;
}
PTA experiment 11-2-4 delete even nodes of single linked list (20 points)
This problem requires two functions to store the read data as a single linked list and delete the even value nodes in the linked list. The linked list node is defined as follows:
struct ListNode {
int data;
struct ListNode *next;
};
Function interface definition:
struct ListNode *createlist(); struct ListNode *deleteeven( struct ListNode *head );
The function createlist reads in a series of positive integers from the standard input and establishes a single linked list according to the reading order. When reading − 1, it indicates the end of input, and the function should return a pointer to the single chain header node.
The function deleteeven deletes the even value node in the single linked list head and returns the head pointer of the result linked list.
Example of referee test procedure:
#include <stdio.h>#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist();struct ListNode *deleteeven( struct ListNode *head );void printlist( struct ListNode *head ){
struct ListNode *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}
int main(){
struct ListNode *head;
head = createlist();
head = deleteeven(head);
printlist(head);
return 0;
}
/* Your code will be embedded here */
Input example:
1 2 2 3 4 5 6 7 -1
Output example:
1 3 5 7
struct ListNode *createlist()
{
int number;
struct ListNode *p,*head,*tail=head=NULL;
scanf("%d",&number);
while(number!=-1){
p=(struct ListNode *)malloc(sizeof(struct ListNode ));
p->data=number;
if(head==NULL) head=p;
else tail->next=p;
tail=p;
tail->next=NULL;//Don't forget this sentence
scanf("%d",&number);
}
return head;
}
struct ListNode *deleteeven( struct ListNode *head )
{
struct ListNode *p,*tail;
while(head&&head->data%2==0){
p=head;
head=head->next;
free(p);
}
if(head==NULL) return NULL;
p=head;
tail=head->next;
while(tail){
if(tail->data%2==0){
p->next=tail->next;
free(tail);
}else p=tail;
tail=p->next;
}
return head;
}
PTA exercise 11-8 single linked list node deletion (20 points) experiment 11-2-8 single linked list node deletion (20 points)
This problem requires two functions to store the read data as a single linked list and delete all nodes in the linked list that store a given value. The linked list node is defined as follows:
struct ListNode {
int data;
ListNode *next;
};
Function interface definition:
struct ListNode *readlist(); struct ListNode *deletem( struct ListNode *L, int m );
The function readlist reads a series of positive integers from the standard input, and establishes a single linked list according to the reading order. When reading − 1, it indicates the end of input, and the function should return a pointer to the single chain header node.
The function deletem deletes all nodes in the single linked list L where m is stored. Returns a pointer to the header node of the result chain.
Example of referee test procedure:
#include <stdio.h>#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *readlist();struct ListNode *deletem( struct ListNode *L, int m );void printlist( struct ListNode *L ){
struct ListNode *p = L;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}
int main(){
int m;
struct ListNode *L = readlist();
scanf("%d", &m);
L = deletem(L, m);
printlist(L);
return 0;
}
/* Your code will be embedded here */
Input example:
10 11 10 12 10 -1 10
Output example:
11 12
struct ListNode *readlist(){
int number;
scanf("%d",&number);
struct ListNode *p,*head=NULL,*tail=head;//head must be equal to NULL
while(number!=-1){
p=(struct ListNode *)malloc(sizeof(struct ListNode ));
p->data=number;
if(head==NULL) head=p;
else tail->next=p;
tail=p;
tail->next=NULL;//Don't forget this sentence!!
scanf("%d",&number);//Don't forget to get the address!
}
return head;
}
struct ListNode *deletem( struct ListNode *L, int m ){//L is equivalent to head.
struct ListNode *p,*tail;
while(L&&L->data==m){
p=L;
L=L->next;
free(p);
}
if(L==NULL) return NULL;
p=L;
tail=L->next;
while(tail!=NULL){
if(tail->data==m){//It's Tail - > data, not tail
p->next=tail->next;
free(tail);
}else p=tail;//In the back p, we have to go forward.
tail=p->next;//If the data is continuously m, after tail - > next is given to p - > next, the tail is free (tail - > next does not exist), so use p - > next;!
}
return L;
}
LeetCode 905. Sort arrays by parity
Given A nonnegative integer array A, returns an array in which all even elements of A are followed by all odd elements.
You can return any array that meets this condition as the answer.
Example:
Input:[3,1,2,4] Output:[2,4,3,1] output [4,2,3,1]，[2,4,1,3] and [4,2,1,3] Will also be accepted.
Tips:
1.1 <= A.length <= 5000 2.0 <= A[i] <= 5000
int* sortArrayByParity(int* A, int ASize, int* returnSize){
int *ret=(int *)malloc(sizeof(int)*ASize);
int head=0,tail=ASize-1;
*returnSize = ASize;
for(int i=0;i<ASize;i++){
if(A[i]&1) ret[tail--]=A[i];//==if(A[i] %2==1)
else ret[head++]=A[i];
}
return ret;
}
PTA exercise 1.8 two point search (20 points)
This problem requires the implementation of binary search algorithm.
Function interface definition:
Position BinarySearch( List L, ElementType X );
The List structure is defined as follows:
typedef int Position;typedef struct LNode *List;struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* Saves the position of the last element in the linear table */
};
L is a linear table passed in by the user, in which ElementType elements can be compared through >, = =, <, and the title ensures that the incoming Data is incremental and orderly. The BinarySearch function finds the position of X in the Data, that is, the array subscript (Note: the element is stored from subscript 1). If found, the subscript is returned; otherwise, a special failure flag NotFound is returned.
Example of referee test procedure:
#include <stdio.h>#include <stdlib.h>
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* Saves the position of the last element in the linear table */
};
List ReadInput(); /* The referee realizes, and the details are not shown in the table. The element is stored from subscript 1 */Position BinarySearch( List L, ElementType X );
int main(){
List L;
ElementType X;
Position P;
L = ReadInput();
scanf("%d", &X);
P = BinarySearch( L, X );
printf("%d\\n", P);
return 0;
}
/* Your code will be embedded here */
Input example 1:
5 12 31 55 89 101 31
Output example 1:
2
Input example 2:
326 78 23331
Output example 2:
0
Position BinarySearch( List L, ElementType X )
{
int low=1,high=L->Last,mid;
while(low<=high){
mid=(high+low)/2;
if(L->Data[mid]>X) high-=1;
else if(L->Data[mid]<X) low+=1;
else return mid;
}
return NotFound;
}
PTA experiment 11-2-6 odd value node list (20 points)
This problem requires two functions to store the read data as a single linked list and re form a new linked list of odd nodes in the linked list. The linked list node is defined as follows:
struct ListNode {
int data;
ListNode *next;
};
Function interface definition:
struct ListNode *readlist(); struct ListNode *getodd( struct ListNode **L );
The function readlist reads a series of positive integers from the standard input, and establishes a single linked list according to the reading order. When reading − 1, it indicates the end of input, and the function should return a pointer to the single chain header node.
The function getodd separates the nodes with odd values in the single linked list L and reconstitutes a new linked list. Return the pointer to the header node of the new chain. At the same time, change the address stored in L to the header node address of the chain after deleting the odd value node (so pass in the pointer of L).
Example of referee test procedure:
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *readlist();struct ListNode *getodd( struct ListNode **L );void printlist( struct ListNode *L ){
struct ListNode *p = L;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
}
int main(){
struct ListNode *L, *Odd;
L = readlist();
Odd = getodd(&L);
printlist(Odd);
printlist(L);
return 0;
}
/* Your code will be embedded here */
Input example:
1 2 2 3 4 5 6 7 -1
Output example:
1 3 5 7 2 2 4 6
struct ListNode *readlist(){
int number;
scanf("%d",&number);
struct ListNode *p,*head,*tail=head=NULL;
while(number!=-1){
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->data=number;
p->next=NULL;//NULL after tail
if(head==NULL) head=p;
else tail->next=p;
tail=p;
scanf("%d",&number);
}
return head;
}
struct ListNode *getodd( struct ListNode **L ){
struct ListNode *newhead,*p,*newtail=newhead=NULL,*head,*tail=head=NULL;;
//int count=0;
while(*L){
p=(*L)->next; //p is the second node, and * L - > next will be modified in if and else, so it will be written out in advance
if((*L)->data%2!=0){
if(newhead==NULL){
newhead=*L;
}else{
newtail->next=*L;
}
newtail=*L;
newtail->next=NULL;
*L=p;//Next node
}else{
if(head==NULL){
head=*L;
}else{
tail->next=*L;
}
tail=*L;
tail->next=NULL;
*L=p;
}
}
*L=head;//Finally, return the head to * L, and the rest are even numbers
return newhead;
}
PTA experiment 11-2-7 statistics of the number of professionals (15 points)
This problem requires the implementation of a function to count the number of students majoring in computer in the student number chain. The linked list node is defined as follows:
struct ListNode {
char code[8];
struct ListNode *next;
};
The student number here is 7 digits in total, of which the second and third digits are the major number. The number of computer major is 02.
Function interface definition:
int countcs( struct ListNode *head );
Where head is the head pointer of the student ID linked list passed in by the user; The function counts counts and returns the number of students majoring in computer in the head linked list.
Example of referee test procedure:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ListNode {
char code[8];
struct ListNode *next;
};
struct ListNode *createlist(); /*The referee realizes, and the details are not shown in the table*/int countcs( struct ListNode *head );
int main(){
struct ListNode *head;
head = createlist();
printf("%d\\n", countcs(head));
return 0;
}
/* Your code will be embedded here */
Input example:
1021202 2022310 8102134 1030912 3110203 4021205
Output example:
3
int countcs(struct ListNode *head )
{
struct ListNode *p;
int count = 0;
for(p = head; p != NULL; p = p->next)
if(p->code[1] == '0' && p->code[2] == '2')
count++;
return count;
}
707. Design linked list
Design the implementation of linked list. You can choose to use single linked list or double linked list. A node in a single linked list should have two attributes: val and next. val is the value of the current node, and next is the pointer / reference to the next node. If you want to use a two-way linked list, you also need an attribute prev to indicate the previous node in the linked list. It is assumed that all nodes in the linked list are 0-index.
Implement these functions in the linked list class:
get(index): get the value of the index node in the linked list. Returns - 1 if the index is invalid.
addAtHead(val): add a node with value val before the first element of the linked list. After insertion, the new node will become the first node in the linked list.
addAtTail(val): append the node with the value of val to the last element of the linked list.
addAtIndex(index,val): add a node with value val before the index node in the linked list. If the index is equal to the length of the linked list, the node will be attached to the end of the linked list. If the index is greater than the length of the linked list, the node will not be inserted. If the index is less than 0, the node is inserted in the header.
deleteAtIndex(index): if the index is valid, delete the index node in the linked list.
Example:
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //The linked list becomes 1 - > 2 - > 3 linkedList.get(1); //Return 2 linkedList.deleteAtIndex(1); //Now the linked list is 1 - > 3 linkedList.get(1); //Return 3
Tips:
All val All values are [1, 1000] Within. The number of operations will be [1, 1000] Within. Do not use built-in LinkedList Library.
typedef struct {
int val;
struct MyLinkedList *next;
} MyLinkedList;
/** Initialize your data structure here. */
/*First edition, error demonstration
Idea:
Create an obj that is NULL:
When there is add, judge that if obj is empty now, assign it to the first node.
Another one, hang on the next of this node.
Problems:
1. obj The content pointed to by itself will change with the first node.
Because we have an interface, we can add nodes on the head of the linked list. In this way, every time obj is the first node of the linked list, its direction will change.
I don't think there is any problem, but in fact, in the actual measurement, obj will become invalid after it is called from the function (I don't know why, please ask the comment area for advice. The addresses are malloc)
Causes an error.
2. When it comes to index, you need to judge whether it is an empty linked list every time, and it is not easy to judge when index = 0
3. Freeing memory also causes problems
Author: Songshu
Link:< https://leetcode-cn.com/problems/design-linked-list/solution/707-she-ji-lian-biao-cyu-yan-chao-xiang-xi-ban-ben/ >
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.*/
MyLinkedList* myLinkedListCreate() {
MyLinkedList *obj=(MyLinkedList *)malloc(sizeof(MyLinkedList));
obj->val=0;
obj->next=NULL;
return obj;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList* obj, int index) {
/* 1,Intercept obvious invalid indexes
Three invalid indexes
1. index < 0
2. The linked list is empty and any index is invalid.
3. index The length of the linked list is exceeded*/
if(index<0||!obj->next) return -1;
MyLinkedList *p=obj->next;//To make p the first node is obj - > next, not obj
for(int i=0;i<index;i++){//Why i start with 0? Do nodes start from 0?
p=p->next;
if(!p){
return -1;
}
}
if(p) return p->val;
else return -1;
/*If P exists, return the value of p; if not, return - 1;*/
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
MyLinkedList *p=(MyLinkedList*)malloc(sizeof(MyLinkedList));
p->val=val;
p->next=obj->next;
obj->next=p;
}
/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {//
MyLinkedList *p=obj,*p1=(MyLinkedList *)malloc(sizeof(MyLinkedList));
p1->val=val;
p1->next=NULL;
while(p->next){
p=p->next;
}
p->next=p1;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
if(index<=0) return myLinkedListAddAtHead(obj,val);/*If it is a negative index direct connector insertion method, then return to the head node
It's been changed for a long time. There's no return!!!!!!! returnreturn inserts the linked list of a node after returning the head node;*/
/*First complete the initialization of the node in the first step, and then proceed to the second and third steps*/
MyLinkedList *p=obj,*p1=(MyLinkedList*)malloc(sizeof(MyLinkedList));
p1->val=val;
p1->next=NULL;
/*Find the index-1 node*/
for(int i=0;i<index;i++){
p=p->next;
if(!p) free(p1);
}
p1->next=p->next;
p->next=p1;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
/*It's easy to make mistakes when using for*/
MyLinkedList *p=obj,*p1;
int j=0;
while((p->next)&&(j<index)){
j++;
p=p->next;
}
p1=p->next;
if(p1){
p->next=p1->next;
free(p1);
}
}
void myLinkedListFree(MyLinkedList* obj) {
MyLinkedList *p=obj->next;
while(obj){
p=obj;
obj=obj->next;
free(p);
}
}
/**
* Your MyLinkedList struct will be instantiated and called as such:
* MyLinkedList* obj = myLinkedListCreate();
* int param_1 = myLinkedListGet(obj, index);
* myLinkedListAddAtHead(obj, val);
* myLinkedListAddAtTail(obj, val);
* myLinkedListAddAtIndex(obj, index, val);
* myLinkedListDeleteAtIndex(obj, index);
* myLinkedListFree(obj);
*/
141. Circular linked list
Given a linked list, judge whether there are links in the linked list.
If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the rings in a given list, we use the integer pos to represent the position where the tail of the list is connected to the list (the index starts from 0). If pos is - 1, there is no ring in the linked list. Note: pos is not passed as a parameter, but only to identify the actual situation of the linked list.
Returns true if there are links in the linked list. Otherwise, false is returned.
Advanced:
Can you solve this problem with O(1) (i.e., constant) memory?
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: there is a ring in the linked list, and its tail is connected to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: there is a ring in the linked list, and its tail is connected to the first node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: there are no links in the linked list.
Tips:
The number range of nodes in the linked list is [0, 104] -105 <= Node.val <= 105 pos by -1 Or a valid index in the linked list.
bool hasCycle(struct ListNode *head) {
if(!head||!head->next) return false;
struct ListNode *p1, *p2=p1=head;
while(p2&&p2->next){//p2 must be written, and cannot be written as while (p2 - > next & & p2)
/*p2->next If it does not exist, it means that it is not a circular linked list. If it is not a circular linked list, the cycle will terminate, and then execute the final return false*/
p1=p1->next;
p2=p2->next->next;//p2 takes one step more than p1 each time to gradually catch up with p1
if(p1==p2) return true;
}
return false;
}
For the circular linked list, first define p1p2 as the slow and fast pointer respectively, make the fast pointer P2 take one step more than p1 each time, gradually catch up with p1, and then return true when judging that the two pointers are equal. Use while (P2 & & P2 - > next), where P2 must be written before and cannot be written as while (P2 - > next & & P2), otherwise the compilation fails. If the loop condition P2 - > next does not exist, it indicates that it is not a circular linked list or a circular linked list, the loop will terminate, and then execute the final return false
LeetCode 142. Circular linked list II
Given a linked list, return the first node from the linked list into the ring. If the linked list is acyclic, null is returned.
In order to represent the rings in a given list, we use the integer pos to represent the position where the tail of the list is connected to the list (the index starts from 0). If pos is - 1, there is no ring in the linked list. Note that pos is only used to identify the ring and is not passed to the function as an argument.
Note: it is not allowed to modify the given linked list.
Advanced:
can you use O(1) space to solve this problem?
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: returns the linked list node with index 1. Explanation: there is a ring in the linked list, and its tail is connected to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: returns the linked list node with index 0. Explanation: there is a ring in the linked list, and its tail is connected to the first node.
Example 3:
Input: head = [1], pos = -1 Output: Return null Explanation: there are no links in the linked list.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *p1,*p2=p1=head;
int flag=0;//Be sure to initialize to 0
while(p2&&p2->next){
p1=p1->next;
p2=p2->next->next;
if(p1==p2) {
flag=1;/*p1，p2 If the flag exists, there must be a ring*/
break;
}/*Remember to exit if the meeting point is found. If the circular linked list does not meet the while condition, it will exit automatically*/
}
if(flag){
p1=head;
while(p1!=p2){
p1=p1->next;
p2=p2->next;
}/*flag If it exists, there must be a ring, and the loop can end. After that, just return to the node pointed to by the pointer*/
return p1;
}
return NULL;
}
Double fingered needle method: set the fast pointer to meet when it has walked n circles. At this time, the slow pointer has walked x+y nodes. It is calculated that the length x outside the ring is equal to the length z from the meeting point to the entry point. After the fast and slow pointers meet, one pointer returns to the head node, and the other pointer continues to start from the meeting point. At this time, the fast and slow pointers move the same distance at the same time. The node after meeting again is the entry node. Remember to initialize flag to 0, p1 and p2, then
flag
If there is, there must be a ring. Use if to judge
flag
If it exists, make the slow pointer return to the header node for reuse
while
Find the incoming ring node that meets, because
flag
The existential ring must exist, so there is no need to worry that the loop will not terminate. After termination, it will directly return to the encounter node. If the ring does not exist
flag=0
Directly execute the last step return NULL
LeetCode 160. Intersecting linked list
Write a program to find the starting node where two single linked lists intersect.
As shown in the following two linked lists:
The intersection begins at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input explanation: the value of intersection node is 8 (note that if two linked lists intersect, it cannot be 0). The linked list starts from the respective header A by [4,1,8,4,5]，Linked list B by [5,0,1,8,4,5]. stay A In, there are 2 nodes before the intersecting node; stay B In, there are 3 nodes before the intersection node.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Reference of the node with value = 2 Input explanation: the value of intersection node is 2 (note that if two linked lists intersect, it cannot be 0). The linked list starts from the respective header A by [0,9,1,2,4]，Linked list B by [3,2,4]. stay A In, there are 3 nodes before the intersection node; stay B In, there is 1 node before the intersection node.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: null Input explanation: the linked list starts from the respective header A by [2,6,4]，Linked list B by [1,5]. Because the two linked lists do not intersect, so intersectVal Must be 0, and skipA and skipB Can be any value. Explanation: the two linked lists do not intersect, so they return null.
be careful:
if two linked lists have no intersection, null is returned
after returning the results, the two linked lists must still maintain the original structure.
it can be assumed that there are no cycles in the whole linked list structure.
the program shall meet the O(n) time complexity as much as possible, and only use O(1) memory.
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(!headA||!headB) return NULL;
struct ListNode *p1=headA,*p2=headB;
while(p1!=p2){
p1=p1?p1->next:headB;
p2=p2?p2->next:headA;
/*NULL is also regarded as the last node of the two linked lists, which has no effect on the respective length and total length.
Writing p1p2 instead of P1 - > next P2 - > next can also judge the empty linked list*/
}
return p1;
}
Mathematically proved that each cycle of their journey is equal, which is A+B=B+A.
If they do not intersect, they will go to the last NULL after passing through the same number of nodes, and the loop ends.
If we intersect, then we push back. Since we can meet at the tail node, the successor nodes of the tail node also meet until we push back to the first intersection point.
LeeCode 19. Delete the penultimate node of the linked list
Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.
Advanced: can you try using one scan?
Example 1:
Input: head = [1,2,3,4,5], n = 2 Output:[1,2,3,5]
Example 2:
Input: head = [1], n = 1 Output:[]
Example 3:
Input: head = [1,2], n = 1 Output:[1]
Tips:
The number of nodes in the linked list is sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode*p=NULL,*p1,*p2=p1=head;
int k=n;
while(k-1){
p2=p2->next;
k--;
}/*Make p2 advance n-1 nodes to the nth node, which is equivalent to for (int i = 0; I < n-1; I + +) p2 = p2 - > next;*/
while(p2->next){
p2=p2->next;
p=p1;
p1=p1->next;
}
if(p==NULL) head=head->next;/*It is important to deal with boundary values, such as deleting header nodes when k < 0*/
else p->next=p1->next;
free(p1);
return head;
}
LeeCode 206. Reverse linked list
Reverse a single linked list.
Example:
input: 1->2->3->4->5->NULL output: 5->4->3->2->1->NULL
Advanced:
You can iterate or recursively reverse the linked list. Can you solve the problem in two ways?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//**Method 1: iteration**//
struct ListNode* reverseList(struct ListNode* head){
struct ListNode*cur=head,*pre=NULL;
while(cur){
struct ListNode*tempnext=cur->next; /*If temp=cur, temp - > next will change with cur - > next. Therefore, cur - > next should be saved in advance instead of cur*/
cur->next=pre;
pre=cur;/*pre Be sure to follow cur, so that the previous node can point to the next one*/
cur=tempnext;
}
return pre;/*If the head node cur does not exist, NULL is returned directly*/
}
//**Method 2: recursion**//
struct ListNode* reverseList(struct ListNode* head){
if(!head||!head->next) return head;
struct ListNode*newhead=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return newhead;
}
Recursion from the back to the front and recursion to the last. The last node is newhead and the penultimate node is head. Make newhead point to head, and then cancel the point of head - > next to newhead. In the process of recursion from the back to the front, head - > next - > next and head - > next are changed, and newhead has always been the last node! The linked list starts from the last item, and the original head node points to NULL. Therefore, the last new header node is returned
LeeCode 328. Parity linked list
Given a single linked list, all odd and even nodes are arranged together. Note that the odd and even nodes here refer to the parity of node numbers, not the parity of node values.
Try using the in place algorithm. The space complexity of your algorithm should be O(1), the time complexity should be O(nodes), and nodes is the total number of nodes.
Example 1:
input: 1->2->3->4->5->NULL output: 1->3->5->2->4->NULL
Example 2:
input: 2->1->3->5->6->4->7->NULL output: 2->3->6->7->1->5->4->NULL
explain:
The relative order of odd and even nodes should be maintained. The first node of the linked list is regarded as an odd node, the second node is regarded as an even node, and so on.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
Judge whether the whole linked list has been traversed, for example, 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > null. When traversing the node with node value of 6 (pevenhead - > next = = null), it means that the whole linked list has been traversed; 1 - > 2 - > 3 - > 4 - > 5 - > null; when traversing the node with node value of 5 (oddhead - > next = = null), it means that the whole linked list has been traversed. The official judgment condition while (even! = null & & even. Next! = null) is actually the same. Its even is odd - > next.*/
struct ListNode* oddEvenList(struct ListNode* head){
if(!head||!head->next) return head;
struct ListNode*oddhead=head,*evenhead=head->next,*pevenhead=evenhead;
while(oddhead->next&&pevenhead->next){
oddhead->next=oddhead->next->next;
oddhead=oddhead->next;
pevenhead->next=pevenhead->next->next;
pevenhead=pevenhead->next;
}
oddhead->next=evenhead;
return head;
}
Firstly, oddhead is defined to store odd nodes and pevenhead stores even nodes. Evenhead is fixed as the head node of even nodes. Use the while loop to traverse the whole linked list. When either oddhead - > next or pevenhead - > next does not exist, it indicates that the linked list has completed the traversal, which is expressed as while (oddhead - > next & & pevenhead - > next). At this time, make the last odd node point to the fixed evenhead, Just return the header node head.
LeetCode 21. Merge two ordered linked lists
Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]Output:[1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []Output:[]
Example 3:
Input: l1 = [], l2 = [0]Output:[0]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/*Method 1: recursion*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1==NULL) return l2;
if(l2==NULL) return l1;
if(l1->val<l2->val) {
l1->next=mergeTwoLists(l1->next,l2);
return l1;
}else {
l2->next=mergeTwoLists(l2->next,l1);
return l2;
}
/*Each traversal assigns the smaller node - > next and the smaller node in another linked list to the next of the node until the traversal is empty*/
}
/*Method 2: iteration*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode*head=(struct ListNode*)malloc(sizeof(struct ListNode)),*p=head;
/*Control the head unchanged, and the double pointer p makes a small tail to connect the nodes*/
if(!l1) return l2;
if(!l2) return l1;
while(l1&&l2){
if(l1->val<=l2->val){//If L1 - > Val = = L2 - > Val, it exists directly after p in order.
p->next=l1;
l1=l1->next;
}else{
p->next=l2;
l2=l2->next;
}
p=p->next;
}
if(!l1) p->next=l2;
if(!l2) p->next=l1;
return head->next;
}
/*Method 3: hard pulling + simplified bubbling*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(!l1) return l2;
if(!l2) return l1;
struct ListNode*p=l1,*q=NULL;
while(p->next){
p=p->next;
}
p->next=l2;
for(p=l1;p;p=p->next){
for(q=p->next;q;q=q->next){
if(p->val>q->val){
int t=p->val;
p->val=q->val;
q->val=t;
}
}
}
return l1;
}
Last time, we used to connect the two linked lists and then arrange the simplified bubble sorting. This time, we used recursive and iterative methods to recurse. Because each layer recursively returns the node with small value and connects the node with the next small node, when any of l1 or l2 is empty, the recursion ends, and the first layer recursively returns the smaller header node in l1 and l2, It is equivalent to directly returning an ordered linked list. The second iteration of the method defines two pointers. The head remains unchanged and is used for the final return. p is used as a small tail to connect the newly added nodes. When l1l2 still exists, insert the subsequent nodes in turn. If it does not exist, directly connect the remaining linked list behind, because l1l2 has been arranged in ascending order, and then return to the head node. If (l1 - > Val < = l2 - > VAL) should be followed by the less than sign. If it is not added, it can pass LEETCODE, but it can not pass a test point of PTA.
LeetCode 203. Remove linked list elements
Give you a head node of the linked list and an integer val. please delete all nodes in the linked list that meet the requirements Val = = Val's node and returns a new header node.
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6 Output:[1,2,3,4,5]
Example 2:
Input: head = [], val = 1 Output:[]
Example 3:
Input: head = [7,7,7,7], val = 7 Output:[]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
while(head){
if(head->val==val) head=head->next;
else break;
}
if(!head ) return NULL;
struct ListNode*p2=head->next,*p1=head;
while(p2){
if(p2->val==val){//To delete p2, just move p2 and change the next of p1
p1->next=p2->next;
free(p2);
p2=p1->next;
}else {//If not deleted, p1p2 move forward together
p1=p1->next;//p1 should advance before p2, p2 = p1 - > next
p2=p1->next;
}
}
return head;
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyhead = new ListNode(0),temp = dummyhead;
dummyhead.next=head;
while(temp.next != null){
if(temp.next.val==val){
temp.next = temp.next.next;
}else{
temp = temp.next;
}
}
return dummyhead.next;
}
}
LeetCode 61. Rotating linked list
Give you a head node of the linked list. Rotate the linked list and move each node of the linked list k positions to the right.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output:[4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4 Output:[2,0,1]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/*Not very considerate, 1 We didn't consider the problem of too large k value. We should continue to work hard
2.It is not considered that the header node is empty
3.k is not considered as a multiple of count*/
struct ListNode* rotateRight(struct ListNode* head, int k){
if(!head) return NULL;
struct ListNode*p=head,*p1=NULL,*p2=NULL;
int count=0,m=0;
while(p){
p=p->next;
count++;
}
k%=count;
if(k==0) return head;//If it is a multiple of i or 0, the header node is returned directly
p=head;
p1=head;
while(count-k-m-1){
p=p->next;
m++;
}/*p Go to the penultimate k+1, p1 goes to the penultimate k*/
p1=p->next;//Don't forget that
p->next=NULL;
p2=p1;
while(p2->next) p2=p2->next;
p2->next=head;
return p1;
}
LeetCode 2. Add two numbers
Give you two non empty linked lists to represent two non negative integers. They store each number in reverse order, and each node can store only one number.
Please add the two numbers and return a linked list representing sum in the same form.
You can assume that neither number starts with 0 except the number 0.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4] Output:[7,0,8] Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0] Output:[0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output:[8,9,9,9,0,0,0,1]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/*1.It is not considered that if tempval still exists at the end of L1 and L2, it needs to enter a bit later.
2.The leading node does not apply for space for new nodes. It is easier to apply for a new node assignment first than to assign a new node first and then connect. If the lead node is used, first apply for a node and then assign a value to the new node. In the next cycle, apply for a new node. If the lead node is not used, the method of applying first and then assigning a value will apply for one more node at the end of the cycle.
Stick to your right ideas*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
if(!l1) return l2;
if(!l2) return l1;
struct ListNode*returnlist=(struct ListNode*)malloc(sizeof(struct ListNode)),*p=returnlist;
int tempval=0;
while(l1||l2||tempval){
if(l1){
tempval+=l1->val;
l1=l1->next;
}
if(l2){
tempval+=l2->val;
l2=l2->next;
}
p->next=(struct ListNode*)malloc(sizeof(struct ListNode));
p=p->next;
p->val=tempval%10;
tempval/=10;
}
p->next=NULL;
return returnlist->next;
}
LeetCode 138. Copy linked list with random pointer
Give you a linked list with a length of n. each node contains an additional random pointer random, which can point to any node or empty node in the linked list.
To construct this linked list Deep copy . The deep copy should consist of exactly n new nodes, in which the value of each new node is set to the value of its corresponding original node. The next pointer and random pointer of the new node should also point to the new node in the replication linked list, and these pointers in the original linked list and the replication linked list can represent the same linked list state. The pointer in the copy linked list should not point to the node in the original linked list.
For example, if there are two nodes X and Y in the original linked list, where x.random -- > y. Then, the corresponding two nodes X and Y in the copy linked list also have x.random -- > y.
Returns the header node of the copy linked list.
A linked list composed of n nodes is used to represent the linked list in input / output. Each node is represented by a [val, random_index]:
- Val: one represents node Integer of val.
- random_index: the node index pointed by the random pointer (range from 0 to n-1); null if it does not point to any node.
Your code only accepts the head node of the original linked list as the incoming parameter.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output:[[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output:[[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]] Output:[[3,null],[3,0],[3,null]]
Example 4:
Input: head = [] Output:[] Explanation: the given linked list is null (null pointer), so it returns null.
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
/* 1.There is no case where the write head is empty
2.The deep copy writes while as if*/
/*Method 1: twice traversal*/
struct Node* copyRandomList(struct Node* head)
{
if(!head) return head;
struct Node*p1=head,*chead=NULL,*p2=chead;
struct Node*u1,*u2;
/*Shallow copy*/
while(p1)
{/*Create a new tail node, and then make the previous tail point to this node*/
struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
temp->val=p1->val;
temp->next=NULL;
temp->random=NULL;
if(!chead) chead=temp;
else p2->next=temp;
p2=temp;
p1=p1->next;
}
p1=head;
p2=chead;
/*Deep copy*/
while(p1){
if(!p1->random)
p2->random=NULL;
else
{
u1=head;
u2=chead;
while(p1->random!=u1){
u1=u1->next;
u2=u2->next;
}
p2->random=u2;
}
p1 = p1->next;
p2 = p2->next;
}
return chead;
}
LeetCode 155. Minimum stack
Design a stack that supports push, pop and top operations and can retrieve the smallest element in a constant time.
- push(x) -- pushes element x onto the stack.
- pop() -- delete the element at the top of the stack.
- top() -- get the stack top element.
- getMin() -- retrieves the smallest element in the stack.
Example:
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output: [null,null,null,null,-3,null,0,-2] Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> return -3. minStack.pop(); minStack.top(); --> Return 0. minStack.getMin(); --> return -2.
/*1.Updating minval when pushing the stack into the node does not take into account the situation when obj is empty (! Obj - > top)
2.Traverse to find the minimum node. Before traversal, judge whether the head node exists!! If it exists, the minval is updated. If it does not exist, the minval cannot be operated, otherwise the original correct minimum value will be changed.
3.You also need to judge whether there is a header node when entering or leaving the stack!! Entering and leaving the stack is an operation. It is enough to use if to judge whether there is a header node and then operate. Be sure to get out of the stack first and then update the minimum value!!
4.With the update minimum function, the update minimum can be called directly after a node is out of the stack, and there is no need to manually update the minimum again.
5.In the function of returning the minimum value (int minStackGetMin), use if to judge that if obj exists, you can directly return the minimum value. Remember to return - 11 if it does not exist!! Because the logic of other functions is correct.
6.If the return value is a function of type int, do not return NULL, but - 1.
7.First use if to judge and then push the new node. Otherwise, if there is no header node, the assignment of obj - > minval will be affected.
8.After writing that the header pointer exists, remember that the header pointer does not exist.
9.free After that, make the pointer NULL*/
typedef struct node{
int val;
struct node *next;
}node;
typedef struct MinStack{
node *top;
int minval;
}MinStack;
MinStack* minStackCreate() {
MinStack*p=(MinStack*)malloc(sizeof(MinStack));
p->top=NULL;
return p;
}
void minStackPush(MinStack* obj, int x) {
if(!obj->top||(obj->top&&x<obj->minval)) obj->minval=x;
node*temp=(node*)malloc(sizeof(node));
temp->val=x;
temp->next = obj->top;
obj->top=temp;
}
void findMinVal(MinStack *obj)
//Function to update the minimum value
{
struct node*p=obj->top;
if(p){
obj->minval=p->val;
while(p){
if(obj->minval>p->val) obj->minval=p->val;
p=p->next;
}
}
}
void minStackPop(MinStack* obj) {
struct node*p=obj->top;
if(p){
obj->top=obj->top->next;//Be sure to get out of the stack first and then update the minimum value!
if(p->val==obj->minval) findMinVal(obj);
free(p);
p=NULL;
}
}
int minStackTop(MinStack* obj) {
if(obj->top) return obj->top->val;
else return -1;
}
int minStackGetMin(MinStack* obj) {
struct node*p=obj->top;
if(p) return obj->minval;
return -1;
/*if(p){
obj->minval=p->val;
while(p){
if(obj->minval>p->val) obj->minval=p->val;
p=p->next;
}
}
return obj->minval;*/
}
void minStackFree(MinStack* obj) {
node*p=obj->top;
while(p){
node*p1=p->next;
free(p);
p=p1;
}
free (obj);
}
/**
* Your MinStack struct will be instantiated and called as such:
* MinStack* obj = minStackCreate();
* minStackPush(obj, val);
* minStackPop(obj);
* int param_3 = minStackTop(obj);
* int param_4 = minStackGetMin(obj);
* minStackFree(obj);
*/
LeetCode 1021. Delete the outermost bracket
Valid parenthesis strings are empty (""), "(" + A + ")" or A + B, where a and B are valid parenthesis strings, and + represents the connection of strings. For example, "", "()", "(()) ()" and "(() ())" are valid parenthesis strings.
If the valid string s is non empty and there is no method to split it into S = A+B, we call it primitive, where A and B are non empty valid parenthesis strings.
A non empty valid string S is given, and its primitive decomposition is considered, so that S = P_1 + P_2 + ... + P_k. Where P_i is a valid parenthesis string primitive.
Perform primitive decomposition on S, delete the outermost parentheses of each primitive string in the decomposition, and return s.
Example 1:
Input:"(()())(())" Output:"()()()" Explanation: The input string is "(()())(())"，Primitive decomposition "(()())" + "(())"， Delete the outermost bracket in each section to get "()()" + "()" = "()()()".
Example 2:
Input:"(()())(())(()(()))" Output:"()()()()(())" Explanation: The input string is "(()())(())(()(()))"，Primitive decomposition "(()())" + "(())" + "(()(()))"， Delete the outermost bracket in each section to get "()()" + "()" + "()(())" = "()()()()(())".
Example 3:
Input:"()()" Output:"" Explanation: The input string is "()()"，Primitive decomposition "()" + "()"， Delete the outermost bracket in each section to get "" + "" = "".
/*When the first left parenthesis of the outermost layer is put on the stack, the count is 0 and will not be put on the stack. If the count of the middle parenthesis is not 0, it will be put on the stack. When the last right parenthesis of the outermost layer is put on the stack, the count will be reduced to 0 first, and then it will not be put on the stack. Finally, put '\ \ 0' on the stack to indicate the end of the character.
if(count!= 0)Put it in front of count + + to ensure that the first left parenthesis is is not recorded. Similarly, the following count first -- make the count change to 0 before the last right parenthesis is is not recorded */
char * removeOuterParentheses(char * S){
int count=0,top=-1;
char*stack=(char*)malloc((sizeof(char)*strlen(S)+1));
for(int i=0;i<strlen(S);i++){
if(S[i]=='('){
if(count!=0)
{
stack[++top]=S[i];
}
count++;
}
if(S[i]==')')
{
count--;
if(count!=0){
stack[++top]=S[i];
}
}
}
stack[++top]='\\0';
return stack;
}
LeetCode Sword finger Offer 09 Queue with two stacks
Implement a queue with two stacks. The declaration of the queue is as follows. Please implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue respectively. (if there are no elements in the queue, the deleteHead operation returns - 1)
Example 1:
Input: ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] Output:[null,null,3,-1]
Example 2:
Input: ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] Output:[null,-1,null,null,5,2]
Tips:
- 1 <= values <= 10000
- At most 10000 calls will be made to appendTail and deleteHead
/*1.There is no need to assign values when defining the structure. Just list the elements and assign values in the creation function. Len in the creation function still needs to be expressed as obj - > len.
2.When the array subscript in the function uses top, it still needs to be written as obj - > s [+ + obj - > Top], and obj - > cannot be ignored
3.When deleting, the top2 subscript is used to delete. If top2 is - 1, it proves that it is deleted empty, it returns - 1. If it is not deleted empty, it returns top2 --. Obj - > s [top2 --] is returned first, and then top2 --, so there is no need to worry about top2 being 0.
Call the function once to delete only one node
4.When elements enter and exit the stack, obj - > s [+ + top] is the first to enter the stack, and obj - > s [top --] is the first to exit the stack.
*/
typedef struct CQueue{
int len;
int *s1,top1;
int *s2,top2;
} CQueue;
CQueue* cQueueCreate() {
CQueue*p=(CQueue*)malloc(sizeof(CQueue));
p->len=1000;
p->s1=malloc(p->len*sizeof(int));
p->s2=malloc(p->len*sizeof(int));
p->top1=-1;
p->top2=-1;
return p;
}
void cQueueAppendTail(CQueue* obj, int value) {//In stack 1
while(obj->top2!=-1){
obj->s1[++obj->top1]=obj->s2[obj->top2--];
}
obj->s1[++obj->top1]=value;
}
int cQueueDeleteHead(CQueue* obj) {//Stack 2
while(obj->top1!=-1){
obj->s2[++obj->top2]=obj->s1[obj->top1--];
}
return obj->top2==-1?-1:obj->s2[obj->top2--];
}
void cQueueFree(CQueue* obj) {
free(obj->s1);
free(obj->s2);
free(obj);
}
/**
* Your CQueue struct will be instantiated and called as such:
* CQueue* obj = cQueueCreate();
* cQueueAppendTail(obj, value);
* int param_2 = cQueueDeleteHead(obj);
* cQueueFree(obj);
*/
LeetCode 622. Design cyclic queue
Design your loop queue implementation. Cyclic queue is a linear data structure whose operation performance is based on FIFO (first in first out) principle, and the tail of the queue is connected after the head of the queue to form a loop. It is also called "ring buffer".
One advantage of the circular queue is that we can use the space previously used by the queue. In a normal queue, once a queue is full, we cannot insert the next element, even if there is still space in front of the queue. But with circular queues, we can use this space to store new values.
Your implementation should support the following operations:
MyCircularQueue(k): Constructor, set the queue length to k . Front: Get element from team leader. If the queue is empty, return -1 . Rear: Gets the end of queue element. If the queue is empty, return -1 . enQueue(value): Inserts an element into the circular queue. Returns true if successfully inserted. deQueue(): Deletes an element from the loop queue. Returns true if the deletion was successful. isEmpty(): Check whether the circular queue is empty. isFull(): Check if the circular queue is full.
Example:
MyCircularQueue circularQueue = new MyCircularQueue(3); // Set the length to 3
circularQueue.enQueue(1); // Return true
circularQueue.enQueue(2); // Return true
circularQueue.enQueue(3); // Return true
circularQueue.enQueue(4); // false is returned. The queue is full
circularQueue.Rear(); // Return 3
circularQueue.isFull(); // Return true
circularQueue.deQueue(); // Return true
circularQueue.enQueue(4); // Return true
circularQueue.Rear(); // Return 4
Tips:
All values are in the range of 0 to 1000; The operand will be in the range of 1 to 1000; Do not use the built-in queue library.
/* 1.The circular queue obj - > front = = obj - > rear & & obj - > flag = 0 is empty. (obj - > rear + 1)% queuesize = = front is full.
2.obj->rear There is no data in that cell.
3.The data is represented by the data field pointer * data. When applying for space, remember to convert the applied space into (int).
4.The queue size int size and int flag are not defined to judge whether the queue is full.
5.No parameter check was performed when creating the queue.
6.When an element enters the queue, it is necessary to judge whether the queue is full, and when it leaves the queue, it is necessary to judge whether the queue is empty.
7.myCircularQueueFront myCircularQueueRear and myCircularQueueRear only return element values and do not operate on subscripts. When myCircularQueueRear returns, if rear is 0, it returns obj - > Val [obj - > size-1], obj - > Val [obj - > rear-1]. First judge whether the queue is empty.
8.flag Whether it is 0 is determined and assigned in the queue entry, queue exit and initialization. myCircularQueueIsEmpty and myCircularQueueIsFull only need to judge the value of flag to judge whether the queue is full.
*/
typedef struct MyCircularQueue {
int *val; //Queue for saving elements
int front;
int size;
int rear;
int flag;//Flag whether the queue is full - > 1 full 0
//If this flag bit is not used, the array needs to leave one more empty bit to judge whether the queue is full
//That is, when the head pointer is at the next position of the tail pointer (multiple empty bits), the queue is full.
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) { //k is the queue length
if(k<0) return NULL;
MyCircularQueue *p=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
p->val=(int*)malloc(k*sizeof(int));
p->rear=p->front=0;
p->size=k;
p->flag=0;
return p;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//
if(myCircularQueueIsFull(obj))
return false;
obj->val[obj->rear]=value;
obj->rear=(obj->rear+1)%obj->size;
if (obj->rear == obj->front)//After inserting a new element, the two pointers point to the same, and the queue is full.
obj->flag=1;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//
if(myCircularQueueIsEmpty(obj))
return false;
obj->val[obj->front]=0;//Clear queue header data
obj->front=(obj->front+1)%obj->size;//Head pointer backward
obj->flag=0;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->val[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
if(obj->rear == 0) //If the end of queue pointer points to array [0], the array [obj - > size-1] is returned
return obj->val[obj->size-1];
else
return obj->val[obj->rear-1];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->front==obj->rear&&obj->flag==0)
return true;
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if(obj->flag==1)
return true;
return false;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->val);
obj->val = NULL;
free(obj);
obj = NULL;
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/
LeetCode 20. Valid brackets
Given a string s that only includes' (',' ',' {','} ',' [','] ', judge whether the string is valid.
Valid strings must meet:
- The left parenthesis must be closed with the same type of right parenthesis.
- The left parentheses must be closed in the correct order.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]" Output: false
Example 4:
Input: s = "([)]" Output: false
Example 5:
Input: s = "{[]}"
Output: true
Tips:
- 1 <= s.length <= 104
- s consists only of parentheses' () [] {} '
Number of passes 595761
Number of submissions 1355616
/*First, judge whether top is equal to 0. If it is equal to 0, use return to return true (the value is 1). Otherwise, use return to return false (the value is 0).
strlen Only the number of characters is calculated, excluding the last \ \ 0.
*/
bool isValid(char * s){
char*stack=(char*)malloc(10000*sizeof(char));
if(strlen(s)&1) return false;
int top=-1;
for(int i=0;i<strlen(s);i++){
if(s[i]=='(')
stack[++top]=')';
else if(s[i]=='[')
stack[++top]=']';
else if(s[i]=='{')
stack[++top]='}';
else if(top==-1||stack[top]!=s[i])
return false;
else top--;
}
return top==-1;
}
The left bracket corresponds to the right bracket, indicating that the bracket is valid. Traverse the string. If the left parenthesis is encountered, put the corresponding right parenthesis on the stack. If the right parenthesis is, judge whether the top of the stack is the same right parenthesis. If it is different, it will not match. If it is the same, it will be out of the stack and continue to traverse the next character of the string. Finally, if the stack is not empty, it indicates that the number of left parentheses is greater than that of right parentheses, which does not match.
/*The last two cases of judgment can also be written as
If it is a right bracket, judge whether the top of the stack is the same right bracket. If it is different, it will not match, and if it is the same, it will be out of the stack,*/
else if(top > -1 && stack[top] == s[i])
top--;
else
return false;
LeetCode 739. Daily temperature
Please regenerate a list according to the daily temperature list. The output of the corresponding position is: at least the number of days to wait in order to observe a higher temperature. If the temperature will not rise after that, please replace it with 0 in this position.
For example, given a list of temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Tip: the length range of air temperature list is [1, 30000]. The value of each temperature is Fahrenheit, which is an integer in the range of [30, 100].
/*Method 1: traversal + stack*/
/**
* Note: The returned array must be malloced, assume caller calls free().
1.If you use the calloc function, you do not need to initialize to 0, and malloc needs to be initialized to 0. After the dynamic allocation of memory, calloc automatically initializes the memory space to zero, while malloc does not initialize, and the data inside is random garbage data. Malloc function: the return value of the function is an object. Calloc function: the return value of the function is an array.
2.When the stack is not empty and the current temperature is greater than the temperature of the element at the top of the stack, you should not only assign a value to the answer, but also get out of the stack!
3.The number of days (position) is stored in the stack. When entering the stack, the pointer first increases by one and is written as stack[++top] = i;
4.stack[top]Is the number of days of the stack top element, so T[stack[top] is the temperature of the stack top element.
*/
int* dailyTemperatures(int* T, int TSize, int* returnSize){
int *res=(int*)malloc(sizeof(int)*TSize);
memset(res,0,TSize*sizeof(int));
int top=-1;
int stack[TSize];
for(int i=0;i<TSize;i++){
while(top>-1&&T[i]>T[stack[top]]){
res[stack[top]]= i - stack[top];//The day of the stack top element
top--;//Be sure to remember to get out of the stack
}
stack[++top] = i; /*First put the first day into the stack to judge the next day, so write the while on the top of the stack, otherwise the first day will be compared with yourself, and the final results will all be 0*/
}
*returnSize=TSize;
return res;
}
First put the first day into the stack to judge the next day, so write the while on the top of the stack, otherwise the first day will be compared with yourself, and the final results will all be 0
Use a stack to record the number of days. If the stack is empty, directly put the number of days into the stack. The answer array records at least the number of days to wait. If the stack is not empty and the current element temperature is greater than the temperature of the day recorded at the top of the stack, assign the current number of days - the number of days recorded at the top of the stack to the answer array element whose subscript is the number of days recorded at the top of the stack in the answer array. If there are still days left in the final stack, that is, the stack is not empty, the temperature will not rise in the next few days after the proof. This position is replaced by 0. Therefore, at the beginning, you need to assign the answer array to 0. Finally, the answer array is returned.
/*Method 2: traverse from back to front and optimize.
It will time out from the front to the back, so it is necessary to compare from the back to the front. The last day in the answer array is directly assigned as 0. In the second layer of loop, the subscript j automatically adds the minimum number of days to wait stored in the answer array each time, which is written as j+res[j]. Because it is traversed from the back to the front, the median value of the subscript answer array after I is correct. If res[j]==0 after I, It indicates that T[j] at this time is the largest element after T[i]. At this time, if the largest element T[j] after T[i] is still less than T[i], it indicates that there is no larger element after T[i], and the assignment res[i]=0;*/
int* dailyTemperatures(int* T, int TSize, int* returnSize){
int *res = (int *)malloc(sizeof(int) * TSize);
memset(res,0,TSize*sizeof(int));
for (int i = TSize - 2; i >= 0; i--) {
for (int j = i + 1; j <=TSize-1; j += res[j]) {//Add directly to the next larger number and skip all smaller numbers.
if (T[j] > T[i]) {
res[i] = j - i;
break;
} else if (res[j] == 0) {//After the description, there is no element larger than it. There is no need to continue the loop traversal, and directly jump out of the loop for 0;
res[i] = 0;
break;
}
}
}
*returnSize = TSize;
return res;
}
It's time-out from front to back...
/int dailyTemperatures(int T, int TSize, int* returnSize){
int res=(int)malloc(sizeof(int)*TSize);
memset(res,0,TSize*sizeof(int));
int flag=1;
for(int i=0;i<TSize;i++){
flag=0;
for(int j=i+1;j<TSize;j++){
if(T[j]>T[i]){
res[i]=j-i;
flag=1;
break;
}
if(flag) {
//res[i]=0;
break;
}
}
}
- returnSize=TSize;
return res;
}*/
LeetCode 234. Palindrome linked list
Please judge whether a linked list is a palindrome linked list.
Example 1:
input: 1->2 output: false
Example 2:
input: 1->2->2->1 output: true
Advanced:
Can you solve this problem with O(n) time complexity and O(1) space complexity?
bool isPalindrome(struct ListNode* head){
struct ListNode*p1,*p2=p1=head;
int count=0;
while(p1){
p1=p1->next;
count++;
}
/*count Is the number of knots*/
if(count ==1) return true;
p1=head;
p2=head;
for(int i=0;i<count/2-1;i++)
{
p2=p2->next;
}
/*Half of the nodes minus one is the last node in the first half*/
struct ListNode*p3=p2->next;
p2->next=NULL;
struct ListNode*pre=(struct ListNode*)malloc(sizeof(struct ListNode));
pre->next=NULL;
while(p3){
struct ListNode*Next=p3->next;
p3->next = pre;
pre=p3;
p3=Next;
}
/*After transposing, p3 traverses from back to front, and p1 traverses from front to back. Once the numbers are different, return false*/
while(p1&&pre){
if(p1->val!=pre->val)
return false;
pre=pre->next;
p1=p1->next;
}
return true;
}
/*First traverse the number of nodes, then control p2 to go to the last node in the first half, transpose the nodes in the second half, and then control p1 to compare with the split nodes in the second half in turn. Once the numbers are different, it is not a palindrome.*/
LeetCode 19. Delete the penultimate node of the linked list
Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.
- *Advanced: * * can you try using one scan?
Example 1:
Input: head = [1,2,3,4,5], n = 2 Output:[1,2,3,5]
Example 2:
Input: head = [1], n = 1 Output:[]
Example 3:
Input: head = [1,2], n = 1 Output:[1]
Tips:
- The number of nodes in the linked list is sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* newhead= (struct ListNode*)malloc(sizeof(struct ListNode));
newhead->next=head;
struct ListNode*pfast=newhead,*pslow=newhead;
n++; /*If the fast pointer takes one more step, the slow pointer can point to the previous node to delete*/
while(n){
n--;
pfast=pfast->next;
}
while(pfast){
pfast=pfast->next;
pslow=pslow->next;
}
//pslow->next = pslow->next->next;
pfast = pslow->next; /*Assign a value to pfast*/
pslow->next=pfast->next ;
free(pfast);
return newhead->next;
}
LeetCode 28. Implement str ()
realization strStr() Function.
Here are two strings haystack and need. Please find the first position of the need string in the haystack string (the subscript starts from 0). If it does not exist, - 1 is returned.
explain:
What value should we return when need is an empty string? This is a good question in the interview.
For this problem, we should return 0 when need is an empty string. This is different from C language strstr() And Java indexOf() The definition does not match.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output:-1
Example 3:
Input: haystack = "", needle = "" Output: 0
Tips:
- 0 <= haystack.length, needle.length <= 5 * 104
- haystack and need consist of lowercase English characters only
/* int j = 0;It should be written in the loop, otherwise the array will cross the boundary when there are many i's like the following.
"mississippi"
"issip"
Every time you encounter a new I, you should make a new round of comparison until haystack [i + J]= Need [J + +] or j = = len2 (complete string comparison). If the situation is not satisfied after traversal, return-1 indicates that no need is found in haystack.
*/
int strStr(char * haystack, char * needle){
int len1 = strlen(haystack),len2 = strlen(needle);
if(!len2)
return 0;
for(int i=0;i<strlen(haystack);i++){
int j=0;
while(haystack[i+j]==needle[j++]){
if(j==len2)
return i;
}
}
return -1;
}
1047. Delete all adjacent duplicates in the string
Given the string S composed of lowercase letters, the duplicate deletion operation will select two adjacent and identical letters and delete them.
Repeat the deduplication operation on S until the deletion cannot continue.
Returns the final string after all deduplication operations are completed. The answer is guaranteed to be unique.
Example:
Input:"abbaca" Output:"ca" Explanation: For example, in "abbaca" In, we can delete "bb" Because the two letters are adjacent and the same, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca"，Among them, only "aa" You can delete duplicates, so the last string is "ca".
char * removeDuplicates(char * S){
int top = -1;
char *stack = (char*)malloc(sizeof(char) * (strlen(S) + 1));
for(int i=0;i<strlen(S);i++){
if(top==-1 || S[i]!=stack[top]){ /*Two cases of stacking, 1 Stack is empty. 2. The stack top element is not equal to the current traversal element*/
stack[++top]=S[i];
}
else{
top--;
}
}
stack[++top]='\\0';
return stack;
}
Traverse the string. If the stack is empty or the element at the top of the stack is not equal to the current element, it will be put on the stack, and the rest will be out of the stack. When judging, top==-1 is written in front, s [i]= Stack [top] is written later to prevent the array from crossing the boundary due to top=-1 at the beginning.
LeeTcode1544. Collating strings
Give you a string of uppercase and lowercase letters s.
In a sorted string, two adjacent characters s[i] and s[i+1], where 0 < = I < = s.length-2, the following conditions shall be met:
- If s[i] is a lowercase character, s[i+1] cannot be the same uppercase character.
- If s[i] is an uppercase character, s[i+1] cannot be the same lowercase character.
Please arrange the string. Each time you can select two adjacent characters that meet the above conditions from the string and delete them until the string is sorted.
Please return the sorted string. Under the given constraints, the answer corresponding to the test sample is unique.
- *Note: * * empty strings are also sorted strings, although there are no characters in them.
Example 1:
Input: s = "leEeetcode" Output:"leetcode" Explanation: no matter what you choose for the first time i = 1 still i = 2，Will make "leEeetcode" Reduced to "leetcode" .
Example 2:
Input: s = "abBAcC" Output:"" Explanation: there are many different situations, but all of them will lead to the same result. For example: "abBAcC" --> "aAcC" --> "cC" --> "" "abBAcC" --> "abBA" --> "aA" --> ""
Example 3:
Input: s = "s" Output:"s"
Tips:
- 1 <= s.length <= 100
- s contains only lowercase and uppercase letters
/*Method 1: violence solution
char * makeGood(char * s){
if(strlen(s)==1)
return s;
int len=strlen(s),j=0,top=-1;
char *stack=(char*)malloc(sizeof(char)*len);
for(int i=0;i<len;i++){
while(s[i+1]==s[i]+32||s[i+1]==s[i]-32){
for(int p=0;p<2;p++){
for(int j=i;j<len;j++){
s[j]=s[j+1];
}
}
i=0;
}
}
s[strlen(s)]='\\0';
return s;
}
Traverse the string. If the next character and the current character are case sensitive to each other, all the characters in the back will be moved forward twice, and then i=0 will be traversed from the beginning again to prevent the formation of new adjacent characters with mutual case in the front after the movement is completed. Because two characters are deleted each time, the time is actually very short.*/
/*Method 2: the wonderful use of stack*/
char * makeGood(char * s){
int len = strlen(s),top=-1;
char *stack=(char*)malloc(sizeof(char)*1000);
for(int i =0;i<len;i++){
stack[++top] = s[i];
if(top>=1) /*The pointer cannot be smaller than - 1 after pop-up*/
if(abs(stack[top]-stack[top-1])==32)
top-=2;
}
stack[++top]='\\0';
return stack;
}
/*Build a stack, put it on the stack in turn, and then judge whether the top element of the stack and the previous character of the top element are uppercase and lowercase characters to be deleted. If so, pop up two characters and continue to traverse. Note that the pointer cannot be smaller than - 1 after pop-up.*/
LeetCode 137. The number II appears only once
Give you an integer array nums. Except that an element appears only once, every other element appears * * three times** Please find and return the element that appears only once.
Example 1:
Input: nums = [2,2,3,2] Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99] Output: 99
Tips:
- 1 <= nums.length <= 3 * 104
- 231 <= nums[i] <= 231 - 1
- In nums, each element occurs exactly three times except one element occurs only once
- *Advanced: * * your algorithm should have linear time complexity. Can you do it without using extra space?
int singleNumber(int* nums, int numsSize){
int arr[32] = {0};
for(int i=0;i<numsSize;i++)
{
for(int j=0;j<32;j++)
{
arr[j]+= (nums[i]>>j) &1;
}
}
unsigned int ans=0;
for(int j=31;j>=0;j--)
{
arr[j]%=3;
ans<<=1;
ans |=arr[j];
}
return ans;
}
Method 1: bit operation (each bit is calculated separately)
An int has 4 bytes and 32 bits. First, establish an array arr with a length of 32 to store the sum of each byte occupied by each int, and then make the remaining 3 for the sum of each bit respectively. Finally, the remaining binary represents the number that appears only once. Then use an unsigned int (when shifting an unsigned int, the highest bit will not have any particularity. Unsigned integers must be printed with% u. when shifting an int, the highest bit must be considered, and the shift to the right is equivalent to (signed value) / 2.) It is used to move each bit of array arr from 31 to 0 to the left in reverse order, and then return this number.
When taking numbers in reverse order, use or to record each number instead of adding, because adding is to add + 1 to the decimal number represented by this binary number, and adding to binary will cause different situations.
Method 2: finite state machine (not yet understood)
First understand one thing: the bit operations involved in this problem satisfy the commutative law and the associative law. Therefore, for the out of order array abcbccb, the cumulative bit operation ret = abcbccb is equivalent to ret = bbbccca. Just consider the simple and orderly situation
Therefore, the upper pass through two variables
once = (once ^ nums[i]) & (~twice);
twice = (twice ^ nums[i]) & (~once);
Because B ^ B = 0; b & 0 = 0; b & (~b) = 0; The following table can be obtained:
Occurrences 1 2 3
once b 0 0
twice 0 b 0
The contribution of the number appearing three times to the result is 0, and the contribution of the number appearing once to the result is itself.
So once the loop ends is the result
code
int singleNumber(int* nums, int numsSize){
int once = 0;
int twice = 0;
for (int i = 0; i < numsSize; i++){
once = (once ^ nums[i]) & (~twice);
twice = (twice ^ nums[i]) & (~once);
}
return once;
}
Author: Dong Bei Zhang Da Shuai
Link: https://leetcode-cn.com/problems/single-number-ii/solution/cyu-yan-jie-jin-shuang-bai-wei-yun-suan-yuan-li-xi/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.
1. Why return one?
If there is only one digit, Ken exists on one.
2. Why is the two formula the same as one
Draw a picture and find it. The two variables are as like as two peas.
LeetCode 682. Baseball game
You are now the recorder of a baseball game with a special game system. This game consists of several rounds. The scores in the past few rounds may affect the scores in the next few rounds.
At the beginning of the game, the record was blank. You will get a string list of recorded operations ops, where ops[i] is the ith operation you need to record. ops follows the following rules:
- Integer x - indicates the new score x obtained in this round
- "+" - indicates that the new score obtained in this round is the sum of the previous two scores. The title data ensures that there are always two valid scores in front of this operation.
- "D" - indicates that the score newly obtained in this round is twice that of the previous round. The title data ensures that there is always a valid score in front of this operation.
- "C" - indicates that the previous score is invalid and will be removed from the record. The title data ensures that there is always a valid score in front of this operation.
Please return the sum of all scores in the record.
Example 1:
Input: ops = ["5","2","C","D","+"] Output: 30 Explanation: "5" - Record plus 5, the record is now [5] "2" - Record plus 2, the record is now [5, 2] "C" - Invalidate the record of the previous score and remove it. The record is now [5]. "D" - Record plus 2 * 5 = 10 ，The record is now [5, 10]. "+" - Record plus 5 + 10 = 15 ，The record is now [5, 10, 15]. Sum of all scores 5 + 10 + 15 = 30
Example 2:
Input: ops = ["5","-2","4","C","D","9","+","+"] Output: 27 Explanation: "5" - Record plus 5, the record is now [5] "-2" - Record plus -2 ，The record is now [5, -2] "4" - Record plus 4, the record is now [5, -2, 4] "C" - Invalidate the record of the previous score and remove it. The record is now [5, -2] "D" - Record plus 2 * -2 = -4 ，The record is now [5, -2, -4] "9" - Record plus 9, the record is now [5, -2, -4, 9] "+" - Record plus -4 + 9 = 5 ，The record is now [5, -2, -4, 9, 5] "+" - Record plus 9 + 5 = 14 ，The record is now [5, -2, -4, 9, 5, 14] Sum of all scores 5 + -2 + -4 + 9 + 5 + 14 = 27
Example 3:
Input: ops = ["1"] Output: 1
int calPoints(char ** ops, int opsSize){
int stack[opsSize],top = -1,sum = 0; // Cumulative score
for(int i = 0; i < opsSize; i++) {
switch(ops[i][0]) {
case 'D' :
stack[++top] = stack[top] * 2;
sum += stack[top];
break;
case '+' :
stack[++top] = stack[top] + stack[top - 1];
sum += stack[top];
break;
case 'C' :
sum -= stack[top--];
break;
default :
stack[++top] = atoi(ops[i]);
sum += stack[top];
}
}
return sum;
}
LeetCode147. Insert and sort the linked list
Insert and sort the linked list.
The animation of insert sorting is shown above. Starting from the first element, the linked list can be considered to have been partially sorted (represented by black).
At each iteration, an element (indicated in red) is removed from the input data and inserted in place into the ordered linked list.
Insert sorting algorithm:
- Insertion sorting is iterative, moving only one element at a time until all elements can form an ordered output list.
- In each iteration, insert sort only removes an element to be sorted from the input data, finds its appropriate position in the sequence, and inserts it.
- Repeat until all input data is inserted.
Example 1:
input: 4->2->1->3 output: 1->2->3->4
Example 2:
input: -1->5->3->4->0 output: -1->0->3->4->5
Pass times 83532
Submission times 123925
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
1.If the back is big, insert the big back into the front.
2.First separate c with p and then insert c in front, otherwise the pointing will be wrong
3.t->next The value of is greater than c, and c is inserted between t and t - > next*/
struct ListNode *insertionSortList(struct ListNode *head) {
if(!head||!head->next)
return head;
struct ListNode *newhead=(struct ListNode *)malloc(sizeof(struct ListNode)),*t,*p,*c;
newhead->next=head;
c = head;
p = newhead;
while(c){
if(p->val>c->val){
t=newhead;
while(t->next->val < c->val)
{
t=t->next;
}
p->next=p->next->next; /*First separate c with p and then insert c in front, otherwise the pointing will be wrong*/
c->next=t->next; /*t->next The value of is greater than c, and c is inserted between t and t - > next*/
t->next=c;
}else{
p=p->next;
}
c=p->next;
}
return newhead->next;
}
LeetCode844. Compare strings with backspace
Given two strings S and T, when they are input into a blank text editor respectively, judge whether they are equal and return the result# Represents a backspace character.
- *Note: * * if you enter a backspace character for empty text, the text will continue to be empty.
Example 1:
Input: S = "ab#c", T = "ad#c" Output: true Explanation: S and T Will become“ ac".
Example 2:
Input: S = "ab##", T = "c#d#" Output: true Explanation: S and T Will become "".
Example 3:
Input: S = "a##c", T = "#a#c" Output: true Explanation: S and T Will become“ c".
Example 4:
Input: S = "a#c", T = "b" Output: false Explanation: S Will become“ c"，but T Still“ b".
Tips:
- 1 <= S.length <= 200
- 1 <= T.length <= 200
- S and T contain only lowercase letters and the character '#'.
Advanced:
- Can you solve this problem with O(N) time complexity and O(1) space complexity?
/* 1.strcmp(str1,str2)，If str1=str2, zero is returned
2.if(t[i]=='#' && top>0)Forgot to add & & top > 0
3.When top==-1, you also have to judge whether it is' # ', which cannot be backspace but cannot be put on the stack*/
/*"y#fo##f"
"y#f#o##f"*/
bool backspaceCompare(char * s, char * t){
char stack1[strlen(s)+1],stack2[strlen(t)+1];
int top= -1;
for(int i=0 ;i<strlen(s) ; i++){
if(s[i]=='#' && top>=0)
top--;
else if(s[i]!='#')
stack1[++top]=s[i];
}
stack1[++top]='\\0';
top= -1;
for(int i=0; i<strlen(t) ;i++){
if(t[i]=='#' && top>=0)
top--;
else if(t[i]!='#')
stack2[++top]=t[i];
}
stack2[++top]='\\0';
if(strcmp(stack1,stack2)==0)
return true;
else
return false;
}
1598. Folder operation log collector
Simple difficulty 14
The LeetCode file system keeps a log record every time a user changes a folder.
The following describes the change operation:
- ".. /": move to the parent folder of the current folder. If you are already in the home folder, continue to stay in the current folder.
- ". /": continue to stay in the current folder * ***
- "x /": move to a subfolder named x. The title data is guaranteed to always exist in the folder x.
Give you a string list logs, where logs[i] is the operation performed by the user in the ith step.
The file system is located in the home folder when it starts, and then perform the operations in logs.
After performing all changes to the folder, please find out the minimum number of steps required to return to the home folder.
Example 1:
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-qb5f8lap-1619619986508) (D: / program files / typoraplicture / sample_11_1957. PNG)]
Input: logs = ["d1/","d2/","../","d21/","./"] Output: 2 Interpretation: Execution "../" Change the folder twice to return to the main folder
Example 2:
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-ngslozjt-1619619986510) (D: / program files / typoraplicture / sample_22_1957. PNG)]
Input: logs = ["d1/","d2/","./","d3/","../","d31/"] Output: 3
Example 3:
Input: logs = ["d1/","../","../","../"] Output: 0
/*Encountered.. /, Returns the level - 1 of the master file.
Encountered. /, There is no change in the level of the returned master file.
Because x is a subfolder when x /
When x / is encountered, the level + 1 of the main file is returned.*/
int minOperations(char ** logs, int logsSize){
int sum = 0;
for(int i =0;i < logsSize;i++){
if(!strcmp(logs[i],"./"))
continue;
else if(!strcmp(logs[i],"../")){ /*You must enlarge parentheses, otherwise else will match if (sum > 0)*/
if(sum>0)
sum-=1;
}
else
sum++;
}
return sum;
}
1290. Binary linked list to integer
Simple difficulty 80
Give you a reference node head of single linked list. The value of each node in the linked list is either 0 or 1. It is known that this linked list is a binary representation of an integer number.
Please return the decimal value of the number represented by the linked list.
Example 1:
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-o4xdttm8-1620536982489) (D: / program files / typoraplicture / graph-1. PNG)]
Input: head = [1,0,1] Output: 5 Explanation: binary number (101) Convert to decimal (5)
Example 2:
Input: head = [0] Output: 0
Example 3:
Input: head = [1] Output: 1
Example 4:
Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] Output: 18880
Example 5:
Input: head = [0,0] Output: 0
int getDecimalValue(struct ListNode* head){
struct ListNode*p=head;
int ans=0;
while(p)
{
ans=(ans<<1) | p->val;
p=p->next;
}
return ans;
}
Bit operation, each time the binary represented by the number is shifted to the left by one bit, and then the 0 or 1 or operation in the linked list is included. The previous 0 does not change, but only the last bit is changed.
LeetCode283. Move zero
Simple difficulty 1056
Given an array num, write a function to move all zeros to the end of the array while maintaining the relative order of non-zero elements.
Example:
input: [0,1,0,3,12] output: [1,3,12,0,0]
void moveZeroes(int* nums, int numsSize){
int left=0,right=0;
for(right=0;right<numsSize;right++)
{
if(nums[right]!=0)
{
int t=nums[right];
nums[right]=nums[left];
nums[left]=t;
left++;
}
}
}
Double pointer traverses the array, right traverses the array, the left is an array that is not 0, and right points to 0 to continue the traversal. If it is not 0, it will be exchanged with left and then left + +, so that the left is full of non-zero numbers and the order will not change. If left and right point to the same non-zero number at the beginning, they will also be exchanged. At the same time, make left + +, until left points to 0, and then make right advance until it points to non-zero number exchange.
LeetCode200. Number of islands
Medium difficulty 1143
Give you a two-dimensional grid composed of '1' (land) and '0' (water). Please calculate the number of islands in the grid.
Islands are always surrounded by water, and each island can only be formed by adjacent land connections in the horizontal and / or vertical direction.
In addition, you can assume that all four sides of the mesh are surrounded by water.
Example 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
void dfs(int row,int col,int a,int b,char **grid){
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
if( a>=row || b>=col || a<0 || b<0 || grid[a][b] == '0') //Note: judgment comes first
{
return ;
}
else
{
grid[a][b] = '0';
}
for(int i=0;i<4;i++)
{
int aa = a + dir[i][0];
int bb = b + dir[i][1];
dfs(row,col,aa,bb,grid);
}
}
int numIslands(char** grid, int gridSize, int* gridColSize){
int row = gridSize,count=0;
int col = gridColSize[0];
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if( grid[i][j] == '1')
{
dfs(row,col,i,j,grid);
count++;
}
}
}
return count;
}
For deep search, first traverse each grid. If it is 0, skip it. If it is 1, use the deep search function to turn 1 into 0 for each grid in the order of bottom right and top left. First turn 1 into 0 from the right of this node, then return to the previous node, and then traverse it in the order of bottom right and top left. Each time, you can complete turning an island into 0. Count the number of each piece.