leetcode-406-416

leetcode 406题 416题

leetcode406题题目:

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

示例:

输入:[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var reconstructQueue = function(people) {

var result = [];
people.sort(compare);
for(var i=0;i<people.length;i++){
var index = people[i][1];
result.splice(index,0,people[i]);
}
return result;
};
function compare(a,b){
if(a[0]==b[0]){
return a[1]-b[1];
}
return b[0]-a[0];
}

leetcode416题题目:

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

注意: 每个数组中的元素不会超过 100;数组的大小不会超过 200。

示例:

示例1:

输入:[1, 5, 11, 5]

输出:true

解释:数组可以分割成 [1, 5, 5] 和 [11].

示例2:

输入:[1, 2, 3, 5]

输出:false

解释:数组不能分割成两个元素和相等的子集.

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var canPartition = function(nums) {
var sum = 0;
for(var h=0;h<nums.length;h++){
sum = sum + nums[h];
}
if(sum%2!=0){
return false;
}
var halfSum = parseInt(sum/2);
var arr = [];
for(var j=0;j<halfSum+1;j++){
arr[j] = false;
}
arr[0] = true;
for(var i=0;i<nums.length;i++){
for(var j=halfSum;j>=nums[i];j--){
arr[j] = (arr[j]||arr[j-nums[i]])?true:false;
}
}
return arr[halfSum];
};

艾丽.范宁

分享到