CodeCrusader's questions

A descrição da tarefa é:

Tenho uma matriz de números distintos de 1 a n, por exemplo arr = [5, 3, 4, 1, 2]

Inicialize uma variável chamada order para 1, agora percorra o arr da esquerda para a direita e procure o elemento que corresponde à variável order, se encontrado incremente order e siga em frente. Em outras palavras, podemos dizer Inicialize uma variável chamada order para 1, então primeiro percorra o array da esquerda para a direita e veja onde 1 aparece no array, então incremente order para 2, então siga em frente no array e procure por 2, se encontrado incremente order para 3. Iterar da esquerda para a direita como acima é chamado de operação

para quando arr = [5,3,4,1,2], em uma passagem da esquerda para a direita, a ordem muda seu valor de 1 para 2 quando arr[3] é encontrado e então de 2 para 3 quando arr[4] é encontrado

Repita os passos acima até que a ordem da variável atinja o valor n. O número de repetições é chamado de operações.

Então quando arr [ 5,3,4,1,2], o número mínimo de operações necessárias é 3

import java.util.*;

class Main {
    public static int solve(List<Integer> arr) {
        int n = arr.size();
        int order = 0; // Number of sorted items found
        int operations = 0;  // Count of full array scan
        
        while (sortedCount < n) {
            order++;
            for (int i = 0; i < n; i++) {
                if (arr.get(i) == order + 1) {
                    order++;
                }
            }
        }        
        return operations;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(5, 3, 4, 1, 2))); // Output: 3
        System.out.println(solve(Arrays.asList(3,1,4,2,5))); // Output: 2
        System.out.println(solve(Arrays.asList(1,2,3,4))); // Output: 1
        System.out.println(solve(Arrays.asList(2,1))); // Output: 2
    }
}

Meu código funciona em tempo O(n^2), como podemos resolver isso em menos complexidade de tempo

Tenho uma lista de tarefas de tamanho ne o tempo gasto para processar é representado como tasks[i], onde ié o índice da tarefa.

Etapa de processamento: Essas tarefas devem ser processadas sequencialmente de i = 0a i = n-1, uma após a outra.

Agora há outra lista de programadores de tamanho m, que podem trabalhar nas tarefas por uma duração especificada representada por programmers[i], onde ié o índice.

Diz-se que uma tarefa está concluída se seu valor for 0; caso contrário, é uma tarefa pendente.

Portanto, se houver algumas tarefas pendentes até o final da etapa de processamento mencionada acima, o processamento deverá ser reiniciado de i = 0parai = n-1

Se todas as tarefas forem concluídas, podemos carregá-las novamente e iniciar o processamento do início.

Quero coletar quantas tarefas ainda estão pendentes depois que cada programador trabalha durante o período especificado.

Aqui está um exemplo:

Exemplo 1

n=5, tarefas = [2, 4, 5, 1, 1] m=5, programadores =[1, 5, 1, 5, 2]

Portanto, o número de tarefas pendentes =[5, 3, 3, 1, 0]

Exemplo 2

tarefas = [1, 2, 4, 1, 2] programadores =[3, 10, 1, 1, 1]

Saída =[3,0,4,4,3]

Exemplo 3

tarefas = [1, 4, 4] programadores =[9, 1, 4]

Saída =[0, 2, 1]

Aqui está meu código que roda em tempo O(m*n):

import java.util.*;

public class Main {

    public static List<Integer> getPendingTasks(List<Integer> tasks, List<Integer> programmers) {
        List<Integer> pendingTasks = new ArrayList<>();
        List<Integer> originalTasks = new ArrayList<>(tasks); // Save original tasks for reloading
        int n = tasks.size();
        
        for (int programmer : programmers) {
            int timeRemaining = programmer;
            for (int i = 0; i < n && timeRemaining > 0; i++) {
                if (tasks.get(i) > 0) {
                    if (tasks.get(i) <= timeRemaining) {
                        timeRemaining -= tasks.get(i);
                        tasks.set(i, 0);
                    } else {
                        tasks.set(i, tasks.get(i) - timeRemaining);
                        timeRemaining = 0;
                    }
                }
            }

            // Count pending tasks
            int pending = 0;
            for (int task : tasks) {
                if (task > 0) {
                    pending++;
                }
            }

            pendingTasks.add(pending);

            // Reload tasks if all are completed
            if (pending == 0) {
                tasks = new ArrayList<>(originalTasks);
            }
        }

        return pendingTasks;
    }

