郑州pc网站建设,nike网站开发背景及意义,php网站开发周期多长,专门做app的网站一、算法概念题
1. 二分法
总结链接几种查找情况的模板另一个好记的总结总结#xff1a;搜索元素两端闭#xff0c;while带等#xff0c;mid1#xff0c;结束返-1 搜索边界常常左闭右开#xff0c;while小于#xff0c;mid看边界开闭#xff0c;闭开#xff0c;结束i…一、算法概念题
1. 二分法
总结链接几种查找情况的模板另一个好记的总结总结搜索元素两端闭while带等mid±1结束返-1 搜索边界常常左闭右开while小于mid看边界开闭闭±开结束if检查左然后返回例1标准 循环条件left highleft mid 1, right mid - 1return mid / -1 例2找左边界有序有重复 循环条件left highleft mid 1, right mid右边界向左收缩return nums[left] target ? left : -1 例3找右边界有序有重复 循环条件left highmid xxx 1left mid, right mid - 1return nums[right] target ? right : -1 总结基本上是循环条件判断条件边界更新方法的不同组合
2. DFS
Leetcode-695. 岛屿的最大面积代码模板 def dfs(row, col):if row 0 or col 0 or row m or col n or not grid[row][col]:return 0grid[row][col] 0return dfs(row-1, col) \dfs(row1, col) \dfs(row, col-1) \dfs(row, col1) 1if not grid:return 0m len(grid)n len(grid[0])ans 0for i in range(m):for j in range(n):if grid[i][j]:ans max(ans, dfs(i,j))return ans3. BFS
Leetcode-1162. As Far from Land as Possible代码模板
def maxDistance(grid: List[List[int]]) - int:# 从1开始出发bfs记录距离m len(grid)n len(grid[0])start []# 存入所有起点1的位置for i in range(m):for j in range(n):if grid[i][j]:start.append([i,j,0])# 特例if not start or len(start) m*n:return -1# 四个方向x [1,0,-1,0]y [0,1,0,-1]while start:i, j, dis start.pop(0)for k in range(4):row i x[k]col j y[k]if row 0 or col 0 or row m or col n or grid[row][col]:continuestart.append([row,col,dis1])grid[row][col] 1 #访问过的位置记录为1return dis #最后一个dis4. 动态规划
典型题总结
5. 滑动窗口
双指针、快针慢针典型题链表、数组、子串
6. 快排
def quick_sort(array, l, r):if l r:q partition(array, l, r)quick_sort(array, l, q - 1)quick_sort(array, q 1, r)def partition(array, l, r):x array[r]i l - 1for j in range(l, r):if array[j] x:i 1array[i], array[j] array[j], array[i]array[i 1], array[r] array[r], array[i 1]return i 1各种树
Trie树红黑树
二、算法题
1. topK的3种解法
冒泡最小堆快排分布式
2. 3Sum
3. 反转链表
4.1 判断有向图是否存在环
DFS从一点出发若回到该点则说明存在环从入度为0的点出发邻接表储存的时间复杂度为O(VE)拓扑排序例题把所有入度为0的点和其输出的边依次删除如果最后不剩点了则说明没有环代码 拓扑序表示有向无环图
4.2 判断无向图是否存在环
Union-Find并查集 初始化所有元素的根为-1遍历每一条边修改根节点合并集合时让两者拥有相同的根其中一个的根一定是-1如果出现相同的根则说明有环 BFS 黑白灰初始化为白入队为灰出队为黑如果子结点的颜色有不是白色的说明有环在此之前已经访问过一次了
5. 最近一个小时内访问频率最高的10个IP
每秒对应一个HashMapIP地址为key出现次数作为value同时建立一个固定大小为10的小根堆用于存放当前出现次数最大的10个IP每次来一个请求就把该秒对应的HashMap里对应的IP计数器增1并查询该IP是否已经在堆中存在 如果不存在则把该IP在3600个HashMap的计数器加起来与堆顶IP的出现次数进行比较如果已经存在则把堆中该IP的计数器也增1并调整堆 每过一秒把最旧的那个HashMap销毁并为当前这一秒新建一个HashMap这样维持一个一小时的窗口每次查询top 10的IP地址时把堆里10个IP地址返回来即可
三、编程语言概念题
1. python中is和的区别
is是用来判断两个变量引用的对象是否为同一个用于判断引用对象的值是否相等可以通过id()函数查看引用对象的地址
python生成器
四、大数据Spark/MapReduce
1. Spark性能如何调优
避免创建重复的RDD尽量复用同一RDD尽量避免使用shuffle类算子优化数据结构使用Hive ETL预处理数据过滤少数导致倾斜的key提高shuffle操作的并行度两阶段聚合将reduce join转为map join
