leetcode-215-221

leetcode215题221题:

leetcode215题(数组中的第K个最大元素):

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例:

输入:[3,2,1,5,6,4]和k=6

输出:5

输入:[3,2,3,1,2,4,5,5,6]和k=4

输出:4

解答:
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
var findKthLargest = function(nums, k) {
return kth(nums,0,nums.length-1,k);
function kth(nums,left,right,k){
var start = left;
var end = right;
var key = nums[start];//表示以第一个元素为参考值
while(start<end){
while(start<end&&nums[end]<=key){
end--;
}
nums[start]=nums[end];//当出现不小于key的nums[end]时,将其赋值给nums[start]
while(start<end&&nums[start]>=key){
start++;
}
nums[end]=nums[start];//当出现大于key的nums[start]时,将其赋值给nums[end]
}
if(start==k-1){
return key;
}
if(start<k-1){
return kth(nums,start+1,right,k);
}
return kth(nums,left,start-1,k);
}
};

leetcode221题(最大正方形):

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例:

示例

解答:

dp[i][j]代表以 i,j为正方形右下角的最大边长是多少

动态方程:

在 matrix[i][j] == “1”,情况下

​ dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var maximalSquare = function(matrix) {
if(matrix.length==0){
return 0;
}
var max = 0;
var dp = [];
for(var i=0;i<=matrix.length;i++){
dp[i] = [];
for(var j=0;j<=matrix[0].length;j++){
dp[i][j]=0;
}
}
for(var i=1;i<=matrix.length;i++){
for(var j=1;j<=matrix[0].length;j++){
if(matrix[i-1][j-1]==1){
dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1;
max = Math.max(max,dp[i][j]*dp[i][j]);
}
}
}
return max;
};
分享到