    public static void main(String[] args) {
        // Example 1
        List<Integer> tasks1 = Arrays.asList(2, 4, 5, 1, 1);
        List<Integer> programmers1 = Arrays.asList(1, 5, 1, 5, 2);
        System.out.println("Output: " + getPendingTasks(tasks1, programmers1)); // Output: [5, 3, 3, 1, 0]

        // Example 2
        List<Integer> tasks2 = Arrays.asList(1, 2, 4, 1, 2);
        List<Integer> programmers2 = Arrays.asList(3, 10, 1, 1, 1);
        System.out.println("Output: " + getPendingTasks(tasks2, programmers2)); // Output: [3, 0, 4, 4, 3]

        // Example 3
        List<Integer> tasks3 = Arrays.asList(1, 4, 4);
        List<Integer> programmers3 = Arrays.asList(9, 1, 4);
        System.out.println("Output: " + getPendingTasks(tasks3, programmers3)); // Output: [0, 2, 1]
    }
}

Também tentei usar PriorityQueue para processar apenas tarefas pendentes:

import java.util.*;

class Main {

    public static List<Integer> getPendingTasks(List<Integer> tasks, List<Integer> programmer) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> pending = new PriorityQueue<>();
        int n = tasks.size();
        List<Integer> originalTasks = new ArrayList<>(tasks);

        // Initialize set with all tasks
        for (int i = 0; i < n; i++) {
            pending.add(i);
        }
        Queue<Integer> q = new PriorityQueue<>(pending);
        
        // Process each item
        for (int p : programmer) {
            int timeAvailable = p;

            // Process only unprocessed tasks
            List<Integer> balancedTask = new ArrayList<>();
            
            while (!q.isEmpty()) {
                int i = q.poll();
                if (tasks.get(i) <= timeAvailable) {
                    timeAvailable -= tasks.get(i);
                    // Task fully processed
                } else {
                    tasks.set(i, tasks.get(i) - timeAvailable); // Partially processed
                    timeAvailable = 0; // time exhausted
                    balancedTask.add(i);
                }
            }
            q.addAll(balancedTask);
            result.add(q.size());
            if(q.size() ==0) {
                tasks = originalTasks;
                q= pending;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(getPendingTasks(Arrays.asList(2, 4, 5, 1, 1), Arrays.asList(1, 5, 1, 5, 2))); 
        // Expected: [5, 3, 3, 1, 0]
        
        System.out.println(getPendingTasks(Arrays.asList(1, 2, 4, 1, 2), Arrays.asList(3, 10, 1, 1, 1))); 
        // Expected: [3, 0, 4, 4, 3]
        
        System.out.println(getPendingTasks(Arrays.asList(1, 4, 4), Arrays.asList(9, 1, 4))); 
        // Expected: [0, 2, 1]
    }
}

Mas o código acima também é executado em O(n*m*log(m))complexidade de tempo

Restrições:

n and m in range 1 to 2 * 10^5
each item in input lists is 1 to 10^9

Quero saber como resolver isso em menos complexidade de tempo

Dadas duas sequências s de comprimento m e outra sequência t de comprimento n, conte quantas subsequências de s são maiores que t

Uma sequência p é chamada maior que outra sequência q se ela satisfaz os casos abaixo:

a) p[i] > q[i] na primeira posição onde p e q diferem, ou
b) |p| > |q| e q é um prefixo de p (onde |p| denota o comprimento da senha p).

Exemplo:

s = "bab" t = "ab"

Resultado = 5

Explicação:

