Java | LeetCode

Задача: 491. Non-decreasing Subsequences Сложность: medium Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке. Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

👨‍💻 Алгоритм: 1⃣Инициализация и запуск функции обратного отслеживания Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0. 2⃣Функция обратного отслеживания Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента. 3⃣Возврат результата После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его. 😎 Решение:

class Solution {
    private void backtrack(int[] nums, int index, List<Integer> sequence,
            Set<List<Integer>> result) {
        if (index == nums.length) {
            if (sequence.size() >= 2) {
                result.add(new ArrayList<>(sequence));
            }
            return;
        }
        if (sequence.isEmpty() ||
                sequence.get(sequence.size() - 1) <= nums[index]) {
            sequence.add(nums[index]);
            backtrack(nums, index + 1, sequence, result);
            sequence.remove(sequence.size() - 1);
        }
        backtrack(nums, index + 1, sequence, result);
    }

    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        List<Integer> sequence = new ArrayList<Integer>();
        backtrack(nums, 0, sequence, result);
        return new ArrayList(result);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 892. Surface Area of 3D Shapes Сложность: easy Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности. Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

👨‍💻 Алгоритм: 1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани. 2⃣Для каждой башни уменьшить площадь боковых граней, которые прилегают к соседним башням, с учетом высоты соседних башен. 3⃣Просуммировать все значения площадей для получения итоговой площади поверхности. 😎 Решение:

public int surfaceArea(int[][] grid) {
    int n = grid.length;
    int area = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                area += (grid[i][j] * 4) + 2;
            }
            if (i > 0) {
                area -= Math.min(grid[i][j], grid[i-1][j]) * 2;
            }
            if (j > 0) {
                area -= Math.min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
    }
    return area;

Ставь 👍 и забирай 📚 Базу знаний

Задача: 79. Word Search Сложность: medium Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке. Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза. Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

👨‍💻 Алгоритм: 1⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки. 2⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова. 3⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования. 😎 Решение:

class Solution {
    private char[][] board;
    private int ROWS;
    private int COLS;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.ROWS = board.length;
        this.COLS = board[0].length;

        for (int row = 0; row < this.ROWS; ++row) {
            for (int col = 0; col < this.COLS; ++col) {
                if (this.backtrack(row, col, word, 0)) return true;
            }
        }
        return false;
    }

