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

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;}};