站长之家是什么网站_东营市建设管理局_阿森纳英超积分_北京推广

---

1. 反转字符串

题目描述

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

数据范围：

• 字符串长度 (0 \leq n \leq 1000)
• 要求：空间复杂度 (O(n))，时间复杂度 (O(n))

---

示例

示例 1

输入：
"abcd"
输出：
"dcba"

示例 2

输入：
""
输出：
""

---

解题思路

双指针法

1. 初始化：

   • 使用两个指针，一个指向字符串的开头（i），另一个指向字符串的末尾（j）。

2. 交换字符：

   • 交换 str[i] 和 str[j] 的值。
   • 移动指针 i++ 和 j--。

3. 终止条件：

   • 当 i >= j 时，停止交换。

---

代码实现

#include <string.h>char* solve(char* str) {int i = 0;int j = strlen(str) - 1;while (i < j) {// 交换字符char temp = str[i];str[i] = str[j];str[j] = temp;// 移动指针i++;j--;}return str;
}

---

复杂度分析

• 时间复杂度：(O(n))，需要遍历字符串的一半。
• 空间复杂度：(O(1))，仅使用常数空间。

---

2. 判断回文字符串

题目描述

给定一个长度为 (n) 的字符串，判断该字符串是否是回文。如果是回文，返回 true，否则返回 false。

回文定义：字符串正序与其逆序逐字符一致。

数据范围：

• 字符串长度 (0 < n \leq 1000000)
• 要求：空间复杂度 (O(1))，时间复杂度 (O(n))

---

示例

示例 1

输入：
"absba"
输出：
true

示例 2

输入：
"ranko"
输出：
false

示例 3

输入：
"a"
输出：
true

---

解题思路

双指针法

1. 初始化：

   • 使用两个指针，一个指向字符串的开头（i），另一个指向字符串的末尾（j）。

2. 比较字符：

   • 比较 str[i] 和 str[j] 是否相等。
   • 如果相等，移动指针 i++ 和 j--。
   • 如果不相等，直接返回 false。

3. 终止条件：

   • 当 i >= j 时，说明字符串是回文，返回 true。

---

代码实现

#include <stdbool.h>
#include <string.h>bool judge(char* str) {int i = 0;int j = strlen(str) - 1;while (i <= j) {if (str[i] != str[j]) {return false; // 如果字符不相等，返回 false}i++;j--;}return true; // 如果所有字符都相等，返回 true
}

---

复杂度分析

• 时间复杂度：(O(n))，需要遍历字符串的一半。
• 空间复杂度：(O(1))，仅使用常数空间。

---

3. 合并区间

题目描述

给定一组区间，合并所有重叠的区间，并保证合并后的区间按起点升序排列。

区间定义：

struct Interval {int start; // 起点int end;   // 终点
};

数据范围：

• 区间组数 (0 \leq n \leq 2 \times 10^5)
• 区间值 (0 \leq \text{val} \leq 2 \times 10^5)
• 要求：空间复杂度 (O(n))，时间复杂度 (O(n \log n))

---

示例

示例 1

输入：
[[10,30],[20,60],[80,100],[150,180]]
输出：
[[10,60],[80,100],[150,180]]

示例 2

输入：
[[0,10],[10,20]]
输出：
[[0,20]]

---

qsort()

1. base：

   • 指向待排序数组的起始地址。
   • 在本题中，base 是 intervals，即待排序的区间数组。

2. nmemb：

   • 数组中元素的个数。
   • 在本题中，nmemb 是 intervalsLen，即区间的数量。

3. size：

   • 数组中每个元素的大小（以字节为单位）。
   • 在本题中，size 是 sizeof(struct Interval)，即每个 Interval 结构体的大小。

4. compar：

   • 指向比较函数的指针。该函数用于定义排序规则。
   • 在本题中，compar 是 compare 函数。

---

compare 函数

compare 函数用于定义排序规则。它的原型如下：

int compare(const void *a, const void *b);

• 参数：

  • a 和 b 是指向数组中两个元素的指针。
  • 在本题中，a 和 b 是指向 Interval 结构体的指针。

• 返回值：

  • 如果 a 应该排在 b 前面，返回一个负整数。
  • 如果 a 和 b 相等，返回 0。
  • 如果 a 应该排在 b 后面，返回一个正整数。

---

排序规则

1. 按起点升序排序：

   • 如果两个区间的起点不同，按起点从小到大排序。

2. 按终点升序排序：

   • 如果两个区间的起点相同，按终点从小到大排序。

参数	说明
base	待排序数组的起始地址
nmemb	数组中元素的个数
size	每个元素的大小
compar	比较函数，定义排序规则

解题思路

排序 + 合并

1. 排序：
   • 将所有区间按起点升序排序。如果起点相同，按终点升序排序。
     qsort 是 C 标准库中的一个函数，用于对数组进行排序。它的原型如下：

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

2. 合并：
   • 初始化结果数组，将第一个区间加入结果。
   • 遍历剩余区间，如果当前区间与结果数组中的最后一个区间重叠，则合并；否则，将当前区间加入结果数组。

---

代码实现

#include <stdlib.h>// 区间定义
struct Interval {int start;int end;
};// 比较函数，用于排序
int compare(const void* a, const void* b) {struct Interval* intervalA = (struct Interval*)a;struct Interval* intervalB = (struct Interval*)b;if (intervalA->start == intervalB->start) {return intervalA->end - intervalB->end; // 按终点升序}return intervalA->start - intervalB->start; // 按起点升序
}// 合并区间函数
struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize) {if (intervalsLen == 0) {*returnSize = 0;return NULL;}// 排序qsort(intervals, intervalsLen, sizeof(struct Interval), compare);// 初始化结果数组struct Interval* result = (struct Interval*)malloc(intervalsLen * sizeof(struct Interval));*returnSize = 0;// 将第一个区间加入结果result[0] = intervals[0];(*returnSize)++;// 遍历剩余区间for (int i = 1; i < intervalsLen; i++) {// 如果当前区间与结果数组中的最后一个区间重叠if (intervals[i].start <= result[(*returnSize) - 1].end) {// 合并区间result[(*returnSize) - 1].end = (intervals[i].end > result[(*returnSize) - 1].end) ? intervals[i].end : result[(*returnSize) - 1].end;} else {// 不重叠，将当前区间加入结果(*returnSize)++;result[(*returnSize) - 1] = intervals[i];}}return result;
}

---

复杂度分析

• 时间复杂度：(O(n \log n))，排序的时间复杂度为 (O(n \log n))，合并的时间复杂度为 (O(n))。
• 空间复杂度：(O(n))，用于存储结果数组。

---

总结

问题	方法	时间复杂度	空间复杂度	核心思想
反转字符串	双指针法	(O(n))	(O(1))	从两端向中间交换字符
判断回文字符串	双指针法	(O(n))	(O(1))	从两端向中间比较字符
合并区间	排序 + 合并	(O(n \log n))	(O(n))	按起点排序后合并重叠区间

前两题双指针非常简单。后面合并区间只要注意范围,学会qsort和compare函数就还好。