Acwing 4211. 序列重排

思路：
双关键字排序
关键是证明：
假设第因子2的个数为xi
因子3的个数为yi
可行解的必要条件xi < x(i + 1) || xi == x(i + 1) && yi > y(i + 1)

现证按照双关键字因子2的个数从小到大，相同时再按因子3的个数从大到小排得到的序列是唯一的，即证对任意i != j，有xi != xj || yi != yj
反证法：假设xi == xj且yi == yj
由于题目保证有解，一定满足必要条件，故当xi == xj时，yi != yj一定成立，推出矛盾，故序列是唯一的。

最终要求的解满足必要条件且满足必要条件的序列是唯一的，所以满足必要条件的解就是最终的序列。、

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         long[][] a = new long[n][3];
  8.         for (int i = 0; i < n; i++) {
  9.             a[i][0] = sc.nextLong();
  10.             a[i][1] = get2(a[i][0]);
  11.             a[i][2] = get3(a[i][0]);
  12.         }
  13.         Arrays.sort(a, (o1, o2) -> {
  14.                 if (o1[1] == o2[1])
  15.                     return o1[2] > o2[2] ? -1 : 1;
  16.                 else
  17.                     return o1[1] > o2[1] ? 1: -1;
  18.             });
  19.         for (int i = 0; i < n; i++) {
  20.             System.out.print(a[i][0] + " ");
  21.         }
  22.     }
  24.     static long get2(long x) {
  25.         long cnt = 0;
  26.         while (x % 2 == 0) {
  27.             cnt++;
  28.             x /= 2;
  29.         }
  30.         return cnt;
  31.     }
  32.     static long get3(long x) {
  33.         long cnt = 0;
  34.         while (x % 3 == 0) {
  35.             cnt++;
  36.             x /= 3;
  37.         }
  38.         return cnt;
  39.     }
  40. }

AcWing 1211. 蚂蚁感冒

思路: 关键是将掉头看作”穿过”, 然后分情况讨论即可

Acwing 3474. 坠落的蚂蚁

类似于Acwing 1211蚂蚁感冒

777. 在LR字符串中交换相邻字符

在一个由 ‘L’ , ‘R’ 和 ‘X’ 三个字符组成的字符串（例如”RXXLRXRXL”）中进行移动操作。一次移动操作指用一个”LX”替换一个”XL”，或者用一个”XR”替换一个”RX”。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

示例 :
输入: start = “RXXLRXRXL”, end = “XRLXXRRLX”
输出: True
解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

提示：
1 <= len(start) = len(end) <= 10000。
start和end中的字符串仅限于’L’, ‘R’和’X’。

思路：
R和L看成人，X看作空，R只能向右，L只能向左，且LR不能交换位置
故可用双指针解决
具体做法是：从左往右按序找到start和end中每一个不为X的字符c1, c2
若c1 !=c2，返回false
若c1 == c2 == R && pos[c1] > pos[c2]或c1 == c2 == L && pos[c1] < pos[c2]，返回false

932. 漂亮数组

思路：分奇偶，递归处理，太难想到了

AcWing 1453. 移掉K位数字

思路：
贪心，利用栈的单调性

联-04. 合作开发

为了不断提高用户使用的体验，开发团队正在对产品进行全方位的开发和优化。
已知开发团队共有若干名成员，skills[i] 表示第 i 名开发人员掌握技能列表。如果两名成员各自拥有至少一门对方未拥有的技能，则这两名成员可以「合作开发」。
请返回当前有多少对开发成员满足「合作开发」的条件。由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。
注意：

  • 对于任意 skills[i] 均升序排列。

示例 1：
输入：
skills = [[1,2,3],[3],[2,4]]
输出: 2
解释：
开发成员 [1,2,3] 和成员 [2,4] 满足「合作开发」的条件，技能 1 和 4 分别是对方未拥有的技术
开发成员 [3] 和成员 [2,4] 满足「合作开发」的条件，技能 3 和 4 分别是对方未拥有的技术
开发成员 [1,2,3] 和成员 [3] 不满足「合作开发」的条件，由于开发成员 [3] 没有对方未拥有的技术
因此有 2 对开发成员满足「合作开发」的条件。
示例 2：
输入：
skills = [[3],[6]]
输出: 1
解释：
开发成员 [3] 和成员 [6] 满足「合作开发」的条件
因此有 1 对开发成员满足「合作开发」的条件。
提示：

  • 2 <= skills.length <= 10^5
  • 1 <= skills[i].length <= 4
  • 1 <= skills[i][j] <= 1000
  • skills[i] 中不包含重复元素

思路：
正向思考考虑可以合作的成员对数量很困难，可以考虑反向思考，计算不能合作的成员对数量。
对成员按照其拥有的技能个数从大到小排序，从前往后累加每个成员技能的所有子集的个数(使用哈希)，如果当前成员x拥有的所有技能是前面某些成员y的子集，说明该成员不能与y合作。

  1. class Solution {
  2.     public int coopDevelop(int[][] skills) {
  3.         int mod = (int)(1e9 + 7), N = 1010;
  4.         int n = skills.length;
  5.         Map<Long, Integer> map = new HashMap<>();
  7.         Arrays.sort(skills, (o1, o2) -> (o2.length - o1.length));
  8.         long res = 0;
  10.         for (int[] p : skills) {
  11.             int m = p.length;
  12.             long s = 0;
  13.             for (int x : p) {
  14.                 s = s << 10 | x; 
  15.             }
  16.             res += map.getOrDefault(s, 0);
  18.             for (int i = 1; i < 1 << m; i++) {
  19.                 long v = 0;
  20.                 for (int j = 0; j < m; j++) {
  21.                     if ((i >> j & 1) == 1)
  22.                         v = v << 10 | p[j];
  23.                 }
  24.                 map.merge(v, 1, Integer::sum);
  25.             }
  26.         }
  27.         res = 1L * n * (n - 1) / 2 - res;
  28.         return (int)(res % mod);
  29.     }
  30. }

:::tips 本题的哈希比较巧妙，考虑到每个成员最多拥有4个技能，每个技能的编号范围是[1, 1000]，故可以考虑对每个技能采用10位二进制位存储，采用一个long型整数即可唯一标识一组技能集(题目已说技能从小到大排好序) :::

1072. 按列翻转得到最大值等行数

思路：
通过反转某些列得到全0或全1的那些行在翻转前也相同或互补
用哈希表将行分类
一个trick是将每一行的元素与每一行的行首元素异或后再加到字符串中。

AcWing 2049. 奶牛摄影

自定义排序，确定任意两头奶牛的相对位置

581. 最短无序连续子数组

如何一次遍历确定边界！

128. 最长连续序列

巧妙使用哈希表