leetcode hard题目整理(#^.^#)(4、1220、410、85、149,363)
4 寻找两个有序数组的中位数
题目描述: 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
思路: 将题目转换为寻找两个数组合并后的第k大的元素(数组有序),k为(n +1) / 2
或者分别为n / 2
以及n / 2 + 1
。递归改变k的大小。每次取两个数组中的k/2位置的数(当较小长度的数组不足k/2的长度时,取该数组的最后一个数,则另一个数组取k - pos1
的位置的数),并比较大小,较小的数最大可能为第k - 1大的数,则删掉该位置前的所有数(移动st),并更新k值,重复迭代,直到k为1。
class Solution {
public:
double findKthNum(vector<int>&nums1, vector<int>& nums2, int st1, int st2, int n1, int n2, int k) {
if(n1 == 0)
return nums2[st2 + k - 1];
if(n2 == 0)
return nums1[st1 + k - 1];
if(k == 1)
return min(nums1[st1], nums2[st2]);
int pos1, pos2;
if(n1 <= n2) {
pos1 = min(k / 2, n1);
pos2 = k - pos1;
}
else {
pos2 = min(k / 2, n2);
pos1 = k - pos2;
}
if(nums1[st1 + pos1 - 1] < nums2[st2 + pos2 - 1])
return findKthNum(nums1, nums2, st1 + pos1, st2, n1 - pos1, n2, k - pos1);
return findKthNum(nums1, nums2, st1, st2 + pos2, n1, n2 - pos2, k - pos2);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
if((n1 + n2) % 2 == 1)
return findKthNum(nums1, nums2, 0, 0, n1, n2, (n1 + n2 + 1) / 2);
int a = findKthNum(nums1, nums2, 0, 0, n1, n2, (n1 + n2) / 2);
int b = findKthNum(nums1, nums2, 0, 0, n1, n2, (n1 + n2) / 2 + 1);
return 1.0 * (a + b) / 2;
}
};
1220 统计元音字母序列的数目
**题目描述:**给你一个整数 n,请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串:
字符串中的每个字符都应当是小写元音字母(‘a’, ‘e’, ‘i’, ‘o’, ‘u’)
每个元音 ‘a’ 后面都只能跟着 ‘e’
每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’
每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’
每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’
每个元音 ‘u’ 后面只能跟着 ‘a’
由于答案可能会很大,所以请你返回 模 10^9 + 7 之后的结果。
思路: 二维动态规划。保存每一位每个字母出现频率。
class Solution {
public:
int countVowelPermutation(int n) {
int MOD = 1e9 + 7;
int ans = 0;
vector<vector<long long>> dp(2, vector<long long>(5, 0));
for(int i= 0; i < 5; i++) {
dp[0][i] = 1;
}
for(int i = 1; i < n; i++) {
if(i % 2 == 0) {
dp[0][0] = (dp[1][1] + dp[1][2] + dp[1][4]) % MOD;
dp[0][1] = (dp[1][0] + dp[1][2]) % MOD;
dp[0][2] = (dp[1][1] + dp[1][3]) % MOD;
dp[0][3] = dp[1][2] % MOD;
dp[0][4] = (dp[1][2] + dp[1][3]) % MOD;
}
else {
dp[1][0] = (dp[0][1] + dp[0][2] + dp[0][4]) % MOD;
dp[1][1] = (dp[0][0] + dp[0][2]) % MOD;
dp[1][2] = (dp[0][1] + dp[0][3]) % MOD;
dp[1][3] = dp[0][2] % MOD;
dp[1][4] = (dp[0][2] + dp[0][3]) % MOD;
}
}
if((n - 1) % 2 == 0)
return (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3] + dp[0][4]) % MOD;
return (dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4]) % MOD;
}
};
410 分割数组的最大值
**题目描述:**给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
数组长度 n 满足以下条件:1 ≤ n ≤ 1000;1 ≤ m ≤ min(50, n)
思路: 二分子数组的最小最大值,子数组和的范围为原数组中最大值到原数组所有数的和之间。利用二分出的mid值计算能将原数组分成多少个子数组,并将该值与m进行比较,调整二分答案。
class Solution {
public:
int hhh(vector<int>& nums, long long mid) {
long long sum = 0;
int cnt = 1;
for(int i = 0; i < nums.size(); i++) {
if(sum + nums[i] > mid) {
sum = nums[i];
cnt++;
}
else
sum += nums[i];
}
return cnt;
}
int splitArray(vector<int>& nums, int m) {
long long sum = 0, max_num = 0;
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
max_num = max(max_num, (long long)nums[i]);
}
// 二分最大值
long long ans = 0;
long long low = max_num, high = sum, mid = 0;
while(low <= high) {
mid = (low + high) / 2;
// cout<<mid<<" "<<hhh(nums, mid)<<endl;
if(hhh(nums, mid) <= m) {
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return int(ans);
}
};
85 最大矩形
题目描述: 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
思路: 初始化一个与原矩阵大小相同的二维数组,先计算给定矩阵中每一行的前缀和。三层循环分别遍历矩形的左条边,右条边,以及横边。若两条竖边之间和与长度值相等,则将其加入到tmp_ans中,并更新ans值,若不相等,则将tmp_ans清零。
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0)
return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(j == 0)
dp[i][j] = matrix[i][0] - '0';
else
dp[i][j] = dp[i][j - 1] + matrix[i][j] - '0';
}
}
int ans = 0;
for(int col1 = 0; col1 < n; col1 ++) {
for(int col2 = col1; col2 < n; col2 ++) {
int tmp_ans = 0;
int dis = col2 - col1 + 1;
for(int row = 0; row < m; row++) {
int sum = 0;
if(col1 - 1 >= 0)
sum = dp[row][col2] - dp[row][col1 - 1];
else
sum = dp[row][col2];
if(sum == dis) {
tmp_ans += sum;
ans = max(ans, tmp_ans);
}
else
tmp_ans = 0;
}
}
}
return ans;
}
};
149 直线上最多的点数
题目描述: 给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
思路: 枚举。两次遍历所给的n个点,根据两点确定一条直线,用哈希表存储在同一条直线(斜率相同)的点的个数,不断更新最大值并返回。使用斜率会产生误差,不能得到正确答案,将其转化一下。 求两点的横坐标之差以及纵坐标之差,求其最大公约数,并用最大公约数约分,如果两点斜率相同,则约分后的结果相同。0与任何数的最大公约数为另一个非0数。 最终哈希表中的key值以x * 1e9 + y
形式保存。
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
unordered_map<long long, int> mp;
int ans = 0;
for(int i = 0; i < points.size(); i++) {
mp.clear();
int same_cnt = 0, tmp_ans = 0;
for(int j = 0; j < points.size(); j++) {
if(points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
same_cnt++;
continue;
}
int gcd = __gcd(points[i][0] - points[j][0], points[i][1] - points[j][1]);
int x = (points[i][0] - points[j][0]) / gcd;
int y = (points[i][1] - points[j][1]) / gcd;
mp[1LL * x * 1e9 + y]++;
tmp_ans = max(tmp_ans, mp[1LL * x * 1e9 + y]);
}
ans = max(tmp_ans + same_cnt, ans);
}
return ans;
}
};
363 矩形区域不超过 K 的最大数值和
题目描述: 给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不大于 k 的最大矩形和。
思路: 思路同85题。不同点: 确定矩形区域左右两边范围后,以第一行为上边,遍历每一条边为下边,将所围成的矩形面积放入set中排序,根据pre_sum1 - pre_sum2 >= k
可得pre_sum1 - k >= pre_sum2
。即,要求不超过K的最大矩形面积,则求满足pre_sum1 - k >= pre_sum2
条件的最小pre_sum2(利用lower_bound()函数)。不断更新ans值。
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int row = 0; row < m; row++) {
for(int col = 0; col < n; col++) {
if(col == 0)
dp[row][col] = matrix[row][col];
else
dp[row][col] += dp[row][col - 1] + matrix[row][col];
}
}
int ans = -1e9;
set<int> s;
for(int col1 = 0; col1 < n; col1++){
for(int col2 = col1; col2 < n; col2++) {
int pre_sum = 0;
s.clear();
s.insert(0);
for(int row = 0; row < m; row++) {
if(col1 - 1 >= 0)
pre_sum += dp[row][col2] - dp[row][col1 - 1];
else
pre_sum += dp[row][col2];
auto it = s.lower_bound(pre_sum - k);
if(it != s.end())
ans = max(ans, pre_sum - (*it));
s.insert(pre_sum);
}
}
}
return ans;
}
};