Python3 ծրագիր՝ ձախ և աջ պտույտ ունեցող թվի ամենաերկար ենթահաջորդության համար
Այս խնդիրում մենք կգտնենք տվյալ տողի ամենաերկար ենթահաջորդության երկարությունը, որպեսզի այն ունենա աջ և ձախ պտույտ:
Խնդիրը կարող ենք լուծել՝ գտնելով տրված տողի բոլոր ենթահաջորդականությունները և ստուգելով, թե արդյոք որոշակի ենթահաջորդություններ ունեն նույն պտույտը աջ և ձախ։ Մյուս մոտեցումը օգտագործում է այն դիտարկումը, որ տողը կարող է ունենալ միայն ձախ և աջ պտույտ նույնը, եթե այն պարունակում է մեկ նիշ կամ այլընտրանքային նիշ, իսկ ձախը հավասար է:
Խնդրի հայտարարություն – Մենք տվել ենք ալֆա տող, որը պարունակում է միայն թվային թվեր: Պետք է գտնել տողի ամենաերկար ենթահաջորդության չափը, որն ունի աջ և ձախ պտույտներ։
Նմուշի օրինակներ
Մուտք
alpha = "700980503"
Ելք
4
Բացատրություն – Ամենաերկար ենթահաջորդականությունը, որն ունի նույն պտույտը աջ և ձախ, դա «0000»-ն է:
Մուտք
alpha = ‘19199019’
Ելք
6
Բացատրություն – Ստացված ենթահաջորդականությունը «191919» է:
Մուտք
alpha = ‘13141115611171’
Ելք
9
Բացատրություն – Ամենաերկար ենթահաջորդությունը, որն ունի նույն պտույտը աջ և ձախ, դա «111111111» է:
Մոտեցում 1
Այս մոտեցմամբ մենք կգտնենք տվյալ տողի բոլոր ենթահաջորդականությունները։ Դրանից հետո մենք կօգտագործենք Python զանգվածի կտրումը, որպեսզի ստուգենք, թե արդյոք ենթահաջորդականությունը ունի նույն պտույտը աջ և ձախ:
Ալգորիթմ
Քայլ 1 – Նախաստորագրեք «maxLen»-ը -1-ով` պահպանելու ենթահաջորդության առավելագույն երկարությունը:
Քայլ 2 – Կանչեք getSubs() ֆունկցիան՝ ստանալու համար տրված տողի բոլոր ենթահաջորդությունները:
Քայլ 2.1 – getSubs() ֆունկցիայում սկզբնավորեք «allSubs» զանգվածը մեկ դատարկ տողային տարրով:
Քայլ 2.2 – Սկսեք անցնել տողը և ստեղծեք զանգվածի պատճենը «temp» փոփոխականում:
Քայլ 2.3 – Անցեք «temp» զանգվածը և ավելացրեք «ch» նիշը ժամանակավոր զանգվածի հաջորդականությանը: Դրանից հետո «allSubs» զանգվածում տեղադրեք նոր ենթահաջորդություն:
Քայլ 2.4 – Վերադարձեք «allSubs» զանգվածը:
Քայլ 3 – Բոլոր ենթահաջորդությունները ստանալուց հետո անցեք ենթահերթությունների զանգվածը:
Քայլ 4 – Կտրեք ենթահաջորդականությունը՝ օգտագործելով subseq[1:] + subseq[:1]՝ ձախ ռոտացիան ստանալու համար: Նաև կտրատեք ենթահաջորդականությունը՝ օգտագործելով subseq[str_len - 2:] + subseq[:str_len - 2]՝ ճիշտ պտույտ ստանալու համար:
Քայլ 5 – Եթե ձախ և աջ պտույտը նույնն է, թարմացրեք maxLen արժեքը, եթե այն փոքր է ենթահերթականի երկարությունից:
Քայլ 6 – Վերադարձրեք «maxLen» փոփոխականի արժեքը:
Օրինակ
def getSubs(alpha):
allSubs = ['']
for ch in alpha:
# Create a copy of the array containing all subsequences
temp = allSubs[:]
# Append character to each subsequence of the array to generate new subsequences
for subseq in temp:
allSubs.append(subseq + ch)
return allSubs
def maxSubSeqLen(alpha):
maxLen = -1
str_len = len(alpha)
allSubs = getSubs(alpha)
# Traverse all subsequences
for subseq in allSubs:
# check if the subsequence has the same left and right rotation
if subseq[1:] + subseq[:1] == subseq[str_len - 2:] + subseq[:str_len - 2]:
maxLen = max(maxLen, len(subseq))
# Return the answer
return maxLen
alpha = "1919019"
print("The maximum length of subsequence having the same left and right rotations is - ")
print(maxSubSeqLen(alpha))
Արդյունք
The maximum length of subsequence having the same left and right rotations is -
6
Ժամանակի բարդություն – O(2N), քանի որ գտնում ենք տվյալ տողի բոլոր ենթահաջորդականությունները։
Տիեզերական բարդություն – O(2N), քանի որ մենք պահում ենք տվյալ տողի բոլոր ենթահաջորդականությունները:
Մոտեցում 2
Այս մոտեցման մեջ մենք կօգտագործենք դիտարկումը՝ հիմնված խնդրի մուտքագրման և արդյունքի վրա: Տողը կարող է ունենալ միայն ձախ և աջ պտույտ նույնը, եթե տողը պարունակում է բոլոր նույն նիշերը կամ ունի հավասար երկարություն և պարունակում է այլընտրանքային նիշեր:
Այսպիսով, մենք կգտնենք ամենաերկար ենթահաջորդությունները ըստ երկու պայմանների:
Ալգորիթմ
Քայլ 1 – Նախաձեռնեք «maxLen» փոփոխականը -1-ով:
Քայլ 2 – Օգտագործեք օղակը՝ 0-ից 9-ը անցնելու համար: Նաև օգտագործեք մեկ այլ ներդիր օղակ՝ 0-ից 9-ը անցնելու համար: Այստեղ մենք կազմում ենք զույգ թվանշաններ, ինչպիսիք են 00, 01, 02, … 01, 12, 13, 14,… 97, 98, 99 և այլն: Այսպիսով, մենք կգտնենք տվյալ տողի թվանշանների զույգը և կվերցնենք ենթահերթականի առավելագույն երկարությունը:
Քայլ 3 – Նախաձեռնեք «currMax» և «isSecond» փոփոխականները 0-ով, որպեսզի պահպանեք թվերի առկա զույգերի ընդհանուր թիվը տվյալ տողում և հետևեք զույգի առաջին կամ երկրորդ նիշը գտնելուն: տողի մեջ՝ այլընտրանքային ենթահաջորդություն ստեղծելու համար:
Քայլ 4 - Սկսեք անցնել տողը: Եթե «isSecond»-ը հավասար է 0-ի, իսկ նիշը հավասար է «p»-ի, «isSecond»-ը փոխեք 1-ի և «currMax» արժեքը ավելացրեք 1-ով:
Քայլ 5 - Եթե «isSecond»-ը հավասար է 1-ի, իսկ նիշը հավասար է «q»-ի, փոխեք «isSecond»-ը 0-ով և ավելացրեք «currMax» արժեքը 1-ով:
Քայլ 6 – Եթե p-ն և q-ն նույնը չեն, իսկ «currMax»-ը կենտ է, ապա դրա արժեքը նվազեցրեք 1-ով:
Քայլ 7 – Թարմացրեք «maxLen»-ի արժեքը, եթե այն փոքր է «currMax» փոփոխականի արժեքից:
Քայլ 8 – Վերադարձրեք «maxLen» արժեքը:
Օրինակ
def maxSubSeqLen(alpha):
# Length of the string
str_len = len(alpha)
maxLen = -1
# Travere the string
for p in range(10):
for q in range(10):
currMax, isSecond = 0, 0
# Find an alternate combination of p and q
for k in range(str_len):
# Finding the p
if (isSecond == 0 and ord(alpha[k]) - ord('0') == p):
isSecond = 1
# Increase the current value by 1
currMax += 1
# Finding q
elif (isSecond == 1 and ord(alpha[k]) - ord('0') == q):
isSecond = 0
# Increase the current value by 1
currMax += 1
# For odd length of resultant subsequence.
if p != q and currMax % 2 == 1:
# Decrease the value of currMax by 1
currMax -= 1
# Get maximum length
maxLen = max(currMax, maxLen)
# Return the answer
return maxLen
# Driver code
alpha = "700980503"
print("The maximum length of subsequence having the same left and right rotations is - ")
print(maxSubSeqLen(alpha))
Արդյունք
The maximum length of subsequence having the same left and right rotations is -
4
Ժամանակի բարդություն – O(N*10*10) ~ O(N) տողով անցնելու համար:
Տիեզերքի բարդություն – O(1), քանի որ մենք չենք օգտագործում լրացուցիչ տարածք:
Առաջին մոտեցումը ժամանակատար է, քանի որ մենք գտնում ենք տվյալ տողի բոլոր ենթահաջորդությունները: Երկրորդ մոտեցումը լավագույն մոտեցումներից մեկն է, քանի որ այն ունի նվազագույն ժամանակային բարդություն: Ծրագրավորողները կարող են փորձել գտնել ամենաերկար ենթատողը, որն ունի նույն ձախ և աջ պտույտը ավելի շատ պրակտիկայի համար: