LeetCode(101) -- 144, 146, 147, 148

P144. Binary Tree Preorder Traversal (Medium)

Given a binary tree, return the preorder traversal of its nodes’ values.

My Solution

Given a binary tree, return the preorder traversal of its nodes’ values.

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }

    private void preorder(TreeNode node, List<Integer> ans) {
        if (node == null) {
            return;
        }
        ans.add(node.val);
        preorder(node.left, ans);
        preorder(node.right, ans);
    }
}

100%

P146. LRU Cache (Medium)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up: Could you do both operations in O(1) time complexity?

Solution

public class LRUCache {

  class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;
  }

  private void addNode(DLinkedNode node) {
    /**
     * Always add the new node right after head.
     */
    node.prev = head;
    node.next = head.next;

    head.next.prev = node;
    head.next = node;
  }

  private void removeNode(DLinkedNode node){
    /**
     * Remove an existing node from the linked list.
     */
    DLinkedNode prev = node.prev;
    DLinkedNode next = node.next;

    prev.next = next;
    next.prev = prev;
  }

  private void moveToHead(DLinkedNode node){
    /**
     * Move certain node in between to the head.
     */
    removeNode(node);
    addNode(node);
  }

  private DLinkedNode popTail() {
    /**
     * Pop the current tail.
     */
    DLinkedNode res = tail.prev;
    removeNode(res);
    return res;
  }

  private Map<Integer, DLinkedNode> cache = new HashMap<>();
  private int size;
  private int capacity;
  private DLinkedNode head, tail;

  public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;

    head = new DLinkedNode();
    // head.prev = null;

    tail = new DLinkedNode();
    // tail.next = null;

    head.next = tail;
    tail.prev = head;
  }

  public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) return -1;

    // move the accessed node to the head;
    moveToHead(node);

    return node.value;
  }

  public void put(int key, int value) {
    DLinkedNode node = cache.get(key);

    if(node == null) {
      DLinkedNode newNode = new DLinkedNode();
      newNode.key = key;
      newNode.value = value;

      cache.put(key, newNode);
      addNode(newNode);

      ++size;

      if(size > capacity) {
        // pop the tail
        DLinkedNode tail = popTail();
        cache.remove(tail.key);
        --size;
      }
    } else {
      // update the value.
      node.value = value;
      moveToHead(node);
    }
  }
}

P147. Insertion Sort List (Medium)

Sort a linked list using insertion sort.

My Solution

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = head;
        while (curr.next != null) {
            int val = curr.next.val;
            ListNode insertionCurr = dummy;
            while (insertionCurr.next != null && insertionCurr.next.val < val) {
                insertionCurr = insertionCurr.next;
            }
            if (insertionCurr == curr) {
                curr = curr.next;
            } else {
                ListNode node = curr.next;
                curr.next = node.next;
                ListNode next = insertionCurr.next;
                insertionCurr.next = node;
                node.next = next;
            }
        }
        return dummy.next;
    }
}

66%

The Best Solution

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        return merge(insertionSortList(head), insertionSortList(mid));
    }
    ListNode merge(ListNode n1, ListNode n2) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while (n1 != null && n2 != null) {
            if (n1.val > n2.val) {
                ListNode tmp = n1;
                n1 = n2;
                n2 = tmp;
            }
            pre.next = n1;
            n1 = n1.next;
            pre = pre.next;
        }
        pre.next = n1 != null ? n1 : n2;
        return dummy.next;
    }
}

这明明是merge sort，不是insertion sort

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy=new ListNode(Integer.MIN_VALUE);
        dummy.next=head;//错误点
        ListNode cur=dummy;
        while(cur.next!=null){
            if(cur.val<=cur.next.val){
                cur=cur.next;//错误点，否则无限循环
                continue;
            } 
            ListNode n=cur.next;
            cur.next=cur.next.next;
            ListNode icur=dummy;
            while(icur.next.val<n.val) icur=icur.next;
            n.next=icur.next;
            icur.next=n;
            //cur=cur.next;//错误点 4->2->1->3 把2移到4的前面之后就不用cur=cur.next
        }
        return dummy.next;
    }
}

98% 思路跟我差不多，但简洁很多，也快很多。学习这个。

P148. Sort List (Medium)

Sort a linked list in O(n log n) time using constant space complexity.

Solution

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        return merge(sortList(head), sortList(mid));
    }
    
    private ListNode merge(ListNode n1, ListNode n2) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while (n1 != null && n2 != null) {
            if (n1.val > n2.val) {
                ListNode tmp = n1;
                n1 = n2;
                n2 = tmp;
            }
            pre.next = n1;
            n1 = n1.next;
            pre = pre.next;
        }
        pre.next = n1 != null ? n1 : n2;
        return dummy.next;
    }
}

97%