- 博客(160)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 蒟蒻的LeetCode刷题记录101~110
101. 对称二叉树/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool isSymmetric(Tre
2020-10-15 22:18:30
368
1
原创 蒟蒻的LeetCode刷题记录91~100
91. 解码方法class Solution {public: int numDecodings(string s) { int n = s.size(); s = ' ' + s;//为了方便，让下标从1开始，所以加上一个空格 vector<int> f(n + 1); f[0] = 1;//0个数字是的解码方案算作1 for (int i = 1; i <= n; i ++ ) {
2020-10-14 11:51:18
268
原创 蒟蒻的LeetCode刷题记录81~90
81. 搜索旋转排序数组 II和第33题类似的思路，依旧是二分,但是即便是二分，时间复杂度依旧是O(n)O(n)O(n)，所以不如直接线性扫描一遍，具体的题解。class Solution {public: bool search(vector<int>& nums, int target) { for (auto& x : nums) { if (x == target) return true; }
2020-10-13 21:23:18
142
原创 蒟蒻的LeetCode刷题记录61~70
61. 旋转链表/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* rotateRight(ListNode* head, int k) { if (
2020-10-11 22:47:34
91
原创 蒟蒻的LeetCode刷题记录41~50
41. 缺失的第一个正数将数组所有的数放入哈希表，随后从 1 开始依次枚举正整数，并判断其是否在哈希表中；但是这样的做法不符合题目的空间要求：class Solution {public: int firstMissingPositive(vector<int>& nums) { unordered_set<int> hash; for (auto x : nums) hash.insert(x); int res
2020-10-09 22:49:04
119
原创 蒟蒻的LeetCode刷题记录21~30
21. 合并两个有序链表跟之前剑指的题是一样的，直接归并。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListN
2020-10-07 18:06:54
104
原创 蒟蒻的LeetCode刷题记录11~20
11. 盛最多水的容器class Solution {public: int maxArea(vector<int>& height) { int res = 0; for (int i = 0, j = height.size() - 1; i < j; ) { res = max(res, min(height[i], height[j]) * (j - i)); if (height
2020-10-06 15:20:17
133
原创 蒟蒻的LeetCode刷题记录1~10
1.两数之和class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hash; for (int i = 0; i < nums.size(); i++) { if (hash.count(target - nums[i])) return {ha
2020-10-05 22:54:33
178
原创 Acwing算法基础课学习笔记(十八)--贪心之排序不等式&&绝对值不等式&&推公式
排队打水#include <iostream>#include <algorithm>using namespace std;const int N = 100010;int n;int t[N];int main(){ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &t[i]); sort(t, t + n);
2020-10-04 21:23:29
352
原创 Acwing算法基础课学习笔记(十七)--贪心之区间问题&&Huffman树
区间选点将每个区间按照右端点从小到大进行排序从前往后枚举区间，end值初始化为无穷小如果本次区间不能覆盖掉上次区间的右端点， ed < range[i].l说明需要选择一个新的点， res ++ ; ed = range[i].r;如果本次区间可以覆盖掉上次区间的右端点，则进行下一轮循环证明证明ans <= cnt ：cnt 是一种可行方案， ans是可行方案的最优解，也就是最小值。证明ans >= cnt ： cnt可行方案是一个区间集合，区
2020-10-04 13:23:27
173
原创 Acwing算法基础课学习笔记(十六)--动态规划之计数类DP&&数位统计DP&&状态压缩DP&&树形DP&&记忆化搜索
整数划分将其转换为完全背包问题：朴素做法：//f[i][j] = f[i - 1][j] + f[i][j - i]#include <iostream>using namespace std;const int N = 1e3 + 7, mod = 1e9 + 7;int f[N][N];int main() { int n; cin >> n; for (int i = 0; i <= n; i ++) {
2020-10-02 15:29:26
306
原创 剑指offer34~44题
二叉搜索树的后序遍历序列此题的重点是考察后序遍历的操作，左右根，也就是将最后一个节点作为分割元素，将分割为左子树、右子树和根节点，再递归判断左右子树是否满足后序遍历的特性，不满足则返回false。递归出口有两个，一个是当序列的左侧位置大于等于右侧位置是返回true，解释下此处为什么会存在大于的情况，以左子树为例，可能会存在某一点没有左子树，而我们对左子树的区间判断是s到l-1，此处的l就是s。每次递归都会干掉最后一个元素。class Solution {public: vector<i.
2020-09-22 22:40:03
70
原创 剑指offer23~33题
反转链表非常直观的动图展示/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* reverseList(ListNode* head) { List
2020-09-21 17:07:21
85
原创 剑指offer12~22题
机器人的运动范围class Solution {public: //计算单个数字的各位之和 int get_single_sum(int x) { int s = 0; while (x) { s += x %10; x /= 10; } return s; } //计算点的各位之和 int get_sum(pair<int, int> p)
2020-09-20 20:19:38
206
原创 剑指offer 1~11题
连续子数组的最大和class Solution {public: int maxSubArray(vector<int>& nums) { int res = INT_MIN; int last = 0; for(int i = 0; i < nums.size(); i++) { last = nums[i] + max(last,0); res = max(res, la
2020-09-18 12:38:13
125
原创 Acwing算法基础课学习笔记(九)--搜索与图论之Prim&&Kruskal&&染色法判定二分图&&匈牙利算法
图论的最后一节，主要讲最小生成树和二分图。常考的是最小生成树，二分图偶尔也会考到。Prim算法求最小生成树最小生成树一般都会用在无向图问题上。/*S:当前已经在联通块中的所有点的集合1. dist[i] = inf2. for n 次 t<-S外离S最近的点 利用t更新S外点到S的距离 st[t] = truen次迭代之后所有点都已加入到S中联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离*/#include <iostr
2020-09-14 11:28:40
171
原创 Acwing算法基础课学习笔记(八)--搜索与图论之最短路问题-Dijkstra&&bellman-ford&&spfa&&Floyd
最短路问题是一个比较大的问题，我们将花一节课的时间来介绍：
2020-09-13 20:08:07
219
原创 Acwing算法基础课学习笔记(七)--搜索与图论之DFS&&BFS&&树与图的深度优先遍历&&树与图的广度优先遍历&&拓扑排序
来到第三章的内容，搜索与图论。排列数字#include<iostream>using namespace std;int n; //需要搜索的个数const int N = 10;int path[N]; //path[]用于保存路径bool st[N]; //用于记录 该步是否已经走过，true则表示被用过void dfs(int u){ if (u == n) //一条路搜索完成 { for (in
2020-09-10 21:47:07
211
原创 Acwing算法基础课学习笔记(六)--数据结构之Hash表&&STL简介
来到数据结构章节的最后一节课，主要内容是哈希表和STL。模拟散列表首先要理解什么是哈希。其实之前的课讲过的离散化就是一种特殊的哈希方式，这里介绍的是一般的哈希方式。算法题中对哈希的操作一般只有添加和查找；删除一般不会涉及，非要进行删除操作的话，也不是真的删除，而是用一个bool变量进行标记即可。...
2020-09-09 21:23:40
251
原创 Acwing算法基础课学习笔记(五)--数据结构之Tire&&并查集&&&堆
Trie字符串统计#include <iostream>using namespace std;const int N = 100010;int son[N][26], cnt[N], idx;//下标是0的点，既是根节点，又是空节点char str[N];void insert(char str[]){ int p = 0;//从根结点开始遍历 for (int i = 0; str[i]; i++) { int u = str[i] - 'a'; if (
2020-09-08 23:17:07
228
原创 Acwing算法基础课学习笔记(四)--数据结构之单链表&&双链表&&模拟栈&&模拟队列&&单调栈&&单调队列&&KMP
单链表算法题中最常考的单链表就是邻接表（用来存储图和数），比如最短路问题，最小生成树问题，最大流问题。双链表用于优化某些问题。利用数组来表达单链表：存储值和指针的两个数组利用下标进行关联。需要注意的是，head不是节点，只是指向某个节点的指针。head存的是链表第一个点的下标，形象地看就好像是指向了头结点。这里贴一个非常有趣的题解#include <iostream>using namespace std;const int N = 100010;int n;int h
2020-09-08 14:48:42
200
1
原创 Acwing算法基础课学习笔记(三)--基础算法之双指针算法 && 位运算 &&离散化 &&区间合并
最长连续不重复子序列双指针算法的核心在于优化，通常把O(n2)O(n^2)O(n2)优化成了O(n)O(n)O(n)。而且之前的快排和归并其实也用了双指针的思想。根据观察发现，当使用i,j两个快慢指针表示当前的指针移动到i的最长不重复序列时候，具有单调性，即i向后移动，j必然向右或者不动，不可能向左移动，这一单调性质导致可以使用双指针算法。在双指针算法中，一个指针扫描整个数组而移动，关键如何找到对应的另一个指针移动的位置，在本题中，我们定义i为块指针，j为慢指针，j的位置定义为i对应的最长不重复序列
2020-09-04 16:58:36
186
原创 Acwing算法基础课学习笔记(一)--基础算法之排序&&二分
快速排序快速排序最大的坑就在于边界值的处理，y总给的这个板子还是很牛逼的！#include <iostream>using namespace std;const int N = 1e6+10;int n;int arr[N];void quickSort(int arr[], int l,int r){ if(l >= r) return; int x = arr[(l + r + 1)/2], i = l - 1, j = r + 1;
2020-09-02 16:45:45
309
原创 c++编译链接过程
编译链接过程预编译（预编译器处理如 #include、#define 等预编译指令，生成 .i 或 .ii 文件）编译（编译器进行词法分析、语法分析、语义分析、中间代码生成、目标代码生成、优化，生成 .s 文件）汇编（汇编器把汇编码翻译成机器码，生成 .o 文件）链接（连接器进行地址和空间分配、符号决议、重定位，生成 .out 文件...
2020-08-25 10:29:22
248
原创 STL常用algorithms
// 简单查找算法，要求输入迭代器（input iterator）find(beg, end, val); // 返回一个迭代器，指向输入序列中第一个等于 val 的元素，未找到返回 endfind_if(beg, end, unaryPred); // 返回一个迭代器，指向第一个满足 unaryPred 的元素，未找到返回 endfind_if_not(beg, end, unaryPred); // 返回一个迭代器，指向第一个令 unaryPred 为 false 的元素，未找到返回 endco
2020-08-24 23:04:34
143
原创 Bug算法(Bug Algorithms)简介（Bug1 & Bug2 & Tangent Bug）
本文所有图片均来自以下这本书:Principles of Robot Motion: Theory, Algorithms, and Implementations[M]. MIT Press, 2005.在上一篇博客我也给出了下载链接。本篇博客主要介绍一下BUG算法:BUG算法（Bug Algorithms）是一种最简单的避障算法。其算法原理类似昆虫爬行的运动决策策略。在未遇到障碍物时，沿直线向目标运动；在遇到障碍物后，沿着障碍物边界绕行，并利用一定的判断准则离开障碍物继续直行。这种应激式的算
2020-08-18 18:12:39
8497
4
原创 Principles of Robot Motion Theory, Algorithms, and Implementations下载
机器人运动理论的原理，算法和实现，非常经典的一本书，做规划的小伙伴们的必备！csdn也有本书的相关资源，但无一例外的都需要积分下载，互联网的分享精神真是被这帮人都玩坏了！原本想上传，无奈不能上传已存在的内容，所以这里给出下载地址，需要的自取！原仓库也有其他一些很不错的书，大家可以一并下载！下载地址...
2020-08-18 16:15:24
2582
11
翻译 手把手教会用C++实现A*算法
书接上回，上一篇博客我们介绍了A算法最基本的原理，本篇博客我们来手把手的教会大家A算法的C++实现！原文链接在此，大佬分别用Python、C++、C#进行了算法的实现orz正文如下：本文是我对A *的介绍的辅助指南，在此我将解释算法的工作原理。在此页面上，我将展示如何实现广度优先搜索，Dijkstra的算法，贪婪的最佳优先搜索和A *。 我尝试使代码保持简单。图搜索有一系列相关算法。算法有很多变体，实现上也有很多变体。将本文展示的代码视为一个起点，而不是适用于所有情况的最终版本。c++实现注
2020-08-18 16:06:23
9003
2
翻译 可能是最好的A*算法简介，没有之一！
关于A∗A^*A∗算法，中文资源有点少，能够通俗解释A∗A^*A∗算法的也很少，之前比较不错的是这里的英文博客，斯坦福大佬十几年前写的博客，也有一些中文翻译。然后我去大佬博客主页翻了翻，看到了最近的一篇关于A∗A^*A∗的文章，详情请看这里的原文连接。本人粗略搜了一下没发现有对应的中文翻译。因此在这里翻译一份，也可以算作是一个重新的学习吧！由于本人水平有限，难免有纰漏，欢迎随时交流指出，转载请注明出处。写在前面本文翻译自 Red Blob Games，强烈建议看一看大佬的原博客，有很多互动的可视化演示，
2020-08-17 15:08:50
1523
2
ROS理论与实践_4.机器人仿真_代码.rar
2020-08-12
Gonzalez-2016-A-review-of-motion-planning-techniq.pdf
2020-07-20
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人