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