海量数字去重
40亿个QQ号，要求相同的QQ号码仅保留一个，内存限制为1个G，怎么实现？
1：申请一个足够大的BitMap，大小为40亿个bit，也就是： 4000000000 * 1 /8/1024/1024 = 476M 只需要不到500MB的空间就可以搞定！
2：遍历这40亿QQ号，把每个号码映射到BitMap中，把对应位置的bit设置为1。 比如，QQ号“12345678”会直接映射到BitMap的第“12345678”个位置，然后置为1，表示它已经出现过。
3：通过遍历BitMap，找出所有bit值为1的位置，这些就是所有的去重后的QQ号。
实现一个LRU算法
实现一个LRU（最近最少使用）缓存可以通过使用HashMap和双向链表来实现。HashMap用于快速查找缓存中的元素，而双向链表用于维护元素的使用顺序
使用HashMap存储键值对，以便快速访问
使用双向链表维护元素的使用顺序，最近使用的元素放在链表头部，最少使用的元素放在链表尾部
每次访问或插入元素时，将该元素移动到链表头部
当缓存容量达到上限时，移除链表尾部的元素
class LRUCache {
private class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final HashMap<Integer, Node> map;
private final Node head;
private final Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.head = new Node(0, 0); // 哨兵节点，头部
this.tail = new Node(0, 0); // 哨兵节点，尾部
head.next = tail;
tail.prev = head;
}
//从map中获取节点，如果不存在返回-1。如果存在，将节点移动到链表头部，并返回节点的值。
public int get(int key) {
Node node = map.get(key);
if (node == null) {
return -1; // 如果键不存在，返回-1
}
moveToHead(node); // 将访问的节点移动到头部
return node.value;
}
//检查键是否存在于map中,如果不存在，创建新节点并添加到链表头部。如果map的大小超过容量，移除链表尾部的节点。如果存在，更新节点的值并移动到链表头部。
public void put(int key, int value) {
Node node = map.get(key);
if (node == null) {
Node newNode = new Node(key, value);
map.put(key, newNode);
addNode(newNode);
if (map.size() > capacity) {
Node tail = popTail();
map.remove(tail.key);
}
} else {
node.value = value;
moveToHead(node);
}
}
//将节点添加到链表头部
private void addNode(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
//从链表中移除节点
private void removeNode(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
}
//将节点移动到链表头部
private void moveToHead(Node node) {
removeNode(node);
addNode(node);
}
//移除并返回链表尾部的节点
private Node popTail() {
Node res = tail.prev;
removeNode(res);
return res;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 返回 1
cache.put(3, 3); // 该操作会使得键 2 作废
System.out.println(cache.get(2)); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得键 1 作废
System.out.println(cache.get(1)); // 返回 -1 (未找到)
System.out.println(cache.get(3)); // 返回 3
System.out.println(cache.get(4)); // 返回 4
}
}
数组找两数之和-简单
给定一个数组和一个目标和，从数组中找两个数字相加等于目标和，输出这两个数字的下标。
两层循环
public int[] twoSum(int[] nums, int target) {
int []ans=new int[2];
for(int i=0;i<nums.length;i++){
for(int j=(i+1);j<nums.length;j++){
if(nums[i]+nums[j]==target){
ans[0]=i;
ans[1]=j;
return ans;
}
}
}
return ans;
}
时间复杂度：两层 for 循环，O（n²）
空间复杂度：O（1）
hash表单循环
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
int sub=target-nums[i];
//考虑一个元素只能用一次
if(map.containsKey(sub)&&map.get(sub)!=i){
return new int[]{i,map.get(sub)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
时间复杂度：降为 O（n）
空间复杂度：空间换时间，开辟了一个 hash table ，空间复杂度变为 O（n）
还可以不初始化map
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int sub=target-nums[i];
if(map.containsKey(sub)){
return new int[]{i,map.get(sub)};
}
//时间换空间，不先初始化
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}