Day02 集合 | 30. 串联所有单词的子串、146. LRU 缓存、811. 子域名访问计数

一、30. 串联所有单词的子串

1、思路

将字符串数组存入map，key为每个元素，value为元素个数， 遍历字符串，每次截取字符串数组长度，将截取后的字符串再次分段截取并存入map1中，最后比对2个map，相同则添加索引到list中

class Solution {

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        int substrLength = 0;
        for (String word : words) {
            substrLength += word.length();
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i + substrLength <= s.length(); i++) {
            if (valid(s.substring(i, i + substrLength), words, map)) {
                list.add(i);
            }
        }
        return list;
    }

    public boolean valid(String sub, String[] words, Map<String, Integer> map) {
        int k = words[0].length();
        Map<String, Integer> map1 = new HashMap();
        for (int i = 0; i < sub.length(); i += k) {
            String key = sub.substring(i, i + k);
            map1.put(key, map1.getOrDefault(key, 0) + 1);
        }
        return map1.equals(map);
    }
}

二、146. LRU 缓存

1、思路

HashMap + 链表 ,map方便查找，链表方便头插和去尾部，以及删除

2、代码

class LRUCache {

    Map<Integer, Node> map = new HashMap();
    Node head;
    Node tail;
    int capacity;

    // 需要实现功能
    // 1、头部插入
    // 2、尾部删除
    // 3、查询数据是否存在
    // 4、若存在，还需要更新数据,链表需要删除，然后重新插入
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);
        addFirst(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 更新node中的value
            node.value = value;
            remove(node);
            addFirst(node);// 链表更新
        } else {
            Node node = new Node();
            node.key = key;
            node.value = value;
            map.put(key, node);
            addFirst(node);
            if (map.size() > capacity) {
                map.remove(tail.pre.key);
                remove(tail.pre);
            }
        }
    }

    public void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void addFirst(Node node) {
        // head = node2
        // head = node =node2
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }
}

class Node {
    Node next;
    Node pre;
    int key;
    int value;

    public Node() {

    }
}

三、811. 子域名访问计数

1、思路

使用hashmap存储相同数据 以及次数，使用递归拆解域名

2、代码

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> map = new HashMap();
        List<String> list = new ArrayList();
        for(String cp : cpdomains){
            String[] split =  cp.split(" ");
            split(Integer.parseInt(split[0]),split[1],map);
        }
        for(String key :map.keySet()){
            list.add(map.get(key) +" "+ key);
        }
        return list;
    }
    public void split(int number, String domain, Map<String, Integer> map){
        if(map.containsKey(domain)){
            int value = map.get(domain);
            map.put(domain, number + value);
        }else{
            map.put(domain, number);
        }

        int dotIndex = domain.indexOf('.'); // 找到第一个点的位置
        if (dotIndex == -1) {
            return ; // 如果没有点，返回
        }
        split(number,domain.substring(dotIndex + 1),map); // 截取第一个点后面的内容
    }
}