BFS finish

BFS简介 BFS（Breadth First Search）：宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。 代码模板 我们利用一个辅助队列来存储每一层的结点。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeN...

算法思路 这道题主要考察BFS，我们只需要按照BFS的模板写就可以，只不过在奇数层从左到右输出，偶数层从右至左输出，我们可以用个flag标识奇偶层。 代码实现 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<int> temp; //保留每一层结点的数组 vector<vector<i...

ccc

1、简介 我们在递归的时候说到过，一般我们如果想把递归的算法转换至非递归的实现，我们可以自己利用辅助栈来代替系统栈保存一些信息。所以在实现二叉树的三种非递归遍历的时候，我们需要开辟一个辅助栈来保存一些信息。 2、二叉树结点结构 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/  3、先序遍历 2.1 实现思路 我们只需要开辟一个栈，先让根节点入栈。只要栈不空，我们循环的访问栈...

1、思路 由于二叉树的结构本身就是递归的，所以其很多操作都可以递归的实现。比如三种遍历操作。比如对于先序遍历，我们只需要先访问其根节点，再递归的访问左右子树即可。 2、二叉树结点结构 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/  3、先序遍历 void preOrder(TreeNode *root) { if(root) { cout<<root->...

路漫漫其修远兮

1、简介 我们想要复制一个文件描述符的话，经常会使用dup（）函数和dup2（）函数。关于dup（）函数的使用十分简单，但是很多人在使用dup2（）函数进行文件重定向的时候会有疑问，总觉得两个参数是反的。接下来我说一下对这个函数的理解。^-^ 2、dup2（）函数 2.1 头文件和函数原型 #include <unistd.h> int dup2(int oldfd, int newfd);  2.2 参数简介  oldfd:原来的文件描述符 newfd：复制成的新的文件描述符  2.3 函数返回值  成功：将oldfd复制给newfd, 两个文件描述符指向同一个文件 失败：返回-...

cnm的位运算

打卡

动态规划emmmm

1、全排列简介 比如对于一个序列：[1,2,3]、这个序列的全排列就是：  [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 全排列的定义十分简单。我们在刷题的过程中也经常会碰见一些需要求全排列的题目。比如：链接字符串的排列、链接把数组排成最小的数等。接下来我们用递归的思路去实现下数的全排列。  2、递归思路 比如对于序列[1,2,3]。其全排列过程其实是这样的：我们首先固定住1，然后对2、3进行全排列。在对2、3进行全排列的过程中呢，我们采取的方法也是一样的，就是固定住2，对3进行全排列。（由此可以看出这里可以用递归）固定住1的全排列排完之后呢，...

算法思路 利用双指针，定义一个指针i和一个指针j。让i开始走。固定住j。然后我们利用一个辅助数组来记录下每个字符出现的次数。比如对于字符串“abcabcdd”，当i走到第二个a的时候，a出现了两次，这时候让j开始向前走。走到b。这时候i和j之间的字符串是bca。没有重复的，i可以继续走，j继续固定。i走到b的时候b出现两次。这时候要移动j直至没有字符出现次数超过两次。如此反复直到i走到字符串结尾。 代码实现 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 *...