Leetcode 146 LRU(最近最少使用)缓存机制

最近最少使用的一个缓存机制是操作系统这门课程里面的一个概念

非常直观基本的一个思路就是HashMap+加双端链表

使用 HashMap 是为了提高查找的一个效率在O(1)

双端链表是为了提高增加或者交换元素位置时的开销O(1)

当然这么做是代价,是使用了一些额外的空间O(n)

下面的代码参考自官方文档的题解。

class LRUCache extends LinkedHashMap<Integer, Integer>{

    int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        int res = super.getOrDefault(key, -1);
        return res;
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {

        return size() > capacity;
    }
}

值得注意的是Java语言内部实现了这个结构非常和我们需求很相符,

其中内部内置final private boolean assessOrder这个变量,如果这个变量值是true的话,每次get操作get到的那个元素/(或者put插入的元素)会插入到链表头的位置。是在初始化的时候默认值是false,所以我们要在构造函数显式给定

同时在put方法结束前的最后会调用remove all these entry这个方法,这个方法返回true,就会去掉最后一个元素,默认是返回一个false,所以我们要对这个方法进行重写,以满足我们的需求。

当然也可以手写一个双向链表和使用Hashmap的方式实现

class LRUCache{

    class Node {
        int val;
        int key;
        Node pre;
        Node next;
        public Node(int key, int val) {this.key = key; this.val = val;}
    }
    int capacity;
    Node dummyHead = new Node(0,0);
    Node dummyTail = new Node(0,0);
    HashMap<Integer, Node> hm = new HashMap<>();
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
    }
    
    public int get(int key) {
        if (hm.containsKey(key)) {
            Node cur = hm.get(key);
            moveToHead(cur, true);
            return cur.val;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (hm.containsKey(key)) {
            Node cur = hm.get(key);
            cur.val = value;
            moveToHead(cur, true);
        } else {
            Node cur = new Node(key, value);
            hm.put(key, cur);
            moveToHead(cur, false);
            if (hm.size() > capacity)
                removeTail();
        }
    }

    private void moveToHead(Node cur, boolean removeFlag) {
        if (removeFlag) {
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        cur.pre = dummyHead;
        cur.next = dummyHead.next;
        dummyHead.next.pre = cur;
        dummyHead.next = cur;
    }

    private void removeTail() {
        Node cur = dummyTail.pre;
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
        cur.next = null;
        cur.pre = null;
        hm.remove(cur.key);
    }

    private void printList(){
        Node cur = dummyHead.next;
        while (cur != dummyTail) {
            System.out.print("" + cur.val + "->");
            cur = cur.next;
        }
        System.out.println();
    }

}

迭代、递归、动态规划的粗浅区别

简单说说个人对这三个概念的粗浅认识

递归可以说是最容易理解的一个概念 ,简单的说就是函数里面调用自己,问题转化为小问题,分而治之。

迭代的理解 就是通过上一步的结果,通过一个函数,得到现在的结果;而现在的结果,用同样的函数,得到再下一步的结果;不断迭代,简单举一个累加过程的例子, \( sum_{new} = sum_ {old} + arr[i] \) 。

或者从数学中很有名的牛顿迭代法来理解,之所以叫做迭代就是由于牛顿迭代法求根的时候,有一个迭代公式

\(x_{new} = x_{old} – \frac{f'(x_ {old} )}{f(x_ {old} )}\)

就是符合迭代的一个思想,就是用上一步的结果推下一步的结果, 而且每一步都是相同的公式, 不断迭代,直到逼近零点。

动态规划有点类似于迭代的方式,但是又不完全等同于迭代,因为动态规划是一种自底向上的一个算法,并且有自己的状态转移方程和最优子结构性质,转移方程有点类似于迭代法中的迭代公式。

华为2020.5.13 实习笔试

第一题 给定两个年月日,第一个日期给了星期几,推断第二个日期是星期几。

思路:将日期转化为公元0000年起的绝对天数,注意闰年的判断等。然后再相减两个日期,在做一些mod7运算和负数处理就可以了。

第二题 给定一组站台和路灯的坐标,路灯可以调整亮度且所有路灯的亮度一致,所有站台被照亮之后的最小亮度值。

思路:将路灯的坐标进行一下排序,然后便利站台列表,找出和站台距离最近的那个路灯的距离,并且求所有站台最近路灯距离的最大值,作为最终的最小亮度值。可能涉及二分查找等。

第三题:有特定数量的书和特定数量的读者,每个读者都有喜欢的数的列表,若要满足所有读者的需求,书本数量的最小值是多少。

思路:可以将问题转化为二部图进行求解。

LeetCode 50 pow(x,n) 与 java中的数组越界问题

这题参考了leetcode官方题解中的迭代法思路,主要是结合了二进制位运算的优势以及结合二进制表示数的特点进行求解。

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        long N = n;
        boolean isPos = N > 0 ? true : false;
        N = Math.abs(N);
        double res = 1;
        double tmp = x;
        for(int i = 0; i < 32; i ++) {
            long addOrNot = N & 1;
            if (addOrNot == 1) res *= tmp;
            tmp *= tmp;
            N >>= 1;    
       }
       return isPos ? res : 1.0 / res;
    }

解体的时候需要注意一个取绝对值的时候的越界问题,因为n如果取了最小值,即32位的,不管取绝对值也好,前面添加符号也好,都是原来的最小值,因此会对逻辑产生影响。因此采用long类型的变量来避免额外的错误。

        int i = Integer.MIN_VALUE;
        System.out.println(i);
        System.out.println(-i);
        System.out.println(Math.abs(i));

对应输出结果为

leetcode 39 & 40 组合总数

回溯法解决

两道题的思路都是类似的,用回溯来解决问题。

39题由于数值数字没有重复的,并且每个数字可以用零到无数次,所以是一个比较简单的回溯。

40题的数字是有出现重复的,并且每个数字只可以用一次或者不用, ,所以需要先对待用的数字进行排序, 然后再在loop循环里面,排除重复的情况。

39题代码

class Solution:
    
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        def backtrace(index, tmp, target):
            if target <= 0:
                if target == 0:
                    self.res.append(tmp.copy())
            else:
                for i in range(index, len(candidates)):
                    tmp.append(candidates[i])
                    backtrace(i, tmp, target - candidates[i])
                    tmp.pop()
        backtrace(0, [], target)
        return self.res

40题代码

class Solution(object):
    def combinationSum2(self, candidates, target):
        self.res = []
        candidates.sort()
        def backtrace(index, tmp, target):
            if target == 0:
                self.res.append(tmp[:])
            elif target > 0:
                for i in range(index, len(candidates)):
                    if i > index and candidates[i] == candidates[i-1]: continue
                    tmp.append(candidates[i])
                    backtrace(i + 1, tmp, target - candidates[i])
                    tmp.pop()
        
        backtrace(0, [], target)
        return self.res

参考链接:https://www.bilibili.com/video/BV1V4411h7dU/

编程题:带障碍的机器人的最短路径

题目:输入为一个正数n以及一个block数组表示障碍所在的坐标x,y,机器人从左上角0,0开始,每一步只能走上下左右的位置,并且每走一步就会放block数组里面的一个障碍,如果机器人已经经过这个位置障碍就不放置,没有经过这个位置block就放置,直到block放置完成为止,如果机器人能够到达右下角就返回机器人所经过格子的最少个数,否则返回-1。

很明显,这道题就是要使用,bfs广度优先搜索,问题 就是在block数组如何限制下一步选择? 选用bfs带有step的函数模板,然后在每一个step,将status数组里面的block所在的位置设为无法到达,那么问题就解决了。

import java.util.ArrayList;
import java.util.LinkedList;

class Position{
    public int x;
    public int y;
    public Position(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Test9 {
    public int solution() {
        int n = 5;
        int [][] block = {{0,1}, {1,1}, {2,1}, {3,1}, {4,3}, {3,3}};
        int blockCount = block.length;
        int [][] status = new int[n][n];
        if (n == 1) return 1;

        LinkedList<Position> q = new LinkedList<Position>();
        int step = 0;
        int x = 0, y = 0;
        status[x][y] = 1;
        q.add(new Position(x, y));

        while (!q.isEmpty()) {
            int roundCount = q.size();
            for (int i = 0; i < roundCount; i++) {
                Position cur = q.poll();
                if (step < blockCount && status[block[step][0]][block[step][1]] == 0)
                    status[block[step][0]][block[step][1]] = 2;
                if(cur.x == n - 1 && cur.y == n - 1) return step + 1;
                for (Position p: getNextPosition(cur, status, n)){
                    status[p.x][p.y] = 1;
                    q.add(p);
                }
            }
            step ++;
        }
        return -1;
    }
    
    public ArrayList<Position> getNextPosition(Position cur, int[][] status, int n) {
        ArrayList<Position> al = new ArrayList<>();
        int x = cur.x, y = cur.y;
        if (x + 1 < n &&  status[x + 1][y] == 0) al.add(new Position(x + 1, y));
        if (y + 1 < n &&  status[x][y + 1] == 0) al.add(new Position(x, y + 1));
        if (x - 1 >= 0 &&  status[x - 1][y] == 0) al.add(new Position(x - 1, y));
        if (y - 1 >= 0 &&  status[x][y - 1] == 0) al.add(new Position(x, y - 1));
        return al;
    }

    public void printStatus(int [][] status) {
        for (int i = 0; i < status.length; i++) {
            for (int j = 0; j < status[0].length; j++) {
                System.out.print(status[i][j] + " ");
            }
            System.out.println();
        }
    }
}

下面为测试用例的调试结果,更加直观,1表示bfs访问到的节点,2表示每一个时间步放置的障碍。

KMP 算法

首先贴出本人写的KMP算法,本人习惯next数组的第一位存的是-1,下面是代码:

def KMP(txt, pat):
    if pat == "": return 0
    def get_next_arr(pat):
        next_arr, j, k =[-1], 0, -1
        while j < len(pat) - 1:
            if k == -1 or pat[j] == pat[k]:
                k, j = k + 1, j + 1
                next_arr.append(k)
            else:
                k = next_arr[k]
        return next_arr

    next_arr = get_next_arr(pat)

    i, j = 0, 0
    while i < len(txt) and j < len(pat):
        if j == -1 or txt[i] == pat[j]:
            i, j = i + 1, j + 1
        else:
            j = next_arr[j]
    if j == len(pat):
        return i - j
    return -1

KMP代码关键有两个部分

首先是求解next数组,next数组记录的内容是pat中字串的最长相同前后缀的长度,这个数据需要先求出来,方便后续的字符串匹配处理。next数组求解过程中的k=next[k]这个步骤不太好理解,详细可以参考文章,或者视频

第二点就是在匹配主串的过程,其中需要借助next数组进行巧妙的指针变化,主串的指针可以实现不回退。 KMP算法的时间复杂度是O(n+m)

LeetCode 23 合并K个有序链表

这道题可以采用类似于归并排序的方式进行解题,一种自顶向下的方法,关键在于partition函数和merge两个函数。partition函数问题的规模大于2就不断的往下分,直至问题的规模小于等于2,当问题的规模为1的话就直接返回那个有序列表单问题的规模为2的话,就用merge函数合并两个列表并返回。

书写代码的过程中需要注意两个事项,

  • 当k等于0的时候,应该直接返回空
  • partition函数的一个边界情况,也需要好好斟酌一下
    • 因为在最终调用partition的时候,[0,len(lists)-1],也就是左闭右闭的一个区间
    • 只当左边界和右边界相同的时候,就直接返回的那个链表就可以,
    • 当左右边左边接小于右边界的时候就要取一个中间值,中间值是两数相加除以2并向下取整,所以厄在求左半边的一个partition结果的时候可以取m,右半边的左边界就要取m加1,因为是 左闭右闭的一个区间,这样也可以保证m不会大于右边界。
 class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        return self.partition(0, len(lists) - 1, lists)

    def partition(self,start,end,lists):
        # 左闭右闭
        if start == end:
            return lists[start]
        else:
            m = (start + end) // 2
            left = self.partition(start, m, lists)
            right = self.partition(m+1, end, lists)
            return self.merge(left, right)
        
    
    def merge(self, a ,b):
        dummy = tail = ListNode(0)
        while a and b:
            if a.val < b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a if a else b
        return dummy.next

有空可以练习一下非递归自底向上的归并代码。

Leetcode 21 合并两个有序链表

常规思路遍历比较进行合并

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(l1 != null && l2 != null){
            ListNode temp;
            if (l1.val < l2.val){
                temp = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                temp = new ListNode(l2.val);
                l2 = l2.next;
            }
            tail.next = temp;
            tail = temp;
        }
        if (l1 != null)
            tail.next = l1;
        if (l2 != null)
            tail.next = l2;
        return dummy.next;
    }

另一个比较有意思的思路是采用递归的方法。因为当某个链表中的元素已经加入有序链表中时,原始问题就转换为一个较小规模的问题。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null)
            return l1 == null? l2 : l1;

        if (l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
}

LeetCode 2 & LeetCode 445 两数相加

总结:

  • 熟练掌握单项链表的翻转操作(头插法),通常会使用一个dummy节点以辅助链表操作
  • 当一些问题存在逆序的情况下可以考虑用栈数据结构(具有先进后出的特点)进行操作

LeetCode 2

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = tail = ListNode(0)
        c = 0
        while (l1 or l2 or c != 0):
            a = l1.val if l1  else 0
            b = l2.val if l2  else 0
            temp = a + b + c
            c = temp // 10
            tail.next = ListNode(temp % 10)

            tail = tail.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return head.next

LeetCode 445

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1 = []
        stack2 = []
        while(l1):
            stack1.append(l1.val)
            l1 = l1.next
        while(l2):
            stack2.append(l2.val)
            l2 = l2.next
        dummy = ListNode(0)

        c = 0
        while(len(stack1) > 0 or len(stack2) > 0 or c != 0):
            a = stack1.pop() if len(stack1)>0 else 0
            b = stack2.pop() if len(stack2)>0 else 0
            s = a + b + c
            c = s // 10
            temp = ListNode(s % 10)

            p = dummy.next
            dummy.next = temp
            temp.next = p
        return dummy.next