学习并使用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中所有子数组范围的和，子数组是数组中一个连续非空的元素序列。

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();
 */