本文主要记录了五种典型算法题的解法，涵盖数组、链表、字符串、栈、队列等常见数据结构。以下是每道题的具体实现思路和代码示例。

一、二维数组搜索

题目概述

给定一个有序二维数组，寻找目标值是否存在。

解法一：逐行筛选

利用每行的有序性，先筛选可能的行，再在候选行中进行逐列查找。时间复杂度最坏为O(m+n)。

bool searchMatrix(int** grid, int rows, int* cols, int target) {
    int row = 0;
    while (row < rows && grid[row][cols[0] - 1] < target) {
        row++;
    }
    for (int i = 0; i < cols[0]; i++) {
        if (grid[row][i] == target) {
            return true;
        }
    }
    return false;
}

解法二：二分查找

将二维矩阵视为一维有序数组，利用二分查找实现高效查找。时间复杂度为O(log(mn))。

bool searchMatrix(int** grid, int rows, int* cols, int target) {
    int left = 0, right = rows * cols[0];
    while (left < right) {
        int mid = left + (right - left) / 2;
        int x = grid[mid / cols[0]][mid % cols[0]];
        if (x == target) {
            return true;
        }
        if (x < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return false;
}

二、双链表转数组

题目概述

将双向链表转换为数组，并通过指针返回数组长度。

解法思路

通过三次遍历获取链表长度，再进行数组填充。时间复杂度为O(n)。

struct Node {
    int val;
    struct Node* prev;
    struct Node* next;
};

int* listToArray(struct Node* head, int* returnSize) {
    struct Node* tail = head;
    while (tail->next) tail = tail->next;
    int len = 0;
    while (tail) {
        tail = tail->prev;
        len++;
    }
    int* result = (int*)malloc(sizeof(int) * len);
    struct Node* current = head;
    for (int i = 0; i < len; i++) {
        result[i] = current->val;
        current = current->next;
    }
    *returnSize = len;
    return result;
}

三、重复字符串匹配

题目概述

判断字符串a重复多次后是否包含字符串b。

解法思路

使用KMP算法结合数学计算优化实现，避免实际拼接字符串。时间复杂度为O(a + b)。

int kmpSearch(char* text, int textLen, char* pattern, int patternLen) {
    int* pi = (int*)malloc(sizeof(int) * patternLen);
    pi[0] = 0;
    for (int i = 1; i < patternLen; i++) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        pi[i] = j;
    }
    int j = 0;
    for (int i = 0; i < textLen; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == patternLen) {
            return i - patternLen + 1;
        }
    }
    free(pi);
    return -1;
}

int minRepeats(char* a, char* b) {
    int aLen = strlen(a), bLen = strlen(b);
    if (bLen == 0) return 0;
    int pos = kmpSearch(a, aLen, b, bLen);
    if (pos == -1) return -1;
    if (aLen - pos >= bLen) return 1;
    return (bLen + pos - aLen - 1) / aLen + 2;
}

四、下一个更大元素

题目概述

寻找数组中每个元素右边第一个比它大的元素。

解法思路

使用哈希表和单调栈实现，时间复杂度为O(n)。

int* nextGreater(int* nums, int size, int* returnSize) {
    *returnSize = size;
    int* result = (int*)malloc(sizeof(int) * size);
    memset(result, -1, sizeof(int) * size);
    int* hash = (int*)malloc(sizeof(int) * (size + 1));
    memset(hash, -1, sizeof(int) * (size + 1));
    for (int i = 0; i < size; i++) {
        hash[nums[i]] = i;
    }
    int* stack = (int*)malloc(sizeof(int) * size);
    int top = -1;
    for (int i = size - 1; i >= 0; i--) {
        while (top >= 0 && nums[i] >= stack[top]) {
            top--;
        }
        if (top >= 0 && hash[nums[i]] != -1) {
            result[hash[nums[i]]] = stack[top];
        }
        stack[++top] = nums[i];
    }
    free(stack);
    free(hash);
    return result;
}

五、栈实现队列

题目概述

通过两个栈实现队列的先进先出特性。

解法思路

使用两个栈分别实现入队和出队操作，时间复杂度为O(1)。

typedef struct {
    int* data;
    int size;
    int capacity;
} Stack;

Stack* stackCreate(int capacity) {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->data = (int*)malloc(sizeof(int) * capacity);
    s->size = 0;
    s->capacity = capacity;
    return s;
}

void stackPush(Stack* s, int value) {
    if (s->size < s->capacity) {
        s->data[s->size++] = value;
    }
}

void stackPop(Stack* s) {
    if (s->size > 0) {
        s->size--;
    }
}

int stackTop(Stack* s) {
    if (s->size > 0) {
        return s->data[s->size - 1];
    }
    return -1;
}

bool stackEmpty(Stack* s) {
    return s->size == 0;
}

void stackDestroy(Stack* s) {
    free(s->data);
    free(s);
}

typedef struct {
    Stack* inStack;
    Stack* outStack;
} Queue;

Queue* queueCreate() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->inStack = stackCreate(100);
    q->outStack = stackCreate(100);
    return q;
}

void transfer(Queue* q) {
    while (!stackEmpty(q->inStack)) {
        stackPush(q->outStack, stackTop(q->inStack));
        stackPop(q->inStack);
    }
}

void queuePush(Queue* q, int value) {
    stackPush(q->inStack, value);
}

int queuePop(Queue* q) {
    if (stackEmpty(q->outStack)) {
        transfer(q);
    }
    if (stackEmpty(q->outStack)) {
        return -1;
    }
    int result = stackTop(q->outStack);
    stackPop(q->outStack);
    return result;
}

bool queueEmpty(Queue* q) {
    return stackEmpty(q->inStack) && stackEmpty(q->outStack);
}

void queueDestroy(Queue* q) {
    stackDestroy(q->inStack);
    stackDestroy(q->outStack);
    free(q);
}

总结

本文提供了五种典型算法题的详细解法，涵盖了从暴力解法到优化算法的完整思考过程，并附有完整的代码实现。每种解法都分析了时间复杂度，为理解算法优化提供了参考。