提交作业

ryuhi · ryuhi · commit 55c123001f3e · 2020-08-03T02:06:28.000+08:00
diff --git a/Week08/LRUCache.java b/Week08/LRUCache.java
@@ -0,0 +1,90 @@
+import java.util.HashMap;
+import java.util.Map;
+
+public class LRUCache {
+
+    class CacheNode {
+        private int key;
+
+        private int value;
+
+        private CacheNode prev;
+
+        private CacheNode next;
+
+        public CacheNode() {}
+
+        public CacheNode(int key, int value) {
+            this.key = key;
+            this.value = value;
+        }
+    }
+
+    private Map<Integer, CacheNode> instance;
+
+    private int size;
+    private int capacity;
+    private CacheNode head, tail;
+
+
+    public LRUCache(int capacity) {
+        instance = new HashMap<>(capacity);
+        this.capacity = capacity;
+        // 使用伪头部和伪尾部节点
+        head = new CacheNode();
+        tail = new CacheNode();
+        head.next = tail;
+        tail.prev = head;
+    }
+
+    public int get(int key) {
+        CacheNode node = instance.get(key);
+        if (null == node) {
+            return -1;
+        }
+        int value = node.value;
+        moveToHead(node);
+        return value;
+    }
+
+    public void put(int key, int value) {
+        CacheNode node = instance.get(key);
+        if (null == node) {
+            size++;
+            if(size > capacity) {
+                CacheNode node1 = removeTail();
+                instance.remove(node1.key);
+                size--;
+            }
+            CacheNode newNode = new CacheNode(key, value);
+            instance.put(key, newNode);
+            addToHead(newNode);
+            return;
+        }
+        node.value = value;
+        moveToHead(node);
+    }
+
+    private void addToHead(CacheNode node) {
+        node.prev = head;
+        node.next = head.next;
+        head.next.prev = node;
+        head.next = node;
+    }
+
+    private void removeNode(CacheNode node) {
+        node.prev.next = node.next;
+        node.next.prev = node.prev;
+    }
+
+    private void moveToHead(CacheNode node) {
+        removeNode(node);
+        addToHead(node);
+    }
+
+    private CacheNode removeTail() {
+        CacheNode res = tail.prev;
+        removeNode(res);
+        return res;
+    }
+}
diff --git a/Week08/NOTE.md b/Week08/NOTE.md
@@ -1 +1,61 @@
-学习笔记
+学习笔记
+```java
+    public void bubbleSort(int[] nums) {
+        int size = nums.length;
+        for (int i = 0; i < size -1; i++) {
+            for (int j = i; j < size - 1 - i; j++) {
+                int tmp = nums[j];
+                if (nums[j] > nums[j+1]) {
+                    nums[j] = nums[j+1];
+                    nums[j+1] = tmp;
+                }
+            }
+        }
+    }
+
+   public void selectionSort(int[] arr) {
+        int len = arr.length;
+        int minIndex, temp;
+        for(int i = 0; i < len - 1; i++) {
+            minIndex = i;
+            for(int j = i + 1; j < len; j++) {
+                if(arr[j] < arr[minIndex]) {     // 寻找最小的数
+                    minIndex = j;                 // 将最小数的索引保存
+                }
+            }
+            temp = arr[i];
+            arr[i] = arr[minIndex];
+            arr[minIndex] = temp;
+        }
+    }
+
+    public void insertionSort(int[] arr) {
+        int len = arr.length;
+        int preIndex, current;
+        for(int i = 1; i < len; i++) {
+            preIndex = i - 1;
+            current = arr[i];
+            while(preIndex >= 0 && arr[preIndex] > current) {
+                arr[preIndex + 1] = arr[preIndex];
+                preIndex--;
+            }
+            arr[preIndex + 1] = current;
+        }
+    }
+
+    public void shellSort(int[] arr) {
+        int len = arr.length;
+        for(int gap = (int) Math.floor(len / 2); gap > 0; gap = (int) Math.floor(gap / 2)) {
+            for(int i = gap; i < len; i++) {
+                int j = i;
+                int current = arr[i];
+                while(j - gap >= 0 && current < arr[j - gap]) {
+                    arr[j] = arr[j - gap];
+                    j = j - gap;
+                }
+                arr[j] = current;
+            }
+        }
+    }   
+```
+
diff --git a/Week08/ReversePairs.java b/Week08/ReversePairs.java
@@ -0,0 +1,37 @@
+package com.ryuhi.execute.leetcode;
+
+public class ReversePairs {
+
+    public int reversePairs(int[] nums) {
+        if(nums == null || nums.length == 0) {
+            return 0;
+        }
+        return mergeSort(nums,0,nums.length-1);
+    }
+
+    public int mergeSort(int[] nums,int left,int right){
+        if(right <= left ){
+            return 0;
+        }
+        int mid = (left+right) >> 1;
+        int count = mergeSort(nums,left,mid)+mergeSort(nums,mid+1,right);
+        // 中间数组用于合并
+        int[] cache = new int[right-left+1];
+        int i = left, j = mid+1, k = 0, tmp = left;
+        while(j <= right){
+            while(tmp <= mid && nums[tmp] <=  (long)nums[j] << 1) {
+                tmp++;
+            }
+            while(i <= mid   &&  nums[i]  <   nums[j] ) {
+                cache[k++] = nums[i++];
+            }
+            cache[k++] = nums[j++];
+            count += mid - tmp + 1 ;
+        }
+        while(i <= mid) {
+            cache[k++] = nums[i++];
+        }
+        System.arraycopy(cache,0,nums,left,right- left +1);
+        return count;
+    }
+}
