Java >> Java tutorial >  >> Tag >> Stack

Korrekt algoritme for spil med to stakke på HackerRank

Stack

Ok, jeg vil prøve at forklare en algoritme, som grundlæggende kan løse dette problem med O(n), du skal prøve at kode det selv.

Jeg vil forklare det på det simple eksempel, og du kan afspejle det

1 -> Number of games
10 -> sum should not exceed 10  
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B

Først skal du oprette 2 arrays, arrayet vil indeholde summeringen af ​​alle tallene op til dets indeks af stakken, for eksempel for stak A vil du have dette array

4 6 10 16 17  //index 0 ->4

Det samme vil blive gjort for stak B

2 3 11 16

start derefter for hvert array at iterere fra slutningen af ​​arrayet, indtil du når et tal mindre end eller lig med "summen du ikke bør overskride"

nu er din nuværende sum summen af ​​det punkt, du nåede i begge arrays, bør være 10 +3 =13, så for at nå 10 skal du absolut fjerne flere poster

for at fjerne de ekstra indgange flytter vi indekserne på arrayet igen, for at beslutte, hvilket array der skal flyttes dets indeks, skal du tage den indgang, du peger på (10 for array 1 og 3 for array 2) og opret den med index+1 ( 10/3 ~ 3), (3/2 ~1) flyt derefter indekset for den højeste værdi og genberegn summen

Hvis begge værdier er ens, er det logisk at flytte indekset til den værdi, der har større forskel med dens tidligere (husk, at vi flytter indekset i omvendt rækkefølge).

resultatet vil være summen af ​​indekserne +2.


Denne løsning fungerer godt .... jeg håber det hjælper ...

   import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int g = sc.nextInt();
        for (int tc = 0; tc < g; tc++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int x = sc.nextInt();
            int[] a = readArray(sc, n);
            int[] b = readArray(sc, m);

            System.out.println(solve(a, b, x));
        }

        sc.close();
    }

    static int[] readArray(Scanner sc, int size) {
        int[] result = new int[size];
        for (int i = 0; i < result.length; i++) {
            result[i] = sc.nextInt();
        }
        return result;
    }

    static int solve(int[] a, int[] b, int x) {
        int lengthB = 0;
        int sum = 0;
        while (lengthB < b.length && sum + b[lengthB] <= x) {
            sum += b[lengthB];
            lengthB++;
        }

        int maxScore = lengthB;
        for (int lengthA = 1; lengthA <= a.length; lengthA++) {
            sum += a[lengthA - 1];

            while (sum > x && lengthB > 0) {
                lengthB--;
                sum -= b[lengthB];
            }

            if (sum > x) {
                break;
            }

            maxScore = Math.max(maxScore, lengthA + lengthB);
        }
        return maxScore;
    }
}

løsning i python3

# stack implementation
class Stack:
    lis = []

    def __init__(self, l):
        self.lis = l[::-1]

    def push(self, data):
        self.lis.append(data)

    def peek(self):
        return self.lis[-1]

    def pop(self):
        self.lis.pop()

    def is_empty(self):
        return len(self.lis) == 0


# number of test cases
tests = int(input())
for i in range(tests):
    na, nb, x = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))
    temp = []
    stk_a = Stack(a)
    stk_b = Stack(b)
    score = 0
    count = 0
# first taking elements from stack A , till score becomes just less than desired total
    for j in range(len(a)):
        if score + stk_a.peek() <= x:
            score += stk_a.peek()

            count += 1
            temp.append(stk_a.peek())
            # storing the popped elements in temporary stack such that we can again remove them from score
            # when we find better element in stack B
            stk_a.pop()
# this is maximum number of moves using only stack A
    max_now = count
# now iterating through stack B for element lets say k which on adding to total score should be less than desired
    # or else we will remove each element of stack A from score till it becomes just less than desired total.
    for k in range(len(b)):
        score += stk_b.peek()
        stk_b.pop()
        count += 1
        while score > x and count > 0 and len(temp) > 0:
            count = count - 1
            score = score - temp[-1]
            temp.pop()
        # if the score after adding element from stack B is greater than max_now then we have new set of moves which will also lead
        # to just less than desired so we should pick maximum of both
        if score <= x and count > max_now:
            max_now = count
    print(max_now)

Java tag