力扣Hot100中的困难题
算法
力扣Hot100中的困难题
算法

力扣Hot100中的困难题

1、最长有效括号（栈）

（1）题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

（2）解题思路

遇到“（”入栈，遇到“）”出栈。

（3）错误解法

#include <string.h>
#define MAX(a, b) ((a) > (b) ? a : b)
int longestValidParentheses(char* s) {
    // ()(()会输出4 但是答案为2
    // 遇到(压入栈中，遇到)进行出栈，如果出栈失败c_ans重置为0，否则c_ans++，同时不断更新ans
    int ans = 0;
    int n = strlen(s); 
    char z[n];
    int bottom = -1; // 定义栈尾指针
    int c_ans = 0;
    for (int i = 0; i < n; i++) {
        if (bottom == -1 && s[i] == ")") continue;
        if (s[i] == '(') {
            z[++bottom] = '('; // 入栈
        } else {
            if (z[bottom] == '(') { // 出栈
                c_ans += 2;
                bottom--;
                ans = MAX(ans, c_ans);
            } else {
                c_ans = 0;
            }
        }
    }
    return ans;
}

（4）正确解法，栈中存储下标

#include <string.h>
#define MAX(a, b) ((a) > (b) ? a : b)
int longestValidParentheses(char* s) {
    int n = strlen(s);
    int ans = 0;

    int stack[n+1];
    int top = -1;
    stack[++top] = -1; // 初始参考
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            stack[++top] = i; // 入栈
        } else {
            --top; // 先出栈
            if (top == -1) { // 说明“）”目前多余
                stack[++top] = i; // 新参考
            } else {
                ans = MAX(ans, i - stack[top]);
            }
        }
    }
    return ans;
}

2、柱状图中最大的矩形（栈）

（1）题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

（2）解题思路

    第一种解法是暴力，枚举所有left和right，然后不断更新答案.

第二种解法是维护一个单调递增的栈。穷举：计算了以所有柱子高度为矩形高度的情况。

    如果遇到一个高度a比栈顶索引对应的高度b小，即，弹出栈顶，并把a的索引作为右边界j。

    把当前栈顶作为左边界i。 j-i-1就是宽度。

    栈是更好的发现左边界和右边界。

（3）解法

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int largestRectangleArea(int* heights, int heightsSize) {
    int* stack = (int*)malloc(sizeof(int) * (heightsSize + 2));
    int top = -1;
    int max_area = 0;


    for (int i = -1; i <= heightsSize; i++) {
        // 左右0
        int cur_h = (i == -1 || i == heightsSize) ? 0 : heights[i];

        while (top != -1 && ((stack[top] == -1) ? 0 : heights[stack[top]]) > cur_h) {
            int h = heights[stack[top--]];
            
            // 此时栈顶就是左边界，当前 i 就是右边界
            int left_idx = stack[top];
            int width = i - left_idx - 1;
            
            max_area = MAX(max_area, h * width);
        }
        stack[++top] = i;
    }

    free(stack);
    return max_area;
}

3、寻找两个正序数组的中位数（二分）

（1）题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

（2）解题思路

先合并数组，再二分。

（3）解法

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

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int totalSize = nums1Size + nums2Size;
    int* merged = (int*)malloc(sizeof(int) * totalSize); // 开辟内存
    
    // 合并两个数组
    int i = 0, j = 0, k = 0;
    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] < nums2[j]) {
            merged[k++] = nums1[i++];
        } else {
            merged[k++] = nums2[j++];
        }
    }
    
    // 处理剩余的元素
    if (nums1Size > nums2Size) while (i < nums1Size) merged[k++] = nums1[i++];
    else while (j < nums2Size) merged[k++] = nums2[j++];

    // 计算中位数
    if (totalSize % 2 == 1) return merged[totalSize / 2];
    else return (merged[totalSize / 2 - 1] + merged[totalSize / 2]) / 2.0;
}

4、N 皇后（DFS）

（1）题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

（2）解题思路

DFS+回溯

（3）解法

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

// 检查在(row, col)放置皇后是否安全
bool isSafe(int row, int col, int n, char** board) {
    // 1.检查正上方
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    // 2.检查左上方对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    // 3.检查右上方对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

// 递归函数
void backtrack(int row, int n, int* returnSize, char*** res, char** board) {
    if (row == n) { // 递归出口，存储答案
        res[*returnSize] = (char**)malloc(n * sizeof(char*));
        for (int i = 0; i < n; i++) {
            res[*returnSize][i] = (char*)malloc((n+1)*sizeof(char));
            strcpy(res[*returnSize][i], board[i]);
        }
        (*returnSize)++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(row, col, n, board)) {
            board[row][col] = 'Q';
            backtrack(row + 1, n, returnSize, res, board);
            board[row][col] = '.'; // for+回溯枚举所有情况
        }
    }
}