Valid subsequences of s which are greater than t are
"b"
"ba"
"bb"
"bab"
"b"

restrições: comprimento de s 1 a 10^5 comprimento de t 1 a 100

O comprimento de t pode ser maior que o comprimento de s também com combinações válidas.

Resolvi isso usando uma abordagem recursiva, mas está levando uma complexidade de tempo O(2^n * n).

public class Main {
    private static final int MOD = 1_000_000_007;

    private static void subsequence(String s, int index, String current, List<String> subsequences) {
        if (index == s.length()) {
            if (!current.isEmpty()) {
                subsequences.add(current);
            }
            return;
        }
        subsequence(s, index + 1, current, subsequences);
        subsequence(s, index + 1, current + s.charAt(index), subsequences);
    }

    private static boolean isGreater(String s1, String t) {
        int len1 = s1.length();
        int len2 = t.length();
        for (int i = 0; i < Math.min(len1, len2); i++) {
            if (s1.charAt(i) > t.charAt(i)) {
                return true;
            } else if (s1.charAt(i) < t.charAt(i)) {
                return false;
            }
        }
        return len1 > len2;
    }

    public static int solve(String s, String t) {
        List<String> subsequences = new ArrayList<>();
        subsequence(s, 0, "", subsequences);

        int count = 0;
        for (String e : subsequences) {
            if (isGreater(e, t)) {
                count = (count + 1) % MOD;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(solve("aba", "ab")); // Expected: 3
        System.out.println(solve("bab", "ab")); // Expected: 5
        System.out.println(solve("wrrmkhds", "bebbjvcgzlwtbvasphvm")); // Expected: 255
        System.out.println(solve("o", "h"));   // Expected: 1
    }
}

Como isso pode ser resolvido em menos complexidade de tempo?

Dada uma sequência de comprimento n, quero calcular quantas subsequências são possíveis com as seguintes características:

a) o comprimento da substring é par b) existe um caractere nesta substring cuja frequência é igual à metade do comprimento da substring.

Exemplo s="idafddfii", saída = 13

Explicação:

As substrings válidas são: "id", "da", "af", "fd", "df", "fi", "dafd", "afdd", "fddf", "ddfi", "dfii", "idafdd", "dafddf"

restrições:

1 <= n <= 10 potência 5

s consiste apenas em alfabetos ingleses minúsculos

public class Main {

    public static long solve(String s) {
        int n = s.length();
        long result = 0;
    
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                int len = j - i + 1;
                // Only check even-length substrings
                if (len % 2 == 0) {
                    if (isValid(freq, len)) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
    
    private static boolean isValid(int[] freq, int len) {
        int half = len / 2;
        for (int count : freq) {
            if (count == half) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        String s1 = "aaaaid";
        String s2 = "aidfg";
        String s3 = "ababbab";
    
        System.out.println(solve(s1)); // Output: 3
        System.out.println(solve(s2)); // Output: 4
        System.out.println(solve(s3)); // Output: 8
    }

}

Meu código é executado em complexidade de tempo de O(n^2), quero reduzir essa complexidade de tempo. Qual é a abordagem correta para resolver isso em menos tempo?

Com base na resposta fornecida por @Unmitigated, tentei construir a frequência cumulativa de cada caractere assim, mas agora fiquei preso em como resolver o problema usando essa frequência cumulativa.

import java.util.*;
public class Main {

    public static int solve(String s) {
        int n = s.length();
        int result = 0;
        Map<Character, int[]> map = new HashMap<>();
        for(int i=0; i<n; i++) {
            char ch = s.charAt(i);
            int[] cnt = map.getOrDefault(ch, new int[n]);
            cnt[i] += i == 0 ? 1 : cnt[i-1]+1;
            map.put(ch, cnt);
        }
        for(char c : map.keySet()) {
            System.out.println(c + ":" + Arrays.toString(map.get(c)));
        } 
        // what to do next
        return result;
    }

    public static void main(String[] args) {
        String s = "idafddfii";
        int output = solve(s);
        System.out.println(output); // Output: 13
    }
}