学习并使用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();
 */
Last modification:March 4th, 2022 at 10:23 pm
如果觉得我的文章对你有用,请随意赞赏
END
本文作者:
文章标题:C++实现的基础算法练习
本文地址:http://feiqiuz.com/index.php/archives/18/
版权说明:若无注明,本文皆MixZou的小窝原创,转载请保留文章出处。