没有合适的资源?快使用搜索试试~ 我知道了~
算法笔记学习(7).pdf
需积分: 9 0 下载量 140 浏览量
2022-10-28
11:00:20
上传
评论
收藏 1.85MB PDF 举报
温馨提示
试读
93页
算法笔记学习(7).pdf
资源推荐
资源详情
资源评论
算法笔记学习
算法笔记学习
基础算法
前缀和数组
差分数组
对称旋转问题
螺旋矩阵
二分
数学问题
进制转换
最大公约数
最小公倍数
分数
表示
三项规则:
化简
计算
输出
素数
朴素算法
判素数
获取素数表
Eratosthenes筛法 (O(nloglogn))
数素数
质因子分解
大整数运算
大整数的存储
大整数四则运算
组合数
C++标准模板库(STL)
vector “变长数组”
set “集合”
string "串"
map “映射”
queue “队列”
priority_queue “优先队列”
stack “栈”
pair “一对”
algorithm 头文件下的常用函数
数据结构专题(1)
栈的应用
队列的应用
链表的处理
搜索专题
深度优先搜索(DFS)
广度优先搜索(BFS)
数据结构专题(2)
树与二叉树
二叉树的遍历
构造二叉树
树的遍历
二叉查找树(BST)
平衡二叉树(AVL树)
并查集
堆
哈夫曼树
图算法专题
图的存储
图的遍历
最短路径
DijKstra算法
Bellman-Ford算法 和 SPFA算法
Floyd算法
最小生成树
prim算法(贪吃蛇)
KrusKal算法(连连看)
拓扑排序
关键路径
AOV网和AOE网
关键路径
动态规划
动态规划的递归写法
动态规划的递推写法
最大连续子序列和
最长不下降子序列(LIS)
最长公共子序列(LCS)
最长回文子串
DAG最长路
背包问题
0-1背包问题
完全背包问题
多重背包问题
总结
字符串专题
字符串hash进阶
KMP算法 O(n + m)
next数组
KMP
nextval数组
扩展专题
分块思想
树状数组(BIT)
我的补充
单调栈
滑动窗口
滑动哈希技巧
Rabin-Karp 算法
浅析回溯法与dfs
回溯法
DFS
回溯法与动态规划的区别
DFS
BFS
洗牌算法
快速排序
归并排序
计算完全二叉树节点数
图的遍历
邻接表问题
二分图(双色问题)
并查集
动态规划之问题详解
贪心
注意体会这题
字符串拼接
字符串和数字相互转化:
学会处理二维数据表的上下左右四个方向问题
结尾
基础算法
前缀和数组
前缀和数组类似于小动规问题,可以解决【区域和检索——数组不可变】问题。
设定 preSum数组,preSum[i] 为nums[0...i]的累加和。
要计算nums[i...j]的元素和,则 return preSum[j + 1] - preSum[i] 。
差分数组
差分数组解决【频繁对原始数组的某个区间的元素进行增减】
一般的写法:
对称旋转问题
首先,需要理解基础的对称操作,对于 n x n 的矩阵 matrix,各种对称的转移式如下:
vector<int> diff(n, 0);//初始化
//arrays里装有测试数据,遍历容器使用auto迭代器
for(int array : arrays){
//注意左右端点的选取
//left和right是array中的数据,看题选取边界
diff[left] += val;
diff[right + 1] -= val;
}
int sum = 0 , k = 0;
for(auto d : diff){
sum += d;
answer[k ++] = sum;
}
return answer;
上下对称:matrix[i] [j] -> matrix[n-i-1] [j],(列不变)
左右对称:matrix[i] [j] -> matrix[i] [n-j-1],(行不变)
主对角线对称:matrix[i] [j] -> matrix[j] [i],(行列互换)
副对角线对称:matrix[i] [j] -> matrix[n-j-1] [n-i-1] (行列均变,且互换)
那么,对于顺时针 90° 旋转,先写出转移式:
matrix[i] [j] -> matrix[j] [n-i-1],
可以观察到,我们希望原来的列j不变,且要交换行列位置。
因此可以分解为:上下对称 + 主对角线对称 或者 主对角线对称 + 左右对称,
注意分解顺序是不能换的。
对于顺时针 180° 旋转,可视为两次顺时针 90° 旋转:
顺时针 90° + 顺时针 90°
= 上下对称 + 主对角线对称 + 主对角线对称 + 左右对称
= 上下对称 + 左右对称 (主对角线对称抵消)
这里也可根据顺时针 180° 的转移式:
matrix[i] [j] -> matrix[n-i-1] [n-j-1],
分解为 主对角线对称 + 副对角线对称。
再往后,顺时针 270°,这个可以分解为:
顺时针 180° + 顺时针 90°
= 左右对称 + 上下对称 + 上下对称 + 主对角线对称
= 左右对称 + 主对角线对称 (上下对称抵消)
另外,也可转换为逆时针 90° 来做。
最后,顺时针 360° 即原图。
// 上下对称
void upDownSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n/2; ++i) {
for (int j = 0; j < n; ++j) {
swap(matrix[i][j], matrix[n-i-1][j]);
}
}
}
// 左右对称
void leftRightSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n/2; ++j) {
swap(matrix[i][j], matrix[i][n-j-1]);
}
}
}
// 主对角线对称
void mainDiagSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n-1; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
螺旋矩阵
边界模拟法
step 1:首先排除特殊情况,即矩阵为空的情况。
step 2:设置矩阵的四个边界值,开始准备螺旋遍历矩阵,遍历的截止点是左右边界或者上下边界
重合。
step 3:首先对最上面一排从左到右进行遍历输出,到达最右边后第一排就输出完了,上边界相应
就往下一行,要判断上下边界是否相遇相交。
step 4:然后输出到了右边,正好就对最右边一列从上到下输出,到底后最右边一列已经输出完
了,右边界就相应往左一列,要判断左右边界是否相遇相交。
step 5:然后对最下面一排从右到左进行遍历输出,到达最左边后最下一排就输出完了,下边界相
应就往上一行,要判断上下边界是否相遇相交。
step 6:然后输出到了左边,正好就对最左边一列从下到上输出,到顶后最左边一列已经输出完
了,左边界就相应往右一列,要判断左右边界是否相遇相交。
step 7:重复上述3-6步骤直到循环结束。
// 副对角线对称
void subdiagSymmetry(vector<vector<int>>& matrix) {
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < n-i-1; ++j) {
swap(matrix[i][j], matrix[n-j-1][n-i-1]);
}
}
vector<int> spiralOrder(vector<vector<int> > &matrix) {
vector<int> res;
int n = matrix.size();
if(n == 0) return res;
//初始化四个边界
int left = 0, right = matrix[0].size() - 1;
int up = 0, down = n - 1;
while(left <= right && up <= down){
for(int i = left; i <= right; i ++)
res.push_back(matrix[up][i]);
up ++;
if(up > down) break;
for(int i = up; i <= down; i ++)
res.push_back(matrix[i][right]);
right --;
if(left > right) break;
for(int i = right; i >= left; i --)
res.push_back(matrix[down][i]);
down --;
if(up > down) break;
for(int i = down; i >= up; i --)
res.push_back(matrix[i][left]);
left ++;
if(left > right) break;
}
剩余92页未读,继续阅读
资源评论
fan_yimu666
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功