// 主函数
char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    // 1.准备结果数组
    char*** res = (char***)malloc(1000 * sizeof(char**));
    *returnSize = 0;
    // 2.初始化空的棋盘
    char** board = (char**)malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        board[i] = (char*)malloc((n + 1) * sizeof(char));
        for (int j = 0; j < n; j++) board[i][j] = '.';
        board[i][n] = '\0';
    }
    // 3.开始递归
    backtrack(0, n, returnSize, res, board);

    // 4.记录每个解的行数
    *returnColumnSizes = (int*)malloc((*returnSize) * sizeof(int));
    for (int i =0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = n;
    }

    return res;
}

5、最小覆盖子串（双指针）

（1）题目描述

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的 子串，返回空字符串 ""。

测试用例保证答案唯一。

（2）解题思路

滑动窗口

（3）解法

#include <string.h>
char* minWindow(char* s, char* t) {

    int m = strlen(s), n = strlen(t);
    int reference[128] = {0};
    for (int i = 0; i < n; i++) reference[t[i]]++;
    int window[128] = {0}; // 记录当前窗口每个字符出现的次数
    int total_kinds = 0;
    int current_kinds = 0;
    for (int i = 0; i < 128; i++) if (reference[i] > 0) total_kinds++;
    int left = 0, right = 0;
    int ans_len = m + 1; // 设置一个不可能的答案
    int start = 0;

    while (right < m) {
        if (reference[s[right]] > 0) {
            window[s[right]]++;
            if (window[s[right]] == reference[s[right]]) {
                current_kinds++;
            }
        }
        while (current_kinds == total_kinds) {
            if ((right - left + 1) <= ans_len) {
               start = left; // 更新起点位置
               ans_len = right - left + 1; // 更新长度
            }
            // 收缩窗口（很标准的收缩，只有当满足情况，才进行滑动左边界进一步判断）
            if (reference[s[left]] > 0) {
                window[s[left]]--;
                if (window[s[left]] < reference[s[left]]) current_kinds--;
            }
            left++;
        }
        right++;
    }

    if (ans_len == m + 1) return "";
    char* res = (char*)malloc((ans_len+1) * sizeof(char));
    strncpy(res, s + start, ans_len + 1); //+1表示连'\0'一同复制过去
    return res;
}

6、接雨水（动态规划、双指针）

（1）题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

（2）解题思路

木桶原理

（3）解题

1）动态规划

#define MIN(a, b) ((a) < (b) ? a : b)
#define MAX(a, b) ((a) > (b) ? a : b)
int trap(int* height, int heightSize) {
    // 定义数组left_max_height，left_max_height[i]表示位置i左边柱子的最高高度。
    // 定义数组right_max_height，right_max_height[i]表示位置i右边柱子的最高高度。
    int left_max_height[heightSize];
    int right_max_height[heightSize];
    for (int i = 0; i < heightSize; i++) {
        left_max_height[i] = -1;
        right_max_height[i] = -1;
    }

    // 动态规划
    for (int i = 1; i < heightSize-1; i++) {
        left_max_height[i] = MAX(height[i-1], left_max_height[i-1]);
    }
    for (int i = heightSize-2; i > 0; i--) {
        right_max_height[i] = MAX(height[i+1], right_max_height[i+1]);
    }

    int ans = 0;
    for (int i = 1; i < heightSize - 1; i++) {
        if (MIN(left_max_height[i], right_max_height[i]) > height[i]) {
            ans += MIN(left_max_height[i], right_max_height[i]) - height[i];
        }
    }

    return ans;
}

2）双指针

int trap(int* height, int heightSize) {

    int left = 0, right = heightSize - 1;
    int l_max = 0, r_max = 0;
    int ans = 0;

    while (left < right) {
        // 更新左右两边的最高纪录
        if (height[left] > l_max) l_max = height[left];
        if (height[right] > r_max) r_max = height[right];

        // 核心逻辑：哪边矮，就计算哪边并移动哪边
        if (l_max < r_max) {
            // 左边是短板，水量由 l_max 决定
            ans += l_max - height[left];
            left++;
        } else {
            // 右边是短板，水量由 r_max 决定
            ans += r_max - height[right];
            right--;
        }
    }

    return ans;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注