单链表快速排序

思路：

和普通快排一样，递归实现遍历。递归的每一层都遍历一遍当前的链表，将链表按照节点值分成三部分：等于枢轴值、小于枢轴值和大于枢轴值。递归排序后，将三段链表进行拼接。

时空复杂度：

平均时间复杂度为 O(nlogn)，额外空间复杂度为 O(logn)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    //返回指向当前链表的尾节点指针
    ListNode* get(ListNode* head)
    {
        while(head->next) head = head->next;
        return head;
    }
    ListNode* quickSortList(ListNode* head) {
        if(!head || !head->next) return head;//头结点为空或当前只有头结点
        ListNode *s = new ListNode(-1), *e = new ListNode(-1), *l = new ListNode(-1);
        ListNode *st = s, *et = e, *lt = l;//尾指针，一直指向最后一个节点
        int v = head->val;//枢轴值
        for(auto iter = head; iter != nullptr; iter = iter->next)
        {
            if(iter->val < v) st = st->next = iter;//当前iter接到当前st后，再将st指向新末尾
            else if(iter->val == v) et = et->next = iter;
            else lt = lt->next = iter;
        }
        st->next = et->next = lt->next = nullptr;//因为原节点指针是指向下一节点的，被取出后最后一个节点应指向空
        s->next = quickSortList(s->next);
        l->next = quickSortList(l->next);
        get(s)->next = e->next;
        get(s)->next = l->next;//防止某一个为空
        auto res = s->next;
        delete s, e, l;
        return res;
    }
};

LeetCode365.水壶问题

这题我只会数学解法，太菜了😭

其实第一眼没有思路，瞄了一眼标签是“数学”，就开始推公式
假设容量为x升的水壶进行了a次操作，容量为y升的水壶进行了b次操作，最终两水壶中的水总共是z升。可以得到公式：

emm，好眼熟的公式，好像是斐蜀定理。。。

斐蜀定理

对于任意正整数a，b，那么一定存在非零整数x，y，使得$a \times x + b \times y = gcd(a,\ b)$

再扩展一下，对于这道题的方程$a \times x + b \times y = z，$
当且仅当$z\ |\ gcd(x,\ y)$时该二元不定方程才有整数解。因此这道题就可以解决了。
也就意味着当$x \ + \ y \ge \ z$时应满足：$z \ mod\ gcd(x,\ y)=0$，OK了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool canMeasureWater(int x, int y, int z) {
    if(!x || !y)
    {
        if(x == z || y == z) return true;
        else return false;
    }
        if(x + y < z) return false;
        return !(z % gcd(x, y));
}

好像还有BFS的解法，打算再看一下。

LeetCode面试题40.最小的k个数

三种实现方法：

快速排序：

1 2 3 4 5 6 7 8 9 10 11 12

void quick_sort(int l, int r, vector<int>& arr) { if(l >= r) return; int i = l - 1, j = r + 1, mid = arr[l + r >> 1]; while(i < j) { do i++; while(arr[i] < mid); do j--; while(arr[j] > mid); if(i < j) swap(arr[i], arr[j]); } quick_sort(l, j, arr), quick_sort(j + 1, r, arr); }

归并排序：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void merge_sort(int l, int r, vector<int>& arr, vector<int>& temp) { if(l >= r) return; int mid = l + r >> 1, i = l, j = mid + 1, k = 0; merge_sort(i, mid, arr, temp), merge_sort(j, r, arr, temp); while(i <= mid && j <= r) { if(arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while(i <= mid) temp[k++] = arr[i++]; while(j <= r) temp[k++] = arr[j++]; for(int i = l, k = 0; i <= r; i++, k++) arr[i] = temp[k]; }

然鹅。。。以上两种方法都太菜了😳
最终解决方法：

1	sort(arr.begin(), arr.end());

Over！😂

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment