Ну что же начинаем, пока формат тектовый, затем планирую добавлять видео с разборов.
Начнем с разбора достаточно популярной задачи:

Условие:
Дана строка s. Найти первый неповторяющийся символ и вернуть его индекс. Если такого нет — вернуть -1.

Пример вывода:
s = "leetcode" → 0 (символ 'l')
s = "loveleetcode" → 2 ('v')
s = "aabb" → -1

Пояснение алгоритма
В первую очередь при решении задач важно определить крайние точки: в нашем случае - что будет если все символы будут повторяться? - это определено в условии - нужно вернуть -1

Важно подобрать верную структуру данных: нам важно чтобы мы могли хранить справочник:
элемент - его количество
Идеально использовать мапу, но популярные HashMap и TreeMap не подходят, использовать LinkedHashMap – он запоминает порядок добавления ключей, а нам нужно первое вхождение.

Сам алгоритм не сложный:
Проходим по строке и складываем каждый символ в мапу:
ключ = символ, значение = счётчик вхождений.

Затем проходим по записям карты (в порядке первого появления) и возвращаем индекс первого символа, у которого счётчик == 1.
Сложность:
O(n) по времени, O(n) по памяти.

Теперь напишем сам код:

public class FirstUniqueChar {
public static int firstUniqChar(String s) {
Map<Character, Integer> counts = new LinkedHashMap<>();

// Шаг 1: подсчёт частот. Проходим по строке и смотри если символ уже есть в мапе прибавляем +1, если нет то добавляем со значением 1
for (char ch : s.toCharArray()) {
counts.put(ch, counts.getOrDefault(ch, 0) + 1);
}

// Шаг 2: поиск первого с частотой 1. Проходим по мапе ищем значение =1
for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
if (entry.getValue() == 1) {
return s.indexOf(entry.getKey()); // можно и хранить индекс отдельно
}
}
return -1;
}

public static void main(String[] args) {
System.out.println(firstUniqChar("leetcode")); // 0
System.out.println(firstUniqChar("loveleetcode")); // 2
System.out.println(firstUniqChar("aabb")); // -1
}
}
Просмотры: 61
Открыть в MAX Сообщить о неточности

Сообщить о неточности

Опишите, что нужно исправить. Если есть источник, добавьте ссылку.

Вы покидаете datool.ru

Ссылка ведёт на внешний сайт. datool.ru не отвечает за его содержимое — проверьте адрес, прежде чем вводить пароли или платёжные данные.

Переход через 10 с

Перейти