week 8

sunshead · sunshead · commit 3f678e63117b · 2020-08-02T01:45:54.000-04:00
diff --git a/Week08/problems/146_LRU-cache.java b/Week08/problems/146_LRU-cache.java
@@ -0,0 +1,86 @@
+class LRUCache {
+    private int capacity;
+    private Node head;
+    private Node tail;
+    private Map<Integer, Node> map;
+
+    public LRUCache(int capacity) {
+        this.capacity = capacity;
+        head = null;
+        tail = null;
+        map = new HashMap<>();
+    }
+
+    public int get(int key) {
+        Node node = map.get(key);
+        if (node == null) {
+            return -1;
+        }
+        if (node != tail) {
+            if (node == head) {
+                head = head.next;
+            } else {
+                node.next.prev = node.prev;
+                node.prev.next = node.next;
+            }
+            tail.next = node;
+            node.prev = tail;
+            node.next = null;
+            tail = node;
+        }
+        return node.value;
+    }
+
+    public void put(int key, int value) {
+        Node node = map.get(key);
+        if (node == null) {
+            Node newNode = new Node(key, value);
+
+            if (capacity == 0) {
+                Node temp = head;
+                head = head.next;
+                map.remove(temp.key);
+                capacity++;
+            }
+            if (head == null && tail == null) {
+                head = newNode;
+            } else {
+                tail.next = newNode;
+                newNode.prev = tail;
+                newNode.next = null;
+            }
+            tail = newNode;
+            map.put(key, newNode);
+            capacity--;
+        } else {
+            // node already exit
+            node.value = value;
+            if (node != tail) {
+                if (node == head) {
+                    head = head.next;
+                } else {
+                    node.next.prev = node.prev;
+                    node.prev.next = node.next;
+                }
+                tail.next = node;
+                node.prev = tail;
+                node.next = null;
+                tail = node;
+            }
+        }
+    }
+}
+
+class Node {
+    int key;
+    int value;
+    Node prev;
+    Node next;
+
+    public Node(int key, int value) {
+        this.key = key;
+        this.value = value;
+        prev = null;
+        next = null;
+    }
+}
diff --git a/Week08/problems/190_reverse-bits.java b/Week08/problems/190_reverse-bits.java
@@ -0,0 +1,17 @@
+public class Solution {
+    // need to treat n as an unsigned value
+    public int reverseBits(int n) {
+        if (n == 0) {
+            return 0;
+        }
+        int res = 0;
+        for (int i = 0; i < 32; i++) {
+            res <<= 1;
+            if ((n & 1) == 1) {
+                res++;
+            }
+            n >>= 1;
+        }
+        return res;
+    }
+}
diff --git a/Week08/problems/191_number-of-1-bits.java b/Week08/problems/191_number-of-1-bits.java
@@ -0,0 +1,11 @@
+public class Solution {
+    // need to treat n as an unsigned value
+    public int hammingWeight(int n) {
+        int sum = 0;
+        while (n != 0) {
+            n &= n - 1;
+            sum++;
+        }
+        return sum;
+    }
+}
diff --git a/Week08/problems/231_power-of-two.java b/Week08/problems/231_power-of-two.java
@@ -0,0 +1,8 @@
+class Solution {
+    public boolean isPowerOfTwo(int n) {
+        if (n < 1) {
+            return false;
+        }
+        return (n & (n -1)) == 0;
+    }
+}
diff --git a/Week08/problems/242_valid-anagram.java b/Week08/problems/242_valid-anagram.java
@@ -0,0 +1,18 @@
+class Solution {
+    public boolean isAnagram(String s, String t) {
+        if (s.length() != t.length()) {
+            return false;
+        }
+        int[] count = new int[26];
+        for (int i = 0; i < s.length(); i++) {
+            count[s.charAt(i) - 'a']++;
+            count[t.charAt(i) - 'a']--;
+        }
+        for (int num: count) {
+            if (num != 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+}
