Вам дан 0-индексированный массив целых чисел nums
. Вы должны разделить массив на один или несколько непрерывных подмассивов.
Мы называем разбиение массива действительным, если каждый из полученных подмассивов удовлетворяет одному из следующих условий:
- Подмассив состоит из ровно
2
одинаковых элементов. Например, подмассив[2,2]
хорош. - Подмассив состоит из точно
3
одинаковых элементов. Например, подмассив[4,4,4]
хорош. - Подмассив состоит из ровно
3
последовательных возрастающих элементов, то есть разница между соседними элементами составляет1
. Например, подмассив[3,4,5]
хорош, а подмассив[1,3,5]
— нет.
Вернуть true
, если массив имеет по крайней мере один действительный раздел. В противном случае вернуть false
.
Пример 1:
Input: nums = [4,4,4,5,6] Output: true Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6]. This partition is valid, so we return true.
Пример 2:
Input: nums = [1,1,1,2] Output: false Explanation: There is no valid partition for this array.
Ограничения:
2 <= nums.length <= 105
1 <= nums[i] <= 106
class Solution { public: bool solve(vector<int> &nums, vector<int> &dp, int i){ int n=nums.size(); if(i==n) return true; if(dp[i]!=-1) return dp[i]; bool res=false; if(i+1<n && nums[i]==nums[i+1]){ res=solve(nums, dp, i+2); if(i+2<n && nums[i]==nums[i+2]){ res=res|| solve(nums, dp, i+3); } } if(i+2<n && nums[i+1]-nums[i]==1 && nums[i+2]-nums[i+1]==1){ res=res|| solve(nums, dp, i+3); } return dp[i]=res; } bool validPartition(vector<int>& nums) { int n=nums.size(); if(n==2){ if(nums[0]==nums[1]) return true; } vector<int> dp(n, -1); return solve(nums, dp, 0); } };
Изначально, если длина массива или размер nums равны 2, то возможен только один случай, когда он возвращает true, т.е. nums[0]==nums[1], таким образом, оба являются равными элементами, а для остальных применяется DP :)
Пример 1
Проверьте наличие двух последовательных равных элементов, если они равны, затем сделайте еще один вызов для дальнейшей проверки в массиве, это делается DP, поэтому напряжение не … только проверьте nums [i] == nums [i + 1]… & make res = true и далее проверьте три последовательных одинаковых элемента, если они равны, затем сделайте еще один вызов для дальнейшей проверки в этом массиве, это делается DP.
разрешение = разрешение || solve( — ) // в этом res будет установлено значение true, если первые 2 элемента равны, затем проверьте дальнейший вызов.
Если все I случай и II случай не работают, проверьте для III случая 3 возрастающих числа.
Пример 2
Спасибо !! Счастливого обучения :)