د ورکړل شوي مزي څخه د اعظمي وزن بدلیدل


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon تورکاک ByteDance کوډ نیټه DE شا ايکسپيډيا JP Morgan اولا کیبونه
متحرک برنامې تار

ستونزه بیان

د ورکړل شوې تار ستونزې د اعظمي حد اعظمي بدلون وايي چې یوازې دوه حرفې '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

BA → 2 - 1 = 1

AA → 2

بی بی → 2

څنګه چې دا ټول بدلونونه ورته وزن لري ، نو موږ کولی شو د هرډول ممکنه بدلونونو څخه یو غوره کړو.

BAA
3

توضیحي: په مجموعي ډول trans بدلونونه شتون لري ، له هغې جملې څخه چې یوه جوړه او یو واحد کردار لري هغه اعظمي ارزښت لري.

 

د ورکړل شوي تار د اعظمي وزن د بدلون لپاره تګلاره

بې لارې چلند

موږ د هرې کرکټر د بدلولو سره ټول ممکنه بدلونونه کوو. د ټولو بدلونونو رامینځته کولو وروسته موږ د هر بدلون ارزښت ومومئ او بیا د هر بدلون لپاره محاسبه کولو سره اعظمي ارزښت ومومئ.

اغیزمنه کړنلاره

موږ به د تکرار په کارولو سره د محاسبې کمولو لپاره د ټاکل شوي تار تار اعظمي وزن لیږد موندلو لپاره تکرار وکاروو. که موږ اوسنی کرکټر او دوهم کرکټر توپیر ولرو ، دا دا جوړه ده. پدې حالت کې ، موږ دوه اختیارونه لرو یا نو موږ لومړی کرکټر بدل کړو او مخکې لاړ شو یا موږ د کرکټرونو تغیر او وړاندې تګ نه کوو. بل حالت به دا وي کله چې موږ اوسني کرکټر او دوهم حروف ورته یو. په دې حالت کې ، موږ به کرکټر ٹوگل او دا جوړه جوړه کړو ، یا موږ نه شو او پرمخ لاړ شو.

څنګه چې لومړنۍ (یا اصلي) ستونزه په کوچني فرعي ستونزو کې بدله کیدی شي ، نو موږ به یې وکاروو متحرک برنامه د فرعي ستونزو ذخیره کولو لپاره او نور یې کارول.

کوډ

د ورکړل شوي تار ستونزه د اعظمي وزن بدلون لپاره 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

د پیچلتیا تحلیل

د وخت پیچلتیا: O (N)

لدې چې موږ الګوریتم کارولی دی چې د 1D DP کاروي ، او د دولتونو ترمنځ لیږد هم O (1) دی. دا د O (N) ټول وخت پیچلتیا کې الګوریتم چلوي.

د ځای پیچلتیا: O (N)

دلته موږ د DP لپاره 1D سرنی کارولی دی ، پدې توګه الګوریتم د O (N) ځای پیچلتیا لري.