嵌入式必备基础手撕算法

一、数组与指针基础（必考）

1. 数组反转

考察点：指针、边界、原地操作

void reverse(int *arr, int n)
{
    int l = 0, r = n - 1;
    while (l < r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
        l++;
        r--;
    }
}

这些问题在嵌入式八股文专栏都涵盖了。

全网最全面的嵌入式八股文专栏：https://www.nowcoder.com/creation/manager/columnDetail/mPZ4kk

2. 查找最大 / 最小值

int max(int *a, int n)
{
    int m = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > m) m = a[i];
    return m;
}

3. 删除数组中的指定元素（原地）

int remove_val(int *a, int n, int val)
{
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] != val)
            a[k++] = a[i];
    }
    return k;  // 新长度
}

二、字符串处理（嵌入式最常考）

4. 手写 strlen

int my_strlen(const char *s)
{
    int len = 0;
    while (*s++) len++;
    return len;
}

5. 手写 strcpy

char *my_strcpy(char *dst, const char *src)
{
    char *ret = dst;
    while ((*dst++ = *src++));
    return ret;
}

6. 判断字符串是否为回文

int is_palindrome(const char *s)
{
    int l = 0, r = my_strlen(s) - 1;
    while (l < r) {
        if (s[l++] != s[r--])
            return 0;
    }
    return 1;
}

三、排序算法（手撕首选）

7. 冒泡排序

void bubble_sort(int *a, int n)
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j+1]) {
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
}

8. 插入排序（嵌入式很爱）

void insert_sort(int *a, int n)
{
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

四、链表（嵌入式面试核心）

9. 单链表反转（必背）

struct node {
    int data;
    struct node *next;
};

struct node* reverse_list(struct node *head)
{
    struct node *prev = NULL;
    struct node *cur = head;

    while (cur) {
        struct node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

10. 判断链表是否有环（快慢指针）

int has_cycle(struct node *head)
{
    struct node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return 1;
    }
    return 0;
}

五、栈与队列（RTOS / 驱动常考）

11. 用数组实现栈

#define MAX 100
int stack[MAX];
int top = -1;

int push(int x)
{
    if (top == MAX - 1) return -1;
    stack[++top] = x;
    return 0;
}

int pop(int *x)
{
    if (top == -1) return -1;
    *x = stack[top--];
    return 0;
}

12. 循环队列判空 / 判满

// 空：front == rear
// 满：(rear + 1) % N == front

六、位运算（嵌入式特色）

13. 判断奇偶

int is_odd(int x)
{
    return x & 1;
}

14. 统计二进制 1 的个数

int count_ones(unsigned int x)
{
    int cnt = 0;
    while (x) {
        x &= (x - 1);
        cnt++;
    }
    return cnt;
}

15. 不用临时变量交换两个数

void swap(int *a, int *b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

七、递归基础（适度）

16. Fibonacci（面试会问优化）

int fib(int n)
{
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

面试官真正想看什么？

1. 指针是否安全
2. 边界条件是否完整
3. 时间 / 空间复杂度意识
4. 是否贴合嵌入式场景（不用 STL、不用递归乱开栈）
5. 代码风格是否工程化