网站运营是做什么的怎么样,微信视频制作小程序,asp网站经常 响应,南昌自主建站模板点击上方蓝字设为星标每周一、三、五上午 8:30 准时推送下面开始今天的学习#xff5e;前言查找#xff0c;是使用计算机处理问题时的一个最基本的任务#xff0c;因此也是算法面试中非常常见的一类问题。很多算法问题的本质#xff0c;就是要能够高效使用查找。LeetCode 中… 点击上方蓝字设为星标每周一、三、五上午 8:30 准时推送下面开始今天的学习前言查找是使用计算机处理问题时的一个最基本的任务因此也是算法面试中非常常见的一类问题。很多算法问题的本质就是要能够高效使用查找。LeetCode 中有很多问题都会用到集合和字典(C 中为 set 和 map , Python 中为 set 和 dict) 这两种数据结构今天我们将会对 LeetCode 这类问题进行总结所有代码采用 Python 实现并可以在 力扣(LeetCode)里 AC。灵活选择键值454. 四数相加 II题目描述给定四个包含整数的数组列表 ABCD计算有多少个元组(ijkl)使得 A[i] B[j] C[k] D[l] 0。为了使问题简单化所有的 ABCD 具有相同的长度 N且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间最终结果不会超过 231 - 1 。例如:解题思路暴力解法时间复杂度 O(n^4)将 D 中的元素放入查找表时间复杂度 O(n^3)将 A B 的每一种可能放入查找表然后 两重循环对在查找表中寻找是否存在 -(C[i] D[i])时间复杂度为 O(n^2)。两数相加的和作为键值我采用第三种方法实现代码实现49. 字母异位词分组题目描述给定一个字符串数组将字母异位词组合在一起。字母异位词指字母相同但排列不同的字符串。示例:说明所有输入均为小写字母。不考虑答案输出的顺序。解题思路对字符串数组中每一个字符串进行排序之后如果遇到相等的字符串就说明该字符串对应的排序前的字符串是字母易位词。找字母易位词的过程用哈希表每当出现一个新的字母易位词就往 ret 中添加一个 list同时往哈希表中添加该字母易位词并将该字母易位词在哈希表中的 value 值存成该 list 的索引值出现哈希表中已经存在的字母易位词直接往对应索引的 list 中添加即可。排序后的字符串作为键值代码实现447. 回旋镖的数量题目描述给定平面上 n 对不同的点“回旋镖” 是由点表示的元组 (i, j, k)其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。找到所有回旋镖的数量。你可以假设 n 最大为 500所有点的坐标在闭区间 [-10000, 10000] 中。示例:解题思路暴力解法三重循环枚举所有的可能性。 时间复杂度为O(n^3)使用查找表观察到 i 是一个 “枢纽”对于每个点i遍历其余点到i的距离 对于每个枢纽 i计算它到其它点j的距离并将距离作为键存入字典 dict 中value 为距离的个数。时间复杂度为O(n^2)。 距离作为键值代码实现149. 直线上最多的点数题目描述给定一个二维平面平面上有 n 个点求最多有多少个点在同一条直线上。解题思路两点可以确定一条直线那么选择固定一个点求其他点与固定点的斜率如果斜率相同那么斜率相同的点在同一条直线上。同时要考虑斜率可能为无穷大也有可能两个点为同一个点。键值应该为斜率。代码实现查找表和滑动窗口219. 存在重复元素 II题目描述给定一个整数数组和一个整数 k判断数组中是否存在两个不同的索引 i 和 j使得 nums [i] nums [j]并且 i 和 j 的差的绝对值最大为 k。解题思路结合使用滑动窗口和查找表不断查找当前滑动窗口内有没有重复值。我们通过建立一个 record 查找表表中存的是窗口中的数另外我们要注意的是当窗口的大小k的时候我们要移除 record 中最左边的元素(保证我们窗口中有 k 个数)代码实现220. 存在重复元素 III题目描述给定一个整数数组判断数组中是否有两个不同的索引 i 和 j使得 nums[i] 和 nums[j] 的差的绝对值最大为 t并且 i 和 j 之间的差的绝对值最大为 ķ。解题思路也是查找表与滑动窗口的思路维持滑动窗的大小最大为 k遍历每一个元素 nums[i]在活动窗口中寻找 |one-nums[i]| t即窗口中的元素范围为[one-t…onet] 之间代码实现总结我们知道在准备面试的时候刷算法题是一种捷径特别是刷力扣但是不能一味的刷题我们需要总结和思考对于一些相似的题目我们应该多想想他们的思想其实很多题的解题思路都是相近的。本文作者军旗编辑版式霍霍声明本文归 “力扣” 版权所有如需转载请联系。
