昨天晚上有事情，导致都没有做题，所以计划的做题只能每次拖后一天，但是今天不能再拖了。

Leetcode 406：根据身高重建队列

题目描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

其实这道题我看到之后，第一想到的就是排序，当然怎么排序还是一个问题。后来经过思考之后我想到在排完序之后我可以这样做：根据第2个元素的大小，插入相应的位置，这样，只要我先插入的是第一个元素大的item，后续有item插入同一位置的时候，就可以保证第一个元素小的item前面比它小的item个数是第二个元素大小，第一个元素大的item前面比它小的item个数也是第二个元素所表示的大小。

所以这就要求我们，首先要对第一个元素从大到小排列，第二个元素从小到大排列。具体见代码。

代码示例

    static bool cmp(vector<int> a,vector<int> b)
    {
        if(a[0]>b[0])
            return true;
        if (a[0] == b[0] && a[1] < b[1])
            return true;
        return false;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>>result;
        for(auto p:people)
        {
            result.insert(result.begin()+p[1],p);
        }
        return result;
    }

代码性能

排序复杂度：O(nlogn)
插入复杂度 O(n^2)
总的来说复杂度O(n^2)

Leetcode 416：分割等和子集

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200

示例

示例1：
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11]。

示例2：
输入：[1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

解题思路

其实这个题是Leetcode494的简化版本。首先我们可以把本题的题意重写为下面这段话，意思不变：

给定一个非负整数数组，a1, a2, …, an,。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回是否可以使最终数组和为目标数 0 。

由于目标数是0，实际上这个数组所有元素之和sum应该是我们所认为的和的两倍，所以如果sum为奇数，则直接返回false，其它参考494来做即可。

但是目前在leetcode上第74个用例总是出错，问题尚待研究。

代码实现

    bool canPartition(vector<int>& nums) {
    if (nums.empty())
        return false;
    int sum = 0;
    for (auto n : nums)
    {
        sum += n;
    }
    cout << sum << endl;
    if (sum % 2 == 1)
        return false;
    sum /= 2;
    vector<int> dp(sum + 1, INT_MIN);
    dp[0] = 0;
    for (int i = 0; i < nums.size(); i++) {
        int n = nums[i];
        for (int j = sum; j >= n; j--)
        {
            dp[j] = max(dp[j], dp[j - n] + n);
            if (dp[j] < 0)
                dp[j] = INT_MIN;
        }
    }
    return dp.back()==sum;

}
};