Leetcode - 周赛394_list[] g = new arraylist[n];遍历输出

目录

一，3120. 统计特殊字母的数量 I

二，3121. 统计特殊字母的数量 II

三，3122. 使矩阵满足条件的最少操作次数

四，3123. 最短路径中的边

---

一，3120. 统计特殊字母的数量 I

本题就是统计有多少个字母的大小写同时出现在字符串word中，分别使用一个数组来统计大写字母和小写字母的出现次数。 

代码如下： 

class Solution {
    public int numberOfSpecialChars(String word) {
        int[] cnt1 = new int[26];//大写
        int[] cnt2 = new int[26];//小写
        for(char ch : word.toCharArray()){
            if(Character.isUpperCase(ch)){
                cnt1[ch-'A']++;
            }else{
                cnt2[ch-'a']++;
            }
        }
        int ans = 0;
        for(int i=0; i<26; i++){
            if(cnt1[i]>0 && cnt2[i]>0)
                ans++;
        }
        return ans;
    }
}

二，3121. 统计特殊字母的数量 II

本题比上一题多了一些条件，不仅要大小写都出现，并且所有的小写字母都要出现在其对应大写字母的前面。所以可以使用两个数组分别存储，一个存储大写字母的第一次出现下标，另一个存储小写字母最后一次出现下标，如果大小写都出现&小写字母的下标<大写字母的下标，那么就+1。

代码如下：

class Solution {
    public int numberOfSpecialChars(String word) {
        int[] idx1 = new int[26];//大写字母第一次出现的下标
        int[] idx2 = new int[26];//小写字母最后一次出现的下标
        Arrays.fill(idx1, -1);
        Arrays.fill(idx2, -1);
        char[] ch = word.toCharArray();
        for(int i=0; i<ch.length; i++){
            if(Character.isLowerCase(ch[i])){
                idx2[ch[i]-'a'] = i;
            }else{
                idx1[ch[i]-'A'] = idx1[ch[i]-'A']==-1?i:idx1[ch[i]-'A'];
            }
        }
        int ans = 0;
        for(int i=0; i<26; i++){
            if(idx1[i]!=-1&&idx2[i]!=-1&&idx1[i]>idx2[i])
                ans++;
        }
        return ans;
    }
}

上述做法更加不容易出错，但是还有更加省时间的做法，可以一次遍历实现，使用一个hash表来统计出现的大小写字母，再使用一个数组 cnt 来统计 26 个字母的状态：

• 0：该字母没有计入答案
• 1：该字母已计入答案
• 2：该字母不可能是答案

遍历该字符串：

• 如果是大写字母，并且之前出现过小写字母，将cnt[i] = 0 (表示该字母没有被计入ans中)，将cnt[i] = 1，ans++
• 如果是小写字母，并且之前出现过大写字母&& cnt[i] == 1 (表示该字母已经被计入ans中)，将cnt[i] = 2 (表示该字母不可能是答案)，ans--
• 如果是大写字母，并且之前没有出现过小写字母，将cnt[i]=2 (表示该字母不可能是答案)，防止出现BbB这种情况

class Solution {
    public int numberOfSpecialChars(String word) {
        Set<Character> set = new HashSet<>();//统计大小写
        int[] cnt = new int[26];
        //0：该字母没有计入答案
        //1：该字母已计入答案
        //2：该字母被计入答案后又出现小写字母，又被删除
        int ans = 0;
        for(char ch : word.toCharArray()){
            if(Character.isUpperCase(ch)){
                //小写字母出现后大写字母出现的情况
                if(set.contains(Character.toLowerCase(ch)) && cnt[ch-'A']==0){
                    cnt[ch-'A'] = 1;
                    ans++;
                }
                //出现小写字母未出现，先出现大写字母的情况！！！（容易忽略）
                if(!set.contains(Character.toLowerCase(ch))){
                    cnt[ch-'A'] = 2;
                }
            }else{
                //出现大写字母后，又出现小写字母的情况
                if(set.contains(Character.toUpperCase(ch)) && cnt[ch-'a']==1){
                    cnt[ch-'a'] = 2;
                    ans--;
                }
            }
            set.add(ch);
        }
        return ans;
    }
}

三，3122. 使矩阵满足条件的最少操作次数

没有思路，先考虑暴力求解，也就是枚举每一列选择保留的数字，保证相邻两列保留的数不一样，求保留的最大值，所以 dfs 就需要两个变量，一个存储当前的列数，一个存储上一个保留的数字。

dfs(i，pre) 的定义：前 i 列数可以保留的最大数目。

• 结束条件：i < 0，返回 0
• 每次递归要做：使用 j 遍历0~9，res = Math.max( res，dfs(i-1，j)+cnt[ i ][ j ])，cnt[ i ][ j ]表示当前列中有多少个 j 
• 结果： res

