- 博客(141)
- 收藏
- 关注
RSS订阅
原创 C++ 参数加入const &的作用
一.作为传入参数不可以修改其值二.如果实参与形参的数据类型相同时，则不会创建新的临时变量，即形参和实参的地址相同三.如果实参与形参的数据类型不同时，则会在函数体中创建一个新的形参临时变量来存储实参类型，这里会自动对实参进行强制类型转化，转化为形参类型，此时形参与实参地址不同#include<iostream>#include<string>using namespace std;void g(string &a, const string &b){
2021-06-14 09:45:02
1349
6
原创 CSAPP-深入理解计算机系统-task01计算机系统漫游
计算机系统漫游（上）1.hello world程序的创建-运行-退出的流程hello world程序从编写到最终执行结束需要经过下面这4个步骤：-创建/create-编译/compile-运行/run-退出/exit创建的代码如下，保存为hello.c的文件：#include<stdio.h>int main(void) { printf("hello, world"); return 0;}编译部分：通过gcc -o hello hello.c命令完成
2021-12-14 14:51:01
1540
原创 剑指 Offer II 105. 岛屿的最大面积-经典BFS和DFS问题
https://leetcode-cn.com/problems/ZL6zAn/解题思路：采用BFS：需要用到额外空间队列或者栈采用DFS：不需要额外空间注意：grid的更新//DFSclass Solution {public: int maxAreaOfIsland(vector<vector<int>>& grid) { int ans = 0; for(int i = 0; i < grid.si.
2021-09-29 09:39:46
194
原创 114. 二叉树展开为链表-二叉树
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/解题思路：本题观察最后链表从头至尾的顺序正好是前序遍历的结果，所以考虑将前序遍历结果进行存储然后再进行相应的连接注意：1.前序遍历存储的位置2.递归结束的条件参考：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-.
2021-09-28 16:39:44
161
原创 leetcode 226. 翻转二叉树-二叉树
https://leetcode-cn.com/problems/invert-binary-tree/解题思路:在前序遍历位置进行交换,因为前序是从根节点遍历注意:1.递归结束条件/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), l.
2021-09-28 10:36:10
107
原创 剑指 Offer 07. 重建二叉树-二叉树
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/解题思路本题的解题思路是根据前序和后序遍历的特点,查找到根节点位置以及边界进行递归重建注意:1.递归结束的条件2.边界的计算参考https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/.
2021-09-28 10:00:39
60
原创 剑指 Offer 14- I. 剪绳子-动态规划
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/zhu-shi-xing-ti-jie-dong-tai-gui-hua-jia-4xfp/解题思路：一根绳子剪成两段后，实际上还是根绳子，那么就是一个问题可以拆分成相同子问题来解决，所以考虑用动态规划，这里要注意dp应该存储的内容注意：1.dp的定义2.循环条件有个隐藏值就是j只需要循环到i的一半就行class Solution {public:// 本.
2021-09-14 15:23:46
47
原创 剑指 Offer 12. 矩阵中的路径-DFS+回溯(复原)
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/本题是一个遍历查找的过程，初始位置随机，每次移动的方向有4个，所以本题是遍历+DFS递归+回溯注意:1.边界判断2.满足条件返回3.回溯,防止选择方向时走到走过的位置class Solution {private: // 记录board的大小 int rows,cols;public: bool exist(vector<ve.
2021-09-12 21:23:20
91
原创 剑指 Offer 11. 旋转数组的最小数字-二分法
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/本题是查找问题，可以考虑用二分查找来做，时间复杂度为O(log(n))class Solution {public: int minArray(vector<int>& numbers) { int low = 0; int high = numbers.size() - 1; .
2021-09-12 20:55:01
56
原创 剑指 Offer 09. 用两个栈实现队列
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/解题思路:考虑用两个栈来模拟队列,主要是实现队列的先进先出问题class CQueue {private: stack<int>stack1,stack2;public: CQueue() { while(!stack1.empty()){ stack1.pop();.
2021-09-12 18:56:14
51
原创 Leetcode313. 超级丑数-多指针+动态规划
地址https://leetcode-cn.com/problems/super-ugly-number/解题思路本题要求返回第n个超级丑数,我们知道1是第一个超级丑数,而任何一个超级丑数都可以通过前面的超级丑数乘以质数数组用的元素得到,所以可以采用多指针+备忘录思想,多指针实际存储的是当前索引值乘以指向备忘录形成一个超级丑数注意:1.指针更新可能存在多指针需要更新,避免备忘录中出现重复class Solution {public: int nthSuperUglyNumber.
2021-08-09 14:36:17
75
原创 Leetcode1962. 移除石子使总数最小-优先队列
链接:https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total/解题思路:从题中可以看出这个floor函数实际上就是数量的一半的意思,本题每一次移除某一堆石子的一半,所以为了剩下的石子总数最小,我们每一次都要对石子数量最多的进行减半操作,所以每一次都要返回最大的值,这里就需要构建大顶堆注意:1.大顶堆构建2.堆的弹出和压入操作class Solution {public: int minStoneSum.
2021-08-09 13:29:18
123
原创 leetcode 802. 找到最终的安全状态-DFS+颜色标注状态
链接：https://leetcode-cn.com/problems/find-eventual-safe-states/解题思路：本题主要是判断图中结点如果在环内那么一定是不安全的，因为环内结点一定存在一条路径是无法到达最终结点的，所以采用DFS+颜色标注进行环的判断注意：1.颜色标注定义2.颜色状态转换class Solution {public: vector<int> eventualSafeNodes(vector<vector<int&g.
2021-08-05 10:43:58
273
原创 牛客 平分物品-DFS
地址链接：https://www.nowcoder.com/practice/908255677b6f4c18a9074c12f21acd59?tab=note解题思路:对于每一个数组元素的选择可以有三种，分别为分给第一个人、分给第二个人、或者丢弃，那我我们可以采用深度优先搜索+三种选择注意：1.递归结束条件2.递归入口设计#include<iostream>#include<vector>#include<algorithm>#include.
2021-08-04 17:03:41
163
原创 Leetcode 347. 前 K 个高频元素-优先队列（构建小顶堆）
解题思路:首先遍历用map记录每一个元素的频率,然后利用小顶堆进行存储,小顶堆的大小为k注意:1.小顶堆创建的实现2.删除和插入操作class Solution {public: // 构建小顶堆比较方法 static bool cmp(pair<int, int>& m, pair<int, int>& n) { return m.second > n.second; } vector&l.
2021-07-28 13:56:12
105
原创 Leetcode 863. 二叉树中所有距离为 K 的结点-Hashmap+DFS
解题思路：本题是寻找离木标结点相距k的所有结点，这里不但右子树结点还可能存在父亲等其他结点，因为树是一种递归结构不会存储父节点，所以先DFS遍历存储每一个结点的父节点，然后再DFS进行满足田间的搜索注意：1.满足条件搜索时避免发生重复搜索，要加入一个from结点，该节点递归的前一个结点/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; *.
2021-07-28 13:25:14
84
原创 Leetcode 138. 复制带随机指针的链表-递归(回溯)+hashmap
解题思路：本题要求进行深拷贝，而且存在一个随机指针，这个指针的指向可能还没在当前链表中，所以要先进行存储，这里采用hashmap进行存储，其中key表示原结点，val表示新创建的结点注意：1.递归结束条件为head==nullptr2.map的存储问题/*// Definition for a Node.class Node {public: int val; Node* next; Node* random; Node(int _val).
2021-07-22 09:37:21
70
原创 Leetcode 1921. 消灭怪物的最大数量-排序+贪心
解题思路：首先要计算所有怪兽攻击到城市所花费的次数，然后按照此时从小到达排序，我们要先杀掉次数少的，如果第n轮次的无法杀掉怪兽就输掉了注意：1.花费时间计算需要-1再除2.查询攻破轮次class Solution {public: int eliminateMaximum(vector<int>& dist, vector<int>& speed) { // 计算每一怪兽攻下城市花费的时间 for(int ..
2021-07-21 22:02:37
364
原创 datawhale OCR竞赛task02-改进策略
一、采用尝试其他模型进行微调或者采用多模型共同预测二、在检测前再加入一个方向检测分类模块，降低检测困难，提升检测准确率三、添加直方图均衡化和透视变换来矫正倾斜样本四、存在字体模糊问题，可以采用锐化和对比度增强手段来提升文字边缘信息...
2021-07-21 20:14:05
89
原创 leetcode 1838. 最高频元素的频数-滑动窗口
解题思路：本题是求最大可能频数，虽然是求解最值问题，但是并不能想象成迭代子问题，所以不能利用动态规划，而题目给的数据量为10^5并不能利用暴力破解，这样的话会超过限制，所以要进行一系列的优化，采用滑动窗口思想进行优化注意：1.当右边窗口向右移动时，如何计算需要的频率，以及如和更新左边界class Solution {public: int maxFrequency(vector<int>& nums, int k) { if(nums.empt..
2021-07-19 10:48:37
89
原创 Leetcode 210. 课程表 II-图-深度优先搜索
解题思路：可以参考https://blog.csdn.net/jhb1021821368/article/details/118863116这个题，只不过本题要求对图进行拓扑排序，这里多加了一个模拟的栈结构，在栈底下存储深度优先搜索的最深结点class Solution {private: // 存储有向图 vector<vector<int>>edges; // 存储结点的状态0表示未搜索，1表示正在搜索，2表示搜索完成 vector..
2021-07-17 21:51:12
78
原创 Leetcode 207. 课程表-图-深度优先搜索
解题思路：如题目所示，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。实际上可以想象为有一个值为1的结点指向值为0的结点，而且每一个可以指向的结点数量并不固定，所以就是个有向图，而要想判断是否能够完成，实际上对于图来说如果存在环那么就意味着存在两个结点互相指向（互相需要），所以如果存在环那么一定无法学完所有课程注意：1.如何将题目所给参数转化为抽象的图结构2.如何进行深度优先搜索3.如何判断是否存在环结构class Solution {// 本题思路是将题..
2021-07-17 21:46:46
58
原创 leetcode 152. 乘积最大子数组-动态规划
解题思路：本题与第53题最大子序列的和相似，可以考虑动态规划来解决注意事项：1.两数相乘要分正负号class Solution {public:// 动态规划类似第53题最大子序列的和 int maxProduct(vector<int>& nums) { vector<int>maxv(nums),minv(nums); for(int i = 1;i<nums.size();++i){ ..
2021-07-16 16:27:11
37
原创 Leetcode 148. 排序链表-归并排序
解题思路：本文要求将无序链表进行排序，可以选择归并排序注意：1.归并分为左右递归和融合模块/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ..
2021-07-15 21:29:17
100
原创 Leetcode 102. 二叉树的层序遍历-BFS（广度优先搜索）
解题思路：本题要求按照层来遍历，想到BFS采用的思路正是和二叉树层次遍历一样，采用队列来优先管理每层结点，然后遍历该层所有结点注意：1.遍历结束标志/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), righ..
2021-07-13 14:05:20
110
原创 Leetcode 78. 子集-回溯
解题思路：本题是返回解的集合，考虑选用回溯来暴力递归，这里题目说数组元素互不相同，要求返回的子集不重复，只需要利用index来控制不走回头路注意：1.递归返回条件2.index的使用，注意在函数参数传递的时候传的是i+1class Solution {public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>&..
2021-07-12 15:04:42
39
原创 leetcode 70. 爬楼梯-动态规划
解题思路：每一个台阶的方法数与上一个台阶和上上一个台阶方法数相关，所以可以采用动态规划的思想注意：1.初始化内容2.状态转移方程class Solution {public: // 采用动态规划思想，f(x) = f(x-1)+f(x-2) int climbStairs(int n) { int p =0,q = 0,r = 1; for(int i = 0;i<n;++i){ p = q; ..
2021-07-06 13:56:51
47
原创 leetcode 64. 最小路径和-动态规划
解题思路：本题要求求解出最短路径，而每一次的选择只能向下或者向右走，所以每一个位置都和他上面和左面的路径大小相关，采用备忘录的迭代思想（动态规划）来解决此类问题注意1.备忘录初始化的一些数据2.转移状态函数的设计class Solution {public: // 动态规划 int minPathSum(vector<vector<int>>& grid) { int h = grid.size(); in..
2021-07-06 13:24:51
66
原创 leetcode 62. 不同路径-动态规划
解题思路：本题要求求出路径数量，可以从题目中看出每一个点的路径数量等于他左边和上边点的路径数量之和，所以可以采用动态规划思想，构建备忘录注意：1.初始化备忘录2.状态转移方程class Solution {public: // 动态规划，每一步都是由左边的格子和上面的格子路径之和来计算的，而且在[0][j]和[i][0]在边界上的路径为1 int uniquePaths(int m, int n) { // 创建二维备忘录存储每一个位置的路径数量 ..
2021-07-04 21:39:30
47
原创 leetcode 46. 全排列-回溯算法
解题思路本题输出所有可能的排列，采用回溯算法注意：1.筛选条件class Solution {public: vector<vector<int>> permute(vector<int>& nums) { vector<int>path; vector<vector<int>>res; unordered_set<int>myset;//存..
2021-07-03 20:34:11
96
原创 leetcode 39. 组合总和-回溯算法
解题思路:本文要求给出所有符合条件的组合，考虑采用不会走回头路的回溯算法注意:1.递归退出条件2.不走回头路设置3.提前结束(break)class Solution {public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector...
2021-07-03 20:09:32
113
原创 leetcode 451. 根据字符出现频率排序-桶排序
解题思路：统计的是数量问题，而且是要求最终进行排序，想到重复元素个数比较多，可以采用桶排序的思想进行排序存储注意：1.桶排序索引的设计2.相同频率的元素的处理，采用string进行push_back，然后解析的时候再单独拿出每一个charclass Solution {public: string frequencySort(string s) { unordered_map<char,int>mymap; int maxflag ..
2021-07-03 15:05:54
65
原创 leetcode 17. 电话号码的字母组合-回溯算法
解题思路：要求找出所有组合，所以选用回溯算法注意：1.退出迭代条件2.char转intclass Solution {public: vector<string> letterCombinations(string digits) { if(digits.empty()){return {};} // 存储所有可能性 vector<string> source = {"abc","def","ghi","j..
2021-07-02 16:52:20
62
原创 leetcode LCP 07. 传递信息-回溯算法
解题思路：本题就是一个有向图的遍历问题，可以采用深度优先，广度优先，回溯等递归算法，本题的解答方法采用回溯算法注意：1.递归结束条件2.数组遍历边界问题3.筛选条件class Solution {public: int numWays(int n, vector<vector<int>>& relation, int k) { if(relation.size()==0)return 0; vector<int..
2021-07-01 10:43:45
109
原创 leetcode 116. 填充每个节点的下一个右侧节点指针-二叉树
解题思路：本题实际上就是将每一层的所有结点利用next指针相连，但是要注意这里出现了不同父节点的叶子结点相连，这个也是本题的难点注意：1.递归的出口条件2.叶子结点操作的位置/*// Definition for a Node.class Node {public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL),...
2021-06-22 19:48:22
66
原创 Leetcode -剑指 Offer 38. 字符串的排列-回溯法
解题思路：题目要求输出所有排列，这种类似于暴力破解方法可以考虑选用回溯法进行递归遍历，同时加入一些选择条件，来判断是否符合条件，注意本题要求输出的结果中不能存在重复元素，所以考虑用set存储注意：1.如何判断某一个元素是否被加入到路径中，这里可以选用一个数组来记录索引位置是否被加入到路径，注意设置记录为true或者false的时机2.判断满足条件加入到路径中class Solution {public: vector<string> permutation(str..
2021-06-22 09:52:56
86
原创 leetcode 401. 二进制手表-暴力破解枚举法
解题思路:本题要求，根据输入的二进制亮灯的数量，来求解出所有可能得时间，我们知道时间的显示是在一个固定的范围，所以可以考虑枚举求解，然后按照条件进行筛选注意;1.枚举的范围2.string的处理class Solution {public:// 暴力破解枚举法 vector<string> readBinaryWatch(int turnedOn) { vector<string> res; for(int h = 0;...
2021-06-21 08:59:03
124
原创 leetcode 1863. 找出所有子集的异或总和再求和-回溯法
解题思路：本文要遍历所有子集，所以可以考虑回溯法，因为每一个都会被遍历到，而且方便筛选符合条件的结果注意：1.结果反回值的处理2.递归退出的条件3.加入路径的筛选class Solution {public: int subsetXORSum(vector<int>& nums) { int res = 0; vector<int> path; trace(nums,path,res,0); ..
2021-06-19 20:22:11
170
原创 leetcode 1239. 串联字符串的最大长度-回溯法
解题思路：本题要求返回的是最长长度，因为每一次再做拼接时候，需要考虑自身的每一个字符是否是不重复的，而且还要考虑，自身字符是否和已存在满足要求的字符串重复，随意需要整个遍历很多次，然后只选择满足要求的部分加入到路径中，选择采用回溯算法注意：1.注意满足加入路径的条件2.遍历条件3.在递归后面加入pop操作class Solution {public: int maxLength(vector<string>& arr) { int curr = 0; i..
2021-06-19 14:52:30
82
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人