【Day01】堆与字符串处理算法详解

技术文档

坚持用清晰易懂的图解 + 代码语言，让每个知识点变得简单！
🚀呆头个人主页详情
🌱 呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭： “不患无位，患所以立。”

【Day01】堆与字符串处理算法详解

摘要
目录
- 一、堆数据结构基础
- - 堆的基本操作
  - 堆排序
- 二、字符串处理算法
- - 1. 有效的字母异位词
  - 2. 判断字符串的两半是否相似
  - 3. 字符串最后一个单词的长度
  - 4. 验证回文串
- 三、堆相关选择题解析
- 总结

摘要

本文包含：编程题与堆相关选择题
【力扣242】有效的字母异位词【链接直达----------请点击】
【力扣1704】判断字符串的两半是否相似【链接直达----------请点击】
【牛客HJ1】字符串最后一个单词的长度【链接直达----------请点击】
【力扣125】验证回文串【链接直达----------请点击】

📌 坚持打卡：
算法没有捷径，但正确的方法能让你少走弯路。每天15分钟，和我一起用代码雕刻思维！

（正文开始👇）

#include #include class MaxHeap {private: std::vector<int> heap; // 上浮操作 void heapifyUp(int index) { int parent = (index - 1) / 2; // 如果当前节点大于父节点，则交换并继续上浮 if (index > 0 && heap[index] > heap[parent]) { std::swap(heap[index], heap[parent]); heapifyUp(parent); } } // 下沉操作 void heapifyDown(int index) { int largest = index; int left = 2 * index + 1; int right = 2 * index + 2; int size = heap.size(); // 找出当前节点、左子节点和右子节点中的最大值 if (left < size && heap[left] > heap[largest]) { largest = left; } if (right < size && heap[right] > heap[largest]) { largest = right; } // 如果最大值不是当前节点，则交换并继续下沉 if (largest != index) { std::swap(heap[index], heap[largest]); heapifyDown(largest); } } public: // 插入元素 void insert(int value) { heap.push_back(value); heapifyUp(heap.size() - 1); } // 删除堆顶元素 int extractMax() { if (heap.empty()) { throw std::out_of_range(\"Heap is empty\"); } int max = heap[0]; heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) { heapifyDown(0); } return max; } // 建堆 void buildHeap(const std::vector<int>& array) { heap = array; // 从最后一个非叶子节点开始，依次进行下沉操作 for (int i = heap.size() / 2 - 1; i >= 0; i--) { heapifyDown(i); } } // 打印堆 void printHeap() { for (int value : heap) { std::cout << value << \" \"; } std::cout << std::endl; } // 获取堆大小 int size() { return heap.size(); } // 判断堆是否为空 bool empty() { return heap.empty(); }};

堆排序

堆排序是一种基于堆数据结构的排序算法，其步骤如下：

将无序数组构建成一个堆
将堆顶元素与末尾元素交换，调整堆结构
重复步骤2，直到所有元素排序完成

