1.44通配符匹配
1.1题目描述
给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
'?'可以匹配任何单个字符。'*'可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
示例 2：
输入：s = "aa", p = "*" 输出：true 解释：'*' 可以匹配任意字符串。
示例 3：
输入：s = "cb", p = "?a" 输出：false 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示：
0 <= s.length, p.length <= 2000s仅由小写英文字母组成p仅由小写英文字母、'?'或'*'组成
1.2 算法类型
动态规划
1.3leetcode环境下的c语言运行代码
#include <stdio.h>
#include <stdbool.h>
// 返回1表示匹配，返回0表示不匹配
int isMatch(char *s, char *p) {
int m = strlen(s);
int n = strlen(p);
bool dp[m + 1][n + 1];//为了方便处理边界情况和空字符串的情况，我们将字符串的长度加1，这样就可以使用0索引来表示空字符串的情况。
memset(dp, false, sizeof(dp));
dp[0][0] = true;
// 处理模式字符串开头为 * 的情况
for (int i = 1; i <= n; ++i) {
if (p[i - 1] == '*') {
dp[0][i] = true;
} else {
break; // 如果模式字符串以 * 开头，则空字符串可以匹配该模式字符串
}
}
//dp[i][j]的值，表示字符串s前i个字符是否能够匹配模式字符串p的前j个字符。
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
// 处理 * 在中间和末尾的情况
if (j < n && p[j] == '*') { // 处理 * 在中间的情况
dp[i][j] = dp[i][j - 1]; // 如果 * 在中间，则与前一个字符匹配或不匹配都可能
} else { // 处理 * 在末尾的情况
dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; // 与前一个字符或当前字符匹配或不匹配都可能dp[i][j-1]不匹配s的第i个字符：这意味着 * 匹配零个字符
}
} else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // ? 表示匹配任意一个字符，s[i-1]表示与当前字符匹配
}
}
}
return dp[m][n]; // 返回结果，不再是布尔值，而是匹配状态（1表示匹配，0表示不匹配）
}2.402移掉k位数
2.1题目描述
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：
输入：num = "1432219", k = 3 输出："1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：
输入：num = "10200", k = 1 输出："200" 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：
输入：num = "10", k = 2 输出："0" 解释：从原数字移除所有的数字，剩余为空就是 0 。
提示：
1 <= k <= num.length <= 105num仅由若干位数字（0 - 9）组成- 除了 0 本身之外，
num不含任何前导零
2.2算法类型
贪心
2.3leetcode环境下的c语言运行代码
#include <stdio.h>
#include <stdlib.h>//用于malloc和free
#include <string.h>
char* removeKdigits(char* num, int k) {
int len = strlen(num);
if (len == k) {
return "0";
}//如果字符串的长度等于要移除的位数，则返回"0"
char* stack = (char*)malloc((len + 1) * sizeof(char));//为栈分配内存，用于存储移除k个数字后的结果
int top = -1;//初始化栈顶为 -1。
for (int i = 0; i < len; i++) {
while (top >= 0 && k > 0 && stack[top] > num[i]) {//如果栈不为空、还有要移除的数字且栈顶元素大于当前字符，则将栈顶元素出栈并减少要移除的数字数量。动态分配一个字符数组stack，大小为len + 1，用于存储移除k个数字后的结果。这个栈会被模拟成一个递增的栈，栈顶元素始终是最小的。
top--;
k--;
}
stack[++top] = num[i];//将当前字符入栈。
}
while (k > 0) {
top--;
k--;
}//移除栈顶的元素，直到没有剩余要移除的数字或栈为空。
int start = 0;//用变量start找到第一个非零字符的位置。这个变量会记录结果字符串的起始位置。
while (start <= top && stack[start] == '0') {
start++;
}//跳过前导零
if (start > top) {
return "0";
}//如果开始位置大于栈顶，则返回 "0"。start表示结果字符串的起始位置而栈中的元素则是按递增顺序排列的。
char* result = (char*)malloc((top - start + 2) * sizeof(char));//动态分配一个新的字符数组来存储结果。
int idx = 0;//初始化索引为 0。
for (int i = start; i <= top; i++) {//将栈中剩余的元素复制到结果数组中。
result[idx++] = stack[i];//在结果字符串的末尾添加空字符。
}
result[idx] = '\0';
free(stack);//释放之前分配的栈内存
return result;
}3.（53最大字数组求和）
3.1题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为
O(n)的解法，尝试使用更为精妙的 分治法 求解。
2.2算法类型
分治法
2.3leetcode环境下的c语言运行代码
#include <stdio.h>
int max(int a,int b){
return a>b?a:b;
}
int maxSubArray(int nums[], int n) {
// 分治
// 将区间从中间切开，答案就在3个区间中：[left,mid]、[mid+1,right]、包含[mid,mid+1]的区间
// 对这3份求最大，第3个区间一定包含nums[mid]和nums[mid+1]，向外扩散即可
if (n == 0)
return 0;
return maxSubArraySum(nums, 0, n - 1);
}
// 包含中间两数的区间最大值
int maxCrossingSum(int nums[], int left, int mid, int right) {
// 一定会包含 nums[mid] 这个元素
int sum = 0;
int leftSum = INT_MIN;
// 左半边包含 nums[mid] 元素，最多可以到什么地方
// 走到最边界，看看最值是什么
// 计算以 mid 结尾的最大的子数组的和
for (int i = mid; i >= left; i--) {
sum += nums[i];
if (sum > leftSum)
leftSum = sum;
}
sum = 0;
int rightSum = INT_MIN;
// 右半边不包含 nums[mid] 元素，最多可以到什么地方
// 计算以 mid+1 开始的最大的子数组的和
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
if (sum > rightSum)
rightSum = sum;
}
return leftSum + rightSum;
}
// 左右两个区间的最大值
int maxSubArraySum(int nums[], int left, int right) {
if (left == right) // 长度为1的区间
return nums[left];
int mid = left + (right - left) / 2;
return max(maxSubArraySum(nums, left, mid), max(maxSubArraySum(nums, mid + 1, right), maxCrossingSum(nums, left, mid, right)));
}
