Почему структуры данных важны при решении задач кодирования.
Введение
Когда я не знал структур данных, вложенные циклы for были моим хлебом насущным для решения или, точнее, грубой силы, задач кодирования. В этой статье я покажу вам, как я решил относительно простую задачу кодирования двумя разными способами и почему один метод лучше другого. Но прежде чем начать, вы должны знать о нотации большого O и почему это важно.
Обозначение большого O
Проще говоря, нотация Big O показывает нам, насколько эффективно наш код будет работать в наихудших сценариях. Когда данные очень маленькие, разница минимальна, но по мере увеличения размера входных данных увеличивается и относительная разница между сложностью каждого большого O до линейного, квадратичного, экспоненциального или даже факторного уровней. Эти сложности представлены, как вы уже догадались, большой буквой O. См. рисунок ниже для визуального представления каждой из них.
Проблема кодирования
Имея две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя букву из magazine, и false если иначе.
Подход первый: вложенные циклы For
Когда я впервые столкнулся с этой проблемой, я подумал, что она достаточно проста. Все, что мне нужно сделать, это перебрать каждый символ в ransomNote и сравнить их один за другим с каждым символом в magazine, избегая при этом сложностей, таких как пересчет повторяющихся букв.
Чтобы объяснение этого подхода было кратким, посмотрите на мой полный код ниже вместе с комментариями для каждого шага:
public static boolean canConstruct(String ransomNote, String magazine) {
/*First check if the ransomNote string is larger than magazine, if
that's the case then it is already impossible and therefore false */
if (ransomNote.length() > magazine.length()){
return false;
}
/*Next we create String builder objects containing our two string
arguments. This way we can modify them in our for-loops*/
StringBuilder rString = new StringBuilder(ransomNote);
StringBuilder mString = new StringBuilder(magazine);
/*Nested for loops where the outer-loop represents the character
index for ransomNote, and the inner-loop for magazine*/
for (int i=0; i< rString.length(); i++){
for (int j=0; j< mString.length(); j++){
/*This if-statement will check if the character found in each
String index are equal to each other */
if(rString.charAt(i)==mString.charAt(j)){
/*If equal we use the following stringbuilder method
to replace that character with an empty space*/
rString.setCharAt(i,' ');
mString.setCharAt(j, ' ');
}
}
}
/*Once the loops are finished we convert our ransomNote stringbuilder
object back to a regular string */
ransomNote = rString.toString();
/*Finally we check if our String is blank (not empty) and return true
if it is*/
if (ransomNote.isBlank()){
return true;
}
/*Otherwise, we return false */
return false;
}
Большинство комментариев в моем коде говорят сами за себя, но у вас, вероятно, есть несколько вопросов. Например, почему вместо этого я не использовал метод String replace(old char,new char)? Проблема в том, что этот метод заменяет ВСЕ экземпляры символа, что затем испортит весь процесс проверки в операторе if. У Stringbuilder setCharAt(index,new char) этой проблемы нет. В дополнение к этому, существует также подход удаления каждого символа, который был признан равным, но это приведет к путанице с циклами for, поскольку они полагаются на длину строки, чтобы решить, нужно ли ей снова зацикливаться. Кроме того, причина, по которой я в первую очередь устанавливаю равные символы пустыми, заключается в том, чтобы избежать пересчета повторяющихся символов, что даст нам неверный результат. Это более простой способ отследить, какие символы были найдены, без повторяющегося символа, который все испортит. Когда объект ransomNote StringBuilder полностью пуст, это подтверждает, что magazine содержит все буквы, необходимые для построения содержащегося в нем слова.
Теперь, почему этот метод считается неполноценным? Вложенные циклы for излишне сложны и вызывают квадратичное время выполнения, также известное как O(n²) в нотации Big O, а это не то, что нам нужно, когда оптимизация и эффективность являются ключевыми целями для каждый инженер-программист. Итак, давайте посмотрим на лучший подход.
Второй подход: HashMap
Структура данных HashMap хранит наборы данных в виде пар ключ-значение, а не в виде индекса, как в массиве. Этот метод сбора позволяет HashMaps находить значение или фрагмент данных за постоянное время O(1), используя свой метод contains. Сравните это с чем-то вроде ArrayList, которому потребуется цикл for для перебора всего его индекса, чтобы найти те же самые данные за линейное время O(n). Этобудет зависеть от того, насколько велик набор данных и насколько далеко часть необходимых данных находится от начала/конца ArrayList.
Теперь посмотрите на завершенный код ниже и его комментарии:
public static boolean canConstruct(String ransomNote, String magazine) {
/*Same as last time we check the length of the ransomeNote string
against magazine to decide if it's impossible from the getgo */
if (ransomNote.length() > magazine.length()){
return false;
}
/*We create a HashMap that will store a Character key,
paired with an Integer value */
HashMap<Character,Integer> letterMap = new HashMap<>();
/*For-loop to iterate through each character in magazine string
and put the data into our HashMap*/
for(int i=0; i<magazine.length(); i++){
/* if-else statement to put each character as a key, and the amount
of time it shows up in the String as a value paired with it*/
if(letterMap.containsKey(magazine.charAt(i))){
letterMap.put(magazine.charAt(i),letterMap.get(magazine.charAt(i))+1);
}else{
letterMap.put(magazine.charAt(i),1);
}
}
/*For-loop to iterate through each character in ransomNote string */
for(int i=0; i<ransomNote.length(); i++){
/*if statement checks whether our HashMap contains the character
found in ransomNote string at index i*/
if(letterMap.containsKey(ransomNote.charAt(i))){
/*if it does contain the character then we update our HashMap by
decreasing the value paired with that character key*/
letterMap.put(ransomNote.charAt(i),letterMap.get(ransomNote.charAt(i))-1);
/*if a key's value ever drops to -1 then we know that
ransomNote contains an extra repeat of a character that we
don't have in magazine, so we return false*/
if(letterMap.containsValue(-1)){
return false;
}
/*If the character isn't found in our HashMap at all then we also
return false as then it's impossible to construct the String*/
}else{
return false;
}
}
/*Once getting out of the for-loop is a success then that means the HashMap
is carrying a sufficent amount of characters needed to construct the
ransomNote string, so we return true*/
return true;
}
В первом цикле for у нас есть оператор if-else, который проверяет, содержит ли наш HashMap keyset символ, найденный в индексе i журнала String . Если этот символ уже есть, то он просто добавляет 1 к значению этой пары. Если нет, то он добавит символ вместе со значением 1. Это позволяет нам использовать каждый символ как ключ и соответствующее значение, представляющее количество этого символа. у нас есть. Назначение следующего цикла for уже хорошо объяснено в комментариях выше.
Используя этот подход HashMap, мы уменьшили нашу сложность с O(n²) до O(n). Здесь огромная разница во времени доступа, которая тем заметнее, чем больше размер входных данных. Вам также может быть интересно, увеличивает ли сложность использование двух циклов for или вложенных операторов if: в любом из этих случаев сложность остается неизменной, так что все в порядке. Можно ли еще улучшить этот код? Конечно, можно, но я позволю вам разобраться в этом самостоятельно.
Заключение
Надеюсь, мне удалось хотя бы немного убедить вас в важности понимания структур данных, их преимуществ и того, как использовать это в вашем коде. Теперь идите туда и приступайте к кодированию со структурами данных!
Спасибо, что прочитали. Если вам понравилось, не стесняйтесь оставлять отзывы и, возможно, свое собственное мнение о том, как вы могли бы улучшить мой код!