void heapSort(std::vector<int>& arr) { int n = arr.size(); // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 一个个从堆顶取出元素 for (int i = n - 1; i > 0; i--) { // 将当前堆顶（最大值）移到末尾 std::swap(arr[0], arr[i]); // 对剩余的堆进行调整 heapify(arr, i, 0); }}// 调整堆结构void heapify(std::vector<int>& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // 如果左子节点大于根节点 if (left < n && arr[left] > arr[largest]) { largest = left; } // 如果右子节点大于当前最大值 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是根节点 if (largest != i) { std::swap(arr[i], arr[largest]); // 递归地调整受影响的子树 heapify(arr, n, largest); }}

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

二、字符串处理算法

字符串是编程中最常见的数据类型之一，下面介绍几种常见的字符串处理算法。

1. 有效的字母异位词

问题描述：判断两个字符串是否互为字母异位词（即两个字符串包含相同的字符，但字符顺序可能不同）。

解题思路：使用计数法，统计每个字符出现的次数，如果两个字符串中每个字符出现的次数相同，则它们互为字母异位词。

class Solution {public: bool isAnagram(string s, string t) { // 如果长度不同，直接返回false if (s.length() != t.length()) { return false; } // 创建一个大小为26的数组，用于统计每个小写字母的出现次数 // \'a\' - \'a\' = 0, \'b\' - \'a\' = 1, ..., \'z\' - \'a\' = 25 std::vector<int> char_counts(26, 0); // 遍历两个字符串，同时进行计数和抵消 for (int i = 0; i < s.length(); ++i) { // 统计字符串s中每个字符的出现次数（增加计数） char_counts[s[i] - \'a\']++; // 抵消字符串t中每个字符的出现次数（减少计数） char_counts[t[i] - \'a\']--; } // 检查char_counts数组，如果所有计数都为0，则说明是字母异位词 for (auto count : char_counts) { if (count != 0) { return false; } } // 如果所有计数都为0，返回true return true; }};

代码解析：

首先检查两个字符串的长度是否相同，不同则直接返回false
使用一个大小为26的数组来统计每个小写字母的出现次数
遍历字符串s和t，对于s中的字符增加计数，对于t中的字符减少计数
最后检查数组中的所有计数是否都为0，如果是则返回true，否则返回false

时间复杂度：O(n)，其中n是字符串的长度
空间复杂度：O(1)，因为使用了固定大小的数组

2. 判断字符串的两半是否相似

问题描述：给定一个偶数长度的字符串，判断其前半部分和后半部分中元音字母的数量是否相同。

解题思路：分别统计字符串前半部分和后半部分中元音字母的数量，然后比较它们是否相等。

class Solution {public: // 判断字符是否为元音字母 bool isVowel(char c) { // 转换为小写后判断 c = tolower(c); return c == \'a\' || c == \'e\' || c == \'i\' || c == \'o\' || c == \'u\'; } bool halvesAreAlike(string s) { int begin = 0; // 前半部分的起始索引 int count1 = 0; // 前半部分的元音字母计数 int end = s.size() / 2; // 后半部分的起始索引 int count2 = 0; // 后半部分的元音字母计数 // 同时遍历前半部分和后半部分 while(end < s.size()) { // 统计前半部分的元音字母 if(isVowel(s[begin])) { count1++; } // 统计后半部分的元音字母 if(isVowel(s[end])) { count2++; } begin++; end++; } // 比较两部分的元音字母数量是否相等 return count1 == count2; }};

代码解析：

定义一个辅助函数isVowel来判断字符是否为元音字母
使用两个指针分别指向字符串的前半部分和后半部分
同时遍历前半部分和后半部分，统计元音字母的数量
最后比较两部分的元音字母数量是否相等

时间复杂度：O(n)，其中n是字符串的长度
空间复杂度：O(1)

3. 字符串最后一个单词的长度

问题描述：给定一个字符串，计算其最后一个单词的长度。

解题思路：从字符串末尾向前遍历，找到最后一个单词的起始位置，然后计算长度。

#include #include using namespace std;int main() { string s; // 读取一行输入，包括空格 getline(cin, s); // 查找最后一个空格的位置 size_t pos = s.rfind(\' \'); // 如果找到了空格，则最后一个单词的长度为字符串长度减去空格位置再减1 if(pos != string::npos) { cout << s.size() - pos - 1 << endl; } else { // 如果没有找到空格，说明整个字符串就是一个单词 cout << s.size() << endl; } return 0;}

代码解析：

使用getline函数读取一行输入，包括空格
使用rfind函数从右向左查找第一个空格的位置
如果找到了空格，则最后一个单词的长度为字符串长度减去空格位置再减1
如果没有找到空格，说明整个字符串就是一个单词，长度为字符串的长度

时间复杂度：O(n)，其中n是字符串的长度
空间复杂度：O(1)

4. 验证回文串

问题描述：给定一个字符串，判断其是否为回文串，只考虑字母和数字字符，忽略大小写。

解题思路：使用双指针法，从字符串的两端向中间移动，跳过非字母数字字符，比较字符是否相同。

class Solution {public: bool isPalindrome(string s) { int begin = 0; // 左指针 int end = s.size() - 1; // 右指针 while(begin < end) { // 跳过非字母数字字符 while(begin < end && !isalnum(s[begin])) { begin++; } while(begin < end && !isalnum(s[end])) { end--; } // 比较字符（忽略大小写） if(tolower(s[begin]) != tolower(s[end])) { return false; } // 移动指针 begin++; end--; } return true; }};

代码解析：

使用两个指针begin和end分别指向字符串的开头和结尾
使用isalnum函数判断字符是否为字母或数字
使用tolower函数将字符转换为小写后进行比较
如果在任何时候发现不匹配的字符，则返回false
如果所有字符都匹配，则返回true

时间复杂度：O(n)，其中n是字符串的长度
空间复杂度：O(1)

三、堆相关选择题解析

堆是一种有用的数据结构。下列那个关键码序列是一个堆()。
A. 94,31,53,23,16,72
B. 94,53,31,72,16,23
C. 16,53,23,94,31,72
D. 16,31,23,94,53,72

解析：
堆是一种完全二叉树，如果是最大堆，则每个节点的值都大于或等于其子节点的值；如果是最小堆，则每个节点的值都小于或等于其子节点的值。

对于选项A：94,31,53,23,16,72
构建二叉树：

 94 / \\ 31 53 / \\ /23 16 72

检查：

94 > 31 且 94 > 53，满足最大堆性质
31 > 23 且 31 > 16，满足最大堆性质
53 < 72，不满足最大堆性质

因此，选项A不是一个堆。

对于选项B：94,53,31,72,16,23
构建二叉树：

 94 / \\ 53 31 / \\ /72 16 23

检查：

94 > 53 且 94 > 31，满足最大堆性质
53 < 72，不满足最大堆性质

因此，选项B不是一个堆。

对于选项C：16,53,23,94,31,72
构建二叉树：

 16 / \\ 53 23 / \\ /94 31 72

检查：

16 < 53 且 16 < 23，不满足最大堆性质
53 > 31，不满足最小堆性质

因此，选项C不是一个堆。

对于选项D：16,31,23,94,53,72
构建二叉树：

 16 / \\ 31 23 / \\ /94 53 72

检查：

16 < 31 且 16 < 23，满足最小堆性质
31 < 94 且 31 < 53，满足最小堆性质
23 < 72，满足最小堆性质

因此，选项D是一个最小堆。

答案：D

将关键字序列50, 40, 95, 20, 15,70,60,45,80调整成一个小根堆,堆结构是15,20,60,45,40,70, 95,50,80,该说法正确吗?()
A. 正确
B. 不正确

解析：
小根堆要求每个节点的值都小于或等于其子节点的值。我们将给定的堆结构表示为二叉树：

 15 / \\ 20 60 / \\ / \\ 45 40 70 95/ \\50 80

检查每个非叶子节点：

15的子节点是20和60，15 < 20且15 < 60，满足小根堆性质
20的子节点是45和40，20 < 45且20 < 40，满足小根堆性质
60的子节点是70和95，60 < 70且60 < 95，满足小根堆性质
45的子节点是50和80，45 < 50且45 < 80，满足小根堆性质

因此，该堆结构是一个小根堆，说法正确。

答案：A

已知序列25, 13, 10, 12,9是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,调整过程中元素之间进行的比较次数是()
A. 1
B. 2
C. 4
D. 5

解析：
原始大根堆：25, 13, 10, 12, 9
插入元素18后：25, 13, 10, 12, 9, 18

将18插入到堆的末尾后，需要进行上浮操作。首先，我们将堆表示为二叉树：

 25 / \\ 13 10 / \\ /12 9 18

上浮过程：

比较18和其父节点10：18 > 10，交换位置

 25 / \\ 13 18 / \\ /12 9 10

比较18和其父节点25：18 < 25，不交换

因此，比较次数为2。

答案：B

已知关键字序列5,8,12,19, 28, 20, 15,22是小根堆(最小堆),插入关键字3,调整后得到的小根堆是()
A. 3, 5, 12, 8, 28, 20, 15, 22, 19
B. 3, 5, 12, 19, 28, 20, 15, 22, 8
C. 3, 8, 12, 5, 28, 20, 15, 22, 19
D. 3, 5, 15, 8, 28, 20, 12, 22, 19

解析：
原始小根堆：5, 8, 12, 19, 28, 20, 15, 22
插入元素3后：5, 8, 12, 19, 28, 20, 15, 22, 3

将3插入到堆的末尾后，需要进行上浮操作。首先，我们将堆表示为二叉树：

 5 / \\ 8 12 / \\ / \\ 19 28 20 15 / \\ 22 3

上浮过程：

比较3和其父节点19：3 < 19，交换位置

 5 / \\ 8 12 / \\ / \\ 3 28 20 15 / \\ 22 19

比较3和其父节点8：3 < 8，交换位置

 5 / \\ 3 12 / \\ / \\ 8 28 20 15 / \\ 22 19

比较3和其父节点5：3 < 5，交换位置

 3 / \\ 5 12 / \\ / \\ 8 28 20 15 / \\ 22 19

因此，调整后的小根堆是：3, 5, 12, 8, 28, 20, 15, 22, 19

答案：A

在堆排序的过程中,建立一个堆的时间复杂度是()
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n²)

解析：
建立堆的过程是从最后一个非叶子节点开始，依次向前进行下沉操作。对于一个有n个节点的完全二叉树，最后一个非叶子节点的索引是n/2-1。

对于每个非叶子节点，下沉操作的时间复杂度是O(logn)，因为最坏情况下需要从根节点下沉到叶子节点，树的高度是logn。

乍看之下，建堆的时间复杂度似乎是O(n/2 * logn) = O(nlogn)。

但实际上，更精确的分析表明，建立堆的时间复杂度是O(n)。这是因为并非所有节点都需要下沉到叶子节点，靠近叶子节点的非叶子节点下沉的距离很短。具体来说，对于高度为h的节点，下沉操作的时间复杂度是O(h)，而在一个有n个节点的完全二叉树中，高度为h的节点数量大约是n/2^(h+1)。

因此，建堆的总时间复杂度为：
Σ(h=0 to logn) O(h * n/2^(h+1)) = O(n * Σ(h=0 to logn) h/2^(h+1)) = O(n)

答案：A

总结

本文介绍了堆数据结构的基本概念、操作和应用，以及几种常见的字符串处理算法。堆是一种重要的数据结构，广泛应用于优先队列、堆排序等场景。字符串处理算法则是编程中的基础技能，掌握这些算法可以帮助我们更高效地解决各种问题。

希望本文对你理解堆和字符串处理算法有所帮助！

【Day01】堆与字符串处理算法详解

【Day01】堆与字符串处理算法详解

摘要

目录

一、堆数据结构基础

堆的基本操作

堆排序

二、字符串处理算法

1. 有效的字母异位词

2. 判断字符串的两半是否相似

3. 字符串最后一个单词的长度

4. 验证回文串

三、堆相关选择题解析

总结

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签

【Day01】堆与字符串处理算法详解

【Day01】堆与字符串处理算法详解

摘要

目录

一、堆数据结构基础

堆的基本操作

堆排序

二、字符串处理算法

1. 有效的字母异位词

2. 判断字符串的两半是否相似

3. 字符串最后一个单词的长度

4. 验证回文串

三、堆相关选择题解析

总结

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签