В это время атаки Covid-19 мир кажется безмолвным и самым могущественным человеком, страной и всем остальным, как муравей против слона на войне. Так что в это трудное время мы должны занять себя такой деятельностью, которая нам пригодится. И, не теряя этого времени, мы можем сделать какую-нибудь продуктивную работу, тем самым это может быть скрытым удовольствием. И как люди из IT или cs люди, мы знаем, что кодирование гораздо важнее в этом мире, чтобы жить лучше, да, есть много доступных вариантов, но все же я предпочитаю кодирование среди всего прочего, особенно как студент, это очень важно. И если вы изучаете информатику, то этот пост может быть вам полезен. Итак, давайте начнем это путешествие...!
Итак, сегодня я собираюсь обсудить одну проблему, которая была задана в моем интервью на должность стажера-разработчика программного обеспечения. И чаще всего на собеседовании вы будете сталкиваться с такими вопросами. Поэтому я хочу обсудить это.
Вопрос : Количество островов
Учитывая двумерную карту сетки '1's (суша) и '0's (вода), подсчитайте количество островов. Остров окружен водой и образован путем соединения соседних земель по горизонтали или вертикали. Вы можете предположить, что все четыре края сетки окружены водой.
Пример 1:
Input: 11110 11010 11000 00000 Output: 1
Пример 2:
Input: 11000 11000 00100 00011 Output: 3
Итак, на первый взгляд вопрос выглядит таким простым и его легко написать. Но когда вы думаете об этом крайнем случае, ваше мышление может быть ошибочным. Поэтому, пожалуйста, задайте вопрос дважды, а затем попытайтесь решить его.
Всегда помните одну вещь, как кодер
«Подумайте дважды, прежде чем писать код»
Так что вполне нормально потратить 10 минут на обдумывание, а не на реализацию этой сложной идеи. Так что теперь переходим к проблеме, поскольку проблема упоминает, что вам нужно найти все острова, которые не связаны друг с другом. Таким образом, в основном вам нужно найти всю такую группу 1, чтобы ни один элемент одной группы не касался средств, смежных с другим элементом другой группы. Как показано в примере, нам нужно найти только номер острова.
Итак, сначала мы можем создать одну функцию, которая может обрабатывать соседей текущей ячейки, и если какая-либо из них имеет значение 1, то разверните ее и найдите группу единиц. Итак, эта функция выглядит так, как показано ниже.
Здесь сетка - это матрица, которая дана нам в качестве входных данных самого вопроса. а переменная с именем «ans» — это глобальная переменная, которая обрабатывает количество островов. В этой функции мы передаем значение номера строки, номера столбца и матрицы сетки, чтобы мы могли найти подходящего соседа и вычислить то же самое, вызвав рекурсию. Когда мы посещаем и ячейку, мы собираемся сделать эту ячейку посещенной, сделав значение от 1 до 0. Так что нам не нужна дополнительная память для другой матрицы, которая обрабатывает, посещается ли текущая ячейка или нет. Так что это хорошая идея, если вы думаете в соответствии с этим. Теперь из основной функции нам просто нужно вызвать эту функцию вычисления только для той ячейки, которая имеет 1 в качестве элемента. И он удалит все соседние с ним единицы, потому что во время посещения мы делаем эти единицы равными 0, поэтому он не будет повторяться. И мы получим правильный ответ. Итак, окончательный код выглядит так
Код выше написан на языке C++. Если вы хотите запустить этот код, попробуйте запустить его в leetcode .
Спасибо, что прочитали этот пост. Пожалуйста, поделитесь отзывом об этом посте, так как это мой первый пост, я могу сделать так много ошибок, поэтому, пожалуйста, прокомментируйте его.
Спасибо..
Хорошего дня… особенно Кодеру…
