Алгоритмы

В Java пустой объект String занимает:
заголовок объекта (8 байт) + ссылка (4 байта) + массив char (16 байт) + 1 int (4 байта) + 1 long (8 байт) = 40 байт.
```Формула для вычисления занимаемой памяти объектом String: 40 + 2 * n, где n — длина строки.

### Задача

Дан массив последовательности. У вас есть возможность перевернуть элементы в любом диапазоне массива один раз (переворот необязателен). Найдите максимальный подмассив с максимальной суммой.
Например, дан массив `[1, 3, 5, -10, 10]`, переворот `[-10, 10]` даст массив `[1, 3, 5, 10, -10]`, максимальная сумма подмассива будет `[1, 3, 5, 10]`.

### Решение задачи

Используется динамическое программирование. Формула для нахождения максимальной суммы подмассива:

`dpMax[i] = Math.max(dpMax[i - 1] + arr[i], arr[i])`

Записывается текущая максимальная сумма curMax, формула для нахождения максимальной суммы подмассива после переворота:

`dpReverse[i] = Math.max(arr[i] + curMax, arr[i] + dpReverse[i - 1])`

Полный исходный код решения и его описание: [перейти к исходному коду](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E6%89%BE%E6%9C%80%E5%A4%A7%E7%B4%AF%E5%8A%A0%E5%92%8C%E5%BA%8F%E5%88%97_%E5%8F%A6%E8%BD%AC.java)


## Задача о рюкзаке 0-1 — задача на собеседовании в Meituan и ByteDance

### Задача

Вор, который грабит магазин, обнаружил n товаров. i-й товар стоит v[i] долларов и весит w[i] фунтов, где v[i] и w[i] — целые числа. Вор хочет взять с собой товары с максимальной стоимостью, но его рюкзак может вместить не более W фунтов, где W — целое число. Какие товары он должен взять, чтобы максимизировать стоимость?### Решение задачи
Эту задачу называют задачей о рюкзаке 0-1, потому что для каждого товара вор либо берет его полностью, либо оставляет его. Он не может взять часть товара или взять один и тот же товар несколько раз. Поэтому задачу о рюкзаке 0-1 нельзя решить с помощью алгоритма жадного поиска (локальное оптимальное решение не обязательно является глобальным оптимальным решением). Прежде всего рассмотрим рекурсивное решение:
```java
/**
 * Рассчитывает максимальную стоимость, которую можно уместить в рюкзаке, используя рекурсивный подход, который имеет высокую временную сложность.
 * Рекурсивный подход включает повторное вычисление множества промежуточных результатов, что приводит к экспоненциальному увеличению сложности вычислений при увеличении размера данных.
 * @param v стоимость товара
 * @param w вес товара
 * @param space оставшийся объем
 * @param current текущая позиция
 * @param cost текущая общая стоимость
 */
