የአንድ የተሰጠ ሕብረቁምፊ ከፍተኛ ክብደት መለወጥ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ብላክ ሮክ ByteDance የኮድ ቁጥር ዴ ሻው Expedia ጂፒ ሞርጋን ኦላ ካብስ
ተለዋዋጭ ፕሮግራም ሕብረቁምፊ

የችግሩ መግለጫ

የተሰጠው የሕብረቁምፊ ችግር ከፍተኛው የክብደት ለውጥ ‹A› እና ‹B› ን የያዘ ሁለት ቁምፊ ብቻ የያዘ ክርክር ይሰጠዋል ፡፡ ማንኛውንም ቁምፊ በመቀየር ሕብረቁምፊን ወደ ሌላ ገመድ የምንለውጥበት ክዋኔ አለን ፡፡ ስለሆነም ብዙ ለውጦች አሉ ፡፡ ከሁሉም ሊለወጡ ከሚችሉት ለውጦች መካከል ከፍተኛውን የክብደት ለውጥ ክብደት ይወቁ ፡፡

አልጎሪዝም

Weight of string = weight of total pairs + weight of single characters - total number of toggles.
Two different consecutive characters are considered as pairs.
Weight of single pair (both characters are different) = 2
Weight of single character = 1
(These values are just some random values and can be taken as input)

ለምሳሌየአንድ የተሰጠ ሕብረቁምፊ ከፍተኛ ክብደት መለወጥ

BA
2

ማብራሪያ:

ወደ ህብረቁምፊ “AA” አራት አማራጮች አሉ ፣ ወደ እነዚህ የሚከተሉት ወደ

AB → 2 - 1 = 1

ቢኤ → 2 - 1 = 1

AA → 2

ቢቢ → 2

እነዚህ ሁሉ ለውጦች ተመሳሳይ ስለመሆናቸው ከሚኖሩ ለውጦች መካከል አንዱን መምረጥ እንችላለን ፡፡

BAA
3

ማብራሪያ-በጠቅላላው 8 ለውጦች አሉ ፣ ከእነዚህ ውስጥ አንድ ጥንድ እና አንድ ነጠላ ገጸ-ባህሪ ያላቸው ለውጦች ከፍተኛው እሴት አላቸው ፡፡

 

የተሰጠው ሕብረቁምፊ ለከፍተኛው የክብደት ለውጥ አቀራረብ

የዋህ አቀራረብ

እያንዳንዱን ባሕርይ በመቀየር ሁሉንም ሊሆኑ የሚችሉ ለውጦችን እናደርጋለን ፡፡ ሁሉንም ለውጦች ካደረግን በኋላ የእያንዳንዱን ለውጥ ዋጋ እናገኛለን ከዚያም የእያንዳንዱን ለውጥ ዋጋ በማስላት ከፍተኛውን እሴት እናገኛለን ፡፡

ውጤታማ አቀራረብ

ስሌቶችን ለመቀነስ በመከርከም የተሰጠ ሕብረቁምፊ ከፍተኛውን የክብደት ለውጥ ለማግኘት እንደገና መመለስን እንጠቀማለን። የወቅቱ ገጸ-ባህሪ እና ሁለተኛው ባህሪ ከሌለን ይህ ያ ጥንድ ነው። በዚህ አጋጣሚ እኛ ሁለት አማራጮችን አለን ወይ የመጀመሪያውን ገፀ ባህሪ ቀይረን ወደፊት እንራመድ ወይም ቁምፊዎቹን ቀያይረን ወደ ፊት አንጓዝ ፡፡ ሌላኛው ሁኔታ የአሁኑ ባህሪ እና ሁለተኛ ቁምፊዎች አንድ ዓይነት ሲኖረን ነው ፡፡ በዚህ አጋጣሚ ገጸ-ባህሪውን ቀይረን ጥንድ እናደርጋለን ፣ ወይም እኛ አናደርገውም እና ወደፊት እንቀጥላለን ፡፡

የመጀመሪያ (ወይም የመጀመሪያው) ችግር ወደ ትናንሽ ንዑስ ችግሮች ሊቀየር ስለሚችል እኛ እንጠቀማለን ተለዋዋጭ ፕሮግራም ንዑስ ችግሮቹን ለማከማቸት እና የበለጠ እነሱን ለመጠቀም ፡፡

ኮድ

ለተሰጠው የሕብረቁምፊ ችግር ከፍተኛ የክብደት ለውጥ C ++ ኮድ

#include<bits/stdc++.h>
using namespace std;

int pairCost, toggleCost;

int maxWeightOfTransformation(string s, vector<int> &dp, int i, int stringLength){
    //base case
    if(i>=stringLength)
        return 0;
    if(dp[i]!=-1)
        return dp[i];

    // consider current character as a single character(not a pair)
    int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
    if(i+1<stringLength){
        if(s[i]!=s[i+1])
            answer = max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        else
            answer = max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
    }
    return dp[i] = answer;
}

int main()
{
    string s;cin>>s;
    cout<<"Enter pairCost and toggleCost"<<endl;
    cin>>pairCost>>toggleCost;
    int stringLength = s.size();
    vector<int> dp(stringLength, -1);
    cout << "Maximum weight of a transformation of "<<s<<" is " <<maxWeightOfTransformation(s, dp, 0, stringLength);
    return 0;
}
AB
Enter pairCost and toggleCost
2 1
Maximum weight of a transformation of AB is 2

ለተሰጠው ሕብረቁምፊ ከፍተኛ ክብደት ለመለወጥ የጃቫ ኮድ

import java.util.*;

class Main{
    static int pairCost, toggleCost;
    
    static int maxWeightOfTransformation(String s, int[] dp, int i, int stringLength){
        //base case
        if(i>=stringLength)
            return 0;
        if(dp[i]!=-1)
            return dp[i];
    
        // consider current character as a single character(not a pair)
        int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
        if(i+1<stringLength){
            if(s.charAt(i)!=s.charAt(i+1))
                answer = Math.max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
            else
                answer = Math.max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        }
        return dp[i] = answer;
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println("Enter pairCost and toggleCost");
        pairCost=sc.nextInt();
        toggleCost=sc.nextInt();
        int stringLength = s.length();
        int dp[] = new int[stringLength];
        for(int i = 0;i<stringLength;i++)dp[i]=-1;
        int answer = maxWeightOfTransformation(s, dp, 0, stringLength);
        System.out.println("Maximum weight of a transformation of "+s+" is "+answer);
    }
}
AB 
Enter pairCost and toggleCost 
2 1
Maximum weight of a transformation of AB is 2

ውስብስብነት ትንተና

የጊዜ ውስብስብነትኦ (ኤን)

እኛ 1 ዲ ዲ ፒ እየተጠቀመ ያለ ስልተ ቀመር ስለምንጠቀም እና በክፍለ-ግዛቶች መካከል የሚደረግ ሽግግርም እንዲሁ O (1) ነው ፡፡ ይህ አልጎሪዝም በ O (N) ጠቅላላ የጊዜ ውስብስብነት ውስጥ እንዲሠራ ያደርገዋል።

የቦታ ውስብስብነትኦ (ኤን)

እዚህ ለዲፒ የ 1 ዲ ድርድርን ተጠቅመናል ፣ ስለሆነም አልጎሪዝም የ O (N) የቦታ ውስብስብነት አለው ፡፡