题解 | #牛群名字覆盖#

牛群名字覆盖

https://www.nowcoder.com/practice/e6cef4702e7841f59cf47daf9bafb241

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param t string字符串
     * @return string字符串
     */

    public String minWindow(String s, String t) {
        // write code here
        Deque<Character> queue = new LinkedList<>();
        int count = t.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = -1;
        int right = 0;
        String result = "";
        int len = Integer.MAX_VALUE;
        while (right < s.length()) {
            while (count != 0 && right < s.length()) {
                queue.addLast(s.charAt(right));
                if (map.containsKey(s.charAt(right))) {
                    map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
                    if (map.get(s.charAt(right)) >= 0) {
                        count--;
                    }
                }
                right++;
            }
            if (right == s.length() && count != 0 && len == Integer.MAX_VALUE) {
                return "";
            }
            while (count == 0) {
                left++;
                queue.removeFirst();
                if (map.containsKey(s.charAt(left))) {
                    map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                    if (map.get(s.charAt(left)) > 0) {
                        count++;
                    }
                }
            }
            queue.addFirst(s.charAt(left));
            if (queue.size() < len) {
                StringBuffer stringBuffer = new StringBuffer();
                for (Character character : queue) {
                    stringBuffer.append(character);
                }
                result = stringBuffer.toString();
                len = result.length();
            }
            queue.removeFirst();
        }
        return result;
    }

}

本题考察的知识点是队列和双指针,所用编程语言是java。

利用队列主要是为了存储我们遍历的字符。首先我们需要明白如何找s中一个子字符串利用子字符串中的字符能够完全组成字符串t,我采用的方法选用哈希表加计数器。哈希表存储字符串t中每个字符出现的次数,计数器用来记录需要匹配的字符个数。我们遍历s中的每个字符串,如果哈希表中存在,则需要将对应出现的次数减一,然后判断此时哈希表中该字符的出现次数是否不小于0,如果不小于则计数器减一。当计数器为0时,则相应左指针开始移动,对应哈希表和计数器的操作相反。当计数器大于0时,则开始计算此时满足条件的字符串。然后继续相同操作,直到右指针到达s字符串末尾位置

全部评论

相关推荐

冷艳的小师弟在看机会:jd测评乱点直接被挂了,哭死~
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务