LeetCode-100题

146. lru-cache(medium)

LeetCode

这题单独拿出来都够写一篇博客的了。
看了别的大佬写的解析，自己来复述一遍理清思路。
想要get和put的时间复杂度为O(1)，那么这个数据结构就要查找快（get）、插入删除快（put）
在已知的结构中，hashmap的get时间复杂度是O(1)的，但是没有保证顺序
链表的插入和删除很快，但是查找很慢
所以可以将链表和hashmap结合起来，java中也提供了这个的实现“LinkedHashMap”。
在这里先不讨论LinkedHashMap的具体实现,先实现lru的get和put的伪代码。

int get(int key){
    if(key 不存在){
        return -1;
    }else{
        将(k,v)提到开头;
        return val;
    }
}

void put(int key,int val){
    Node x = new Node(key,val);
    if(key 存在){
        删除旧数据;
        将新的key插到开头;
    }else{
        if(cache已满){
            删除链表的最后一个数据;
            删除map中的映射;
        }
        将新的节点x插入开头;
        map中新增映射;
    }
}

参考：labuladong

class LRUCache {
    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        int val = map.get(key).val;
        put(key,val);
        return val;
    }

    public void put(int key, int value) {
        Node x = new Node(key,value);
        if(map.containsKey(key)){
            cache.remove(map.get(key));
            cache.addFirst(x);
            map.put(key,x);
        }else{
            if(cap == cache.size()){
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(x);
            map.put(key,x);
        }
    }

}
class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

class DoubleList{
    private Node head, tail;
    private int size;
    //链表头部添加节点
    public void addFirst(Node node){
        if (head == null) {
            head = tail = node;
        } else {
            Node n = head;
            n.prev = node;
            node.next = n;
            head = node;
        }
        size++;
    }
    //移除Node节点
    public void remove(Node node){
        if (head == node && tail == node) {
            head = null;
            tail = null;
        } else if (tail == node) {
            node.prev.next = null;
            tail = node.prev;
        } else if (head == node) {
            node.next.prev = null;
            head = node.next;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        size--;
    }
    //移除最后一个节点
    public Node removeLast(){
        Node node = tail;
        remove(tail);
        return node;
    }
    //获取链表长度
    public int size(){
        return size;
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

169. majority-element (Easy)

LeetCode

这题用HashMap是很好解的，但是题中要求：
设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题

//解法1，HashMap
//时间复杂度O(N)，空间复杂度O(N)
public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap();
        for(int num:nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else{
                map.put(num,1);
            }
        }
        int len = nums.length / 2;
        for(int key : map.keySet()){
            if(map.get(key) > len){
                return key;
            }
        }
        return -1;
}

第二种解法是使用排序，将整个数组使用Arrays.sort排序，中间的那个就是要的答案

public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
}

解法三：
候选人(cand_num)初始化为nums[0]，票数count初始化为1。
当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
当票数count为0时，更换候选人，并将票数count重置为1。
遍历完数组后，cand_num即为最终答案。

public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
}

461. hamming-distance (Easy)

LeetCode

汉明距离：
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

1.对两个数进行异或运算，异或运算的性质（不同则为1相同则为0），我们要算出xor的1的个数就好了
2.遇到最右边的 1 后，如果可以跳过中间的 0，直接跳到下一个 1，效率会高很多
3.x & (x - 1)可以完成2的操作

public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int distance = 0;
        while(xor != 0){
            distance += 1;
            xor = xor & (xor - 1);
        }
        return distance;
    }