Python3 ծրագիր՝ նիշերը նվազագույնի հասցնելու համար, որը պետք է փոխվի՝ տողի ձախ և աջ պտույտը նույնը դարձնելու համար

Պտտումը նշանակում է, որ մենք պետք է տեղափոխենք յուրաքանչյուր նիշ կամ առաջ կամ ետ: Առաջ ուղղությունը նշանակում է պտտում աջ (Կամ ժամսլաքի հակառակ ուղղությամբ), իսկ հետընթացը նշանակում է ձախ պտույտ (կամ ժամացույցի սլաքի ուղղությամբ):

Այս խնդրի մեջ մենք տվել ենք n չափի տող: Մեր խնդիրն է գտնել փոփոխվող նիշի նվազագույն թիվը՝ ստուգելու համար, թե արդյոք հնարավո՞ր է տողի ձախ և աջ պտույտը կատարել նույնը:

Եկեք տեսնենք ստորև բերված բացատրություններով օրինակներ՝ խնդիրը ավելի լավ հասկանալու համար:

Մուտք 1

str = "wxyz"

Ելք 1

2

Բացատրություն

Լարի ձախ պտույտը xyzw է

Լարի ճիշտ պտույտը zwxy է

Այսպիսով, ըստ դիտարկման, փոխեք նիշը 0 str[0]=w դիրքում դեպի y և 3 str[3]=z դիրքում դեպի x: Շարանը դառնում է yxyx:

Հետևաբար, պատասխանը 2 է, քանի որ ձախ և աջ պտտվող տողը դառնում է xyxy:

Մուտք 2

str = "aka"

Ելք 2

1

Բացատրություն

Լարի ձախ պտույտը aak է

Լարի ճիշտ պտույտը կաա է

Այսպիսով, ըստ դիտարկման, փոխեք նիշը 1 str[1]=k դիրքում դեպի a: Շարանը դառնում է աաա։

Հետևաբար, պատասխանը 1 է, քանի որ ձախ և աջ պտտվող տողը դառնում է aaa:

Մոտեցում

Վերը նշված տողի օրինակը տեսնելուց հետո անցնենք մեթոդին։

Այս մոտեցման գաղափարը հիմնված է դիտարկման վրա: Դիտարկումն ունի երկու կետ.

• երբ մենք ունենք զույգ երկարությամբ տող, ապա զույգ ինդեքսում և կենտ ինդեքսում առկա բոլոր նիշերը պետք է լինեն նույնը, որպեսզի ստանանք և՛ աջ, և՛ ձախ պտտվող տողերը:

• Երբ մենք ունենք կենտ երկարությամբ տող, ապա տողի բոլոր նիշերը պետք է նույնը լինեն, որպեսզի ստանանք թե՛ աջ, թե՛ ձախ պտտվող տողերը:

Եկեք տեսնենք ստորև բերված կոդը՝ վերը նշված մոտեցման ավելի լավ հասկանալու համար:

Օրինակ

# Function to find the minimum characters to be removed from the string
def getMinimumChange(str, n):
   # Initialize answer by N in variable minNum
   minChanges = n
   # If the length of the string is even
   if (n % 2 == 0):
      # Created frequency array for Even index
      freqEvenIdx = {}
      # Created frequency array for odd index
      freqOddIdx = {}
      # Traverse for loop to intialize both the frequency array freqEvenddIdx and freqOddIdx to 0
      for ch in range(ord('a'), ord('z') + 1):
         freqEvenIdx[chr(ch)] = 0
         freqOddIdx[chr(ch)] = 0
      # at odd and even index
      for i in range(n):
         if (i % 2 == 0):
            if str[i] in freqEvenIdx:
               freqEvenIdx[str[i]] += 1
         else:
            if str[i] in freqOddIdx:
               freqOddIdx[str[i]] += 1
      # Create variable evenIdxMax and OddIdxMax to store maximum frequency of even place character and odd place character respectively
      evenIdxMax = 0
      oddIdxMax = 0
      # Traverse for loop from a to z to update variable evenIdxMax and OddIdxMax
      for ch in range(ord('a'), ord('z') + 1):
         evenIdxMax = max(evenIdxMax, freqEvenIdx[chr(ch)])
         oddIdxMax = max(oddIdxMax, freqOddIdx[chr(ch)])
      # Update the answerin variable minChanges
      minChanges = minChanges - evenIdxMax - oddIdxMax
   # If the length of the string is odd
   else:
      # Create array to store frequecy of character of the string
      freq = {}
      #  initialize the the freq array
      for ch in range('a', 'z'):
         freq[chr(ch)] = 0
      # Stores the frequency of the characters of the string while traversing the string
      for i in range(n):
         if str[i] in freq:
            freq[str[i]] += 1
      # Stores the maximum freuency of character of the string in variable freqMax
      freqMax = 0
      #  Traverse the for loop to update freqMax
      for ch in range('a', 'z'):
         freqMax = max(freqMax, freq[chr(ch)])
      # Update the answer in variable minChanges
      minChanges = minChanges - freqMax
# Return final answer minChanges
   return minChanges
str = "wxyz"  # Given String
n = len(str)  # Getting size of the given string
# Call the function to get minimum number of changes to make left and right rotated string same
res = getMinimumChange(str, n)
# Print result
print(
   "The minimum number of changes to make the left and right rotated string same are: "
)
print(res)

Արդյունք

The minimum number of changes to make the left and right rotated string same are: 
2

Ժամանակի և տարածության բարդություն

Վերոնշյալ կոդի ժամանակային բարդությունը O(N) է, քանի որ մենք անցնում ենք և՛ զսպանակը, և՛ թիվը:

Վերոնշյալ կոդի տիեզերական բարդությունը O(1) է, քանի որ որևէ լրացուցիչ տարածք չի օգտագործվում որևէ բան պահելու համար:

Որտեղ N-ը տողի չափն է:

Եզրակացություն

Այս ձեռնարկում մենք իրականացրել ենք Python3 ծրագիր՝ նվազագույնի հասցնելու նիշերը, որոնք պետք է փոխվեն՝ տողի ձախ և աջ պտույտը նույնը դարձնելու համար: Մենք ներդրել ենք հաշինգի մոտեցում, քանի որ մենք պետք է պահպանենք հաճախականությունը: Ժամանակի բարդությունը O(N) է, իսկ O(1)-ի և N-ի տարածության բարդությունը տվյալ տողի չափն է: