前言

但是就没办法，平时也没啥理由整天刷题，真到了要面试的时候手感没了还就是得刷leetcode找手感。
就不像以前搞OI的时候每天就只管刷题，手感如何都不会丢。
所以我还在刷leetcode。我的老天爷，想想现在找工作要刷leetcode，以后万一想跳槽了还得刷leetcode。
可能哪一天互联网泡沫破灭了我回家开奶茶店了就不用刷leetcode了。
leetcode我（哔————）

正文

322. 零钱兑换

简单DP。因为amount的范围很小所以直接开数组就行了。
注意最后判断无解。答案最大是amount（若干个面值为1的拼起来），所以只要把INF设置为大于amount的值就行了。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int f[10010], n = coins.size();
        memset(f, 127, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= amount; i ++)
            for (int j = 0; j < n; j ++)
                if (coins[j] <= i)
                    f[i] = min(f[i], f[i - coins[j]] + 1);
        if (f[amount] <= amount)
            return f[amount];
        else return -1;
    }
};

324. 摆动排序

首先有一个结论：有解的数组必定可以分成“较大”和“较小”两部分，满足“较大”部分的最小数大于等于“较小”部分的最大数，且两部分的数字个数最多相差1。
证明这个结论很简单。首先构造一个初始序列：因为一定有解，所以把解的偶数位置上的数字放一堆，奇数位置的放一堆。
显然奇数部分是“较小”的，偶数部分是“较大”的。
如果这样的两个序列不满足要求，那么“较大”那部分的最小数肯定小于“较小”那部分的最大数。这两个数交换一下位置，两个部分数字的个数没变。重复这种操作最后一定能满足要求。
所以只要把这两部分分开就可以了。

能O(n)时间做出来的关键就在于数组里每个数字不大于5000。这样就可以用桶排序的思路做。
我的做法用了O(n)的额外空间。基本思路就是先桶排序，然后把较大的一半放在奇数位，较小的一半放在偶数位。
具体实现里面我首先让奇数位的序列递增，偶数位的序列递减。但这样做出来最后可能有相等的相邻数字（比如样例2）
所以最后再扫一遍把偶数位的序列倒过来就可以了。

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int cnt[50010], mx = 0, n = nums.size();
        for (int i = 0; i < n; i ++) {
            cnt[nums[i]] ++;
            mx = max(mx, nums[i]);
        }
        int p1 = 0, p2 = mx;
        nums.clear();
        while (p1 <= p2) {
            while (p1 <= p2 && cnt[p1] == 0) p1 ++;
            while (p1 <= p2 && cnt[p2] == 0) p2 --;
            if (p1 > p2) break;
            if (cnt[p1] > 0) {
                nums.push_back(p1); cnt[p1] --;
            }
            if (cnt[p2] > 0) {
                nums.push_back(p2); cnt[p2] --;
            }
        }
        p1 = 0; p2 = n - 1;
        if (p2 & 1) p2 --;
        while (p1 <= p2) {
            swap(nums[p1], nums[p2]);
            p1 += 2; p2 -= 2;
        }
    }
};