День 9: Дослідження маніпуляцій з масивами та логічних викликів

Ласкаво просимо до Дня 9 моєї серії блогів про кодинг челенджі! 🚀

Сьогоднішні задачі пов'язані з складними операціями над масивами та логічними міркуваннями. Ці завдання охоплюють різноманітні аспекти, такі як пошук помилок, генерування значень, креативне мислення з цукерками для дітей та стратегічне планування рухів. Кожна задача дає унікальну можливість зануритися в маніпуляції з масивами, математичне обґрунтування та техніки сортування.

Давайте розглянемо рішення:

Задача 1: Виявлення помилки в наборі

https://leetcode.com/problems/set-mismatch

Складність: Легка
Завдання:
Дано масив nums, що містить n цілих чисел, де кожне число знаходиться в діапазоні [1, n]. Потрібно знайти дубльоване число та відсутнє число.

Підхід:

1. Ітерувати по діапазону чисел від 1 до n.
2. Порахувати кількість появ кожного числа в масиві.
3. Якщо число зустрічається двічі, це дубль. Якщо воно не зустрічається, це відсутнє число.

Код:

class Solution {  
 public int[] findErrorNums(int[] nums) {  
 int dup = -1, missing = -1;  

 for (int i = 1; i <= nums.length; i++) {  
 int count = 0;  
 for (int j = 0; j < nums.length; j++) {  
 if (nums[j] == i) {  
 count++;  
 }  
 }  
 if (count == 2) {  
 dup = i;  
 } else if (count == 0) {  
 missing = i;  
 }  
 }  

 return new int[] {dup, missing};  
 }  
}

Задача 2: Отримати максимальне значення в згенерованому масиві

https://leetcode.com/problems/get-maximum-in-generated-array

Складність: Легка
Завдання:
Згенерувати масив nums розміру n + 1, де:

• nums[0] = 0
• nums[1] = 1
• nums[2 * i] = nums[i]
• nums[2 * i + 1] = nums[i] + nums[i + 1]

Потрібно повернути максимальне значення в масиві nums.

Підхід:

1. Використовувати просту ітерацію для генерації значень за заданими правилами.
2. Обчислити максимальне значення під час ітерації.

Код:

class Solution {  
 public int getMaximumGenerated(int n) {  
 if (n == 0) return 0;  
 if (n == 1) return 1;  

 int[] nums = new int[n + 1];  
 nums[0] = 0;  
 nums[1] = 1;  

 for (int i = 1; i <= n / 2; i++) {  
 if (2 * i <= n) {  
 nums[2 * i] = nums[i];  
 }  
 if (2 * i + 1 <= n) {  
 nums[2 * i + 1] = nums[i] + nums[i + 1];  
 }  
 }  

 int max = 0;  
 for (int i = 0; i <= n; i++) {  
 max = Math.max(max, nums[i]);  
 }  

 return max;  
 }  
}

Задача 3: Діти з найбільшою кількістю цукерок

https://leetcode.com/problems/kids-with-the-greatest-number-of-candies

Складність: Легка
Завдання:
Дано масив candies, де candies[i] — кількість цукерок, яку має дитина, необхідно визначити, чи кожна дитина зможе мати найбільшу кількість цукерок після отримання extraCandies.

Підхід:

1. Знайти максимальну кількість цукерок у будь-якої дитини.
2. Перевірити, чи додавання extraCandies до кількості цукерок кожної дитини зробить її кількість не меншою за максимальну.

Код:

import java.util.ArrayList;  
import java.util.List;  

class Solution {  
 public List kidsWithCandies(int[] candies, int extraCandies) {  
 List result = new ArrayList<>();  

 int maxCandies = 0;  
 for (int candy : candies) {  
 maxCandies = Math.max(maxCandies, candy);  
 }  

 for (int candy : candies) {  
 result.add(candy + extraCandies >= maxCandies);  
 }  

 return result;  
 }  
}

Задача 4: Переміщення каменів до поспільних позицій II

https://leetcode.com/problems/moving-stones-until-consecutive-ii

Складність: Середня
Завдання:
Дано масив stones, що представляє позиції каменів, необхідно визначити мінімальні та максимальні рухи, які потрібні для того, щоб камені стали поспільними.

Підхід:

1. Відсортувати масив каменів.
2. Використати два вказівники для обчислення ковзного вікна поспільних каменів для мінімальних рухів.
   3.
   Розрахунок максимальних рухів, розміщуючи найдальші камені послідовно.

Код:

class Solution {  
 public int[] numMovesStonesII(int[] stones) {  
 int n = stones.length;  
 int[] ans = new int[2];  
 int i = 0, j = 0, wsize, scount, minMoves = Integer.MAX_VALUE;  
 Arrays.sort(stones);  
 while (j < n) {  
 wsize = stones[j] - stones[i] + 1;  
 scount = j - i + 1;  

 if (wsize > n) {  
 i++;  
 continue;  
 }  

 if (wsize == n - 1 && scount == n - 1)  
 minMoves = Math.min(minMoves, 2);  
 else minMoves = Math.min(minMoves, n - scount);  

 j++;  
 }  
 ans[0] = minMoves;  
 int maxMoves = 0;  
 if (stones[1] == stones[0] + 1 || stones[n - 1] == stones[n - 2] + 1)  
 maxMoves = stones[n - 1] - stones[0] + 1 - n;  
 else  
 maxMoves = Math.max(((stones[n - 1] - stones[1]) - (n - 1) + 1), ((stones[n - 2] - stones[0]) - (n - 1) + 1));  

 ans[1] = maxMoves;  
 return ans;  
 }  
}

Висновок

• Невідповідність набору (Set Mismatch) продемонструвала підхід на основі брутфорсу для вирішення проблем виявлення відсутніх і дублікатів.
• Отримання максимального значення в згенерованому масиві (Get Maximum in Generated Array) досліджувала ітеративну генерацію масивів з динамічними правилами.
• Діти з найбільшою кількістю цукерок (Kids With the Greatest Number of Candies) показала прості порівняння максимальних значень з додатковими значеннями.
• Переміщення каменів до послідовних II (Moving Stones Until Consecutive II) висвітлила стратегічне сортування та логічні міркування для перестановки каменів.

Ці завдання допомагають удосконалювати мої навички маніпулювання масивами, логічного мислення та ефективних алгоритмів. Чекаю нових викликів!

Слідкуйте за моїми новими кодерськими пригодами у 10-й день! 🚀💪

Перекладено з: Day 9: Exploring Array Manipulations and Logical Challenges