当不得不淘汰某些数据时(通常是容量已满),选择最久未被使用的数据进行淘汰。

class LRUCache {
    class Node {
        int k, v;
        Node l, r;
        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }
    int n;
    Node head, tail;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.v;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.v = value;
        } else {
            if (map.size() == n) {
                Node del = tail.l;
                map.remove(del.k);
                delete(del);
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        refresh(node);
    }

    // refresh 操作分两步:
    // 1. 先将当前节点从双向链表中删除(如果该节点本身存在于双向链表中的话)
    // 2. 将当前节点添加到双向链表头部
    void refresh(Node node) {
        delete(node);
        node.r = head.r;
        node.l = head;
        head.r.l = node;
        head.r = node;
    }

    // delete 操作:将当前节点从双向链表中移除
    // 由于我们预先建立 head 和 tail 两位哨兵,因此如果 node.l 不为空,则代表了 node 本身存在于双向链表(不是新节点)
    void delete(Node node) {
        if (node.l != null) {
            Node left = node.l;
            left.r = node.r;
            node.r.l = left;
        }
    }
}

模拟系统执行「递归」的过程

具体应用:

给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历 。

递归做法:

class DFS{
    public List<Integer> preorder(Node root){
        List<Integer> res = new ArrayList<>();
        dfs(root,res);
        return res;
    }

    public void dfs(Node root,List<Integer> res){
        if(null == root) return;
        //前序遍历位置
        res.add(root.val);
        List<Node> children = root.children;
        for(Node child: children){
            dfs(child,res);
        }
    }
}
阅读全文 »

直观地说就是,让你把一幅图「拉平」,而且这个「拉平」的图里面,所有箭头方向都是一致的,比如上图所有箭头都是朝右的。

图片

对于任何有向图而言,其拓扑排序为其所有结点的一个线性排序(对于同一个有向图而言可能存在多个这样的结点排序)。该排序满足这样的条件——对于图中的任意两个结点uv,若存在一条有向边从u指向v,则在拓扑排序中u一定出现在v前面。

拓扑排序可以用来判断图中是否有环, 还可以用来判断图是否是一条链。

算法思路

阅读全文 »

688. 骑士在棋盘上的概率

象棋骑士有8种可能的走法,如下图所示。每次移动在基本方向上是两个单元格,然后在正交方向上是一个单元格。

每次骑士要移动时,它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘),然后移动到那里。

骑士继续移动,直到它走了 k 步或离开了棋盘。

阅读全文 »

「蓄水池抽样算法」

优势:只需一次遍历,适用总量未知的情况

蓄水池抽样算法可以扩展很多应用范围,比如游戏的签到抽奖系统,在抽奖之前,你不知道参与的总人数。

对于一个池内,获取每个数字的概率都是一样的

  • 如果我们池子中只有一个数字,那么拿到第一个数字的概率就是100%毋庸置疑。
  • 两个数字50% 三个数字每个数字的几率都是33% 以此类推。。。。

当我们不知道池子里有多少个数字的时候,就需要用蓄水池的算法思想去计算。

  • 当链表前行到第一个数字,此时取第一个数字的几率为100%,那result自然等于这个数字。
  • 前进到第二个数字,那么此时取这个数字的几率自然就为50%(池子里只有两个数字),那么就是50%的几率取新数字,50%的几率保留原本的数字。
  • 第三个数字的时候,33%的几率取当前最新的这个数字,66%的几率保留原本的数字。这66%中:原本的数字有50%的几率是1,有50%的几率是2。也就是此时三个数字的概率都为33%。 通过这个算法,就能达到取数的概率均摊,从而实现随机。
阅读全文 »

「优先队列」

应用场景:从序列中找一个最值(最大值或最小值),如果顺序寻找最值需要O(n)的时间,而使用优先队列则只需要O(logn)的时间。

普通的队列是一种先进先出的数据结构,元素在队尾入,在队头出。

在优先队列中。元素被赋予了优先级,具有最高优先级的元素先出。

优先队列是利用堆来实现的,堆可以看作是一棵完全二叉树的循序存储结构,具有n个节点的完全二叉树的深度为(logn)+1

阅读全文 »

「滑动窗口」

//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
//
// 注意:
// 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
// 如果 s 中存在这样的子串,我们保证它是唯一的答案。
//
// 示例 1:
//输入:s = "ADOBECODEBANC", t = "ABC"
//输出:"BANC"
//
//
// 示例 2:
//输入:s = "a", t = "a"
//输出:"a"
//
//
// 示例 3:
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中,
//因此没有符合条件的子字符串,返回空字符串。
//
//
// 提示:
// 1 <= s.length, t.length <= 10⁵
// s 和 t 由英文字母组成
//进阶:你能设计一个在 o(n) 时间内解决此问题的算法吗? Related Topics 哈希表 字符串 滑动窗口 👍 1527 👎 0


import java.util.HashMap;
import java.util.Map;

class Solution
{
    public String minWindow(String s, String t) {
        // 存放t字符的数量,方便进行比对
        Map<Character, Integer> need = new HashMap<>();
        // 存放由截取的s字符数量
        Map<Character, Integer> window = new HashMap<>();
        for (char charArray : t.toCharArray()) {
            need.put(charArray, need.getOrDefault(charArray, 0) + 1);
        }
        int left = 0, start = 0, valid = 0, len = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            char RChar = s.charAt(right);
            // need如果存在右指针所指字符,window将添加所指字符数量
            if (need.containsKey(RChar)) {
                window.put(RChar, window.getOrDefault(RChar, 0) + 1);
                // 当need的右指针所指字符数量与window的右指针所指字符数量相等时,对total数量加一
                if (window.get(RChar).equals(need.get(RChar))) {
                    valid++;
                }
            }
            // 当valid达到need字符种类数时寻找最小值
            while (valid == need.size()) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    // 记录最小值一开始的位置
                    start = left;
                }
                // 获取左指针当前字符,并将左指针左移
                char LChar = s.charAt(left++);
                if (window.containsKey(LChar)) {
                    // 当LChar的个数相等时,说明左指针左移一位后肯定不相等,所以total减一
                    if (window.get(LChar).equals(need.get(LChar))) {
                        valid--;
                    }
                    window.put(LChar, window.get(LChar) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

前缀和主要适用的场景是原始数组不会被修改的情况下,频繁查询某个区间的累加和

prefix[i]就代表着nums[0..i-1]所有元素的累加和,如果我们想求区间nums[i..j]的累加和,只要计算prefix[j+1] - prefix[i]即可,而不需要遍历整个区间求和。

「差分数组」

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减

nums数组构造一个diff差分数组,diff[i]就是nums[i]nums[i-1]之差

阅读全文 »

图片

根据邻接表建图:

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1];
        int to = edge[0];
        // 修完课程 from 才能修课程 to
        // 在图中添加一条从 from 指向 to 的有向边
        graph[from].add(to);
    }
    return graph;
}
0%