昨天晚上有事情，导致都没有做题，所以计划的做题只能每次拖后一天，但是今天不能再拖了。
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个数也是第二个元素所表示的大小。
所以这就要求我们，首先要对第一个元素从大到小排列，第二个元素从小到大排列。具体见代码。
代码示例
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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个用例总是出错，问题尚待研究。
代码实现
| 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 | 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; } }; |
