目录
- [ 判断矩阵经轮转后是否一致](https://leetcode-cn.com/problems/determine-whether-matrix-can-be-obtained-by-rotation/)
- 使二进制字符串字符交替的最少反转次数
- 装包裹的最小浪费空间
判断矩阵经轮转后是否一致
给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false
主要考查数组的翻转,直接新建一个数组,将行翻转为列即可
代码如下
class Solution {
public:
vector<vector<int>> rotate(vector<vector<int>> a) {
auto b = a;
int n = a.size();
for (int i = 0; i < n; i ++ )
for (int j = 0, k = n - 1; j < n; j ++, k -- )
b[i][j] = a[k][i];
return b;
}
bool findRotation(vector<vector<int>>& a, vector<vector<int>>& b) {
for (int i = 0; i < 4; i ++ ) {
a = rotate(a);//每次在原来的基础上进行翻转
if (a == b) return true;
}
return false;
}
};
使二进制字符串字符交替的最少反转次数
给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：
- 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
- 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 ‘0’ ，则反转得到 ‘1’ ，反之亦然。
请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。
我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。
比方说，字符串 “010” 和 “1010” 都是交替的，但是字符串 “0100” 不是。
思路,前后缀分离
分两种情况,
如果n是偶数,可以得知,方式一无任何用处,因为如果是偶数,只有两种情况1010..or 0101..这两种情况再怎么去头加尾也不会改变性质
如果n是奇数,可以在四种情况的基础上用方式一变成交替串
- 10101,
1,0交替出现 - 01010
- 10110 左边
1打头,右边0结尾,中间有两个1 - 01001 左边
0打头,右边1结尾,中间有两个0
所以可以定义一种状态,使得前后分开来计算l[0][j]一> 左边以0开头,前j个字符变成01串所使用方式二的次数r[0][j]一> 右边以0开头,从[j ~ n-1]这些字符变成01串所用步数
还有l[1][j],r[1][j]
代码如下
class Solution {
public:
vector<int> l[2],r[2];
int minFlips(string s) {
int n = s.size();
l[0] = l[1] = r[0] = r[1] = vector<int> (n);
for(int i = 0; i < 2; i ++)
for(int j = 0,c = 0, k = i; j < n; j ++, k ^= 1)
{
if(s[j] - '0' != k)c ++;//注意k的含义,k每次都会变化
l[i][j] = c;
}
for(int i = 0; i < 2; i ++)
for(int j = n - 1, c = 0, k = i; j >= 0; j --, k ^= 1)
{
if(s[j] - '0' != k)c ++;
r[i][j] = c;
}
if(n % 2)//n是奇数
{
int res = min(l[0][n-1], l[1][n-1]);
for(int i = 0; i + 1 < n ; i ++)
{
res = min(res, l[1][i] + r[0][i + 1]);
res = min(res, l[0][i] + r[1][i + 1]);
}
return res;
}
return min(l[0][n-1], l[1][n-1]);
}
};
装包裹的最小浪费空间
给你 n 个包裹，你需要把它们装在箱子里，每个箱子装一个包裹。总共有 m 个供应商提供 不同尺寸 的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸 小于等于 一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。
包裹的尺寸用一个整数数组 packages 表示，其中 packages[i] 是第 i 个包裹的尺寸。供应商用二维数组 boxes 表示，其中 boxes[j] 是第 j 个供应商提供的所有箱子尺寸的数组。
你想要选择 一个供应商 并只使用该供应商提供的箱子，使得 总浪费空间最小 。对于每个装了包裹的箱子，我们定义 浪费的 空间等于 箱子的尺寸 - 包裹的尺寸 。总浪费空间 为 所有 箱子中浪费空间的总和。
- 比方说，如果你想要用尺寸数组为 [4,8] 的箱子装下尺寸为 [2,3,5] 的包裹，你可以将尺寸为 2 和 3 的两个包裹装入两个尺寸为 4 的箱子中，同时把尺寸为 5 的包裹装入尺寸为 8 的箱子中。总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。
请你选择 最优 箱子供应商，使得 总浪费空间最小 。如果 无法 将所有包裹放入箱子中，请你返回 -1 。由于答案可能会 很大 ，请返回它对 109 + 7 取余 的结果。
思路
这题如果暴力写的话复杂度为n * n * logn主要在于排序
如果反向思维,将所有的商家看作主键,对于每一个箱子,可以装的最大的包裹的下标为多少,然后(pos - last) * x - sum(pos ~ last)即可
这里只需排序完之后遍历一遍即可
typedef long long LL;
const LL MOD = 1e9 + 7, INF = 1e18;
class Solution {
public:
int minWastedSpace(vector<int>& p, vector<vector<int>>& bs) {
sort(p.begin(), p.end());
int n = p.size();
LL sum = accumulate(p.begin(), p.end(), 0ll);
LL res = INF;
for(auto b : bs)
{
sort(b.begin(), b.end());
if(b.back() < p.back())continue;
LL t = -sum;
int last = -1;
for(auto x : b)
{
int l = last, r = n - 1;//找到最后一个小于等于x的数的下标
while(l < r)
{
int mid = (l + r + 1) /2 ;
if(p[mid] <= x) l = mid;
else r = mid - 1;
}
if(r == last)continue;
t += (LL)(r - last) * x;
last = r;
}
res = min(res, t);
}
if(res == INF) res = -1;
return res % MOD;
}
};