Neo's Blog

//快速排序算法模板
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + 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);
}

下面这道题目是基于快排思想的TopK，他们的partion逻辑不太一样，其中一个很重要的点在于：
quickselect要求把输入分成了三部分，[<=X] X [>X]；
而上面的quicksort只是把输入分成了两部分，[<X],[>=X]或者[<=X], [>X]
分割点在某一区间内，但是不一定在区间的两端；

```cpp
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        qselect(input, 0, input.size() - 1, k);
        vector<int> res(k);
        for (int i = 0; i < k; ++i) {
            res[i] = input[i];
        }
        return res;
    }

    void qselect(vector<int>& q, int l, int r, int k) {
        if (l >= r) return;
        
        int i = l, j = r, x = q[l];
        while (i < j) {
            while(i < j && q[j] > x) j--; //优先从j开始
            q[i] = q[j];
            while (i < j && q[i] < x) i++;  //注意<=，而不能是<
            q[j] = q[i]
        }  
        a[i] = x;

        //qselect(q, l, j, k);
        //qselect(q, j + 1, r, k);
        
        if (i - l + 1 == k ) return;
        else if (i - l + 1 < k) qselect(q, j + 1, r, k - (i - l + 1)); 
        else  qselect(q, l, j - 1, k);
    }
};

void quick_sort_3part(int q[], int l, int r) {
    if (l >= r) return;
    
    swap(q[l], q[l + rand() % (r - l + 1)]); //随机化
    int lt = l, gt = r, i = l + 1, x = q[l];
    // 6,4,1,3,6,6,6,6,4,3,10,45,32
    // |     |       |     |
    // l    lt      i     gt
    // 三路快排，确定等于主元pivot的左右边界
    while (i <= gt) {
        if (q[i] < x) swap(q[i++], q[++lt]);  //gt左边的元素都比x大，但是gt指向的不一定大
        else if (q[i] > x) swap(q[i], q[gt--]);//把比x大的元素，换到后面了；但换回来的元素不一定“满足条件”，所以i不能变，需要再比较一次！
        else i++;// 等于主元，则继续
    }
    swap(q[l], q[lt]);

    quick_sort_3part(q, l, lt - 1);
    quick_sort_3part(q, gt + 1, r);
}

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        //正向遍历一次，满足了中间大于左边时的要求；
        vector<int> s(arr.size(), 1);
        for (int i = 1;i < arr.size(); i++){
            if (arr[i] > arr[i - 1]) {
                s[i] = s[i - 1] + 1;
            }
        }

        //逆向遍历一遍，继续满足中间大于右边时的要求
        for (int i = arr.size() - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1] && s[i] <= s[i + 1]) {
                s[i] = s[i + 1] + 1;
            }
        }

        int res = 0;
        for (auto x : s) {
            res += x;
        }

        return res;
    }
};

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* pre = new ListNode(-100000);
        ListNode* nHead = pre, *tail = pre;
        int preCnt = 2;
        while (head) {
            if (head->val == pre->val) { //如果当前元素 与 前一个元素；
                preCnt++;
            } else {
                if (preCnt == 1) { //如果前面的元素出现一次
                    tail->next = pre;
                    tail = pre;
                    tail->next = NULL;   
                } 
                pre = head;
                preCnt = 1;
            }
            head = head->next;
        }

        if (preCnt == 1) {
            tail->next = pre;
            pre->next = NULL;
        }

        return nHead->next;
    }
};

class Solution {
public:
    int res;
    int Nqueen(int n) {
        res = 0;
        dfs(0, n, 0, 0, 0);
        return res;
    }

    void dfs(int u, int n, int col, int pie, int na) {
        if (u == n) {
            res++;
            return;
        }

        for (int j = 0; j < n; ++j) {
            //用位运算来记录状态
            //注意对角线的技巧
            //左上 y = x + b;  b = (y - x + N) 来表现一条线！！
            //右下 y = -x + b; b = (y + x) 来表现一条线！！
            if ((col & 1 << j) || (pie & (1 << (n + u - j))) || (na & (1 << (u + j))))
                continue;
            //col，pie，na都是局部变量，不用保存现场
            dfs(u + 1, n, col | (1 << j), pie | (1 << (n + u - j)), na  | (1 << (u + j)));
        }
    }
};

//归并排序算法模板
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);

    vector<int> tmp(r -l + 1);
    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, k = 0; i <= r; i++, k++) q[i] = tmp[k];
}