PunchCode

以终为始

LRU与LFU

146. LRU缓存机制双向链表(存储结构) + 哈希表(快速索引). key为node的一部分, 也是用来索引的标志. class LRUCache { HashMap<Integer, Node> map; DoubleList cache; int capacity; public LRUCache(int capacity) { this.capacity = capacity; map

Posted by 小拳头 on Tuesday, February 16, 2021

数据结构与算法-并查集

框架照搬的参考3. class UF { private int count; //记录连通分量个数 private int[] parent; //存储若干棵树 private int[] size; //记录树的大小 public UF(int n) { this.count = n; parent = new int[n]; size = new int[n]; for (int i = 0; i < n;

Posted by 小拳头 on Monday, February 15, 2021

数据结构与算法-位运算

面试题05.07. 配对交换提取奇数位左移1位, 或上偶数位右移1位. class Solution { public int exchangeBits(int num) { return (((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1)); } } 参考 labuladong算法 L

Posted by 小拳头 on Sunday, January 17, 2021

数据结构与算法-贪心算法

贪心算法是动态规划的特殊情况, 因为贪心的每一步都需要选择最优解. 满足贪心选择性质, 就可以用贪心. 区间调度问题 435. 无重叠区间按右边界从小到大排序

Posted by 小拳头 on Friday, January 15, 2021

数据结构与算法-字符串

参考 labuladong算法 LeetCode提高班第一期——Week5字符串处理专题 leetcode acwing

Posted by 小拳头 on Wednesday, January 13, 2021

数据结构与算法-哈希表

1. 两数之和 class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])) return new int[]{map.get(target - nums[i]), i}; map.put(nums[i], i); } return new int[2]; } } 顺便把3Sum, 4Sum也总结了. 15. 三数之

Posted by 小拳头 on Tuesday, January 12, 2021

数据结构与算法-数学系列

这部分来自于<LeetCode提高班第三期——Week3数学专题>, 有的题不需要数学方法, 用动态规划或者利用数据结构做更容易想象

Posted by 小拳头 on Saturday, January 9, 2021

DFS与BFS

回溯 DFS很多情况下会和回溯结合起来, 先通过全排列问题来构建回溯问题的框架. 我的理解中, 回溯实际上就是一种剪枝的技巧. 算法的本质依然是遍历.

Posted by 小拳头 on Friday, January 8, 2021

数据结构与算法-数组系列

naive双指针 26. 删除排序数组中的重复项快慢指针, fast != slow就可以把slow的下一个重复的值删掉. class Solution { public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int slow = 0, fast =

Posted by 小拳头 on Monday, January 4, 2021

栈队列堆

先用leetcode专题进行练习. 队列实现 622. 设计循环队列利用循环队列节省空间, 可以复用申请的空间. class MyCircularQueue { private int[] queue; private int capacity; private int head; private int count; public MyCircularQueue(int k) { queue =

Posted by 小拳头 on Monday, December 28, 2020