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

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个数也是第二个元素所表示的大小。

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

代码示例

代码性能

排序复杂度：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个用例总是出错，问题尚待研究。

代码实现