其他杂七杂八的问题

分类：总结发布于：2020-07-20

快速排序

partition

int partition(vector<int>& nums, int lo, int hi){
    int v = nums[lo];
    int i = lo, j = hi;
    while(true){
        while(++i < j && nums[i] < v);
        while(nums[--j] > v);
        if(i >= j){
            break;
        }
        std::swap(nums[i], nums[j]);
    }
    std::swap(nums[lo], nums[j]);
    return j;
}

void sort(vector<int>& nums, int lo, int hi){
    if(hi - lo <= 1){
        return;
    }
    int m = partition(nums, lo, hi);
    sort(nums, lo, m);
    sort(nums, m+1, lo);
}

单向链表的快速排序

原理，使用链表头部的值作为 pivot，使用一个指针 q 指向小于等于 pivot 的节点，使用 p 从前往后遍历，遇到小于等于 pivot 的节点，就把值与 q 的下一个交换。然后 q 向后挪一个节点。遍历完成后，q 指向的节点的值一定小于等于 pivot，交换 head 和 q 的值，然后返回 q 作为 partition 的结果。

#include <utility>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

struct Node{
    int value;
    Node* next;
};

Node* partition(Node* head, Node* tail){
    if(head == tail){
        return head;
    }
    int v = head->value;
    Node* q = head;
    Node* p = head->next;
    while(p != tail){
        if(p->value <= v){
            q = q->next;
            ::swap(q->value, p->value);
        }
        p = p->next;
    }
    ::swap(q->value, head->value);

    return q;
}

void quick_sort(Node* head, Node* tail){
    if(head == tail) {
        return;
    }
    Node* mid = partition(head, tail);

    quick_sort(head, mid);
    quick_sort(mid->next, tail);
}

void quick_sort(Node* head){
    quick_sort(head, nullptr);
}


int main(){
    Node head {};
    Node* p = &head;

    vector<int> nums{7,3,7,3,4,5,7,3,5,7,3,7,4,5,7,5,11,2,8,12};
    for(int n: nums){
        p->next = new Node{.value = n, .next = nullptr};
        p = p->next;
    }
    quick_sort(head.next);

    for(p = head.next; p != nullptr; p = p->next){
        cout << p->value << ' ';
    }
    return 0;
}

荷兰旗

荷兰旗问题，三向切分，把数组分为三部分，[< pivot, = pivot, > pivot]

void partition(vector<int>& nums){
    if (nums.size() <= 1){
        return;
    }

    int pivot = nums[0];
    int small = 0, equal = 0, large = nums.size();
    while(equal < large){
        if(nums[equal] < pivot){
            swap(nums[equal++], nums[small++]);            
        }
        else if(nums[equal] == pivot){
            equal ++;
        }
        else{
            swap(nums[equal], nums[--large]);
        }
    }
}

优先队列

C++ 中 priority_queue 默认使用的是 less<> 进行比较，默认堆顶为最大的元素。

priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<>> min_pq;

greater<> 是什么情况呢？为什么没有模版参数？这也能行？greater 定义为模版类是让人们去特化的，但是很多时候，我们只是使用它的默认功能，即调用 a > b，特化与否没有所谓。针对很多类型都做特化，但内部也只是返回 a > b 这很很必要。 greater<> 其实是 greater<void>，STL 中有 void 的特化版本，其中 operator()(T a, U b) 是模版类。

因此，在某些时候不需要对 greater 指定类型，它通常和一些容器类搭配使用，其模版参数和通常就是容器中元素的类型。

归并排序

数组中的逆序对

二分查找

int lower_bound(const vector<int> &nums, int val){
    int lo = 0, hi = nums.size();
    
    while(lo < hi){
        int mid = lo + (hi - lo) / 2;
        if(nums[mid] < val){
            lo = mid + 1;
        }else{
            hi = mid;
        }
    }
    return lo;
}

int upper_bound(const vector<int> &nums, int val){
    int lo = 0, hi = nums.size();

    while(lo < hi){
        int mid = lo + (hi - lo) / 2;
        if(nums[mid] <= val){
            lo = mid + 1;
        }else{
            hi = mid;
        }
    }
    return lo;
}

字符串转浮点数

这个问题在写之前，要考虑如果字符串中存在异常该怎么办。在 C 语言的标准库里面，如果有异常输入，返回为 0。这里也按照这种方式来处理。

double atof(const char* s){
    int sign = 1;
    // 跳过开头的空格
    while(isspace(*s)){
        s++;
    }
    // 处理可能存在的正负号
    if(*s == '-'){
        sign = -1;
    }
    if(*s == '+' || *s == '-'){
        s++;
    }
    // 如果是数字，就一个劲地处理，得到整数部分
    double base = 0;
    while(isdigit(*s)){
        base = base * 10 + (*s - '0');
        s++;
    }
    if(*s == '.'){
        ++s;
    }
    double point = 0;
    int len = 0;
    // 处理小数部分，因为 double 型有效的小数只有 15~16 位，因此这里处理 20 位足够了
    while (isdigit(*s) && len < 20){
        point = point * 10 + (*s - '0');
        s++;
        len++;
    }
    // 把小数缩小，这里使用的是浮点数，不会溢出
    point /= pow(10.0, len);
    return sign * (base + point);
}

LeetCode 题解

积跬步，至千里。