CodeCrusader's questions

任务描述为：

我有一个从 1 到 n 的不同数字数组，例如 arr = [5, 3, 4, 1, 2]

将名为 order 的变量初始化为 1，现在从左到右遍历数组并查找与变量 order 匹配的元素，如果找到则增加 order 并向前移动。换句话说，我们可以说将名为 order 的变量初始化为 1，因此首先从左到右遍历数组并查看 1 在数组中出现的位置，然后将 order 增加到 2，然后在数组中向前移动并查找 2，如果找到则将 order 增加到 3。像上面那样从左到右迭代称为操作

当 arr = [5,3,4,1,2] 时，从左到右依次遍历，当找到 arr[3] 时，order 的值从 1 变为 2，当找到 arr[4] 时，order 的值从 2 变为 3

重复上述步骤，直到变量阶达到值n。重复的次数称为操作。

因此当 arr [ 5,3,4,1,2] 时，所需的最少操作数为 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
    }
}

我的代码运行时间为 O(n^2)，我们如何才能以更低的时间复杂度解决这个问题

我有一个大小为的任务列表n，处理所需的时间表示为tasks[i]，其中i是任务的索引。

处理步骤：i = 0这些任务应按从到的顺序i = n-1一个接一个地进行处理。

现在有另一个大小为 的程序员列表m，他们可以在 所表示的指定时间内完成任务programmers[i]，其中i是索引。

如果任务的值为 0，则表示任务已完成，否则该任务为待处理任务。

因此，如果上述处理步骤结束时仍有一些任务待处理，则处理应从到重新i = 0开始i = n-1

如果所有任务都完成了，那么我们可以重新加载任务并从头开始处理。

我想收集每个程序员在指定的时间内工作后仍有多少任务处于待处理状态。

以下是一个例子：

示例 1

n=5，任务= [2, 4, 5, 1, 1] m=5，程序员=[1, 5, 1, 5, 2]

因此，待处理任务的数量 =[5, 3, 3, 1, 0]

示例 2

任务 =[1, 2, 4, 1, 2] 程序员 =[3, 10, 1, 1, 1]

输出 =[3,0,4,4,3]

示例 3

任务 =[1, 4, 4] 程序员 =[9, 1, 4]

输出 =[0, 2, 1]

以下是我在 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]
    }
}

我还尝试使用 PriorityQueue 仅处理待处理的任务：

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]
    }
}

但是上面的代码也会在O(n*m*log(m))时间复杂度上运行

限制：

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

我想知道如何在较少的时间复杂度内解决这个问题

给定两个长度为 m 的字符串 s 和另一个长度为 n 的字符串 t，计算 s 中有多少个子序列大于 t

如果序列 p 满足以下情况，则称其大于另一个序列 q：

a) 在 p 和 q 不同的第一个位置，p[i] > q[i]，或
b) |p| > |q| 且 q 是 p 的前缀（其中 |p| 表示密码 p 的长度）。

例子：

s="bab" t="ab"

结果= 5

解释：

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

限制： s 的长度为 1 到 10^5，t 的长度为 1 到 100

在有效组合的情况下，t 的长度可以大于 s 的长度。

我使用递归方法解决了这个问题，但时间复杂度为 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
    }
}

如何以较少的时间复杂度解决这个问题？

给定一个长度为 n 的字符串，我想计算有多少个子字符串可能具有以下特征：

a) 子串长度为偶数 b) 该子串中存在一个字符，其频率等于子串长度的一半。

例如 s="idafddfii", 输出 = 13

解释：

有效的子字符串为：“id”、“da”、“af”、“fd”、“df”、“fi”、“dafd”、“afdd”、“fddf”、“ddfi”、“dfii”、“idafdd”、“dafddf”

限制：

1 <= n <= 10 的 5 次方

s 仅由小写英文字母组成

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
    }

}

我的代码运行时间复杂度为 O(n^2)，我想降低这个时间复杂度，在更短的时间内解决这个问题的正确方法是什么。

根据@Unmitigated 提供的答案，我尝试像这样构建每个字符的累积频率，但现在不知道如何使用这个累积频率来解决问题。

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
    }
}