经典的算法面试题(2)

时间:2024-03-12 19:57:22

题目

给定一个字符串,判断它是否是一个回文字符串。回文字符串是指正序和倒序读都一样的字符串。

示例:
输入:"level"
输出:true

输入:"algorithm"
输出:false

解题思路:

  1.  双指针法。首先,我们定义两个指针,一个指向字符串的开头,另一个指向字符串的末尾。然后,我们依次比较两个指针指向的字符是否相等,直到两个指针相遇。如果遇到任何不相等的字符,则说明字符串不是回文字符串。
  2. 使用递归:
    • 将问题转化为子问题,即判断去掉首尾字符后的子字符串是否是回文字符串。
    • 对于长度为0或1的字符串,它们本身就是回文字符串,直接返回True。
    • 如果字符串的首尾字符相等,并且去掉首尾字符后的子字符串也是回文字符串,则整个字符串是回文字符串。
    • 否则,字符串不是回文字符串。
  3. 使用栈:
    • 将字符串入栈,并按照先进后出的顺序出栈。
    • 遍历字符串,依次将字符入栈。
    • 再次遍历字符串,依次从栈顶弹出字符与当前字符进行比较。
    • 如果全部比较通过,则字符串是回文字符串;否则,字符串不是回文字符串。

代码

  1. 双指针法:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isPalindromeTwoPointers(char *s) {
    int start = 0;
    int end = strlen(s) - 1;

    while (start < end) {
        if (s[start] != s[end]) {
            return false;
        }
        start++;
        end--;
    }
    
    return true;
}

int main() {
    char input[] = "level";
    
    if (isPalindromeTwoPointers(input)) {
        printf("The string is a palindrome.\n");
    } else {
        printf("The string is not a palindrome.\n");
    }
    
    return 0;
}
  1. 递归:
    #include <stdio.h>
    #include <stdbool.h>
    #include <string.h>
    
    bool isPalindromeRecursive(char *s, int start, int end) {
        if (start >= end) {
            return true;
        }
        
        if (s[start] != s[end]) {
            return false;
        }
        
        return isPalindromeRecursive(s, start + 1, end - 1);
    }
    
    bool isPalindrome(char *s) {
        int start = 0;
        int end = strlen(s) - 1;
        
        return isPalindromeRecursive(s, start, end);
    }
    
    int main() {
        char input[] = "level";
        
        if (isPalindrome(input)) {
            printf("The string is a palindrome.\n");
        } else {
            printf("The string is not a palindrome.\n");
        }
        
        return 0;
    }

  2. 使用栈:
    #include <stdio.h>
    #include <stdbool.h>
    #include <string.h>
    
    #define MAX_SIZE 100
    
    typedef struct {
        char data[MAX_SIZE];
        int top;
    } Stack;
    
    void init(Stack *s) {
        s->top = -1;
    }
    
    bool isEmpty(Stack *s) {
        return s->top == -1;
    }
    
    bool isFull(Stack *s) {
        return s->top == MAX_SIZE - 1;
    }
    
    void push(Stack *s, char c) {
        if (isFull(s)) {
            printf("Stack overflow.\n");
            return;
        }
        
        s->data[++s->top] = c;
    }
    
    char pop(Stack *s) {
        if (isEmpty(s)) {
            printf("Stack underflow.\n");
            return '\0';
        }
        
        return s->data[s->top--];
    }
    
    bool isPalindromeStack(char *s) {
        int n = strlen(s);
        Stack stack;
        init(&stack);
        
        for (int i = 0; i < n; i++) {
            push(&stack, s[i]);
        }
        
        for (int i = 0; i < n; i++) {
            if (pop(&stack) != s[i]) {
                return false;
            }
        }
        
        return true;
    }
    
    int main() {
        char input[] = "level";
        
        if (isPalindromeStack(input)) {
            printf("The string is a palindrome.\n");
        } else {
            printf("The string is not a palindrome.\n");
        }
        
        return 0;
    }

相关文章