经典的算法面试题（2）

题目

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

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

输入："algorithm"
输出：false

解题思路：

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

代码

双指针法：

#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;
}

递归：

#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;
}

使用栈：

#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;
}

秒客网

经典的算法面试题（2）

题目

解题思路：

代码

相关文章