当前位置：首页 > article >正文

C言算法面试：分类与高频题解析

article 2025/1/30 18:06:16

C言算法面试：分类与高频题解析

算法在编程面试中是必考的内容，熟练掌握常见的算法类型和解题思路是通往 offer 的关键。本文将对算法面试题进行分类，总结高频题目，并给出用 C 语言实现的示例代码。

一、算法面试题分类

1. 数组与字符串

特点：线性数据结构，容易产生边界问题。
常见考点：
- 双指针
- 滑动窗口
- 排序与搜索

高频题：

两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数，并返回它们的数组下标。

代码实现：

#include <stdio.h>
#include <stdlib.h>

// 哈希表结构体
typedef struct {
    int key;
    int value;
} HashNode;

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    HashNode* hashTable = (HashNode*)malloc(numsSize * sizeof(HashNode));
    int hashSize = 0;

    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        for (int j = 0; j < hashSize; j++) {
            if (hashTable[j].key == complement) {
                int* result = (int*)malloc(2 * sizeof(int));
                result[0] = hashTable[j].value;
                result[1] = i;
                *returnSize = 2;
                free(hashTable);
                return result;
            }
        }
        hashTable[hashSize].key = nums[i];
        hashTable[hashSize].value = i;
        hashSize++;
    }

    *returnSize = 0;
    free(hashTable);
    return NULL;
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    int* result = twoSum(nums, 4, target, &returnSize);

    if (result != NULL) {
        printf("Index1 = %d, Index2 = %d\n", result[0], result[1]);
        free(result);
    } else {
        printf("No solution found.\n");
    }
    return 0;
}

2. 链表

特点：动态数据结构，考察指针操作。
常见考点：
- 快慢指针
- 链表的反转
- 环检测

高频题：

反转链表
给定一个单链表，反转链表并返回反转后的头节点。

代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 反转链表函数
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* current = head;

    while (current != NULL) {
        struct ListNode* nextTemp = current->next;
        current->next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

// 测试代码
void printList(ListNode* head) {
    while (head != NULL) {
        printf("%d -> ", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = 1;
    head->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->val = 2;
    head->next->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->next->val = 3;
    head->next->next->next = NULL;

    printf("Original List: ");
    printList(head);

    ListNode* reversed = reverseList(head);
    printf("Reversed List: ");
    printList(reversed);

    return 0;
}

3. 栈与队列

特点：先进后出（栈）与先进先出（队列）。
常见考点：
- 括号匹配
- 单调栈
- 滑动窗口最大值

高频题：

有效的括号
给定一个只包括 ()、[]、{} 的字符串，判断字符串是否有效。

代码实现：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool isValid(char* s) {
    char* stack = (char*)malloc(strlen(s) * sizeof(char));
    int top = -1;

    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '{' || c == '[') {
            stack[++top] = c;
        } else {
            if (top == -1) {
                free(stack);
                return false;
            }
            char topChar = stack[top--];
            if ((c == ')' && topChar != '(') ||
                (c == '}' && topChar != '{') ||
                (c == ']' && topChar != '[')) {
                free(stack);
                return false;
            }
        }
    }

    bool result = (top == -1);
    free(stack);
    return result;
}

int main() {
    char* s = "({[]})";
    if (isValid(s)) {
        printf("The string is valid.\n");
    } else {
        printf("The string is invalid.\n");
    }
    return 0;
}

4. 动态规划

特点：通过状态转移方程解决问题。
常见考点：
- 背包问题
- 最长子序列/子数组
- 零钱兑换

高频题：

最长公共子序列
给定两个字符串，返回它们的最长公共子序列的长度。

代码实现：

#include <stdio.h>
#include <string.h>

int longestCommonSubsequence(char* text1, char* text2) {
    int m = strlen(text1), n = strlen(text2);
    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    return dp[m][n];
}

int main() {
    char* text1 = "abcde";
    char* text2 = "ace";
    printf("The length of LCS is %d\n", longestCommonSubsequence(text1, text2));
    return 0;
}