c++ 面试题(算法类)
2024-10-20 11:45:09
1，从无序的数据流中找到其中位数：（用大根堆和小根堆来实现）
float getMidimum(vector<int>& nums) {
priority_queue<int> bigHeap; // 大数优先
priority_queue<int, vector<int>, greater<int>> smallHeap; // 小数优先
for (int i = ; i < nums.size(); ++i) { // 对每一个输入的元素
if (bigHeap.empty() || nums[i] < bigHeap.top())
bigHeap.push(nums[i]);
else
smallHeap.push(nums[i]);
while (bigHeap.size() > smallHeap.size() + ) {
smallHeap.push(bigHeap.top());
bigHeap.pop();
}
while (smallHeap.size() > bigHeap.size() + ) {
bigHeap.push(smallHeap.top());
smallHeap.pop();
}
}
float temp;// 如果两个堆大小相等
if (bigHeap.size() == smallHeap.size()) {
temp = float(bigHeap.top() + smallHeap.top()) / ;
}
else if (bigHeap.size() < smallHeap.size()) // 如果小堆多一个元素
temp = smallHeap.top();
else // 如果大堆多一个元素
temp = bigHeap.top();
return temp;
}
getMidimum
2，25匹马五条赛道怎么最快选出前三个：（类似于：剑指offer p38：：二维数组中的查找）
参考：https://blog.csdn.net/cmsbupt/article/details/17404183
3，给定出栈顺序，求入栈顺序：
给定入栈顺序，求出栈顺序：
string Out; // 都声明未全局变量
string In;
bool match(string& In) {
int lens = Out.length();
stack<char> stk; // 模拟入栈操作
stk.push(In[]);
int j = , i = ; // j 为入栈序列索引, i 为出栈序列索引
while (i < lens) { // 如果还没有匹配完所有出栈元素序列，则不断进行匹配，直到入栈序列结束
if (j<lens && (stk.empty() || stk.top() != Out[i])) { // 如果入栈序列还有未进入栈的 && （栈空 || 不匹配）--》入栈操作
stk.push(In[j]);
++j; // 指向下一个入栈元素
}
else if (stk.top() == Out[i]) {
stk.pop();
++i;
}
else if (j == lens && !stk.empty()) { // 如果最后一个元素也遍历了，并且此时栈不空---》不是出栈顺序
return false;
}
}
return true;
}
stackMatch
int _tmain(int argc, _TCHAR* argv[])
{
// 给定一个栈的输出序列，找出所有可能的输入序列
cout << "input outStack string[Enter]:";
cin >> Out;
In = Out; sort(In.begin(), In.end()); //求出所有的输入序列,排序的目的是从头开始进行全排列
do {
if (match(In)) // 该函数的功能是对 In 和 Out 进行匹配，传入的总是 In
cout << In << endl;
} while (next_permutation(In.begin(), In.end())); // 该函数的实现见前面leetcode 数组类型题的相关博客 system("pause");
return ;
} int _tmain(int argc, _TCHAR* argv[])
{
// 给定一个栈的输入序列，找出所有可能的输出序列
cout << "input inStack string[Enter]:";
cin >> In;
Out = In; sort(Out.begin(), Out.end()); // 求出所有的输出序列
do {
if (match(In))
cout << Out<< endl; // Out 是不断变化的
} while (next_permutation(Out.begin(), Out.end())); //修改的是 Out 的本身 system("pause");
return ;
}
main
4，给定以排好序的数组(包括负数，0，和正数)，平方后找到其重复的元素（时间复杂度为 n,空间复杂度为 1）注：范围未知道
void show(vector<int>& result) {
for (int i = ; i<result.size(); ++i)
cout << '\t' << result[i];
cout << endl;
}
vector<int> dupNums(vector<int>& nums) {
vector<int> result;
for (int i = ; i<nums.size(); ++i)
nums[i] *= nums[i];
show(nums);
vector<int>::iterator start = nums.begin();
vector<int>::iterator end = nums.end() - ;
while (start != end) {
bool dup = false;
if (*start < *end) {
while ((end - ) != start) {
if (*(end - ) == *end) {
end--;
dup = true;
}
else {
break;
}
} // while2
if (start != (end - ) && dup) {
result.push_back(*end);
end--;
}
else if (start != (end - ) && !dup){
end--;
}
// show(result);
if (end - == start) {
if (*end == *start) {
result.push_back(*start);
}
return result;
}
}//if
else if (*start > *end) {
while (start + != end) {
if (*(start + ) == *start) {
start++;
dup = true;
}
else {
start++;
break;
}
}//while2
if (start + != end && dup) {
result.push_back(*start);
start++;
}
if (start + != end && !dup) {
start++;
}
if (start + == end) {
if (*start == *end) {
result.push_back(*start);
}
return result;
}
}//else if
else {
while (start + != end) {
if (*(start + ) == *start) {
start++;
}
else {
result.push_back(*start);
start++;
break;
}
}
if (start + == end) {
return result;
}
while ((end - ) != start) {
if (*(end - ) == *end) {
end--;
}
else {
end--;
break;
}
}//while2
if (end - == start) {
if (*start == *end) {
result.push_back(*start);
}
return result;
}
}//else
}//while1
return result;
}
dupNums
类似题：给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。空间复杂度为 1。注：范围已知
思路：把 nums[i] 放到 nums[nums[i] - 1] 的位置去（swap 操作）eg:把 4 放到下标为 3 的位置，把 5 放到下标为 4 的位置。
https://blog.csdn.net/zhangbaoanhadoop/article/details/82193866
5，skip_list(跳跃表)：
https://blog.csdn.net/ict2014/article/details/17394259
6，快排（递归）：
//quickSort
int Partition(int* arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot)
--right;
if (left < right) arr[left] = arr[right]; while (left < right && arr[left] <= pivot)
++left;
if (left < right) arr[right] = arr[left];
}
arr[left] = pivot;
return left; // 返回枢纽值所在下标
} void quickSort(int* arr, int left, int right) {
int pivot = ;
if (left <= right) {
pivot = Partition(arr, left, right);
quickSort(arr, left, pivot - );
quickSort(arr, pivot + , right);
}
}
quickSort
快排（非递归，用栈来实现）
void QuickSort(int *a, int left,int right)
{
if (a == NULL || left < || right <= || left>right)
return;
stack<int>temp;
int i, j;
//（注意保存顺序）先将初始状态的左右指针压栈
temp.push(right);//先存右指针
temp.push(left);//再存左指针
while (!temp.empty())
{
i = temp.top();//先弹出左指针
temp.pop();
j = temp.top();//再弹出右指针
temp.pop();
if (i < j)
{
int k = Pritation(a, i, j);
if (k > i)
{
temp.push(k - );//保存中间变量
temp.push(i); //保存中间变量
}
if (j > k)
{
temp.push(j);
temp.push(k + );
}
}
// 参考：http://www.cnblogs.com/ljy2013/p/4003412.html
quickSort(非递归)
快排时间复杂度分析：https://www.cnblogs.com/surgewong/p/3381438.html
快排的几种优化方式：https://blog.csdn.net/sofia_m/article/details/81534390
快排是不稳定的排序算法，那么稳定的意义是什么呢？
答：当有多个字段需要排序时（比如书籍的销量和书籍的价格），我们可以先用稳定排序对价格（从低到高）进行排序，然后在用稳定排序对书籍的销量进行排序，这样排序的结果就是相同销量的数据价格低的排在前面，达到了在第一列排序的基础上排序了第二列。
7，堆排序：
//heapSort
void Swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
//向上调整
void siftUp(int* arr, int u) {
int c, p; // c == child , p == parent
c = u;
for (;;) {
if (c == ) break;
p = c / ;
if (arr[p] > arr[c]) break;
Swap(arr[c], arr[p]);
c = p;
}
}
// 向下调整
void siftDown(int* arr, int l, int u) {
int c, p;
p = l;
for (;;) {
c = * p;
if (c > u) break;
if (c + <= u && arr[c + ] > arr[c]) c++;
if (arr[p] > arr[c]) break;
Swap(arr[p],arr[c]);
p = c;
}
}
// 向上调整建大根堆
void BuildBigHeap(int* arr,int n) {
for (int i = ; i <= n; ++i)
siftUp(arr, i);
}
//向下调整建大根堆
void BuildHeap(int* arr, int n) {
for (int i = n / ; i >= ; --i)
siftDown(arr, i, n);
}
void heapSort(int* arr, int n) {
int i = ;
arr--;
BuildBigHeap(arr, n);
for (i = n; i >= ; --i) {
Swap(arr[], arr[n]);
siftDown(arr, , i - );
}
arr++;
}
heapSort
8，二分搜索
// 二分搜索 // @没有重复值
int binSearch(vector<int>& nums, int target) {
auto left = nums.begin();
auto right = nums.end()-;
while (left <= right) { // 找mid 的对应值，此时 = 号不能忽略，否则 mid 取不到所有值
auto mid = left + (right - left) / ;// 把搜索范围缩小到 right = left or right = left+1，此时 mid = left
if (*mid == target)
return distance(nums.begin(), mid);
if (*mid < target)
left = mid + ;
if (*mid > target)
right = mid - ;
}
return -;
} //@ 有重复值，且返回匹配数 key 的最小下标，等同于 std::lower_bound (返回第一个大于等于 key 的迭代器)
int binSearchDupMinIndex(vector<int>& nums, int target) {
int left = ;
int right = nums.size() - ;
while (left <= right) { // 找mid 的对应值，此时 = 号不能忽略，否则 mid 取不到所有值
int mid = left + (right - left) / ;// 把搜索范围缩小到 right = left or right = left+1，此时 mid = left
if (nums[mid] < target)
left = mid + ;
else if (nums[mid] == target){ // 加以特殊处理
if (mid - >= && nums[mid - ] == target)
right = mid - ;
else
return mid;
}
else {
right = mid - ;
}
}
return -;
} //@ 有重复值，且返回匹配数 key 的最大下标，等同于std::upper_bound(返回第一个大于 key 的元素的迭代器)
int binSearchDupMaxIndex(vector<int>& nums, int target) {
int left = ;
int right = nums.size() - ;
while (left <= right) { // 找mid 的对应值，此时 = 号不能忽略，否则 mid 取不到所有值
int mid = left + (right - left) / ;// 把搜索范围缩小到 right = left or right = left+1，此时 mid = left
if (nums[mid] < target)
left = mid + ;
else if (nums[mid] == target){ // 加以特殊处理
if (mid + <= right && nums[mid + ] == target)
left = mid + ;
else
return mid;
}
else {
right = mid - ;
}
}
return -;
} // [4,5,1,2,3] 旋转数组的二分查找
// @ 无重复值
int binFind(vector<int>& nums, int target) {
int left = ;
int right = nums.size() - ;
while (left <= right) {
int mid = left + (right - left) / ;
if (nums[mid] == target)
return mid;
else if (nums[left] <= nums[mid]) { // mid in left side 递减序列
if (nums[left] <= target && target < nums[mid]) // left---target----mid
right = mid - ;
else // left---mid---target
left = mid + ;
}
else { // mid in right side 递增序列
if (nums[mid] < target && target <= nums[right]) // mid---target---right
left = mid + ;
else // target---mid---right
right = mid - ;
}
}
return -;
} // @有重复值
// 包含重复元素的数组 A = [1,3,1,1,1],当A[m] >= A[left]时，不能确定target 在left side
// 拆分成两个条件：
//（1）若：A[mid] > A[left],则区间 [left,mid] 一定递增
//（2）若 A[mid] == A[left],确定不了，那就 left++,除去此元素再进行此查找过程
int binFindDup(vector<int>& nums, int target) {
int left = ;
int right = nums.size() - ;
while (left <= right) {
int mid = left + (right - left) / ;
if (nums[mid] == target)
return mid;
else if (nums[left] < nums[mid]) { // mid in left side 递减序列
if (nums[left] <= target && target < nums[mid]) // left---target----mid
right = mid - ;
else // left---mid---target
left = mid + ;
}
else if(nums[left] > target){ // mid in right side 递增序列
if (nums[mid] < target && target <= nums[right]) // mid---target---right
left = mid + ;
else // target---mid---right
right = mid - ;
}
else { // 把这个元素除去搜索范围
//skip duplicate one
left++;
}
}
return -;
}
binSearch
9，给定一个数组a,O(n)时间求 a[j] - a[i] 的最大值？
https://blog.csdn.net/xiaofengcanyuelong/article/details/78965552
最新文章
- win7安装oracle 时容易出的问题
- 修正iOS从照相机和相册中获取的图片方向（转）
- python-基础介绍
- Linux Linux程序练习十（网络编程大文件发送）
- The life of an HTML HTTP request
- html页面布局 第8节
- HDU 5805 - NanoApe Loves Sequence （BestCoder Round #86）
- 04737_C++程序设计_第9章_运算符重载及流类库
- (转)Java多线程之Lock的使用 （待整理）
- preg_replace的一些细节
- JavaScript有这几种测试分类
- C++入门之初话多态与虚函数
- yum的使用与配置
- debug，菜鸟必备的求生技能
- 剑指offer：复杂链表的复制
- （转）stm32启动文件详解
- POJ 1840 Eqs 解方程式, 水题 难度:0
- 第39章 ETH—Lwip以太网通信
- [转载]Windows 8 VHD 概述与使用
- 到底什么时候才需要在ObjC的Block中使用weakSelf/strongSelf