# Data structure and program design of leetcode in the direction of postgraduate entrance examination (miscellaneous articles such as number and stack, including train of thought solutions)

## Digital problem

9. Number of palindromes Algorithm idea:
1. First, judge whether x is a negative number. If it is a negative number, it directly returns false without conversion
2. Assign the palindrome number y according to the flashback until Y > = X. at this time, if x = = y | x = = Y / 10, it is the palindrome number, otherwise it is not

Keep taking the remainder of x to 10 and assigning it to a new number y, and record the times of taking the remainder until Y > = x
If the number of times y is the odd of the comparison, then take the remainder of Y as the power of 10

```bool isPalindrome(int x){
if((x < 0) || (x % 10 == 0 && x != 0))
return false;
int y = 0;
while(x > y)	//Assign values to y in reverse order
{
y = y * 10 + x % 10;
x = x / 10;
}
if(x == y || x == y / 10)
return true;
return false;
}
```

172. Zero after factorial Algorithm idea: multiplying a 2 by a 5 can construct a 0, and the number of 2 is far more than 5, so you only need to look at n! The number of 5 is enough, and for each factorial, the number of 5 is n/5

```int trailingZeroes(int n){ //recursion
if (n < 5)
return 0;
else
return n/5 + trailingZeroes(n / 5);
}
int trailingZeroes(int n){ //non-recursive
int count = 0;
while(n / 5 != 0)
{
count += n/5;
n = n / 5;
}
return count;
}
``` Algorithm idea: recursive idea
num = 0 return 0
Num > 0 determines whether num% 10 + adddigits (Num / 10) is a single digit,
If yes, return. If not, call temp back to addDigits again

```int addDigits(int num){
if(num == 0)
return 0;
else
{   int temp = num % 10 + addDigits(num / 10);
if(temp <= 9 && temp >= 0)
return  temp;
else

}

}
```

507. Perfect number Original topic of programming in Jilin University
Algorithm idea 1 The initialization counter is 0, traversing from 2 to sqrt (n),
If n is the square of i, sum += i, otherwise sum + = (Num / i + i)
You also need + 1 at the end, because 1 is also a positive factor
Thought is like a double pointer, close from both sides to the middle

```bool checkPerfectNumber(int num)
{
if( num <= 2)	//If it is less than 2, there is no need to judge
return false;
int sum = 0;
for(int i = 2; i*i <= num; i++ )
{
if( num % i == 0 )
{
if( num/i == i )	//If n is the square of i, sum += i
sum += i;
else			//Otherwise sum + = (Num / I + I)
sum += ( num/i + i );
}
}
if( sum + 1 == num )
return true;
return false;
}
```

## Stack

20. Valid brackets Algorithm idea:
1. Judge the length of the string. If it is an odd number, it will be returned directly. Create a sequential stack stack to save the left parenthesis, and top is the subscript of the top element of the stack
2. Traverse backward from the first character and start matching whenever the right bracket is encountered
 If the stack is empty and a closing bracket is encountered, false is returned
 If the stack encounters an open bracket, put it on the stack
 If the stack is not empty and a closing bracket is encountered, the current character is compared with the top of the stack. If it matches, it is out of the stack. Otherwise, it returns false
3. After traversing the whole string, if the stack is empty, it indicates that the matching is successful and returns true; otherwise, it returns false

```char pair(char a)   //Returns the element that should match
{
if(a == ')')    return '(';
else if (a == '}')  return '{';
return '[';
}
bool isValid(char * s){
int len = strlen(s);
if(len % 2 == 1)    //If the string length is odd, it is returned directly
return false;
char* stack = (char*)malloc(sizeof(char) * (len / 2 + 1));   //sequence stack
int top = -1;
for(int i = 0 ; i < len; i++)
{
if(top == -1 && (s[i] == '}' || s[i] == ')' || s[i] == ']'))    //Stack empty and right parenthesis encountered
return false;
if(s[i] == '(' || s[i] == '{' || s[i] == '[')   //Left bracket stack encountered
{
stack[++top] = s[i];
}
else if(s[i] == ')' || s[i] == '}' || s[i] == ']')  //If it is the same, it will be out of the stack; otherwise, it will return false
{
char c = stack[top];
if(pair(s[i]) == c)
top--;
else
return false;
}
}
if(top == -1)   //After matching, if the stack is empty, return true
return true;
else
return false;
}
```

150. Evaluation of inverse Polish expression Algorithm idea:
1. The initialization sequence stack is used to save numbers and traverse the whole string
2. Whenever you encounter a number and put it into the stack, you need to judge whether the input is a number
Positive number: if the first digit is a number, the first to last digits are combined into a number
Negative number: if the first digit is a negative sign, judge whether the second digit is a number. If it is a number, turn it from the second digit to the last digit into a number
3. Whenever an operator is encountered, the first time out of the stack is op2, and the second time out of the stack element is op1. Operate op2 with op1, and the result is put on the stack

```int evalRPN(char ** tokens, int tokensSize){
int* stack = (int*)malloc(sizeof(int) * tokensSize);
int top = -1, opeartor1, opeartor2;
for(int i = 0; i < tokensSize; i++)//Traverse the entire array
{
if(tokens[i] == '*') //When an operator is encountered, the same below
{
opeartor2 = stack[top--];
opeartor1 = stack[top--];
stack[++top] = opeartor1 * opeartor2;
}
else if(tokens[i] == '/')
{
opeartor2 = stack[top--];
opeartor1 = stack[top--];
stack[++top] = opeartor1 / opeartor2;
}
else if(tokens[i] == '+')
{
opeartor2 = stack[top--];
opeartor1 = stack[top--];
stack[++top] = opeartor1 + opeartor2;
}
else if(tokens[i] == '-' && tokens[i] == '\0')
{
opeartor2 = stack[top--];
opeartor1 = stack[top--];
stack[++top] = opeartor1 - opeartor2;
}
else
{   int sum = 0;
if(tokens[i] == '-' && tokens[i] != '\0') //If the current string is expressed as a negative number
{
for(int j = 1; tokens[i][j] != '\0'; j++)
sum = 10 * sum + tokens[i][j] - '0';
sum *= -1;
}
else
{
for(int j = 0; tokens[i][j] != '\0'; j++)
sum = 10 * sum + tokens[i][j] - '0';
}
stack[++top] = sum;
}
}
return stack;//Return stack top element
}

```

Posted by elwadhos on Tue, 17 May 2022 18:01:13 +0300