Ну что же начинаем, пока формат тектовый, затем планирую добавлять видео с разборов.
Начнем с разбора достаточно популярной задачи:
Условие:
Дана строка 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
}
}
Начнем с разбора достаточно популярной задачи:
Условие:
Дана строка 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
}
}