【Day01】堆与字符串处理算法详解
坚持用清晰易懂的图解+代码语言，让每个知识点变得简单！
🚀呆头个人主页详情
🌱 呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭：“不患无位，患所以立。”
【Day01】堆与字符串处理算法详解
摘要
本文包含：编程题与堆相关选择题
【力扣242】有效的字母异位词【链接直达----------请点击】
【力扣1704】判断字符串的两半是否相似【链接直达----------请点击】
【牛客HJ1】字符串最后一个单词的长度【链接直达----------请点击】
【力扣125】验证回文串【链接直达----------请点击】
📌 坚持打卡：
算法没有捷径，但正确的方法能让你少走弯路。每天15分钟，和我一起用代码雕刻思维！
（正文开始👇）
目录
一、堆数据结构基础
堆（Heap）是一种特殊的完全二叉树，按照其性质可分为最大堆和最小堆：
- 最大堆：每个节点的值都大于或等于其子节点的值
- 最小堆：每个节点的值都小于或等于其子节点的值
堆通常用数组实现，对于数组中的第i个元素：
- 其左子节点位置：
2*i + 1 - 其右子节点位置：
2*i + 2 - 其父节点位置：
(i-1)/2
堆的基本操作
- 插入元素：将新元素添加到堆的末尾，然后进行上浮（heapify-up）操作
- 删除堆顶：移除堆顶元素，将最后一个元素放到堆顶，然后进行下沉（heapify-down）操作
- 建堆：将无序数组转换为堆结构
下面是一个最大堆的C++实现示例：
#include<vector>#include<iostream>classMaxHeap{private: std::vector<int> heap;// 上浮操作voidheapifyUp(int index){int parent =(index -1)/2;// 如果当前节点大于父节点，则交换并继续上浮if(index >0&& heap[index]> heap[parent]){ std::swap(heap[index], heap[parent]);heapifyUp(parent);}}// 下沉操作voidheapifyDown(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:// 插入元素voidinsert(int value){ heap.push_back(value);heapifyUp(heap.size()-1);}// 删除堆顶元素intextractMax(){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;}// 建堆voidbuildHeap(const std::vector<int>& array){ heap = array;// 从最后一个非叶子节点开始，依次进行下沉操作for(int i = heap.size()/2-1; i >=0; i--){heapifyDown(i);}}// 打印堆voidprintHeap(){for(int value : heap){ std::cout << value <<" ";} std::cout << std::endl;}// 获取堆大小intsize(){return heap.size();}// 判断堆是否为空boolempty(){return heap.empty();}};堆排序
堆排序是一种基于堆数据结构的排序算法，其步骤如下：
- 将无序数组构建成一个堆
- 将堆顶元素与末尾元素交换，调整堆结构
- 重复步骤2，直到所有元素排序完成
voidheapSort(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);}}// 调整堆结构voidheapify(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. 有效的字母异位词
问题描述：判断两个字符串是否互为字母异位词（即两个字符串包含相同的字符，但字符顺序可能不同）。
解题思路：使用计数法，统计每个字符出现的次数，如果两个字符串中每个字符出现的次数相同，则它们互为字母异位词。
classSolution{public:boolisAnagram(string s, string t){// 如果长度不同，直接返回falseif(s.length()!= t.length()){returnfalse;}// 创建一个大小为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){returnfalse;}}// 如果所有计数都为0，返回truereturntrue;}};代码解析：
- 首先检查两个字符串的长度是否相同，不同则直接返回false
- 使用一个大小为26的数组来统计每个小写字母的出现次数
- 遍历字符串s和t，对于s中的字符增加计数，对于t中的字符减少计数
- 最后检查数组中的所有计数是否都为0，如果是则返回true，否则返回false
时间复杂度：O(n)，其中n是字符串的长度
空间复杂度：O(1)，因为使用了固定大小的数组
2. 判断字符串的两半是否相似
问题描述：给定一个偶数长度的字符串，判断其前半部分和后半部分中元音字母的数量是否相同。
解题思路：分别统计字符串前半部分和后半部分中元音字母的数量，然后比较它们是否相等。
classSolution{public:// 判断字符是否为元音字母boolisVowel(char c){// 转换为小写后判断 c =tolower(c);return c =='a'|| c =='e'|| c =='i'|| c =='o'|| c =='u';}boolhalvesAreAlike(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<iostream>#include<string>usingnamespace std;intmain(){ string s;// 读取一行输入，包括空格getline(cin, s);// 查找最后一个空格的位置 size_t pos = s.rfind(' ');// 如果找到了空格，则最后一个单词的长度为字符串长度减去空格位置再减1if(pos != string::npos){ cout << s.size()- pos -1<< endl;}else{// 如果没有找到空格，说明整个字符串就是一个单词 cout << s.size()<< endl;}return0;}代码解析：
- 使用getline函数读取一行输入，包括空格
- 使用rfind函数从右向左查找第一个空格的位置
- 如果找到了空格，则最后一个单词的长度为字符串长度减去空格位置再减1
- 如果没有找到空格，说明整个字符串就是一个单词，长度为字符串的长度
时间复杂度：O(n)，其中n是字符串的长度
空间复杂度：O(1)
4. 验证回文串
问题描述：给定一个字符串，判断其是否为回文串，只考虑字母和数字字符，忽略大小写。
解题思路：使用双指针法，从字符串的两端向中间移动，跳过非字母数字字符，比较字符是否相同。
classSolution{public:boolisPalindrome(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])){returnfalse;}// 移动指针 begin++; end--;}returntrue;}};代码解析：
- 使用两个指针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
总结
本文介绍了堆数据结构的基本概念、操作和应用，以及几种常见的字符串处理算法。堆是一种重要的数据结构，广泛应用于优先队列、堆排序等场景。字符串处理算法则是编程中的基础技能，掌握这些算法可以帮助我们更高效地解决各种问题。
希望本文对你理解堆和字符串处理算法有所帮助！
