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;
}
  1. Add up

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
                return addDigits(temp);

    }

}

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
[1] If the stack is empty and a closing bracket is encountered, false is returned
[2] If the stack encounters an open bracket, put it on the stack
[3] 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][0] == '*') //When an operator is encountered, the same below
        {
            opeartor2 = stack[top--];
            opeartor1 = stack[top--];
            stack[++top] = opeartor1 * opeartor2;
        }
        else if(tokens[i][0] == '/')
        {
            opeartor2 = stack[top--];
            opeartor1 = stack[top--];
            stack[++top] = opeartor1 / opeartor2;  
        }
        else if(tokens[i][0] == '+')
        {
            opeartor2 = stack[top--];
            opeartor1 = stack[top--];
            stack[++top] = opeartor1 + opeartor2;
        }
        else if(tokens[i][0] == '-' && tokens[i][1] == '\0')
        {
            opeartor2 = stack[top--];
            opeartor1 = stack[top--];
            stack[++top] = opeartor1 - opeartor2;
        }
        else
        {   int sum = 0;
            if(tokens[i][0] == '-' && tokens[i][1] != '\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[0];//Return stack top element
}

Tags: Algorithm data structure leetcode stack

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