链表反转 原地反转、头插法、递归 LeetCode 206 剑指offer 24 Java实现

    //双指针法(原地反转)
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null, cur = head, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //头插法
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode();
        while (head != null) {
            ListNode next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }

    //递归法
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead =  reverseList(head.next);
        head.next.next = head;
        //这一句实际上执行一次就够了,
        head.next = null;
        return  newHead;
    }

    //递归法优化
    public ListNode reverseList4(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = helper(head);
        head.next = null;
        return newHead;
    }

    public ListNode helper(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = helper(head.next);
        head.next.next = head;
        return newHead;
    }

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();
    }

}

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/

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