套路

记录一些刷leetcode时候没想到的一些套路。

• ACM格式处理输入输出：

// 推荐使用全局变量
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            
            out.println(solution());
        }
        out.flush();
        out.close();
    }
}

• 根据数据量设计算法，$10^5$一般考虑复杂度$O(n)$，$O(nlogn)$，$10^3$一般考虑复杂度$O(n^2)$，500往一般考虑$O(n^3)$。

• 字符串相关，可以考虑使用字典或者hash set相关数据结构，设长度为27。

• 字符串子序列长度相关，滑动窗口。滑动窗口：

1. 双指针
2. 定长集合

• 状态相关，可以用几个数字代表不同状态。（二叉树摄像头问题）

• 树形dp相关，可以用数组记录递归过程中结果。（打家劫舍3）

• 循环数组相关

1. 可以拼接，擅长使用nums[i%size]和nums[(i-1+size) %size]。
2. 不考虑头尾。
3. 反复反转。
4. 总体部分减去中间部分。(环形数组求最大)

• 数组子序列有关常用递推关系式dp[i][j] = max(dp[i+1][j],dp[i][j-1])

• 数组求当前元素后更大或更小元素，可以使用单调栈减轻一个时间复杂度：

for i in range(len(nums)):
            while len(stack)>0 and nums[i] > nums[stack[-1]]:
                answer[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)

• 基于数组当前元素寻找两边比他大或者比他小的元素可以采取单调栈。数组头尾可以加0

• 一个数组根据某个规则抽取元素构成数组的数组的问题，可以考虑使用字典数据结构将相同规则的放在一个key里。

• 发糖果问题考虑正反两次遍历

• 矩阵问题

  • 数独问题用3哈希
  • 螺旋矩阵用四边界
  • 旋转矩阵，分为↖↗↙↘四块旋转
  • 生命游戏，防止别的数据污染，暂时把位置数据改为无法识别的数据。

• 数据区域固定的时候，可以考虑计数排序。

• int1维数据数组，使用位运算替代HashSet，应用：找到两个数组的公共前缀。

• 乘2用<<1替换，无符号左移，除以2用>>1替换，无符号右移。

• 质数相关问题，考虑线性筛。

// 埃筛
  private  static final int MX = 101;
  private static final boolean[] NOT_PRIME = new boolean[MX];
  static {
      NOT_PRIME[1] = true;
      for (int i = 2; i *i <MX ; i++) {
          if(NOT_PRIME[i])
              continue;
          for (int j = i * i; j <MX ; j+=i) {
              NOT_PRIME[j] = true;
          }
      }
  }
  // 欧拉筛
  private static final int MX = 101;
  private static boolean[] notPrime = new boolean[MX];
  private static int[] prime = new int[100];

  static {
      notPrime[0] = notPrime[1] = true;
      int t = 0;
      for (int i = 2; i  < MX ; i++) {
          if(!notPrime[i])
              prime[t++] = i;
          for (int j = 0; j < t && i * prime[j] < MX; j++) {
              notPrime[i * prime[j]] = true;
              if(i % prime[j] ==0)
                  break;
          }
          }
  }

• 考虑有正负的最值问题，可以考虑分别记录最大值和最小值。

• 字母大小写转换，通过^32实现。

• 最大化最小值或者最小化最大值的问题，考虑二分答案。

• 字典序问题中最大的字典序可以设置为~，最小的可以设置为空格。