private static int f(int[] v, int[] w, int space, int current, int cost) {
    if (space <= 0 || current >= v.length) {
        return cost;
    }
    int cost_1 = 0;
    int cost_2 = 0;
    if (space - w[current] >= 0) {
        // Выбор текущего товара, объем уменьшается на вес текущего товара, общая стоимость увеличивается на стоимость текущего товара, переход к следующему товару
        cost_1 = f(v, w, space - w[current], mark, current + 1, cost + v[current]);
    }
    // Не выбирать текущий товар, объем и общая стоимость остаются неизменными, переход к следующему товару
```    cost_2 = f(v, w, space, mark, current+1, cost);
     // Возвращаем большую из двух общей стоимостей: с выбором текущего товара и без него
     return cost_1 > cost_2 ? cost_1 : cost_2;
 }
 ```Динамическое программирование для рекурсивного решения:
 Создаем двумерный массив c для хранения максимальной общей стоимости, где c[i, j] представляет собой максимальную общую стоимость i товаров в рюкзаке с общей вместимостью j.```Цель задачи о рюкзаке 0-1 заключается в получении максимального значения c[n, W], где n — количество доступных товаров, а W — общая вместимость рюкзака.

Оптимальная структура подзадач для задачи о рюкзаке 0-1:
1. Если оптимальное решение включает n-й товар, то следующая подзадача будет иметь вместимость W-w[n] и потребует выбора из первых n-1 товаров.
2. Если оптимальное решение не включает n-й товар, то следующая подзадача будет иметь вместимость W и потребует выбора из первых n-1 товаров.

Таким образом, рекурсивное уравнение для c[i, j] будет: `c[i, j] = max{c[i-1, j], c[i-1, j-w[i]] + v[i]}`

Полное решение задачи и идея: [перейти к исходному коду](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98.java)

## Ключевое k-е по алфавитному порядку число

### Задача
Даны целое число n и k, верните k-е по алфавитному порядку число из диапазона [1, n]. Обратите внимание: k и n могут быть очень большими (1 <= k <= n <= 1000000000).

Пример:

Ввод: n = 13, k = 2

Выход: 10

Ссылка на задачу: https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order

### Идея решения

Если n = 13, k = 2, то алфавитный порядок чисел будет [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], поэтому второе по алфавитному порядку число — это 10.Сначала напишем рекурсивный код для генерации чисел в алфавитном порядке. Поскольку n может быть очень большим, использование рекурсии для больших значений n приведет к превышению времени выполнения. Однако, используя закономерности алфавитного порядка, можно оптимизировать решение.Для n = 99, рекурсивный вывод чисел в алфавитном порядке:

Можно заметить, что числа в алфавитном порядке повторяются по определенной закономерности. Количество чисел в каждом уровне `len = (len * 10 + 1)` повторяется n раз, для n = 10 повторяется 1 раз, для n = 100 повторяется 2 раза, для n = 1000 повторяется 3 раза, количество чисел на каждом уровне соответственно равно 11, 111, 1111 и так далее.

Полное решение задачи и идея: [перейти к исходному коду](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E9%9D%A2%E8%AF%95%E9%A2%98/%E5%AD%97%E5%85%B8%E5%BA%8F%E7%9A%84%E7%AC%ACK%E5%B0%8F%E6%95%B0%E5%AD%97.java)

## Не использовать оператор сложения для вычисления суммы целых чисел — использовать операции с битами

### Задача
Вводятся два целых числа a и b. Не используя оператор сложения (+), включая вызовы функций, выведите сумму a+b. (-999999999 <= a,b <= 999999999)

Пример:

Ввод:

15 33

Вывод:

48

Ввод:

-999999999 999999999

Вывод:

0

### План решения задачи
Так как использование оператора сложения запрещено, единственным способом решения задачи являются операции с битами. Таким образом, задача сводится к использованию операций с битами для реализации сложения.Как это можно сделать? Давайте рассмотрим правила работы с битами:

1^1=0, 0^1=1, 0^0=0

Согласно правилам операции XOR, можно использовать XOR для вычисления суммы чисел.

1&1=1, 1&0=0, 0&0=0

Согласно правилам операции AND, можно использовать AND для вычисления переноса при сложении чисел.

Таким образом, комбинируя операции XOR и AND, можно реализовать сложение целых чисел.

**Процесс вычисления:**

Важно отметить, что диапазон входных чисел ограничен диапазоном int, но сумма двух int может выйти за пределы диапазона int, что может привести к переполнению. Поэтому результат следует сохранять в типе long.

Расширенное обсуждение: Если операции с битами используются для реализации сложения, как можно использовать операции с битами для реализации вычитания?

Полный код решения и план решения: [Перейти к исходному коду](https://gitee.com/you-yuan/Algorithms/blob/master/src/com/yuan/algorithms/%E9%9D%A2%E8%AF%95%E9%A2%98/%E4%B8%8D%E4%BD%BF%E7%94%A8%E5%8A%A0%E5%8F%B7%E5%AE%9E%E7%8E%B0%E6%95%B4%E6%95%B0%E5%8A%A0%E6%B3%95.java)