    protected boolean backtrack(int row, int col, String word, int index) {
        if (index >= word.length()) return true;

        if (
            row < 0 ||
            row == this.ROWS ||
            col < 0 ||
            col == this.COLS ||
            this.board[row][col] != word.charAt(index)
        ) return false;

        boolean ret = false;
        this.board[row][col] = '#';

        int[] rowOffsets = { 0, 1, 0, -1 };
        int[] colOffsets = { 1, 0, -1, 0 };
        for (int d = 0; d < 4; ++d) {
            ret = this.backtrack(
                    row + rowOffsets[d],
                    col + colOffsets[d],
                    word,
                    index + 1
                );
            if (ret) break;
        }

        this.board[row][col] = word.charAt(index);
        return ret;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 532. K-diff Pairs in an Array Сложность: medium Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве. Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия: 0 <= i, j < nums.length i != j |nums[i] - nums[j]| == k Обратите внимание, что |val| обозначает абсолютное значение val. Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

👨‍💻 Алгоритм: 1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums. 2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям: Если k > 0, проверьте, существует ли ключ, равный x + k. Если k == 0, проверьте, есть ли более одного вхождения x. 3⃣ Увеличьте счётчик результатов, если условие выполняется. 😎 Решение:

public class Solution {
    public int findPairs(int[] nums, int k) {

        int result = 0;

        HashMap <Integer,Integer> counter = new HashMap<>();
        for (int n: nums) {
            counter.put(n, counter.getOrDefault(n, 0)+1);
        }


        for (Map.Entry <Integer, Integer> entry: counter.entrySet()) {
            int x = entry.getKey();
            int val = entry.getValue();
            if (k > 0 && counter.containsKey(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 949. Largest Time for Given Digits Сложность: medium Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка. Пример:

Input: arr = [1,2,3,4]
Output: "23:41"

👨‍💻 Алгоритм: 1⃣Перебрать все возможные перестановки массива arr. 2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время. Найти самое позднее допустимое время среди всех перестановок. 3⃣Алгоритм Перебрать все возможные перестановки массива arr. Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время. Найти самое позднее допустимое время среди всех перестановок. Вернуть найденное время в формате "HH ". Если допустимое время не найдено, вернуть пустую строку. 😎 Решение:

import java.util.*;

class Solution {
    public String largestTimeFromDigits(int[] arr) {
        int maxTime = -1;
        List<int[]> permutations = new ArrayList<>();
        permute(arr, 0, permutations);
        
        for (int[] perm : permutations) {
            int hours = perm[0] * 10 + perm[1];
            int minutes = perm[2] * 10 + perm[3];
            if (hours < 24 && minutes < 60) {
                maxTime = Math.max(maxTime, hours * 60 + minutes);
            }
        }
        
        if (maxTime == -1) {
            return "";
        }
        
        String hours = String.format("%02d", maxTime / 60);
        String minutes = String.format("%02d", maxTime % 60);
        return hours + ":" + minutes;
    }
    
    private void permute(int[] nums, int start, List<int[]> res) {
        if (start == nums.length) {
            res.add(nums.clone());
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, res);
            swap(nums, start, i);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Вебинар с ведущим застройщиком Кипра в Лимасоле Как заработать на Кипре 20% ROI за 2 года? 📅 2 октября в 19:00 по Москве На вебинаре расскажем об эксклюзивном стоке Tranio в проекте от ведущего застройщика. Регистрируйтесь бесплатно! Зарегистрироваться #реклама 16+ webinar.tranio.ru О рекламодателе

Задача: 223. Rectangle Area Сложность: medium Даны координаты двух прямоугольных прямоугольников на двумерной плоскости, верните общую площадь, покрытую этими двумя прямоугольниками. Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2). Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2). Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

👨‍💻 Алгоритм: 1⃣Вычислить площади двух прямоугольников: Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту. 2⃣Вычислить перекрытие: Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия. 3⃣Вычислить и вернуть общую площадь: Вычтите площадь перекрытия из суммы площадей двух прямоугольников и верните результат. 😎 Решение:

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int areaOfA = (ay2 - ay1) * (ax2 - ax1);
        int areaOfB = (by2 - by1) * (bx2 - bx1);

        int left = Math.max(ax1, bx1);
        int right = Math.min(ax2, bx2);
        int xOverlap = right - left;

        int top = Math.min(ay2, by2);
        int bottom = Math.max(ay1, by1);
        int yOverlap = top - bottom;

        int areaOfOverlap = 0;
        if (xOverlap > 0 && yOverlap > 0) {
            areaOfOverlap = xOverlap * yOverlap;
        }

        int totalArea = areaOfA + areaOfB - areaOfOverlap;

        return totalArea;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 242. Valid Anagram Сложность: easy Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае. Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз. Пример:

Input: s = "anagram", t = "nagaram"
Output: true

👨‍💻 Алгоритм: 1⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z'). 2⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы. 3⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s. 😎 Решение:

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
        table[t.charAt(i) - 'a']--;
    }
    for (int count : table) {
        if (count != 0) {
            return false;
        }
    }
    return true;
}

Ставь 👍 и забирай 📚 Базу знаний

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 121. Best Time to Buy and Sell Stock Сложность: easy Вам дан массив цен, где prices[i] является ценой данной акции в i-й день. Ваша задача — максимизировать вашу прибыль, выбрав один день для покупки акции и другой день в будущем для ее продажи. Верните максимальную прибыль, которую вы можете получить от этой операции. Если прибыль получить невозможно, верните 0. Пример:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

👨‍💻 Алгоритм: 1⃣Инициализируем minprice как бесконечность и maxprofit как 0. 2⃣Проходим по массиву: если текущая цена меньше minprice, обновляем минимум. Если разница между текущей ценой и minprice больше maxprofit, обновляем прибыль. 3⃣В конце возвращаем maxprofit — максимальную разницу покупки/продажи, которую можно было получить. 😎 Решение:

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) minprice = prices[i];
            else if (prices[i] - minprice > maxprofit) maxprofit = prices[i] -
            minprice;
        }
        return maxprofit;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 634. Find the Derangement of An Array Сложность: medium В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7. Пример:

Input: n = 3
Output: 2

👨‍💻 Алгоритм: 1⃣Инициализация массива для хранения результатов: Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0. 2⃣Вычисление количества отклонений: Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD. 3⃣Возвращение результата: Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7. 😎 Решение:

public class Solution {
    public int countDerangements(int n) {
        final int MOD = 1000000007;
        if (n == 0) return 1;
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
        }
        return dp[n];
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Приглашаем на Yandex Neuro Scale В этом году главная конференция Yandex Cloud объединит разработчиков, архитекторов, инженеров и IT-руководителей, чтобы обменяться опытом и увидеть, как работают технологии, которые меняют индустрии. 7 тематических треков, 50+ докладов, реальные бизнес-кейсы и нетворкинг! ✨Участие бесплатное, нужно только зарегистрироваться!✨ Зарегистрироваться #реклама 16+ scale.yandex.cloud О рекламодателе Реклама на Яндексе

Задача: CodeTestcaseTest ResultTest Result1523. Count Odd Numbers in an Interval Range Сложность: easy Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно). Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

👨‍💻 Алгоритм: 1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен. 2⃣Если low нечётное, увеличьте его на 1. 3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0. 😎 Решение:

class Solution {
    public int countOdds(int low, int high) {
        if ((low & 1) == 0) {
            low++;
        }
        return low > high ? 0 : (high - low) / 2 + 1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Где вести задачи и проекты? Конечно, в Битрикс24 Бесплатный онлайн-сервис для бизнеса и совместной работы. Полный комплект для работы без хаоса. Ставьте первую задачу прямо сейчас Начать #реклама 16+ task-24.bitrix24.ru О рекламодателе

Задача: 279. Perfect Squares Сложность: medium Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n. Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются. Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0. Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums. 2⃣Заполнение массива dp: Для каждого числа i от 1 до n: Для каждого совершенного квадрата s из массива square_nums: Если i меньше текущего совершенного квадрата s, прервите внутренний цикл. Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i. 3⃣Возврат результата: Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n. 😎 Решение:

class Solution {

  public int numSquares(int n) {
    int dp[] = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    int max_square_index = (int) Math.sqrt(n) + 1;
    int square_nums[] = new int[max_square_index];
    for (int i = 1; i < max_square_index; ++i) {
      square_nums[i] = i * i;
    }

    for (int i = 1; i <= n; ++i) {
      for (int s = 1; s < max_square_index; ++s) {
        if (i < square_nums[s])
          break;
        dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1);
      }
    }
    return dp[n];
  }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1344. Angle Between Hands of a Clock Сложность: medium Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками. Ответы с точностью до 10^-5 от фактического значения будут считаться правильными. Пример:

Input: hour = 12, minutes = 30
Output: 165

👨‍💻 Алгоритм: 1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30. 2⃣Найти разницу: diff = abs(hour_angle - minutes_angle). 3⃣Вернуть меньший угол: min(diff, 360 - diff). 😎 Решение:

class Solution {
    public double angleClock(int hour, int minutes) {
        int oneMinAngle = 6;
        int oneHourAngle = 30;

        double minutesAngle = oneMinAngle * minutes;
        double hourAngle = (hour % 12 + minutes / 60.0) * oneHourAngle;

        double diff = Math.abs(hourAngle - minutesAngle);
        return Math.min(diff, 360 - diff);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1213. Intersection of Three Sorted Arrays Сложность: easy Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах. Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

👨‍💻 Алгоритм: 1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений. 2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов. 3⃣Итерация через counter, чтобы найти числа, которые появляются три раза, и вернуть их в виде отсортированного массива. 😎 Решение:

class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> ans = new ArrayList<>();

        Map<Integer, Integer> counter = new TreeMap<>();

        for (Integer e: arr1) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }
        for (Integer e: arr2) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }
        for (Integer e: arr3) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }

        for (Integer item: counter.keySet()) {
            if (counter.get(item) == 3) {
                ans.add(item);
            }
        }
        return ans;

    }
}

Ставь 👍 и забирай 📚 Базу знаний

Как списать долги? Бесплатно через МФЦ! Долги от 200 000₽. Поможем бесплатно списать долг и расторгнуть все кредитные договоры! Узнать больше #реклама нет-кредит.рф О рекламодателе

Задача: 367. Valid Perfect Square Сложность: easy Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае. Идеальный квадрат — это целое число, являющееся квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя. Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt. Пример:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

👨‍💻 Алгоритм: 1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2. 2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num: Если guess_squared == num, вернуть True. Если guess_squared > num, сдвинуть правую границу right = x - 1. В противном случае сдвинуть левую границу left = x + 1. 3⃣Если вышли из цикла, вернуть False. 😎 Решение:

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 2) {
            return true;
        }

        long x = num / 2;
        while (x * x > num) {
            x = (x + num / x) / 2;
        }
        return x * x == num;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе