659. Split Array into Consecutive Subsequences
Вам дан отсортированный в неубывающем порядке массив целых чисел nums.
Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:
Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.
Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).
Пример
Input: nums = [1,2,3,3,4,5]
Output: true
C# решение
сопоставлено/оригиналusing System.Collections.Generic;
public class Solution {
public bool IsPossible(int[] nums) {
var freq = new Dictionary<int, int>();
var need = new Dictionary<int, int>();
foreach (var num in nums) {
if (freq.ContainsKey(num)) {
freq[num]++;
} else {
freq[num] = 1;
}
}
foreach (var num in nums) {
if (freq[num] == 0) continue;
if (need.ContainsKey(num) && need[num] > 0) {
need[num]--;
if (need.ContainsKey(num + 1)) {
need[num + 1]++;
} else {
need[num + 1] = 1;
}
} else if (freq.ContainsKey(num + 1) && freq[num + 1] > 0 &&
freq.ContainsKey(num + 2) && freq[num + 2] > 0) {
freq[num + 1]--;
freq[num + 2]--;
if (need.ContainsKey(num + 3)) {
need[num + 3]++;
} else {
need[num + 3] = 1;
}
} else {
return false;
}
freq[num]--;
}
return true;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public bool IsPossible(vector<int>& nums) {
var freq = new unordered_map<int, int>();
var need = new unordered_map<int, int>();
foreach (var num in nums) {
if (freq.count(num)) {
freq[num]++;
} else {
freq[num] = 1;
}
}
foreach (var num in nums) {
if (freq[num] == 0) continue;
if (need.count(num) && need[num] > 0) {
need[num]--;
if (need.count(num + 1)) {
need[num + 1]++;
} else {
need[num + 1] = 1;
}
} else if (freq.count(num + 1) && freq[num + 1] > 0 &&
freq.count(num + 2) && freq[num + 2] > 0) {
freq[num + 1]--;
freq[num + 2]--;
if (need.count(num + 3)) {
need[num + 3]++;
} else {
need[num + 3] = 1;
}
} else {
return false;
}
freq[num]--;
}
return true;
}
}Java решение
сопоставлено/оригиналimport java.util.HashMap;
import java.util.Map;
public class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
Map<Integer, Integer> need = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
for (int num : nums) {
if (freq.get(num) == 0) continue;
if (need.getOrDefault(num, 0) > 0) {
need.put(num, need.get(num) - 1);
need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
} else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
freq.put(num + 1, freq.get(num + 1) - 1);
freq.put(num + 2, freq.get(num + 2) - 1);
need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
} else {
return false;
}
freq.put(num, freq.get(num) - 1);
}
return true;
}
}JavaScript решение
сопоставлено/оригиналvar isPossible = function(nums) {
let freq = new Map();
let need = new Map();
for (let num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
for (let num of nums) {
if (freq.get(num) === 0) {
continue;
}
if (need.get(num) > 0) {
need.set(num, need.get(num) - 1);
need.set(num + 1, (need.get(num + 1) || 0) + 1);
} else if (freq.get(num + 1) > 0 && freq.get(num + 2) > 0) {
freq.set(num + 1, freq.get(num + 1) - 1);
freq.set(num + 2, freq.get(num + 2) - 1);
need.set(num + 3, (need.get(num + 3) || 0) + 1);
} else {
return false;
}
freq.set(num, freq.get(num) - 1);
}
return true;
};Go решение
сопоставлено/оригиналfunc isPossible(nums []int) bool {
freq := make(map[int]int)
need := make(map[int]int)
for _, num := range nums {
freq[num]++
}
for _, num := range nums {
if freq[num] == 0 {
continue
}
if need[num] > 0 {
need[num]--
need[num+1]++
} else if freq[num+1] > 0 && freq[num+2] > 0 {
freq[num+1]--
freq[num+2]--
need[num+3]++
} else {
return false
}
freq[num]--
}
return true
}Algorithm
Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.
Создание подпоследовательностей:
Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.
Пройдите по каждому элементу в массиве и выполните следующие действия:
Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.
Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.
Если ни одно из условий не выполнено, верните false.
Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.