AI/CV大厂笔试LeetCode高频考题之基础核心知识点

news/2024/3/29 12:53:46/文章来源:https://blog.csdn.net/qq_32998593/article/details/129256381

AI/CV互联网大厂笔试LeetCode高频考题之基础核心知识点

    • 算法复习
      • 1、二叉树的遍历
      • 2、回溯算法
      • 3、二分搜索
      • 4、滑动窗口算法题
      • 5、经典动态规划
      • 6、动态规划答疑篇
        • 6.1、总结一下如何找到动态规划的状态转移关系
      • 7、编辑距离
      • 8、戳气球问题
      • 9、最长公共子序列 Longest Common Subsequence
      • 10、子序列的相关问题。最长,回文,编辑距离。
      • 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 = mid+1 和 right = mid-1

因为我们只找到⼀个target 的索引即可

所以当 nums[mid] == target 时可以⽴即回

  • 寻找左侧边界的二分查找

    在nums[mid] == target时,

    right=mid-1.

  • 寻找右侧边界的二分查找

    在nums[mid] == target时,

    left=mid+1.

返回逻辑记得防止越界,边界检查。

4、滑动窗口算法题

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {unordered_map<char, 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、动态规划答疑篇

  1. 找最优子结构的过程:

    其实就是证明状态转移方程正确性的过程,方程符合最优子结构就可以写暴力解了,写出暴力解就可以看出有没有重叠子问题了,有则优化,无则 OK。

    最优子结构性质作为动态规划问题的必要条件,一定是让你求最值的。 从最简单的 base case 往后推导。

  2. dp数组的遍历方向:

    1、遍历的过程中,所需的状态必须是已经计算出来的

    2、遍历的终点必须是存储结果的那个位置

6.1、总结一下如何找到动态规划的状态转移关系

1、明确 dp 数组所存数据的含义。这一步对于任何动态规划问题都很重要,如果不得当或者不够清晰,会阻碍之后的步骤。

2、根据 dp 数组的定义,运用数学归纳法的思想,假设 dp[0...i-1] 都已知,想办法求出 dp[i],一旦这一步完成,整个题目基本就解决了。

但如果无法完成这一步,很可能就是 dp 数组的定义不够恰当,需要重新定义 dp 数组的含义;或者可能是 dp 数组存储的信息还不够,不足以推出下一步的答案,需要把 dp 数组扩大成二维数组甚至三维数组。

7、编辑距离

编辑距离的dp状态转移矩阵,比较巧妙。如何设计这个函数。左上,左边,上边。三个方向选最小的。跳转到[i+1] [j+1].

if s1[i] == s2[j]:
啥都别做(skip)
i, j 同时向前移动
else:
三选一:
插入(insert)
删除(delete)
替换(replace)

状态转移所依赖的状态必须被提前计算出来

图片

8、戳气球问题

这个问题中我们每戳破一个气球nums[i],得到的分数和该气球相邻的气球nums[i-1]nums[i+1]是有相关性的

这里面比较巧妙的是,如何转移矩阵。将气球🎈划分成不被破坏的,相互独立的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(i+1, j+1)。 字符串相同的时候,应该如何跳转,不同的时候,应该如何跳转。

关于状态转移,当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 数

  1. 涉及两个字符串/数组时(比如最长公共子序列),dp 数组的含义如下:

    在子数组arr1[0..i]和子数组arr2[0..j]中,我们要求的子序列(最长公共子序列)长度为dp[i][j]。第一种情况可以参考这两篇旧文:详解编辑距离和最长公共子序列

  2. 只涉及一个字符串/数组时(比如本文要讲的最长回文子序列),dp 数组的含义如下:

    在子数组array[i..j]中,我们要求的子序列(最长回文子序列)的长度为dp[i][j]

if (s[i] == s[j])
// 它俩一定在最长回文子序列中
dp[i][j] = dp [ i + 1 ] [j - 1] + 2;
else
// s[i+1…j] 和 s[i…j-1] 谁的回文子序列更长?
dp[i][j] = max(dp [i + 1] [j], dp[i] [j - 1]);

图片

另外,看看刚才写的状态转移方程,想求dp[i][j]需要知道dp[i+1][j-1]dp[i+1][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作为容量,put(key,val)存入键值队,get(key)返回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)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_75617.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

系统性能测试指标

性能测试的目的 1.评估系统的能力&#xff0c;测试中得到的负荷和响应时间数据可以被用于验证所计划的模型的能力&#xff0c;并帮助作出决策。 2.识别体系中的弱点&#xff1a;受控的负荷可以被增加到一个极端的水平&#xff0c;并突破它&#xff0c;从而修复体系的瓶颈或薄…

兴达易控Modbus转Profinet网关将丹佛斯变频器接入西门子1200PLC配置案例

案例简介&#xff1a; 本案例是兴达易控Modbus转Profinet网关连接丹佛斯变频器在西门子1200PLC程序控制实例&#xff0c;实现对变频器频率读写&#xff0c;及工作模式切换。 用到的设备为西门子1200PLC一台&#xff0c;丹佛斯变频器一台,兴达易控Modbus转Profinet网关一个 Modb…

OSPF -- (开放式最短路径优先协议)(公共协议)

OSPF -- &#xff08;开放式最短路径优先协议&#xff09;&#xff08;公共协议&#xff09; 1、属性&#xff1a;无类别链路状态IGP协议 无类别&#xff1a;更新携带精确掩码 链路状态&#xff1a;共享拓扑&#xff08;共享LSA&#xff09;本地计算路由IGP&#xff1a; 基于…

读取/etc/profile时发现错误:

读取/etc/profile时发现错误&#xff1a; /etc/profile:行XX&#xff1a;***************** /etc/profile:行XX&#xff1a;***************** 今天遇到这个错误&#xff0c;发现是首行被我编辑时删错了一个符号导致报错&#xff0c;导致每次开机都会报这个文件错误&#xff0…

SpringBoot解决跨域方式

跨域是指在 Web 应用中&#xff0c;一个服务器资源或应用访问另一个服务器资源或应用的资源时候。由于浏览器的同源策略&#xff0c;一般情况下同一个域中的网站或应用可以互相访问资源&#xff0c;但跨域访问会被浏览器拒绝。浏览器出于安全考虑&#xff0c;会限制跨域访问&am…

Jmeter性能测试 入门

Jmeter是一款优秀的开源测试工具&#xff0c; 是每个资深测试工程师&#xff0c;必须掌握的测试工具&#xff0c;熟练使用Jmeter能大大提高工作效率。 熟练使用Jmeter后&#xff0c; 能用Jmeter搞定的事情&#xff0c;你就不会使用LoadRunner了。 我将会覆盖Jmeter的各个功能…

亿发软件:钉钉移动ERP业务在线,审批、管理更方便!

钉钉系统是企业级智能移动办公平台&#xff0c;平台覆盖大中小微各量级企业&#xff0c;帮助中国企业移动办公管理。企业无需复杂的部署操作&#xff0c;在对应的功能制定流程和相关负责人即可。 亿发企业ERP管理系统于2022年与钉钉系统做了对接&#xff0c;提供一站式的企业管…

大数据系统重点

第一章 大数据计算系统概述 1 大数据计算框架概述 计算框架: 一种抽象&#xff0c;在其中提供相应的通用功能供用户编写代码以实现具体功能&#xff0c;从而形成面向应用的软件。 大数据计算框架&#xff1a;面向大数据的计算框架。 Hadoop Hadoop的运行过程 Hadoop的详细…

腾讯云轻量应用服务器和云服务器CVM有什么区别?

腾讯云新推出的轻量应用服务器Lighthouse和原来的CVM云服务器有什么区别&#xff1f;轻量应用服务器Lighthouse是一种易于使用和管理、适合承载轻量级业务负载的云服务器&#xff0c;主要用于Web网站应用&#xff0c;轻量服务器使用及后期运维更加简单方便&#xff1b;云服务器…

【数据结构(四)】树

文章目录树1 树的基本概念1.1 树的定义1.2 基本术语1.3 数的性质2 二叉树的概念2.1 二叉树的定义与特性2.1.1 定义2.1.2 二叉树的性质2.2 几种特殊的二叉树2.2.1 满二叉树2.2.2 完全二叉树2.3 二叉树的存储结构2.3.1 顺序存储2.3.2 链式存储3 二叉树的遍历和线索二叉树3.1 二叉…

敏捷-期末

什么是敏捷开发&#xff1f; 敏捷开发(Agile Development)是一种以人为核心、迭代、循序渐进的开发方法。 怎么理解呢&#xff1f;它不是一门技术&#xff0c;它是一种开发方法&#xff0c;也就是一种软件开发的流程&#xff0c;它会指导我们用规定的环节去一步一步完成项目的开…

二叉树路径查找

题目描述&#xff1a;给定一棵二叉树(结构如下)&#xff0c;其中每个节点值为整数。给定一个值 K&#xff0c;求所有满足如下条件的路径并将路径上节点的值打印出来&#xff1a; 1、路径方向必须向下&#xff0c;即只能从父节点指向子节点 2、路径并不是必须从根节点开始或在叶…

一起玩转开源数据库!OceanBase DevCon 之开源生态全景解析

​ 2023 年 3 月 25 日&#xff0c;首次 OceanBase 开发者大会将在北京举办&#xff0c;OceanBase 首席科学家阳振坤与 OceanBase CTO 杨传辉领携众多技术专家&#xff0c;将与开发者共同探讨单机分布式、云原生、HTAP 等数据库前沿趋势&#xff0c;OceanBase 开源技术全景生…

【安卓】安卓设备实现wifi display解决方案

看文章前&#xff0c;我们需要知道的几个概念&#xff1a; 1、Wifi Direct技术&#xff1b; 2、Wifi Display技术&#xff1b; 3、Miracast标准&#xff1b; 安卓手机用户都知道我们的安卓手机有一个wifi直连功能&#xff0c;在点击设置–》WIFI–》更多Wifi设置–》Wifi直连&a…

【Linux】操作系统与Linux — Linux概述、组成及目录结构

目录 一、什么是操作系统&#xff1f;都有那些&#xff1f; 二、Linux概述 三、Linux组成 三、Linux目录结构 四、Linux目录结构 &#x1f49f; 创作不易&#xff0c;不妨点赞&#x1f49a;评论❤️收藏&#x1f499;一下 一、什么是操作系统&#xff1f;都有那些&#x…

Linux | 1. 挂载新硬盘与磁盘管理

如有错误&#xff0c;恳请指出。 1. Ubuntu挂载新硬盘 查看磁盘状态&#xff1a;sudo fdisk -l 1&#xff09;为新硬盘分区 使用 fdisk 指令对 /dev/sdb 进行分区操作&#xff1a;sudo fdisk /dev/sdb。进入分区工具后&#xff0c;我们可以输入 m 看指令说明&#xff0c;注意…

SQL数据库权限管理-10个数据库角色

为便于管理数据库中的权限&#xff0c;SQL 数据库提供了服务器角色、数据库角色、用户等来划分不同用户拥有的权限差异。今天给大家介绍数据库角色对应的权限。 数据库级角色 存在两种类型的数据库级角色&#xff1a; 数据库中预定义的“固定数据库角色”可以创建的“用户定…

New Bing怼人、说谎、PUA,ChatGPT已经开始胡言乱语了

最近&#xff0c;来自大洋彼岸那头的ChatGPT科技浪潮席卷而来&#xff0c;微软将chatGPT整合搜索引擎Bing开启内测后&#xff0c;数百万用户蜂拥而至&#xff0c;都想试试这个「百事通」。 赶鸭子上架&#xff0c;“翻车”了&#xff1f; 但短短上线十几天&#xff0c;嵌入了…

架构篇之如何画出优秀的架构图(二)

今天是架构篇的第二篇文章,跟大家聊聊如何画出好的架构图。 一、架构图分类 1、业务架构 a. 定义:描述系统对用户提供了什么业务功能。 b. 使用场景: 产品规划业务给高P汇报

高通平台开发系列讲解(Sensor篇)AlsPs的工作原理及介绍

文章目录 一、什么是ALS?二、什么是距感(PS)?三、AlsPs的工作原理四、AlsPs的特性五、距感的校准参数说明六、光感的校准参数说明沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇文章将介绍 AlsPs 的工作原理及介绍。 一、什么是ALS? 光感的英文叫做Ambient Li…