网站浏览思路,张家港网站建设门店,做视频网站需要什么服务器,云南SEO网站建设每日笔记 复习曲线
间隔1天、3天、7天、15天、30天#xff0c;然后以一个月为周期复习 2023. 12. 24
一定要每天早中晚都要复习一下
早中午每段一两道, 而且一定要是同一个类型, 不然刷起来都没有意义 11.29
开始向着面试刷题跟进!
每天刷4题左右 ,一周之内一定要是统一类…
每日笔记 复习曲线
间隔1天、3天、7天、15天、30天然后以一个月为周期复习 2023. 12. 24
一定要每天早中晚都要复习一下
早中午每段一两道, 而且一定要是同一个类型, 不然刷起来都没有意义 11.29
开始向着面试刷题跟进!
每天刷4题左右 ,一周之内一定要是统一类型
而且一定稍作总结, 了解他们的内在思路究竟是怎样的!! 12.26
斐波那契数
爬楼梯
最小花费爬楼梯
不同路径1/2 12.28
整数拆分
重点思路一个正整数可以分为两个或者多个多个可以用dp[i-j]代替一定不能直接分为乘以dp的情况因为这就默认了必须拆分为三个以上
不同的二叉搜索树
重点思路 把左右子树所有情况乘起来递归子树的问题。注意左右节点个数的边界 12.29
01背包理论 12.30
分割等和子集
很难看出来是01背包。满足的条件有
每个元素只有取和不取两个状态结果要满足某一部分和刚好等于什么什么value而背包问题是在限制的重量内计算他们价值最大值 这里只需把求最大值改成求刚好 sum即可此题的weight和value都是nums【i】因为是一个一个数字要求刚好和为sumdp【i】代表在i内之和最大为多少 本题要求刚好等于sum所以结束条件是dp[ sum ] sum 即总量为sum之内刚好最大为sum
最短无序连续子数组 12.31
209. 长度最小的子数组
思路滑动窗口先不断右移直到sumtarget 然后左指针左移直到小于target记录暂时的最小长度然后继续右移右移直到sumtarget 左指针左移直到小于target不断迭代最小长度
和为 K 的子数组
使用前缀和核心是
map.containskey(sum-k);
map.put(sum,map.getOrDefault(sum,0)1); 152. 乘积最大子数组
重点思路使用dp代表前i个最大乘积。但是我们注意到有可能含有负数因此只记录max值是不行的万一后面出现负数乘上去大于max就会使结果不对。
因此 我们需要两个dp数组记录max和min正和反向的最大值。每次迭代dp【i】时我们需要比较【当前数字、上一个max乘以当前数字、上一个min乘以当前数字】最大最小都记录下来。同时不断用max迭代结果res。
优化方式仍然可以采用迭代法。
4.打家劫社这个屋子偷不偷偷就加dp[i-2],不偷就等于dp【i-1】
有一个困扰很久的问题
我以为这个递推公式的意思是相邻的两个元素必须有一个得取。
其实并不是只是限制了要不要取 i 没说不取 i 就要取 i-1 我们等于的是dp【i-1】注意定义所以有可能出现连着两个都不取。但是不可能出现连着三个都不取。 2024 . 1 . 1
无重复字符最长子串
记住map里存放的是当前元素及其下标。如果有就更新到i和最新的 1.15
结束了13天的期末 回归面试征途 算法
最长子串老题
LRU缓存
知识点
聚集索引和二级索引非聚簇索引
回表查询
什么是联合索引
联合索引的创建
为什么需要注意联合索引中的顺序
联合索引的优势
什么是索引失效
覆盖索引
索引创建的原则、什么时候创建 2.27
放完寒假归来第二天正式进入状态重新回归算法题和八股文密集时代
3.5号之前看完八股文每天15集算法题每天至少4道开始
无重复子串 2.28
LRU缓存 3.1
LRU缓存 18分钟ac
三数之和 的双指针解法固定一个for循环再剩下两个双指针
反转链表复习了一遍迭代为什么是now ! null因为迭代完now是最后一个的下一个为什么是返回pre因为pre是现在的最后一个也就是反转过来以后链表的头部
还得复习递归法 3.3
数组中第k个最大元素
学会堆的相关知识学会快速排序 和这道题解法
快速排序方法
通过设定第一个为基准值middle还有左右两个边界交替与middle比较左比middle大就和右交换并且右开始扫描左比middle小就继续扫描下一个右比middle大就继续扫比middle小就赋值给左并且左开始扫描
超级重点必须先移动右指针再移动左指针 因为左指针一开始指的就是middle不能先移动
代码如下 void quickSort(int[] nums,int low,int high) {if(low high){return;}int left low;int right high;int middle nums[low];while(low high){while(low high nums[high--] middle); nums[low] nums[high];while(low high nums[low] middle);nums[high] nums[low];}nums[low] middle;//相遇点就是中值点quickSort(nums,left,low-1);quickSort(nums,low1,right);} 堆排序方法
本题可以直接使用堆
把所有元素加入进去当容量超过k时要寻找的top k的数就把heap顶的数poll出来这样最终遍历完一定是top k的那些数字
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueueInteger heap new PriorityQueue();for(int num:nums){heap.add(num);if(heap.size() k){heap.poll();}}return heap.peek();}
} 堆的知识点
大顶堆父节点大于左右儿子
小顶堆父节点小于左右儿子 重点 必须依次排满从上到下从左到右按顺序排
如何调整堆 LRU缓存
getNode里必须delete因为要查看一本书我们要抽出来放到顶层也就是getNode deleteputFront抽出书getNode来处理
delete和putFront都是很单纯的功能 注意put的写法要putFront然后保存到map 3.4 三数之和
本题需要积累的
if(k0 nums[k]nums[k-1] 必须是和k-1相比不能是k1否则会漏掉多个k的结果 continue;
if(tmp 0)
while(i j nums[i] nums[i]); 必须写成i这里既可以调整了i、j的位置还可以去除重复的数 一举两得
res.add(new ArrayList(Arrays.asList(nums[i],nums[j],nums[k]))); 记住这里的Arrays.asList() 反转链表
记住newHead就是底层的head这个的逻辑就是先通过 注意一定是传入head.next而不是head你传自己有什么意义就成原地打转了 .next才是下一个
这一句进入最底层这句的作用就是递归的入口 一层一层往回反转 每一层的head都自己做反转返回newHead进入上一层
class Solution {public ListNode reverseList(ListNode head) {if(head null || head.next null){return head;}ListNode newHead reverseList(head.next);head.next.next head;head.next null;return newHead;}
} 3.5 最小int的数是 Integer.MIN_VALUE 最大子数组和 明确当前sum如果小于0了则下一个数直接重置sum重新开始累加因为sum已经开始拖累了 3.6
102. 二叉树的层序遍历
思路把每一层node都放进队列里遍历到了左右子节点就放进队列依次遍历
以下为层序遍历基础代码
void bfs(TreeNode root) {QueueTreeNode queue new ArrayDeque();queue.add(root);while (!queue.isEmpty()) {TreeNode node queue.poll(); // Java 的 pop 写作 poll()if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}
}在本题中必须一层的在一个数组中所以得用一个for循环控制每一层加入同一个Array中 92. 反转链表 II 思路
我们把链表分为左、中(反转区域)、右
找到要反转的区域的前一个节点和后一个节点反转完区域内的节点以后再连接左右部分
用到一个dummy节点这样防止特殊情况left为1
注意一开始循环体内代码把left处连接到了begin但是最后我们出来是修改了的 begin.next.next now; 这句话就是在让left处的指针连接右部分而begin.next pre; 是在把左部分和right处连接上。这样左翻转的中右得到了答案 3.7 最长回文子串
思路
使用中心扩散法for循环遍历数组中每一个元素然后分别讨论一个为中心和两个为中心传入fun函数去进行处理。
fun函数就是验证回文以传入的参数作为中心向两边扩散记录长度和字符串更新结果 注意点substring的用法
substring不大写且是用字符串实例s.substring来引用的
切割范围是左闭右开 [left,right 由于此处fun中我们设置的边界 因此退出循环时是在左边界左一位所以left1但右边由于切割范围右开所以right直接不变 3.10 合并两个有序链表 递归我们什么时候使用也就是有重叠的子问题的时候
想清楚
每一层子问题是什么
每一层函数返回的是什么含义
当前一层要干什么
递归的出口
本题就很典型首先每一层返回的含义是剩下的已经接好的链表
本层要干的事情就是接当前的链表
我把后面搞定了的接上然后这一层的我自己返回给上层因为这层该我接上 23. 合并 K 个升序链表
最简单的困难题之一
思路这种一直在动态的排序问题就使用小顶堆把所有链表头的节点加入进去这样他会自动排序我们每一次都可以拿出当前其中最小的那个接在res队列后面
循环条件是heap不为空如果空了就说明添加完了
每次拿出node以后接在后面然后把node的下一个节点非null放进heap中。
注意点
1.用堆要写全称PriorityQueue小顶堆要附带ab- a-b
2.heap的添加方法是offer拿出方法是poll
PriorityQueueListNode heap new PriorityQueue((a,b)-a.val - b.val); 25. K 个一组翻转链表 注意点第三行 还有循环条件k-1因为一次是反转两个两个两个的对换位置 3.11 143. 重排链表
思路
1.找到链表中点 分为左右部分
2.反转右半边部分链表
3.两个链表交替插入 23. 合并 K 个升序链表
最简单的困难题之一
思路这种一直在动态的排序问题就使用小顶堆把所有链表头的节点加入进去这样他会自动排序我们每一次都可以拿出当前其中最小的那个接在res队列后面
循环条件是heap不为空如果空了就说明添加完了
每次拿出node以后接在后面然后把node的下一个节点非null放进heap中。
注意点
1.用堆要写全称PriorityQueue小顶堆要附带ab- a-b
2.heap的添加方法是offer拿出方法是poll
PriorityQueueListNode heap new PriorityQueue((a,b)-a.val - b.val); 3.12
33. 搜索旋转排序数组
重点是二分查找的各个边界 注意这个如果条件只是if(nums[mid] nums[start])那么当nums[mid]和nums[start]相等时代码就不会进入这个分支即使start和mid都指向升序部分的开始。这可能导致错过搜索目标值target的机会特别是当target正好等于nums[start]或nums[mid]时。 这一堆条件要分清跟mid不取等等了不就是答案了跟边界要取等
主要是重点是先分清是在有序区域还是无序区域。我们只讨论有序区域的东西 142. 环形链表 II
找循环位置先找到相遇点然后让p从head开始走slow从相遇点走走到他们相遇就是答案点
注意此处必须这样写循环体。因为用其他写法会超时
也就是必须把fast slow这个判断条件放在里面 148. 排序链表 核心思路归并排序
先找中点拆分为左右两半然后使用递归不断拆分成左右两半每次返回上一层时都把下一层的排序好再返回上去
分析一下这里的递归
子问题是将左右两边的链表排序返回排序以后的链表
递归函数的作用是进左右两层本层的作用是合并两个链表并返回 注意 寻找中点时fast要从head下一个开始因为我们要让slow指向right部分的前一个节点获得right并且断开left和right class Solution {public ListNode sortList(ListNode head) {if (head null || head.next null)return head;ListNode fast,slow;slow head;fast head.next;while(fast ! null fast.next ! null){fast fast.next.next;slow slow.next;}ListNode newhead slow.next;slow.next null;ListNode left sortList(head);ListNode right sortList(newhead);ListNode dummy new ListNode(0);ListNode p dummy;while (true) {if(left null){p.next right;break;}if(right null){p.next left;break;}if(left.val right.val){p.next left;left left.next;}else{p.next right;right right.next;}p p.next;}return dummy.next;}
} 2. 两数相加 独立做出来的mid
直接朴朴素素的相加使用tmp变量记录每两个节点的和本层now就直接取余下一层的用now取整
p1或者p2其中一个为null就不加要不就加上规避了长短不一的结果
退出 条件不仅要同时为null还要保证tmp已经结算完毕了防止最高位进一的情况 滑动窗口
按照这题为模板
这种题的特征是 子串 子数组 这种需要连续元素的
有一个窗口在扫描使用两个变量left限制左范围right用于for遍历计数
tmp,max用于记录最终数据
从0处开始滑动区间 right每加一次就判断right这个元素和窗口内的元素是否满足某种条件
如果不满足了就进入处理块, 不断把left向右推进直到他满足条件, 在外层循环记录tmp和最大的max即可.(此题判断的条件是是否有重复元素有就把left推进到重复的位置) 无重复字符最长子串 字节最经典的一道题
/
注意要用HashMap提高查找效率
containsKey先于put处理防止自己contains自己。调整i位置通过比较两个元素下标谁大来确定谁是后面的0左边界调整位置的时候调整到第一个有效位即重复位1而不是重复位因为如果这个字符串没有重复的此时应该使用j-i1计算结果 然而如果是调整到重复位 结果就变成了j-i没有统一。所以必须挪到重复位的右边(第一个有效位)i Math.max(i,map.get(s.charAt(j))1); 这一句是比较 当前边界和重复字符谁更右 取更右边的作为边界重点要用HashMap来搞。注意put是会覆盖相同的元素的由于遍历的顺序是下标由小到大因此得到的那个重复元素的下标一定是目前最大的直接和左边界比较即可 哈希表(12.9-12.16)
什么时候使用哈希法:
1.当我们需要查询一个元素是否出现过或者一个元素是否在集合里的时候就要第一时间想到哈希法。
经典题: 比较两个集合的元素重叠的地方, 或者这个数组能不能由那个数组里的元素构成
2.当我们需要在一次遍历中记录某种元素出现的次数, 或者记录某个和他相关的特征的时候
抽象来说就是, 需要建立一个数据和另一个数据之间的映射关系的时候
下面是这两种数据结构的一些常用方法
HashMap
put(key, value): 如果key已经存在那么值就更新get(key): 根据key获取valueremove(key): 删除HashMap中指定key的元素containsKey(key): 检查HashMap中是否包含给定的keycontainsValue(value): 检查HashMap中是否包含给定的valuekeySet(): 返回所有key的Setvalues(): 返回所有value的CollectionisEmpty(): 检查是否为空clear(): 清除所有元素map.put(i , getOrDefault(map.get(i),0)1)
HashSet
add(element): 添加一个元素remove(element): 删除一个元素contains(element):是否包含给定的元素isEmpty(): 检查是否为空clear(): 清除所有元素size(): 返回元素的数量iterator(): 返回一个迭代器用于遍历HashSet中的所有元素。
回溯(12.19-12.24)
为什么要用回溯?
for循环只能有单层遍历,但是回溯是可以多层遍历回溯的本质就是多层遍历, 用for循环控制这一层的广度, 用递归控制深度, 用退出条件控制结束时机一定要画图辅助理解,可以明确写递归方法的思路, 这很重要什么题用回溯?问你返回所有可能得什么什么组合,集合, 需要枚举/遍历所有情况 , 特别是组合/子集问题,要从题目抽象中出来
基本步骤
定义结果res集合(ArrayList) 临时存储tmp集合(LinkedList) 当前总和int sum
ListListInteger res new ArrayList();
ListInteger tmp new LinkedList();
int sum0;
定义dfs函数, 包含传入的数组nums, 每次遍历的开头begin, 目标target定义退出条件: 等于target时 把tmp加入res然后返回 超出target直接返回 大小超出也返回定义循环体:注意for(ibegin;ilength;i)
tmp.add(candidates[i]);
sum candidates[i];
dfs(candidates, i ,target);
sum - candidates[i];
tmp.removeLast();
三大要点总结
数组中(有无)重复元素结果中(能否)含有重复元素结果(能否)出现重复集合(顺序不同是否算同一个集合)
主要是修改i begin参数 和 dfs(nums, i ,target)中是 i 还是 i1
子集能重复, 只用修改为 i0 不可重复则是 ibegin
重点情况:
数组中无重复元素 结果中不能含有重复元素 子集不能出现重复: ibegin dfs(nums, i1 ,target)数组中有重复元素 结果中能含有重复元素 子集不能出现重复: 加条件:if(i begin nums[i] nums[i-1]) continue;ibegin dfs(nums, i1 ,target)数组中有重复元素 结果中不含有重复元素 子集不能出现重复:加条件:if(i 0 nums[i] nums[i-1]) continue;ibegin dfs(nums, i1 ,target)###
回文子串问题
12.28
class Solution {ListListString res new ArrayList();ListString tmp new LinkedList();public ListListString partition(String s) {int index 0;dfs(0,s);return res;}public void dfs(int index , String s){if(index s.length()){res.add(new ArrayList(tmp));}for(int i index;i s.length();i){if(fun(index,i,s) true) {String now s.substring(index,i1);tmp.add(now);dfs(i1,s);tmp.removeLast();}}}public boolean fun(int i,int j,String s){while(true){if(i j)return true;if(s.charAt(i) ! s.charAt(j)){return false;}i;j--;}}}
. - 力扣LeetCode
可以算困难一级的了
难点:
把分割方案化为回溯问题, 我们想枚举每一种字符串的分割方式, 再一个一个去验证可以看做是字符间空隙的组合问题(在一个空隙集合中选择不同的空隙组合) 采用回溯枚举因为for循环只能有单层遍历,但是回溯是可以多层遍历(回溯的本质就是遍历, 用for循环控制这一层的广度, 用递归控制深度, 用退出条件控制结束时机 )一定要画图辅助理解, 这很重要,一开始都没意识到判断回文直接双指针
//我们使用index来代表当前遍历的空隙, 当枚举到**最后一个字符后**的空隙时就才遍历
if(index s.length())
{res.add(new ArrayList(tmp));
}for(int i index;i s.length();i)
{//index和i表示我们当前处理的哪两个空隙之间的字符串,只有当前满足是回文我们才继续去dfs,否则直接进入下一个循环,这样保证了只有回文, 并且因为只有遍历到最后一个字符后才会结束,所以不用担心会脏结果if(fun(index,i,s) true) {String now s.substring(index,i1); //注意边界是[index,i]tmp.add(now);dfs(i1,s);//从下一个字符开始继续判断tmp.removeLast();}
}
动态规划(12.25-1.4)
如果某一问题有很多重叠子问题使用动态规划是最有效的。
就是你发现这一步的答案要根据上一步的答案得而且上一步的答案也是同样的方法得到的
所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的
状态转移公式递推公式是很重要但动规不仅仅只有递推公式。 动规五步曲一定要明确的每一步结果写出来
确定dp数组dp table以及下标的含义这很重要注释出来确定递推公式写完dp数组含义以后 立马着手递推公式 用注释先写上dp数组如何初始化一定要注意dp[0] dp[1] 这种边界值的初始化很有可能要取特值确定遍历顺序要确保后面的可以由前面的推出来特别是多维dp举例推导dp数组 为什么要先确定递推公式然后在考虑初始化呢因为一些情况是递推公式决定了dp数组要如何初始化
Debug三问
这道题目我举例推导状态转移公式了么我打印dp数组的日志了么打印出来了dp数组和我想的一样么
背包问题
01背包
1
对于背包问题有一种写法即dpi 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 确定递推公式
不放物品i和上一个相同。由dp[i - 1] [j]推出即背包容量为j里面不放物品i的最大价值此时dpi就是dp[i - 1] [j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)
放物品i等于上一个加这个的value。由dp[i - 1] [j - weight[i]]推出dp[i - 1] [j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1] [j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值
取i那就是后者不取i就是前者
dp[i][j] max{ dp[i-1][j] , dp[i-1][j-weight[i]] value[i] }
2滚动数组法
重点一定要记住 就是数据的覆盖
在此时数组是一遍一遍覆盖的。覆盖前就相当于原来的dp[i-1 ] [j ],所以此时不取物品i 的情况就可以化为dp[j ] 直接就是上一个的。同理要取物品i 就直接化为dp[j-weight ]value[j ]
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]
初始化dp就应该全是0在题目给的全是正整数的情况下可以保证后续被覆盖掉。
循环还是双重循环要有i 控制前n个物品进不进去 但是dp会减少一维度
同时我们可以窥见遍历的次序问题。因为我们要保证j 之前的数据还没有被覆盖
因为有比较dp[j - weight[i]] value[i]的部分
所以我们要倒序遍历
ps能不能交换遍历顺序不能不然就变成 dp[j]表示取前 j 个的背包所背的物品价值可以最大为dp[j] 链表 反转链表 迭代法为什么是now ! null因为迭代完now是最后一个的下一个为什么是返回pre因为pre是现在的最后一个也就是反转过来以后链表的头部
递归法记住newHead就是底层的head这个的逻辑就是先通过 注意一定是传入head.next而不是head你传自己有什么意义就成原地打转了 .next才是下一个
这一句进入最底层这句的作用就是递归的入口 一层一层往回反转 每一层的head都自己做反转返回newHead进入上一层
class Solution {public ListNode reverseList(ListNode head) {if(head null || head.next null){return head;}ListNode newHead reverseList(head.next);head.next.next head;head.next null;return newHead;}
} 反转链表2
最优解先找出pre然后直接穿针引线再拉直代码量极少模仿反转k链表
注意 第三行是pre.next
注意 每次是将两个节点一起反转所以是b-a 环形链表
重点
快指针要在head。next不然你slow永远等于fast 必须先判断fast因为后面的有可能报空指针异常 重排链表
思路
1.找到链表中点 分为左右部分
2.反转右半边部分链表
3.两个链表交替插入 合并两个有序链表 递归我们什么时候使用也就是有重叠的子问题的时候
想清楚
每一层子问题是什么
每一层函数返回的是什么含义
当前一层要干什么
递归的出口
本题就很典型首先每一层返回的含义是剩下的已经接好的链表
本层要干的事情就是接当前的链表
我把后面搞定了的接上然后这一层的我自己返回给上层因为这层该我接上 K 个一组翻转链表
先算出长度再使用两个循环去处理
注意点第三行因为我们采用的是把开头节点右侧的节点一个接一个挪到pre.next头插法
因此是把nex接到pre.next 还有循环条件k-1因为一次是反转两个两个两个的对换位置必须K-1 合并 K 个升序链表
最简单的困难题之一
思路这种一直在动态的排序问题就使用小顶堆把所有链表头的节点加入进去这样他会自动排序我们每一次都可以拿出当前其中最小的那个接在res队列后面
循环条件是heap不为空如果空了就说明添加完了
每次拿出node以后接在后面然后把node的下一个节点非null放进heap中。
注意点
1.用堆要写全称PriorityQueue大顶堆要附带ab- a-b
2.heap的添加方法是offer拿出方法是poll
PriorityQueueListNode heap new PriorityQueue((a,b)-a.val - b.val); 328. 奇偶链表
把一个链表的奇数和偶数节点分别合在一起再相连
直接创建两个节点作为奇偶链表的开头容纳完再接上即可 二叉树 代码
236. 二叉树的最近公共祖先 103. 二叉树的锯齿形层序遍历
记住有三个数据结构
一个当容纳节点的队列一个是res一个是tmp不要把tmp和Deque搞错了
这个题直接在层序遍历基础上
在添加tmp的时候正向添加反向添加就好了一组一组的呀他是
你在那儿管deque的添加顺序不是纯纯给自己找麻烦吗 110. 平衡二叉树
