【读书笔记】《挑战程序设计竞赛》
《挑战程序设计竞赛》
前言
坚持就是胜利，本人使用语言java
一、蓄势待发–准备篇
1.5.1 算法复杂度
1.6.1 O(nlogn)三角形问题
O(nlogn)方法：
- 将边按照从小到大顺序进行排序；
- 从大到小进行搜索，如果，edge[i],edge[i+1],edge[i+2]能构成三角形，即为周长对大的三角形；
原因：
三角形条件： A<B+C （其中A是最长的边）；
要使得周长最长，B+C要尽可能的大；
排序后的B+C剩下边里面的最大，如果不满足，则没有边可以边满足B+C>A,即对A而言，不存在三角形；如果满足，则是最大周长的三角形；
1.6.2 蚂蚁问题
思路：智力题，开动你的小脑经！！
1.6.3 抽签问题（四数之和）
问题描述：数组中是否存在： a+b+c+d = m
解决方案：看成前两个数之和与后两个数之和，利用二分查找，效率为（O(n^2logn)
练习
博客中使用：先排序；双指针（O(n^3)），回溯法（利用条件会剪枝）
二、初出茅庐–初级篇
2.1 “穷竭搜索”–暴力
穷竭搜索：将所有的可能性列出来，在其中寻找答案
递归：自己调用自己
数据结构：
栈Stack（LIFO）：push；pop；peek；
队列Queue（FIFO）：offer；poll；peek；
遍历方法：
深度优先遍历（DFS）：深入；栈；（解数独）
宽度优先遍历（BFS）：周围；队列 （最短路径，最少操作）
2.1.4 DFS–水洼的数量
思路：
- 八联通的则为水洼，需遍历一个单位附近的八个单位并将它们都改成’.’；
- dfs遍历到尽头，并将这些联通的W全部改掉；W连接的所有W都替换成了’.’；
- 直到图中不再存在W为止，执行dfs的次数即为水洼的个数。
练习
2.1.5 BFS–迷宫最短路径
问题：N*M规格迷宫；起点S；终点G；墙壁#；通道.；寻找一条最短路径从起点到达终点
思路：
- 本题要求最短距离，可用 d[N][M] 数组保存距离，INF 初始化；将起点的距离设置成0；
- 将上下左右（可移动，是通道）的距离为当前点的距离+1，并且加入队列；
- 读取队列中节点，BFS遍历上下左右，直到遇见终点或者所有节点访问完成；
- 如果是遇见终点，即为最短距离；如果点访问结束，则不可达；
2.1.6 next_permutation(begin(nums), end(nums))
按照字典序给出nums数组的下一个排列顺序；
C++语言中可以用来跟方便的获取下一个排列顺序；java没有
练习
2.1.7 剪枝
暴力中，有时候解空间很大，深度DFS，有时候很早可以根据某些条件直接跳过，剪枝，来缩小解空间；
2.2 一直向前！–贪心
贪心：不断贪心地选取当前最优的策略
我的经验：主要是看问题贪心选择后能不能变成一样的贪心子问题
2.2.1 硬币问题
思想: 优先兑换面值大的硬币
2.2.2 区间问题
思想: 在可选的工作当中，每次都选择结束时间最早的工作
2.2.3 字典序最小问题
思想: 不断取S开头末尾较小的字符放在T末尾，如果相同，比较S与反转S’的字典序，选择较小方向字符的放在T末尾；
2.2.4 其他问题
思想: 向右遍历尽可能远的选择点，实现覆盖，这样最后获得最少的点
思想: 类比于哈夫曼树，最短的木板最远，最后加权路径和最小；
2.3 动态规划DP
动态规划（DP）：不断贪心地选取当前最优的策略
我的经验：真难get，md