替换子串得到平衡字符串

题目描述

有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

样例

样例输入

s = “QWER”
s = “QQWE”
s = “QQQW”
s = “QQQQ”

样例输出

0 s 已经是平衡的了。
1 我们需要把一个 ‘Q’ 替换成 ‘R’，这样得到的 “RQWE” (或 “QRWE”) 是平衡的。
2 我们可以把前面的 “QQ” 替换成 “ER”。
3 我们可以替换后 3 个 ‘Q’，使 s = “QWER”。

提示

• $1<=s.length<=10^5$
• s.length 是 4 的倍数
• s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符

思路

n的范围为1e5，需要设计的算法的时间复杂度不能大于$O(n^2)$。测试用例有点怪。题目理解起来比较麻烦。
看了题解。使用的是双指针。

代码实现

class Solution {
    public int balancedString(String s) {
        int len = s.length();
        int standard = len / 4;
        int[] arr = new int['Z'];
        for(int i = 0; i < len; i++) arr[s.charAt(i)]++;
        if(arr['Q'] == standard && arr['W'] == standard && arr['E'] == standard && arr['R'] == standard) return 0;
        int ans = len;
        for(int left = 0, right = 0; right < len; right++){
            --arr[s.charAt(right)];
            while(arr['Q'] <= standard && arr['W'] <= standard && arr['E'] <= standard && arr['R'] <= standard){
                ans = Math.min(ans, right - left + 1);
                ++arr[s.charAt(left++)];
            }
        }
        return ans;
    }
}

课程表

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

样例

样例输入

numCourses = 2, prerequisites = [[1,0]]
numCourses = 2, prerequisites = [[1,0],[0,1]]

样例输出

true 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
false 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示

• $1<=numCourses<=10^5$
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

思路

拓扑排序，刚好想写一些拓扑排序的题目，这题应该就是拓扑排序的基本。给出每个点的入度，只需返回能否完成拓扑排序（即图中是否存在自环）。dfs、bfs均可使用。

代码实现

dfs

class Solution {
    List<List<Integer>> edges;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        int[] vis = new int[numCourses];
        for(int i = 0; i < numCourses; i++) edges.add(new ArrayList<>());
        for(int[] cur : prerequisites)  
            edges.get(cur[1]).add(cur[0]);
        for(int i = 0; i < numCourses; i++)
            if(!dfs(vis, i)) return false;
        return true;
    }
	
	// vis状态为1表示当此进行dfs时已经遍历过，再次遇到属于环。即不满足拓扑排序；
	// vis状态为-1表示之前dfs已经遍历过当前结点，相当于给dfs剪枝吧。
    private boolean dfs(int[] vis, int index){
        if(vis[index] == 1) return false;
        if(vis[index] == -1) return true;
        vis[index] = 1;
        for(int i : edges.get(index)){
            if(!dfs(vis, i)) return false;
        }
        vis[index] = -1;
        return true;
    }
}

bfs

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] out = new int[numCourses];
        List<List<Integer>> edges = new ArrayList<>();
        for(int i = 0; i < numCourses; i++) edges.add(new ArrayList<Integer>());
        Queue<Integer> queue = new ArrayDeque<>();
        for(int[] prerequisit : prerequisites){
            out[prerequisit[0]]++;
            edges.get(prerequisit[1]).add(prerequisit[0]);
        }
        for(int i = 0; i < numCourses; i++) 
            if(out[i] == 0) queue.offer(i);
        
        while(!queue.isEmpty()){
            int pre = queue.poll();
            numCourses--;
            for(int cur : edges.get(pre)){
                if(--out[cur] == 0) queue.offer(cur);
            }
        }
        return numCourses == 0;
    }
}