外贸网站建设有用吗,c 网站开发怎么弹出输入框,gov域名网站有哪些,关于征求网站建设AI/CV互联网大厂笔试LeetCode高频考题之基础核心知识点算法复习1、二叉树的遍历2、回溯算法3、二分搜索4、滑动窗口算法题5、经典动态规划6、动态规划答疑篇6.1、总结一下如何找到动态规划的状态转移关系7、编辑距离8、戳气球问题9、最长公共子序列 Longest Common Subsequence…
AI/CV互联网大厂笔试LeetCode高频考题之基础核心知识点算法复习1、二叉树的遍历2、回溯算法3、二分搜索4、滑动窗口算法题5、经典动态规划6、动态规划答疑篇6.1、总结一下如何找到动态规划的状态转移关系7、编辑距离8、戳气球问题9、最长公共子序列 Longest Common Subsequence10、子序列的相关问题。最长回文编辑距离。11、动态规划博弈问题12、贪心算法13、二叉堆实现优先级队列14、LRU缓存淘汰策略15、完全二叉树 满二叉树本人参加了一些互联网大公司N个公司的笔试机试以及后续的面试过程。主要总结一下在笔试和面试中的高频考点。主要是要掌握以下几类算法的核心思想。在笔试和面试的过程中遇到这些问题想清楚思路然后套用下面的解法将会非常有用。我没有刷500道LeetCode题所以整体的刷题量和对事情的复杂程度还没有到位。但是下面的浅见供大家参考一下。互相学习。祝福找工作的同学们一切顺利。
算法复习
1、二叉树的遍历
前序遍历根左右
中序遍历左根右
后序遍历左右根
前序遍历中序遍历能够重构出后序遍历
后序遍历中序遍历能够重构出前序遍历
前序遍历后序遍历无法重构出中序遍历。
void traverse(TreeNode root){//前序遍历traverse(root.left);//中序遍历traverse(root.right);//后序遍历
}2、回溯算法
def backtrack(...):for 选择 in 选择列表做选择backtrack()撤销选择路径选择列表结束条件
动态规划状态选择base case 重叠子问题可以用dp table或者备忘录 优化。
queue 先进先出。 stack 先进后出.
3、二分搜索
因为我们初始化 right nums.length - 1
所以决定了我们的「搜索区」是 [left, right]
所以决定了 while (left right)
同时也决定了 left mid1 和 right mid-1
因为我们只找到⼀个target 的索引即可
所以当 nums[mid] target 时可以⽴即回 寻找左侧边界的二分查找 在nums[mid] target时 rightmid-1. 寻找右侧边界的二分查找 在nums[mid] target时 leftmid1.
返回逻辑记得防止越界边界检查。
4、滑动窗口算法题
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {unordered_mapchar, int need, window;for (char c : t) need[c];int left 0, right 0;int valid 0; while (right s.size()) {// c 是将移入窗口的字符char c s[right];// 右移窗口right;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf(window: [%d, %d)\n, left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d s[left];// 左移窗口left;// 进行窗口内数据的一系列更新...}}
}5、经典动态规划
这个问题有什么「状态」有什么「选择」然后穷举。
对于高楼扔鸡蛋问题状态鸡蛋的个数。楼层的层数随着测试的进行K减少楼层N减少。
选择去哪层楼扔鸡蛋线性扫描二分法等等。策略问题。
穷举加DP table。就可以解决动态规划的特性。 稍微处理一下 base case。 def dp(K, N):for 1 i N:# 最坏情况下的最少扔鸡蛋次数res min(res, max( dp(K - 1, i - 1), # 碎了就去低一层楼找dp(K, N - i) # 没碎就去高一层楼找。) 1 # 在第 i 楼扔了一次)return res对于动态规划的标准步骤 for 状态1 in 状态1的所有取值 for 状态2 in 状态2的所有取值 for … dp[状态1] [状态2] […] 择优(选择1选择2…) stack堆栈先进后出。stack.top( )获取栈顶元素; stack.pop( )删除栈顶元素; stack.push(5)推入元素到栈顶。
6、动态规划答疑篇 找最优子结构的过程 其实就是证明状态转移方程正确性的过程方程符合最优子结构就可以写暴力解了写出暴力解就可以看出有没有重叠子问题了有则优化无则 OK。 最优子结构性质作为动态规划问题的必要条件一定是让你求最值的。 从最简单的 base case 往后推导。 dp数组的遍历方向 1、遍历的过程中所需的状态必须是已经计算出来的。 2、遍历的终点必须是存储结果的那个位置。
6.1、总结一下如何找到动态规划的状态转移关系
1、明确 dp 数组所存数据的含义。这一步对于任何动态规划问题都很重要如果不得当或者不够清晰会阻碍之后的步骤。
2、根据 dp 数组的定义运用数学归纳法的思想假设 dp[0...i-1] 都已知想办法求出 dp[i]一旦这一步完成整个题目基本就解决了。
但如果无法完成这一步很可能就是 dp 数组的定义不够恰当需要重新定义 dp 数组的含义或者可能是 dp 数组存储的信息还不够不足以推出下一步的答案需要把 dp 数组扩大成二维数组甚至三维数组。
7、编辑距离
编辑距离的dp状态转移矩阵比较巧妙。如何设计这个函数。左上左边上边。三个方向选最小的。跳转到[i1] [j1]. if s1[i] s2[j]: 啥都别做skip i, j 同时向前移动 else: 三选一 插入insert 删除delete 替换replace 状态转移所依赖的状态必须被提前计算出来。 8、戳气球问题
这个问题中我们每戳破一个气球nums[i]得到的分数和该气球相邻的气球nums[i-1]和nums[i1]是有相关性的。
这里面比较巧妙的是如何转移矩阵。将气球划分成不被破坏的相互独立的3个子块。
dp[i] [k] dp[k] [j] points[i] * points[k] * points[j]
你不是要最后戳破气球k吗那得先把开区间(i, k)的气球都戳破再把开区间(k, j)的气球都戳破最后剩下的气球k相邻的就是气球i和气球j这时候戳破k的话得到的分数就是points[i]*points[k]*points[j]。
9、最长公共子序列 Longest Common Subsequence
大部分比较困难的字符串问题比如编辑距离都是用二维动态规划来做。涉及到子序列问题用动态规划来做。
子序列问题的核心。 dp 的转移。
从dp(i, j)转移到dp(i1, j1)。 字符串相同的时候应该如何跳转不同的时候应该如何跳转。
关于状态转移当s1[i]和s2[j]相同时不需要删除不同时需要删除所以可以利用dp函数计算两种情况得出最优的结果。
dp[i-1] [j-1]dp[i-1] [j]dp[i] [j-1]dp[i] [j]
10、子序列的相关问题。最长回文编辑距离。
涉及到子序列和最值那几乎可以肯定考察的是动态规划技巧时间复杂度一般都是 O(n^2)。
然后根据实际问题看看哪种思路容易找到状态转移关系。
另外找到状态转移和 base case 之后一定要观察 DP table看看怎么遍历才能保证通过已计算出来的结果解决新的问题
子序列问题一共两种动态规划思路。二维的 dp 数组 涉及两个字符串/数组时比如最长公共子序列dp 数组的含义如下 在子数组arr1[0..i]和子数组arr2[0..j]中我们要求的子序列最长公共子序列长度为dp[i][j]。第一种情况可以参考这两篇旧文详解编辑距离和最长公共子序列 只涉及一个字符串/数组时比如本文要讲的最长回文子序列dp 数组的含义如下 在子数组array[i..j]中我们要求的子序列最长回文子序列的长度为dp[i][j]。 if (s[i] s[j]) // 它俩一定在最长回文子序列中 dp[i][j] dp [ i 1 ] [j - 1] 2; else // s[i1…j] 和 s[i…j-1] 谁的回文子序列更长 dp[i][j] max(dp [i 1] [j], dp[i] [j - 1]); 另外看看刚才写的状态转移方程想求dp[i][j]需要知道dp[i1][j-1]dp[i1][j]dp[i][j-1]这三个位置再看看我们确定的 base case填入 dp 数组之后是这样。为了保证每次计算dp[i][j]左、下、左下三个方向的位置已经被计算出来只能斜着遍历或者反着遍历。 11、动态规划博弈问题
博弈问题的前提一般都是在两个聪明人之间进行编程描述这种游戏的一般方法是二维 dp 数组数组中通过元组分别表示两人的最优决策。
之所以这样设计是因为先手在做出选择之后就成了后手后手在对方做完选择后就变成了先手。这种角色转换使得我们可以重用之前的结果典型的动态规划标志。
12、贪心算法
对于区间问题的处理一般来说第一步都是排序相当于预处理降低后续操作难度。
13、二叉堆实现优先级队列
Priority queue.
优先级队列插入或者删除元素的时候元素会自动排序这底层的原理就是二叉堆的操作。
数据结构的功能无非增删查改优先级队列有两个主要 API分别是insert插入一个元素和delMax删除最大元素如果底层用最小堆那么就是delMin。
insert方法先把要插入的元素添加到堆底的最后然后让其上浮到正确位置。
delMax方法先把堆顶元素 A 和堆底最后的元素 B 对调然后删除 A最后让 B 下沉到正确位置。
优先级队列是基于⼆叉堆实现的主要操作是插⼊和删除。插⼊是先插到最后然后上浮到正确位置。删除操作是删除最大元素先是交换位置到队尾后再删除然后将队列顶部的元素下沉到正确位置。核⼼代码也就⼗⾏。
删除是把第一个元素 pq[1]最值调换到最后再删除然后把新的 pq[1] 下沉到正确位置。
14、LRU缓存淘汰策略
LRU 缓存淘汰算法就是⼀种常⽤策略。LRU 的全称是 Least Recently Used也就是 我们认为最近使⽤的数据应是「有⽤的」 很久都没⽤过的数据应该是⽆⽤的内存满了就优先删除很久没⽤的数据。
LRU 按访问时序淘汰缓存。还有LFU按照访问频率淘汰。优先淘汰较少使用的应用/缓存。
LRU capacity作为容量putkeyval存入键值队getkey返回val。没有则-1。
注意
LRU缓存算法的核心是哈希链表采用双向链表和哈希表结合。借助哈希表赋予了链表快速查找的特性。可以快速查找某个 key 是否存在缓存链表中同时可以快速删除、添加节点。
为什么必须要⽤双向链表因为我们需要删除操作。删除⼀个节点不光要得到该节点本⾝的指针也需要操作其前驱节点的指针⽽双向链表才能⽀持直接查找前驱保证操作的时间复杂度O(1) 。
“为什么要在链表中同时存储 key 和 val⽽不是只存储 val”注意这段代码
if (cap cache.size()) {
// 删除链表最后⼀个数据
Node last cache.removeLast();
map.remove(last.key);
}当缓存容量已满我们不仅仅要删除最后⼀个 Node 节点还要把 map 中映射到该节点的 key 同时删除⽽这个 key 只能由 Node 得到。如果 Node 结构中只存储 val那么我们就⽆法得知 key 是什么就⽆法删除 map 中的键造成错误。
处理链表节点的同时不要忘了更新哈希表中对节点的映射。
链表操作只需要处理指针。比较方便。
在二叉树框架上扩展出一套BST遍历框架。
void BST(TreeNode root, int target)
{if (root.val target)// 找到⽬标 做点什么if (root.val target)BST(root.right, target);if (root.val target)BST(root.left, target);
}15、完全二叉树 满二叉树
完全二叉树如下图每一层都是紧凑靠左排列的
满二叉树如下图是一种特殊的完全二叉树每层都是是满的像一个稳定的三角形。 \quad 完全二叉树 \quad \quad\quad\quad\quad\quad 满二叉树
一棵完全二叉树的两棵子树至少有一棵是满二叉
算法的递归深度就是树的高度 O(logN)每次递归所花费的时间就是 while 循环需要 O(logN)所以总体的时间复杂度是 O(logN*logN)。
