子序列题型
子序列问题[递增的三元子序列](334. 递增的三元子序列 - 力扣（LeetCode）)
最好的：时间复杂度O(n),空间复杂度O(1)
方法1：转换成最长递增子序列问题 时间复杂度为O(nlogn)
方法2：遍历中间元素，维护两个数组 leftNum[] rightNum[] 左边元素的最小值和右边元素的最大值 时间O(n) 空间O(1)
方法3：贪心
思想：为了找到递增的三元子序列，第一个数和第二个数要尽可能的小，这样找到递增的三元子序列的可能性更大
123456789101112131415161718public boolean increasingTriplet(int[] nums) { int n = nums.length; if(n<3){ return false; } int first = nums[0]; int second = Integer.MAX_VALUE; for(int i = 1;i < n;i++){ if(nums[ ...
2023, 平安喜乐
回顾2022年，2022，给了我们一次冬奥会，让我们认识了谷爱凌，羽生结弦；给了我们一首瑜伽垫和一首爱你，让当爹当妈的人做回了男孩女孩；给了我们一张专辑，听了一次最伟大的作品；还有一个足球，让我们送别了青春。2023年，愿大家兔年吉祥，平安喜乐！
--除夕
手写LRU、LFU
手写LRU、LFULRULeast Recently Used
借助链表，表尾是最近访问的数据，表头是最近最久未使用的数据。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123class LRUCache { // 思路，构造新的数据结构 哈希链表 // 也就是hash表加上双向链表 // 尾部是最近存放的元素，头部是最近最久未使用的元素 private HashMap<Integer,Node> map; private DoubleList cache; i ...
321场周赛复盘
321场周赛追加字符以获得子序列
只想到O(n^2)
1234567891011121314151617181920public int appendCharacters(String s, String t) { int i=0; int j=0; int res=0; while(i<s.length()){ if(s.charAt(i)==t.charAt(j)){ int k=i; while(j<t.length()&&k<s.length()){ if(s.charAt(k)==t.charAt(j)){ j++; } k++; } res=j>res?j:res; } i++; ...
回溯算法
回溯算法
回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」
框架
12345678910result = []def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 // 其实，就是前序遍历的位置：在进入某一个节点之前执行 backtrack(路径, 选择列表) 撤销选择 // 后序遍历的位置，在离开某个节点之后执行
注意 Java 的语言特性，因为 Java 函数参数传的是对象引用，所以向 res 中添加 path 时需要拷贝一个新的列表，否则最终 res 中的列表都是空的
在递归之前做选择，在递归之后撤销选择
站在回溯树的一个节点上，你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
例1：「全排列」（无重复数字）
1234567891011121314151617181 ...
第 319 场周赛复盘
第 319 场周赛复习：
求两个数的最大公因数
123int gcd(int a,int b){ return b==0 ? a:gcd(b,a%b);}
区间调度问题，无重复区间
思路：先按照end排序，寻找下一个start要大于等于这个end
例题：无重叠区间
1234567891011121314class Solution { public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals,(a,b)-> a[1]-b[1]); int count=1; int end=intervals[0][1]; for(int i=1;i<intervals.length;i++){ if(intervals[i][0]>=end){ count++; end=int ...
素数 & 模幂
素数，模幂高效计算技巧高效寻找素数204. 计数质数
使用素数筛选法
首先从 2 开始，我们知道 2 是一个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。
然后我们发现 3 也是素数，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素数了。
1234567891011121314151617181920class Solution { public int countPrimes(int n) { boolean isPrime[]=new boolean[n]; Arrays.fill(isPrime,true); for(int i=2;i*i<=n;i++){ if(isPrime[i]){ for(int j=i*i;j<n;j+=i){ isPrime[j]=false; ...
第 318 场周赛复盘
第318场周赛
本周周赛答得不太好，只acc一道，第二第三题均超时
Problem A - 对数组执行操作优化：如果是对数组原地操作
移动0就不需要辅助数组，使用快慢指针，fast遇到0的元素跳过，否则，复制给slow指针
然后，将slow后面的元素都复制给0
1234567891011121314void moveVal(int nums[],int val){ int slow=0; int fast=0; int n=nums.length; while (fast<n){ if(nums[fast]!=val){ nums[slow++]=nums[fast]; } fast++; } for (int i=slow;i<n;i++){ nums[i]=val; }}
Problem B - 长度为 K 子数组中的最大和滑动窗口
我在做的时候，滑动窗口，用HashS ...
图算法
图算法图的存储：
邻接矩阵和邻接表
1234List<Integer> graph[]=new List[numCourses];for(int i=0;i<numCourses;i++){ graph[i]=new LinkedList<>();}
首先，图的遍历和树的遍历的区别
图存在环，从一个节点遍历可能会走到自身；而树从一个节点出发，一定会走到叶子节点，所以遍历图需要辅助数组visited来记录是否被访问过。【所以，如果图一定不存在环，就可以不使用visited数组，】
1234567891011121314151617181920212223// 记录被遍历过的节点boolean[] visited;// 记录从起点到当前节点的路径boolean[] onPath;/* 图遍历框架 */void traverse(Graph graph, int s，boolean[] visited，boolean[] onPath) { if (visited[s]) return; //----前序遍历位置-- ...
链表题型
链表题型汇总
判断链表是否存在环，并找出这个环节点
通过快慢指针，如果快慢指针相遇，说明链表是存在环的。
剑指 Offer II 022. 链表中环的入口节点
方法1：遍历单链表，记录路径
方法2：不需要额外空间，通过以下方法
fast比slow多走了k步，k是环长度的整数倍。
假设相遇点距离环的入口起点为m;则head距离环入口起点k-m【相遇点再走k-m步也能到达环的入口起点】