没有合适的资源?快使用搜索试试~ 我知道了~
喜缺全书算法册 C++实现
需积分: 0 21 下载量 61 浏览量
2023-09-17
12:20:40
上传
评论 1
收藏 762KB DOC 举报
温馨提示
试读
114页
当前阶段:以二分查找为主,前缀和为辅,之后会有其它算法的。文字算法见我的博文,视频算法见我的学院课程。 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,两者长度都为 n 。每次操作中,你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的和。你的目标是对于所有的 0 <= i <= n - 1 ,都满足 nums1[i] != nums2[i] ,你可以进行 任意次 操作,请你返回达到这个目标的 最小 总代价。请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ,如果无法达成目标,返回 -1 。 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ,高度为 heights[i] 。 如果以下条件满足,我们称这些塔是 美丽 的:
资源推荐
资源详情
资源评论
答疑 C/C++/ VC QQ 群:2508429
喜缺全书算法册
--缺陷让我们成长
何志丹 魏家瑜
喜缺(闻缺陷则喜)的意思是:高效暴露问题才能更有效的解决问题。
更多阅读与沟通:
最新版下载:
C++课程的免费讲义:https://edu.csdn.net/course/detail/38771
CSDN 下载频道:https://download.csdn.net/download/he_zhidan/88348653
最新版及非精华题解:
CSDN 博客:https://blog.csdn.net/he_zhidan/
源码下载:我的 CSDN 下载频道。
答疑:Q群 2508429
目录
闻缺陷则喜之算法册..............................................................................................1
视频算法 ..................................................................................................................3
1. 二分查找 .............................................................................................................................4
1.1. 基础 ....................................................................................................................................4
1.2. 习题 ....................................................................................................................................8
最短路径 ................................................................................................................11
1. 深度优先搜索(BFS)最短路径的原理和 C++实现 ...............................................................11
1.1. 时间复杂度 ......................................................................................................................11
1.2. 使用前提 ..........................................................................................................................11
1.3. 典型场景 ..........................................................................................................................11
1.4. 可理解性强的解法 ..........................................................................................................12
1.5. 核心代码 ..........................................................................................................................12
1.6. 测试样例 ..........................................................................................................................13
1.7. 滚动队列优化 ..................................................................................................................14
1.8. 一个队列就够了 ..............................................................................................................15
2. 01BFS 最短距离的原理和 C++实现 ...................................................................................15
2.1. 时间复杂度 ......................................................................................................................15
2.2. 使用前提 ..........................................................................................................................16
2.3. 典型场景 ..........................................................................................................................16
2.4. 解题思路 ..........................................................................................................................16
答疑 C/C++/ VC QQ 群:2508429
2.5. 核心代码 ..........................................................................................................................16
2.6. 测试样例 ..........................................................................................................................17
2.7. 类似场景 ..........................................................................................................................18
2.8. 用双向队列优化 ..............................................................................................................18
3. 朴素迪氏最短单源路径 ....................................................................................................18
3.1. 时间复杂度 ......................................................................................................................18
3.2. 使用前提 ..........................................................................................................................19
4. 堆优化迪氏最短单源路径.................................................................................................19
4.1. 时间复杂度 ......................................................................................................................19
4.2. 使用前提 ..........................................................................................................................19
5. 存在负权边的单源最短路径 .............................................................................................19
6. 多源最短路径....................................................................................................................19
其它 ........................................................................................................................19
1.1. KMP...................................................................................................................................19
1.2. 让数组不相等的最小总代价 ..........................................................................................23
1.3. 美丽塔 ..............................................................................................................................26
1.4. 美丽塔单调栈优化 ..........................................................................................................30
定位用 ....................................................................................................................33
视频算法
本书 CSDN 课程:
算法 C++版-CSDN 程序员研修院
1. 二分查找
1.1. 基础
1.1.1. 最简单的情况
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数,返回任意一个。
答疑 C/C++/ VC QQ 群:2508429
b. 原理
如果中间数和目标数相等,返回中间数索引。
如果中间数小于目标数,则目标数一定不在前半部分。
如果中间数大于目标数,则目标数一定不在后半部分。
假定数组区域是左闭右开区间,中间索引=(左索引+右索引)/2。
c. 测试数据
从 0 到 4 中找 1。
轮次
待查数据
中间数
第一轮
0 1 2 3 4
2
第二轮
0 1
1
从 1 到 5 中查找 4。
轮次
待查数据
中间数
第一轮
1 2 3 4 5
3
第二轮
4 5
5
第三轮
4
4
1.1.2. 重复数据返回第一个
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数,返回第一个。
b. 原理
如果中间数小于目标数,则目标数一定不在前半部分。
如果中间数大于目标数,则目标数一定不在后半部分。
如果中间数等于目标数,则目标数一定不在后半部分。由于左半部分必须包括中间数,
所以左开右闭区间。
c. 测试数据
从 1,2 中寻找 2。
轮次
待查数据
索引
中间数
第一轮
1 2
(-1,1]
1
第二轮
2
(0,1]
2
从 2,2,3 中寻找 2。
轮次
待查数据
索引
中间数
答疑 C/C++/ VC QQ 群:2508429
第一轮
2 2 3
(-1,2]
2
第二轮
2 2
(-1,1]
2
第三轮
2
(-1,0]
2
从 2,3,4 中寻找 2。
轮次
待查数据
索引
中间数
第一轮
2 3 4
(-1,2]
3
第二轮
2 3
(-1,1]
2
第三轮
2
(-1,0]
2
1.1.3. 重复数据返回最后一个
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数,返回最后一个。
b. 原理
一,如果中间数小于目标数,则目标数一定不在左边、中间,可能在右边。
二,如果中间数大于目标数,则目标数一定不在右边、中间,可能在左边。
三,如果中间数等于目标数,则目标数一定不在左边,可能在中间、右边。
数据
左
中
右
左闭右开
0,1,2,3
0,1
2((0+4)/2)
3
0,1,2
0
1
2
0,1
0
1
左开右闭
0,1,2,3
0
1((-1+3)/2)
2,3
0,1,2
0
1,2
0,1
0
1
结论:右(左)开,中间数就和右(左)区间合并,可以保持数据量均衡,左右数量相
差不超过 1。结合原理三,用左闭右开区间。
使用左闭右开(中右合并)后,情况分类
中间数<目标数
中右
>
左
=
中右
结论:小于等于可以合并
c. 测试数据
寻找
期望值
答疑 C/C++/ VC QQ 群:2508429
0123
0
0
0123
1
1
0123
2
2
1123
1
1
0113
1
2
1.1.4. 循环代替递归
循环结束的条件:元素数量小于 2。计算的元素数量可能是 0,也可能是负数(非法数
据)。由于是二分,所以左右边界一个不变, 一个变成中间位置。
1.1.5. 目标数不一定存在
a. 如果目标数不存在,返回-1
解决方法:返回前,判断是否等于目标值,如果不是返回-1。
b. 如果目标数不存在,返回它应该插入的位置
左开右闭
数据(寻找 0)
左右中间索引
1,3,5,7
0,4,2
1,3
0,2,1
1
0,1,0 结束
数据(寻找 2)
左右中间索引
1,3,5,7
0,4,2
1,3
0,2,1
1
0,1 结束
数据(寻找 4)
左右中间索引
1,3,5,7
0,4,2
1,3
0,2,1
3
1,2,1 结束
数据(寻找 6)
左右中间索引
1,3,5,7
0,4,2
5,7
2,4,3
5
2,3,2 结束
数据(寻找 8)
左右中间索引
1,3,5,7
0,4,2
5,7
2,4,3
7
3,4,3 结束
规律:
剩余113页未读,继续阅读
资源评论
闻缺陷则喜何志丹
- 粉丝: 1w+
- 资源: 114
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功