C MindSet: Блог #2

Згенеровано ChatGPT

Опис проблеми:

Вам надано масив цілих чисел nums довжиною n, індексованих з нуля.

Масив nums містить дійсний поділ на індексі i, якщо виконується наступне:

• Сума перших i + 1 елементів більша або рівна сумі останніх n - i - 1 елементів.
• Існує хоча б один елемент праворуч від i. Тобто, 0 <= i < n - 1.

Поверніть кількість дійсних поділів в масиві nums.

Пояснення:

Масив потрібно розділити на дві частини так, щоб сума елементів першої частини була більшою за суму елементів другої частини.

Потрібно повернути кількість таких валідних поділів.

Приклад 1:

Вхід: nums = [10,4,-8,7]  
Вихід: 2  
Пояснення:   
Є три способи розділити масив nums на дві непорожні частини:  
- Поділити масив на індексі 0. Тоді перша частина буде [10], її сума — 10. Друга частина — [4,-8,7], її сума — 3. Оскільки 10 >= 3, i = 0 є дійсним поділом.  
- Поділити масив на індексі 1. Тоді перша частина буде [10,4], її сума — 14. Друга частина — [-8,7], її сума — -1. Оскільки 14 >= -1, i = 1 є дійсним поділом.  
- Поділити масив на індексі 2. Тоді перша частина буде [10,4,-8], її сума — 6. Друга частина — [7], її сума — 7. Оскільки 6 < 7, i = 2 не є дійсним поділом.  
Таким чином, кількість дійсних поділів в масиві nums — 2.

Приклад 2:

Вхід: nums = [2,3,1,0]  
Вихід: 2  
Пояснення:   
Є два дійсних поділи в масиві nums:  
- Поділити масив на індексі 1. Тоді перша частина буде [2,3], її сума — 5. Друга частина — [1,0], її сума — 1. Оскільки 5 >= 1, i = 1 є дійсним поділом.   
- Поділити масив на індексі 2. Тоді перша частина буде [2,3,1], її сума — 6. Друга частина — [0], її сума — 0. Оскільки 6 >= 0, i = 2 є дійсним поділом.

Обмеження:

• 2 <= nums.length <= 105
• -105 <= nums[i] <= 105

Роздуми:

Для відстеження сум двох масивів можна використати методи з рухомим вікном та зменшенням вікна.

Ідея:

1. Ми можемо збільшувати кількість елементів в масиві A та зменшувати кількість елементів в масиві B, коли проходимо через масив.
2. Оскільки ми збільшуємо/зменшуємо елементи масивів, можна підтримувати два рухомі сумування — одне для кожного масиву.
3. Якщо сума масиву A більша за суму масиву B, можемо збільшити лічильник дійсних рішень.
4. Коли в масиві B не залишиться елементів, можна повернути лічильник дійсних рішень.

Пропозиція:

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

Фінальний код:

int waysToSplitArray(int* nums, int numsSize) {  
 int *split, valid = 0;  
 long long int sumA = 0, sumB = 0;  
 split = nums;  

 for (int i = 0; i < numsSize; i++) {  
 sumB += nums[i];  
 }  

 while(split < (nums + numsSize - 1)) {  
 sumA += *split;  
 sumB -= *split;  

 if (sumA >= sumB)  
 valid++;  

 split++;  
 }  

 return valid;  

}

Пояснення коду:

1. Обчислюємо суму всього масиву для sumB.
2. Оскільки один елемент додається до масиву A за раз, сума sumA збільшується на доданий елемент, а сума sumB зменшується на видалений елемент.
3. Після оновлення значень sumA і sumB порівнюємо ці два значення. Якщо умова виконується, збільшуємо valid на 1.
4. Наступний поділ перевіряється, рухаючи вказівник split до наступного елемента.
5. Повторюємо кроки 1–5, поки вказівник не дійде до останнього елемента.
6. Повертаємо кількість дійсних поділів.

Часова складність: O(n)

Продовжуйте читати, якщо вам цікаво, які помилки я зробив до того, як прийшов до остаточного рішення.

Блок 1: Перевищено ліміт часу

Ідея полягала в створенні грубого способу підтримки сум sumA і sumB.

Цей код не працює, оскільки він обчислює sumA та sumB з нуля на кожному кроці циклу.

int waysToSplitArray(int* nums, int numsSize) {  
 int sumA = 0, sumB = 0, *split, valid = 0;  
 split = nums;  

 while(split < (nums + numsSize - 1)) {  
 sumA = 0;  
 sumB = 0;  
 for(int i = 0; i < split - nums + 1; i++) {  
 sumA += nums[i];  
 }  

 for(int i = split - nums + 1; i < numsSize; i++) {  
 sumB += nums[i];  
 }  

 if (sumA >= sumB)  
 valid++;  

 split++;  
 }  

 return valid;  

}

Блок 2: Переповнення знакового цілого

Це рішення вирішує проблему перевищення ліміту часу, але виникає помилка переповнення знакового цілого. Щоб виправити це, я змінив тип змінних sumA і sumB на long long int.

int waysToSplitArray(int* nums, int numsSize) {  
 int sumA = 0, sumB = 0, *split, valid = 0;  
 split = nums;  

 for (int i = 0; i < numsSize; i++)  
 sumB += nums[i];  

 while(split < (nums + numsSize - 1)) {  
 sumA += *split;  
 sumB -= *split;  

 if (sumA >= sumB)  
 valid++;  

 split++;  
 }  

 return valid;  

}

Давайте разом досліджувати та вчитися!

Перекладено з: Number of Ways to Split Array