十道经典面试算法真题详解-ag真人游戏

大家可以看下这篇回溯文章哈，有回溯算法的框架套用。

面试必备：回溯算法详解

7. lru 缓存

请你设计并实现一个满足 lru (最近最少使用) 缓存 约束的数据结构。

实现 lrucache 类：

• lrucache(int capacity) 以 正整数 作为容量 capacity 初始化 lru 缓存

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以o(1) 的平均时间复杂度运行。

示例：

输入
["lrucache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
lrucache lrucache = new lrucache(2);
lrucache.put(1, 1); // 缓存是 {1=1}
lrucache.put(2, 2); // 缓存是 {1=1, 2=2}
lrucache.get(1);    // 返回 1
lrucache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lrucache.get(2);    // 返回 -1 (未找到)
lrucache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lrucache.get(1);    // 返回 -1 (未找到)
lrucache.get(3);    // 返回 3
lrucache.get(4);    // 返回 4

这道题，出现的频率还是挺高的，很多小伙伴在面试时，都反馈自己遇到过原题。

lru，least recently used，即最近使用过的数据是有用的，可以使用双链表 hashmap解答，双链表用于存储lrucache的数据，hashmap实现o（1）的平均时间复杂度。

• 每次从链表尾部添加元素，靠尾的元素就是最近使用过

• 某个key可以通过哈希表快速定位到节点。

对于双链表，需要做哪些事呢。

• 首先是链表初始化，为了方便处理i，虚拟一个头节点和尾结点。

• 添加元素时，放到链表的尾部，表示该元素最近使用过

• 删除双向链表的某个节点

• 删除并返回头节点，表示删除最久未使用的元素

• 返回链表当前长度

lru缓存有哪些方法

• 构造函数初始化方法

• get和put方法

• makerecently 设置某个元素最近使用过的方法，哈希表已经有该元素

• addrecently 添加最近使用过的元素，同时更新map

• deletekey 删除某个key对应的元素,同时删除map上的节点

• removeleastrecently 删除最久未使用的元素

完整代码如下：

class node {
  
    int key,val;
    node next,prev;
    public node(int key,int val){
  
        this.key = key;
        this.val = val;
    }
}
class doublelist {
  
    //虚拟出头节点和尾结点
    private node head, tail;
    private int size;
    //初始化双链表
    public doublelist() {
  
        //虚拟头结点
        head = new node(0, 0);
        //虚拟头结点
        tail = new node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }
    //要加到链表尾部，且越靠近链表尾部，越表示最近使用过
    public void addlast(node x) {
  
        //比如当前链表为：head <-> 1 <-> tail，加入结点x = 2
        x.prev = tail.prev;
        // 完成结点2指向两端的箭头  head <-> 1 <- 2 -> tail; 此时tail.pre = 结点1还未断开
        x.next = tail;
        //head <-> 1 <-> 2 -> tail;
        tail.prev.next = x;
        //head <-> 1 <-> 2 <-> tail;
        tail.prev = x;
        //更新链表长度
        size  ;
    }
    // 删除指定结点
    public void remove(node x) {
  
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }
    // 删除并返回头结点
    public node removehead() {
  
        if (head.next == tail) {
  
            return null;
        }
        node first = head.next;
        // size在remove中更新了
        remove(first);
        // 用作在哈希表中移除最久未使用的数据值
        return first;
    }
    // 获取链表长度
    public int getsize() {
  
        return size;
    }
}
public class lrucache {
  
    private map map;
    private doublelist doublelist;
    private int cap;
    public lrucache(int capacity) {
  
        this.map = new hashmap<>();
        this.doublelist = new doublelist();
        this.cap = capacity;
    }
    public int get(int key) {
  
        if (map.containskey(key)) {
  
            // 先将key标记为最近使用，再返回value
            makerecently(key);
            return map.get(key).val;
        } else {
  
            return -1;
        }
    }
    public void put(int key, int value) {
  
        if (map.containskey(key)) {
  
            deletekey(key); // 从原map中移除该key
            addrecently(key, value); // 更新最近使用
            return;
        }
        int size = doublelist.getsize();
        if (size == cap) {
   // 说明需要移除最久未使用的元素了
            removeleastrecently();
        }
        addrecently(key, value); //添加新的元素进来
    }
    public void makerecently(int key) {
   // 将某个key标记为最近使用的元素（map中已存在的）
        node x = map.get(key);
        doublelist.remove(x); // 先从双链表删除
        doublelist.addlast(x); // 再添加到链表末尾， 因为尾部是最近使用过的元素
    }
    public void addrecently(int key, int value) {
   // 添加最近使用过的元素
        node x = new node(key, value);
        doublelist.addlast(x);
        map.put(key, x);  //更新map
    }
    public void deletekey(int key) {
  
        node x = map.get(key);
        map.remove(key);
        doublelist.remove(x); // 在map中和cache中同时删除
    }
    // 删除最久未使用的元素
    public void removeleastrecently() {
  
        // 最久未使用的一定在链表头部
        node oldnode = doublelist.removehead();
        int oldkey = oldnode.key;
        map.remove(oldkey);
    }
}

8. 合并k个升序链表

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

合并两个有序链表，是比较简单的，相信大家都会做。那么如何合并k个有序链表呢？其实道理是一样的，我们可以借用优先级队列找出最小节点，完整代码如下：

class solution {
  
    public listnode mergeklists(listnode[] lists) {
  
        if(lists.length==0){
  
            return null;
        }
        //虚拟节点
        listnode head = new listnode(0);
        listnode tail = head;
        //优先队列
        priorityqueue queue = new priorityqueue<>(lists.length,(a, b)->(a.val-b.val));
        //将k个链表头节点合并最小堆
        for (listnode node: lists) {
  
            if (node != null) {
  
                queue.add(node);
            }
        }
        while (!queue.isempty()) {
  
            //获取最小节点，放到结果链表中
            listnode node = queue.poll();
            tail.next = node;
                        if (node.next != null) {
  
                queue.add(node.next);
            }
            //指针链表一直往前
            tail = tail.next;
        }
        return head.next;
    }
}

9. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

这道题可以使用滑动窗口来实现。滑动窗口就是维护一个窗口，不断滑动，然后更新答案。

滑动窗口的大致逻辑框架，伪代码如下：

int left =0，right = 0;
while (right < s.size()){
  
  //增大窗口
  window.add(s[right]);
  right  ;
    while (window needs shrink){
  
    //缩小窗口
    window.remove (s[left]);
    left   ;
  }
}

解法流程如下：

• 首先呢，就是获取原字符串的长度。

• 接着维护一个窗口（数组、哈希、队列）

• 窗口一步一步向右扩展

• 窗口在向右扩展滑动过程，需要判断左边是否需要缩减

• 最后比较更新答案

完整代码如下：

int lengthoflongestsubstring(string s){
  
     //获取原字符串的长度
     int len = s.length();
     //维护一个哈希集合的窗口
     set windows = new hashset<>();
     int left=0,right =0;
     int res =0;
     while(right

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

class solution {
  
    public listnode removenthfromend(listnode head, int n) {
  
        listnode dummy = new listnode(0, head);
        listnode first = head;
        listnode second = dummy;
        //first 比second先走n个节点
        for (int i = 0; i < n;   i) {
  
            first = first.next;
        }
        //直到走到链表尾部
        while (first != null) {
  
            first = first.next;
            second = second.next;
        }
        //删除节点
        second.next = second.next.next;
        listnode ans = dummy.next;
        return ans;
    }
}