学习并使用C++实现算法的基础练习,每日更新
排序
快速排序
从中间的数开始查询效率最高,并且两边指针最好扩散一个位置,避免出界的情况,快速排序并不是稳定的排序。
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
if(l >= r) return;
int x = q[(l+r)/2], i = l - 1, j = r + 1;
while(i < j)
{
do i++; while (q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &q[i]);
quick_sort(q, 0, n-1);
for(int i = 0; i < n; i++) printf("%d ", q[i]);
return 0;
}
归并排序
时间复杂度$nlogn$
#include <iostream>
using namespace std;
//const修饰内置类型变量,自定义对象,成员函数,返回值,函数参数
const int N = 1e6 + 10;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
//排查数组情况
if(l > r) return;
//递归分块
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid+1, r);
//合并数组并储存在tmp中
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
//修改原数组
for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", q[i]);
merge_sort(q, 0, n-1);
for(int i = 0; i < n; i++) printf("%d ", q[i]);
}
力扣题
子数组范围和
一个整数数组nums。其中,子数组的范围是子数组中最大元素和最小元素的差值,求nums中所有子数组范围的和,子数组是数组中一个连续非空的元素序列。
注意,INT_MAX和INT_MIN别搞反了,还有long long类型的res别忘记初始化为0!
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long answer = 0;
for(int i = 0; i < n; i++){
int maxValue = INT_MIN, minValue = INT_MAX;
for(int j = i; j < n; j++){
minValue = min(minValue, nums[j]);
maxValue = max(maxValue, nums[j]);
answer += maxValue - minValue;
}
}
return answer;
}
};
剑指offer
用两个栈实现队列
用两个栈实现一个队列,实现appendTail和deleteHead两个函数,分别在队列尾部插入整数和在队列头部删除整数的功能,若队列中没有元素,deleteHead操作返回-1
示例
输入:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]
代码
//C++中的栈,pop返回的是void
class CQueue {
private: stack<int> in;
private: stack<int> out;
public:
CQueue() {
}
void appendTail(int value) {
in.push(value);
}
int deleteHead() {
if(out.empty()){
while(!in.empty()){
out.push(in.top());
in.pop();
}
}
if(out.empty())
return -1;
int head = out.top();
out.pop();
return head;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/