سلام بچه ها! نایان اینجاست و این بیست و چهارمین روز از چالش 100 روزه است. اگر برای اولین بار است که این مطلب را می خوانید، من در طول روز چند سوال را یاد می گیرم و حل می کنم و آنها را اینجا ارسال می کنم.
بیایید درست به مشکل برسیم.
مشکل: دنباله تکان دادن
دنباله تکان دادن دنباله ای است که در آن تفاوت بین اعداد متوالی بین مثبت و منفی متناوب است. اولین تفاوت (در صورت وجود) ممکن است مثبت یا منفی باشد. دنباله‌ای با یک عنصر و دنباله‌ای با دو عنصر غیرمساوی، توالی‌های بی‌اهمیت تکان دادن هستند.
- مثلا، [1, 7, 4, 9, 2, 5] یک دنباله تکان دهنده است زیرا تفاوت های (6، -3، 5، -7، 3) بین مثبت و منفی متناوب است.
- متقابلا، [1, 4, 7, 2, 5] و [1, 7, 4, 5, 5] دنباله های تکان دادن نیستند. اولی به این دلیل نیست که دو تفاوت اول آن مثبت است و دومی به این دلیل نیست که آخرین تفاوت آن صفر است.
- یک دنباله با حذف برخی از عناصر (احتمالاً صفر) از دنباله اصلی به دست می آید و بقیه عناصر به ترتیب اصلی خود باقی می مانند.
با توجه به اعداد آرایه اعداد صحیح، طول طولانی‌ترین دنباله تکان دادن اعداد را برگردانید.
مثال:
ورودی: nums = [1,7,4,9,2,5]
خروجی: 6
توضیح: کل دنباله یک دنباله تکان دادن با تفاوت (6، -3، 5، -7، 3) است.
بینش:
سوال بسیار سرراست است. اگرچه یک اشتباه رایج که می توان انجام داد این است که به جای دنباله تکان دادن، طول تفاوت ها را برگرداند.
بیایید با مشاهدات شروع کنیم و سپس راه حل را بیشتر بهینه کنیم. ما مشکلات بعدی زیادی را انجام داده‌ایم و ذهن ما تقریباً یک بار دیگر الگوی انتخاب عنصر و عدم انتخاب عنصر را تشخیص می‌دهد.
بنابراین ما دقیقاً این کار را با استفاده از بازگشت انجام می دهیم و DP حافظه را به آن اضافه می کنیم تا پیچیدگی زمانی نمایی را بهینه کنیم.
رویکرد:
- ما از آخرین شاخص شروع می کنیم و زمانی که به آخرین شاخص رفتیم متوقف می شویم زیرا نمی توانیم تفاوت آن را محاسبه کنیم. از این رو حالت پایه ما در این مورد if (index <= 0) است. بنابراین ما 0 را برمی گردانیم.
- اگر تصمیم بگیریم عنصر را انتخاب نکنیم، به سادگی در مسیر حرکت خود به جلو حرکت می کنیم.
- اکنون مشاهده کنید که باید دو پارامتر در حال تغییر را حفظ کنیم. یکی شاخص و دوم آخرین علامت تفاوت قبلی است. از این رو ما باید انتخاب خود را دقیقاً آن شرایط را اعمال کنیم. از آنجایی که 0 نه مثبت است و نه منفی، هر زمان که با اختلاف 0 مواجه شدیم، false را برمی گردانیم.
بیایید آن را کدگذاری کنیم.
کد:
class Solution {
public:
int helper(int idx, vector<int>& nums, int n, int lastSign, vector<vector<int>> &dp){
if(idx <= 0){
return 0;
}
int notPick = 0 + helper(idx-1,nums,n, lastSign,dp);
int pick = 0;
if(dp[idx][lastSign] != -1) return dp[idx][lastSign];
if(nums[idx]- nums[idx-1] < 0 && lastSign == 1 || nums[idx]-nums[idx-1] < 0 && lastSign == 2){
pick = 1 + helper(idx-1,nums,n,0,dp);
}
else if(nums[idx]- nums[idx-1] > 0 && lastSign == 0 || nums[idx]-nums[idx-1] > 0 && lastSign == 2){
pick = 1 + helper(idx-1,nums, n, 1,dp);
}
return dp[idx][lastSign] = max(notPick, pick);
}
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
int lastSign;
vector<vector<int>> dp(n, vector<int>(3,-1));
return helper(n-1,nums,n,2,dp)+1;
}
};
پیچیدگی زمانی: O(3*N)
پیچیدگی فضا: O (N*3) + O (N)
ما می توانیم این را با استفاده از روش جدول بندی بیشتر بهینه کنیم.
- ما شاخص خود را در رویکرد فوق افزایش خواهیم داد به طوری که برای جدول بندی از محدوده خارج نشویم زیرا می توانیم فقط نمایه سازی بر اساس 0 داشته باشیم.
- ما همچنین موارد پایه را ایجاد کرده و آنها را ذخیره می کنیم، اما نیازی به این کار نداریم، زیرا قبلاً آرایه خود را به صورت 0 مقداردهی اولیه کرده ایم. Rest کد ما نیز از همان منطق پیروی می کند.
کد:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
int lastSign;
vector<vector<int>> dp(n+1, vector<int>(3,0));
for(int sign = 0; sign <=2; sign++){
dp[0][sign] = 0;
dp[1][sign] = 0;
}
for(int idx = 2; idx < n+1; idx++){
for(int sign = 2; sign >= 0; sign--){
int notPick = 0 + dp[idx-1][sign];
int pick = 0;
if(nums[idx-1]- nums[idx-2] < 0 && sign == 1 || nums[idx-1]-nums[idx-2] < 0 && sign == 2){
pick = 1 + dp[idx-1][0];
}
else if(nums[idx-1]- nums[idx-2] > 0 && sign == 0 || nums[idx-1]-nums[idx-2] > 0 && sign == 2){
pick = 1 + dp[idx-1][1];
}
dp[idx][sign] = max(pick,notPick);
}
}
return dp[n][2] + 1;
}
پیچیدگی زمانی: O(3*N).
پیچیدگی فضا: O (N*3). فضای اضافی به دلیل پشته بازگشتی حذف شد
در اینجا می‌توانیم به وضوح ببینیم که آرایه ما به جای آرایه کامل به ردیف lastSign بستگی دارد و از این رو می‌توانیم فضای آن را حتی بیشتر بهینه کنیم.
کد:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
int lastSign;
vector<int> prev(3,0);
vector<int> cur(3,0);
for(int idx = 2; idx < n+1; idx++){
for(int sign = 2; sign >= 0; sign--){
int notPick = prev[sign];
int pick = 0;
if(nums[idx-1]- nums[idx-2] < 0 && sign == 1 || nums[idx-1]-nums[idx-2] < 0 && sign == 2){
pick = 1 + prev[0];
}
else if(nums[idx-1]- nums[idx-2] > 0 && sign == 0 || nums[idx-1]-nums[idx-2] > 0 && sign == 2){
pick = 1 + prev[1];
}
cur[sign] = max(pick,notPick);
}
prev = cur;
}
return prev[2] + 1;
}
پیچیدگی زمانی: O(3*N).
پیچیدگی فضا: O (1). فضای اضافی حذف شد.
یک رویکرد O(N) برای این سوال با استفاده از رویکرد حریصانه وجود دارد.
ما دو اشاره گر را حفظ می کنیم.
- بررسی کنید که طول اعداد فهرست ورودی کمتر از 2 باشد. اگر بله، طول اعداد را برگردانید. این به این دلیل است که یک دنباله با یک عنصر و یک دنباله با دو عنصر غیر مساوی، دنباله‌های بی‌اهمیت تکان دادن هستند. اگر تفاوت مثبت باشد و lastSign ما مثبت نبود یا برعکس منفی و lastSign منفی نبود، maxLen را افزایش می دهیم و lastSign را به روز می کنیم.
کد:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(n < 2) return n;
int maxLen = 1;
int lastSign;
for(int i = 1; i < n; i++){
int diff = nums[i]-nums[i-1];
if(diff > 0 && lastSign != 1 || diff < 0 && lastSign != -1){
maxLen++;
if(diff > 0){
lastSign = 1;
}
else
{
lastSign = -1;
}
}
}
return maxLen;
}
پیچیدگی زمانی: O(N)
پیچیدگی فضایی: O(1)
