挑战你的算法思维——八道C语言算法类难题

前言

在计算机编程领域，算法是至关重要的基础知识之一。通过解决算法问题，我们可以提升自己的逻辑思维能力，加深对编程语言的理解，并锻炼解决问题的能力。本篇博客将带你深入探讨八道C语言算法类难题，涵盖了递归、搜索、字符串操作等多个方面的算法挑战。

在接下来的内容中，我们将逐一介绍每道难题的具体问题，并提供相应的C语言代码解答。通过挑战这些问题，不仅可以加深对C语言的理解，还能锻炼解决问题的能力和编程思维。让我们一起开始这段有趣的算法之旅吧！

1.最长递增子序列

int lengthOfLIS(int* nums, int numsSize) {
    int dp[numsSize];
    int maxLen = 1;
    
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
        }
    }
    
    return maxLen;
}

2.最大子序和

int maxSubArray(int* nums, int numsSize) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        currentSum = fmax(nums[i], currentSum + nums[i]);
        maxSum = fmax(maxSum, currentSum);
    }
    
    return maxSum;
}

3.二叉树的最大深度

int maxDepth(struct TreeNode* root) {
    if (root == NULL) return 0;
    
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    
    return fmax(leftDepth, rightDepth) + 1;
}

4.括号生成

void generateParenthesisHelper(char* str, int left, int right, int n, int* returnSize, char** result) {
    if (left == n && right == n) {
        result[(*returnSize)] = strdup(str);
        (*returnSize)++;
        return;
    }
    
    if (left < n) {
        str[left + right] = '(';
        generateParenthesisHelper(str, left + 1, right, n, returnSize, result);
    }
    if (right < left) {
        str[left + right] = ')';
        generateParenthesisHelper(str, left, right + 1, n, returnSize, result);
    }
}
 
char** generateParenthesis(int n, int* returnSize) {
    char** result = (char**)malloc(sizeof(char*) * 10000);
    char* str = (char*)malloc(sizeof(char) * (2 * n + 1));
    *returnSize = 0;
    
    generateParenthesisHelper(str, 0, 0, n, returnSize, result);
    
    return result;
}

5.合并K个排序链表

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (listsSize == 0) return NULL;
    struct ListNode* merged = lists[0];
    
    for (int i = 1; i < listsSize; i++) {
        merged = mergeTwoLists(merged, lists[i]);
    }
    
    return merged;
}

6.单词搜索

bool exist(char** board, int boardSize, int* boardColSize, char* word) {
    int m = boardSize, n = *boardColSize;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, m, n, i, j, word, 0)) {
                return true;
            }
        }
    }
    
    return false;
}

7.最小路径和

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = *gridColSize;
    
    for (int i = 1; i < m; i++) {
        grid[i][0] += grid[i-1][0];
    }
    for (int j = 1; j < n; j++) {
        grid[0][j] += grid[0][j-1];
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += fmin(grid[i-1][j], grid[i][j-1]);
        }
    }
    
    return grid[m-1][n-1];
}

8.判断回文链表

bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return true;
    
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    struct ListNode* secondHalf = reverseList(slow->next);
    struct ListNode* firstHalf = head;
    
    while (secondHalf != NULL) {
        if (firstHalf->val != secondHalf->val) {
            return false;
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }
    
    return true;
}