class Solution {
    Map<String, Integer> map = new HashMap<>();
    public int minimumOperations(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] cnt = new int[m][10];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                cnt[j][grid[i][j]]++;
            }
        }
        return n*m - dfs(m-1, cnt, -1);
    }
    int dfs(int i, int[][] cnt, int pre){
        String key = i + "-" + pre;
        if(!map.isEmpty() && map.containsKey(key))
            return map.get(key);
        if(i < 0) return 0;
        int res = 0;
        for(int j=0; j<=9; j++){
            if(j != pre)
                res = Math.max(res, dfs(i-1, cnt, j)+cnt[i][j]);
        }
        map.put(key, res);
        return res;
    }
}

四，3123. 最短路径中的边

本题和上周双周赛一样，考的还是djstra算法，只不过它问的是edges[i]是否在0->n-1节点的最短路径上，这里有两种做法，先讲简单一点的：

使用两次djstra算法，分别算出从0到所有位置的最短路径dis1，以及从n-1到所有位置的最短路径dis2，再遍历edges数组（x=e[0]，y=e[1]，w=e[2]），判断 dis1[x] + dis2[y] + w == dis1[n-1] 或者 dis1[y] + dis2[x] + w == dis1[n-1]，如果相等说明ans[i] = true，否则 ans[i] = false。就是下图两种情况：

代码如下：

class Solution {
    int n;
    public boolean[] findAnswer(int n, int[][] edges) {
        this.n = n;
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e->new ArrayList<>());
        for(int i=0; i<edges.length; i++){
            int[] e = edges[i];
            int x = e[0], y = e[1], w = e[2];
            g[x].add(new int[]{y, w});
            g[y].add(new int[]{x, w});
        } 
        int[] dis1 = dis(g, 0);//0->?的最短路径
        int[] dis2 = dis(g, n-1);//n-1 -> ?的最短路径
        
        int mn = dis1[n-1];
        boolean[] ans = new boolean[edges.length];
        for(int i=0; i<edges.length; i++){
            int[] e = edges[i];
            int x = e[0], y = e[1], w = e[2];
            if(dis1[x] + dis2[y] + w == mn || dis1[y]+dis2[x]+w==mn){
                ans[i] = true;
            }else{
                ans[i] = false;
            }
        }
        return ans;
    }
    int[] dis(List<int[]>[] g, int s){
        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE/2);
        dis[s] = 0;
        PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->x[0]-y[0]);
        que.offer(new int[]{0, s});
        while(!que.isEmpty()){
            int[] t = que.poll();
            int dx = t[0];
            int x = t[1];
            if(dx > dis[x]){
                continue;
            }
            for(int[] y : g[x]){
                int idx = y[0];
                int newDis = dx + y[1];
                if(dis[idx]==Integer.MAX_VALUE/2 || newDis < dis[idx]){
                    dis[idx] = newDis;
                    que.offer(new int[]{newDis,idx});
                }
            }
        }
        return dis;
    }
}

另一种解法和上述解法的思路是相同的，但是时间复杂度更低，只使用一次djstra算法，算出从0到所有位置的最短路径dis，然后从n-1出发，倒着dfs，如果dis[y] + w == dis[x]，就说明当前x-y这段路径在最短路径上。

代码如下：

class Solution {
    public boolean[] findAnswer(int n, int[][] edges) {
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e->new ArrayList<>());
        for(int i=0; i<edges.length; i++){
            int[] e = edges[i];
            int x = e[0], y = e[1], w = e[2];
            g[x].add(new int[]{y, w, i});
            g[y].add(new int[]{x, w, i});
        }
        PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->x[0]-y[0]);
        que.offer(new int[]{0, 0});
        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE/2);
        dis[0] = 0;
        while(!que.isEmpty()){
            int[] t = que.poll();
            int dx = t[0];
            int x = t[1];
            if(dx > dis[x]) continue;
            for(int[] y : g[x]){
                int idx = y[0];
                int newDis = dx + y[1];
                if(dis[idx]==Integer.MAX_VALUE/2 || newDis < dis[idx]){
                    dis[idx] = newDis;
                    que.offer(new int[]{newDis, idx});
                }
            }
        }
        boolean[] ans = new boolean[edges.length];
        if(dis[n-1] == Integer.MAX_VALUE/2) return ans;
        boolean[] vis = new boolean[n];
        dfs(n-1, dis, ans, vis, g);
        return ans;
    }
    void dfs(int x, int[] dis, boolean[] ans, boolean[] vis, List<int[]>[] g){
        vis[x] = true;
        for(int[] t : g[x]){
            int y = t[0], w = t[1], i = t[2];
            if(dis[y] + w != dis[x])
                continue;
            ans[i] = true;
            if(!vis[y]){
                dfs(y, dis, ans, vis, g);
            }
        }
    }
}