Пространственная эффективность

1. Использование битов для хранения большего количества информации

& операция получает значение определённого бита в x

• x&1 получает последний бит;
• x>>1 сдвигает вправо на один бит.

• Игра «Жизнь».

2. Использование одного и того же массива для записи текущего состояния

• Рекурсивный обход с возвратом, требующий постоянного добавления и удаления элементов из текущего массива состояний (ссылка: https://leetcode-cn.com/submissions/detail/61185405/).

Временная эффективность

1. Обход соседних данных с использованием двух массивов для обхода

    private static final int[] DX = {0, 0, 1, -1, 1, 1, -1, -1};
    private static final int[] DY = {1, -1, 0, 0, 1, -1, 1, -1};

Типы задач и соответствующие решения

• 78. Подмножества

  Задача поиска всех подмножеств множества, которая хорошо решается с помощью двоичных битов.

  public static List<List<Integer>> binaryBit(int[] nums) {
      List<List<Integer>> res = new ArrayList<List<Integer>>();
      /*
          Количество подмножеств четырёх чисел
          == количество двоичных чисел от 0 до 1111
          == число, представленное 10000
      */
      for (int i = 0; i < (1 << nums.length); i++) {
          List<Integer> sub = new ArrayList<Integer>();
          // Перебираем каждое число, где двоичный бит равен 1 означает, что число выбрано, и записываем его
          for (int j = 0; j < nums.length; j++)
              if (((i >> j) & 1) == 1) sub.add(nums[j]);
          res.add(sub);
      }
      return res;
  }

• 15. Три суммы

  Подходящий метод трёх указателей, фиксируя одну позицию и выполняя обрезку ветвей при обходе остальных.

Основы Java

1. Сортировка массива int

   Arrays.sort(nums)

2. Преобразование String в массив символов

   new ArrayList<>(Arrays.asList("abc".split("")))

3. Преобразование массива int в список

   List list = Arrays.stream(nums).boxed().collect(Collectors.toList());

4. Накопление значений в hashmap

   Если ключ не существует, установить значение 1; если ключ существует, добавить значение к существующему значению.

   map.merge("key", 1, (oldValue, newValue) -> oldValue + newValue);

5. Если ключ hashMap является списком, а значения совпадают, то это один и тот же список.