Записки LeetCode (15) — 1512. Кількість хороших пар (JS)

текст перекладу

Важкість: Легко

Теги: Масив (Array)、Хеш-таблиця (Hash Table)、Математика (Math)、Підрахунок (Counting)

Перейдіть до LeetCode

Завдання:

Дано масив цілих чисел nums, потрібно повернути кількість хороших пар.

Пара (i, j) називається хорошою, якщо nums[i] == nums[j] та i < j.

Приклад 1:

Вхід: nums = [1,2,3,1,1,3]  
Вихід: 4  
Пояснення: Є 4 хороші пари (0,3), (0,4), (3,4), (2,5), індексація з 0.

Приклад 2:

Вхід: nums = [1,1,1,1]  
Вихід: 6  
Пояснення: Кожна пара в масиві є хорошою.

Приклад 3:

Вхід: nums = [1,2,3]  
Вихід: 0

Ідеї:

Рішення 1

Завдання вимагає знайти кількість пар, які задовольняють умови. Спочатку я вирішив обробити крайні випадки:

Перетворимо nums у Set для визначення, чи всі елементи однакові або чи всі унікальні. Якщо розмір Set дорівнює 0, це означає, що в nums немає елементів, з яких можна утворити пару, і ми відразу повертаємо 0.

Якщо розмір Set дорівнює 1, це означає, що всі елементи однакові. Тому ми можемо взяти загальну кількість повторів мінус 1, а потім від 1 до кінця додавати їх, щоб отримати кількість пар. Це означає, що кожного разу, коли число з’являється n-й раз, воно може утворити пару з попередніми n-1 однаковими числами.

У випадку, якщо це не один з двох наведених випадків, ми створюємо map, щоб записати кількість кожного числа, і в кінці додаємо до підсумку кількість чисел, які зустрічаються більше ніж один раз.

Рішення 2

Пізніше я зрозумів, що можна вирішити задачу, використовуючи лише один цикл, без складної логіки, як у першому рішенні. Виявляється, що друге рішення також використовує map для підрахунку кількості кожного числа, а потім додає значення для кожної кількості. Якщо ви не зовсім розумієте, чому потрібно додавати значення, ось приклад для пояснення:

Потрібно запам’ятати таку ідею:

Кожного разу, коли число з’являється n-й раз, воно може утворити пару з попередніми n-1 однаковими числами

Приклад для [1, 1, 1, 1]:

1. Коли зустрічаємо перше число 1, оскільки перед ним немає інших 1, ми просто записуємо це число в map.
2. Коли зустрічаємо друге число 1, виявляємо, що в map вже є один 1, тобто вже є одна пара, яку можна утворити з новим 1, тому збільшуємо лічильник на 1 і оновлюємо кількість 1 в map до 2.
3. Коли зустрічаємо третє число 1, виявляємо, що в map вже є два 1, тобто вже є дві пари, які можна утворити з новим 1, тому збільшуємо лічильник на 2 і оновлюємо кількість 1 в map до 3.
4. Коли зустрічаємо четверте число 1, виявляємо, що в map вже є три 1, тобто вже є три пари, які можна утворити з новим 1, тому збільшуємо лічильник на 3 і оновлюємо кількість 1 в map до 4.

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

Реалізація:

Рішення 1:

/**  
 * @param {number[]} nums  
 * @return {number}  
 */  
var numIdenticalPairs = function(nums) {  
 const set = new Set(nums)  
 if (set.size === nums.length) return 0;  
 if (set.size === 1) return add(nums.length - 1);  

 const map = new Map();  
 for (let num of nums) {  
 map.set(num, (map.get(num) || 0) + 1);  
 };  

 let result = 0;  
 for (let value of map.values()) {  
 if (value > 1) {  
 result = result + add(value - 1);  
 }  
 }  

 return result;  
};  

function add(num) {  
 if (num === 1) return num;  
 return num + add(num - 1);  
}

Рішення 2:

/**  
 * @param {number[]} nums  
 * @return {number}  
 */  
var numIdenticalPairs = function(nums) {  
 const map = new Map();  
 let count = 0;  
 for (let num of nums) {  
 if (map.has(num)) {  
 const currentNumCount = map.get(num)  
 count += currentNumCount;  
 map.set(num, currentNumCount + 1);  
 } else {  
 map.set(num, 1)  
 }  
 }  

 return count;  
};

Переглянути інші записи по LeetCode:

[

Записки по LeetCode — Каталог

Це запис моїх рішень задач на LeetCode. Сподіваюся, що за допомогою нотаток я зможу закріпити свої ідеї та підходи до вирішення задач.

medium.com

](/@testyixuan173/leetcode-笔记-目录-d5ed809ebced?source=post_page-----de91c55796bc--------------------------------)

Перекладено з: LeetCode 筆記(15) — 1512. Number of Good Pairs (JS)