目录

• [ 判断矩阵经轮转后是否一致](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;

    }
};