2023华为od统一考试(c卷)c++

### 华为OD机试C++试题及解答 #### 题目描述 给定一个字符串 `s` 和一个整数 `k`，编写函数来查找该字符串中的最长子串长度，在此子串中最多可以有 `k` 个不同字符。 #### 解题思路 这个问题可以通过滑动窗口的方法解决。具体来说： - 使用两个指针表示当前窗口的起始位置和结束位置。 - 维护一个哈希表记录当前窗口内每种字符的数量。 - 当窗口内的不同字符数量超过 `k` 时，移动左边界直到满足条件。 - 记录并更新最大符合条件的子串长度。 ```cpp #include <unordered_map> #include <string> using namespace std; int lengthOfLongestSubstringKDistinct(const string& s, int k) { unordered_map<char, int> charCount; int left = 0, maxLength = 0; for (int right = 0; right < s.length(); ++right) { char currentChar = s[right]; charCount[currentChar]++; while (charCount.size() > k) { char leftChar = s[left++]; charCount[leftChar]--; if (charCount[leftChar] == 0) { charCount.erase(leftChar); } } maxLength = max(maxLength, right - left + 1); } return maxLength; } ``` 这段代码实现了上述逻辑，并能有效地找到含有至多 `k` 种不同字符的最大子串长度[^1]。

### 华为 OD 机考 A卷 C++ 题目及答案解析 华为OD机考试题通常涉及多种算法和数据结构的知识点，其中包括但不限于贪心算法、动态规划、二分查找以及字符串处理等内容。以下是基于已知信息整理的相关题目及其解答思路。 #### 贪心算法的应用 在某些场景下，贪心算法能够提供高效的解决方案。例如，在学生重新排队问题中，可以通过比较学生的身高或其他属性来实现最优排列[^1]。对于此类问题，C++ 的实现方式如下： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; bool compare(const pair<int, int>& a, const pair<int, int>& b) { if (a.first != b.first) return a.first > b.first; return a.second < b.second; } int main() { vector<pair<int, int>> students = {{170, 5}, {180, 3}, {160, 7}}; sort(students.begin(), students.end(), compare); for(auto &student : students){ cout << "(" << student.first << ", " << student.second << ")" << endl; } return 0; } ``` 上述代码展示了如何利用 `std::sort` 函数配合自定义比较函数完成对学生队列的重排操作。 #### 二分查找的理解与实践 针对二分查找类问题，理解其核心逻辑并熟练运用是非常重要的[^2]。下面是一个简单的例子，展示如何在有序数组中寻找目标值的位置： ```cpp #include <iostream> #include <vector> using namespace std; int binarySearch(vector<int> nums, int target) { int left = 0, right = nums.size()-1; while(left <= right){ int mid = left + (right-left)/2; // 防止溢出 if(nums[mid]==target){ return mid; } if(target<nums[mid]){ right=mid-1; }else{ left=mid+1; } } return -1; } int main(){ vector<int> data={1,3,5,7,9}; int result=binarySearch(data,5); cout<<result<<endl; return 0; } ``` 此段代码实现了基本的二分查找功能，并返回目标值所在索引位置。 #### 动态规划实例分析 动态规划是一种解决多阶段决策过程优化问题的有效方法。虽然未直接提及于引用材料中，但在实际考试中也较为常见。以下是一道经典的爬楼梯问题作为示范： ```cpp #include <iostream> #include <vector> using namespace std; int climbStairs(int n) { if(n<=2)return n; vector<int> dp(n+1,0); dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; } int main(){ int steps=climbStairs(5); cout<<steps<<endl; return 0; } ``` 该程序计算到达第N级台阶的不同路径数，体现了动态规划的思想应用。 ---