回顾前面刷过的算法（3）

今天简单描述了一下算法思路并手敲了一下下面三个算法，算法题目是刷不完的，但是解题思想是有限的，我们需要学习的就是解题思想，代码展示如下

    //打家劫舍     //思路: 定义一个dp[i],表示偷前 i - 1 个房屋能偷到的最大金额     //则有递推关系式 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])     public int rob(int[] nums) {         if (nums == null || nums.length == 0) {             return 0;         }         int pre = 0, curr = nums[0];         for (int i = 2; i <= nums.length; i++) {             int temp = Math.max(curr, pre + nums[i - 1]);             pre = curr;             curr = temp;         }         return curr;     }       //多数元素     //思路: 方法有很多，这里采用的是每次消除两个不同元素，因为多数元素的数量是大于总数的一半     //所以消除到最后，剩余的元素一定是多数元素     public int majorityElement(int[] nums) {         if (nums == null || nums.length == 0) {             return -1;         }         int count = 0, currentNum = -1;         for (int num : nums) {             if (count == 0) {                 currentNum = num;                 count++;             } else {                 if (num == currentNum) {                     count++;                 } else {                     count--;                 }             }         }         return currentNum;     }             //LRU缓存     //思路: 采用双链表+HashMap实现，hashMap存储key与结点的对应关系便于查找，     //双链表存储结点便于增删     class LRUCache {         private int size;         private final int capacity;         private final DLinkedNode head;         private final DLinkedNode tail;         private final Map<Integer, DLinkedNode> cache = new HashMap<>();          class DLinkedNode {             int key;             int value;             DLinkedNode next;             DLinkedNode pre;              public DLinkedNode() {             }              public DLinkedNode(int _key, int _value) {                 key = _key;                 value = _value;             }         }          public LRUCache(int capacity) {             this.size = 0;             this.capacity = capacity;             head = new DLinkedNode();             tail = new DLinkedNode();             head.next = tail;             tail.pre = head;         }          public int get(int key) {             DLinkedNode node = cache.get(key);             if (node == null) {                 return -1;             }             //因为操作过，需要把它移动到双链表头部             moveToHead(node);             return node.value;         }          public void put(int key, int value) {             DLinkedNode node = cache.get(key);             if (node == null) {                 DLinkedNode newNode = new DLinkedNode(key, value);                 cache.put(key, newNode);                 addToHead(newNode);                 size++;                 if (size > capacity) {                     DLinkedNode temp = removeTail();                     cache.remove(temp.key);                     size--;                 }             } else {                 node.value = value;                 moveToHead(node);             }         }          private void moveToHead(DLinkedNode node) {             removeNode(node);             addToHead(node);         }          private void removeNode(DLinkedNode node) {             node.next.pre = node.pre;             node.pre.next = node.next;         }          private void addToHead(DLinkedNode node) {             node.next = head.next;             node.pre = head;             head.next.pre = node;             head.next = node;         }          private DLinkedNode removeTail() {             DLinkedNode temp = tail.pre;             removeNode(temp);             return temp;         }     }