小胡同的诗

题目链接：leetcode117题面题目大意给你一个二叉树，树节点指针域中多给了一个next指针，让你在时间复杂度尽可能优的情况下把每层的节点利用next指针串成一个链表。解题思路BFS（二叉树层次遍历）利用队列，额外维护一个树的高度，之后按高度把每层的next指针串连起来。但由于使用到额外的空间，显然不是本题的最优解。时间复杂度：O(n)O(n)O(n)，空间复杂度：O(n)O(n)O(n)。DFS+栈我们不难发现，需要处理 next 指针的节点除了整棵树的最右侧链外其余均需要。而

题目链接：leetcode60题目大意给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：“123”“132”“213”“231”“312”“321”给定 n 和 k，返回第 k 个排列。说明：给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。输入: n = 3, k = 3输出: “213”输入: n = 4, k = 9输出: "2314"解题思路数学

题目链接：leetcode17题目大意给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例:输入：“23”输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].解题思路回溯实际上就是输出类似位向量所有组合结果的解法。大水题，注意判空类型。实现代码class Solution { string Tab[10] = {"",

题目链接: poj2248题目大意给你一个数字n，你需要构造一个首项为1，末项为n的递增序列，并且这个序列的非首项的数字都能从它前面找到两项之和与之相等，前面的两项可以为同一项，即可重复，并且要让这个序列尽可能短，如果有多解输出其中一种序列解即可。（n<=100）解题思路朴素搜索我们可以从第二项开始构造。因为已知第一项为1，所以通过前面的已知项生成的后续项一定能保证上述的『x[i]+x[j]=x[k]x[i] + x[j] = x[k]x[i]+x[j]=x[k]』的条件；在生成后

算法描述tarjan算法在求强联通分量效率十分高，核心思想是维护的dfn和low数组；而对于树上公共祖先问题也能离线地处理询问，算法复杂度O(n+q)O(n+q)O(n+q)。算法是：后序遍历树上的结点，每次的子孙结点的祖先集合合并到其父亲结点中（并查集），之后去查询当前结点是否有询问，有询问且两个点都已经访问过那么这个两个点的LCA是另外那个点的祖先。由于是后序遍历的缘故，当前结点和另外那个结...

题目链接：LeetCode235思路：根据BST的性质可以得到以下逻辑：当root介于p、q之间时，LCA(T, p, q) == root；否则LCA要往p、q所在的区间去搜索。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * ...

题目链接：LeetCode236思路：由于是单次的查询，且是二叉链表的存储方式，所以这里采用O(n)O(n)O(n)的遍历方式维护单词询问，核心逻辑是基于后序遍历的dfsdfsdfs。逻辑如下：当root是p、q其中之一时显然root就是LCA(T, p, q);当root非q且非p时要往左右两边搜索，如果恰好一边一个，那么root是LCA(T, p, q)；否则返回搜到非空结点的那一...

链接：二叉搜索树后序遍历序列合法性判断题目详情：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析：分治，根据value(left)&lt;value(root)&lt;value(right)value(left) &lt; value(root) &lt; ...

出栈序列给定正整数 n，编程计算左边轨道车皮编号依次为 1，2，…，n 时，在右边轨道 最多可 以得到多少个不同的车皮编序方案。 例如当 n=3 时，最多得到 5 组不同的编序方 案如下：123132213231321思路：对于一个栈来进行搜索回溯操作，栈有内容时可以进行入栈和出栈两次操作，否则只入栈。注意回溯还原栈的内容时，应从输出队列中拿上一个回来，而不是只是单纯地移动游标，...

题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路：由于是有序的，我们找个起点开始搜索，注意这个起点一定要能确定一个方向是递减一个是递增的，不然两个决策一样地话就不能搜索了，于是找了右上角作为起点dfs,复杂度O(max(row,col))O...

思路：该二叉树能够还原的充分条件是这两个序列必含有一个中序遍历序列。因为通过中序遍历序列以及之外的任意一个序列能够退出左右子树的规模，然后递归地构建父亲节点。Code:/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *rig...

1013 Battle Over Cities （25 分)It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We ...

题目链接：fzu2107题目大意：给一张N * 4的表，分别有2 * 2的方块1个以及多个1 * 2，2 * 1， 1 * 1的方块，要求将这张表填满，问有几种填法。N < 4解题思路：DFS模拟填表的过程（队友尝试手推…orz 自己其实挺怕这种问填法的，导致连模拟都没尝试写，甚至一度以为是状压DP啥的，傻…）。Code：#include <iostream>#inc...

1004 Counting Leaves （30 分)A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.Input Specification:Each input file contains one ...

前言什么是拓扑排序？一个感性的认识是某个开关触发必要的先行条件。例如：一个串联电路形成回路的先行条件是：1，导线联通；2，每个串联分支上联通。假如划分为多个串联分支上也有一个串联路径（实际上就是一条线上串着许多电元件），则整个串联分支联通就递归到多个子分支。根据上面的描述不难发现这是一个递归的过程，我们应用到图论基于DFS求拓扑排序的思想也类似。综上描述，拓扑排序就是一个图上的遍历序列，序列满...

**思路：**借助后序遍历的思想求解，链式存储递归求解。注意前缀权值在LCA点处扣的次数，如果归在一条路径上要扣一次，否则扣两次。#include <bits/stdc++.h>using namespace std;struct BiTree { int id; BiTree *lson, *rson; BiTree ():lson(NULL),rs...

前言FF算法在某些特例下比较慢，相比于EK算法比较容易实现，不用再去记录前驱路径已经每个点的递归下去的最大流。因为前驱节点回溯回来就可以更新，而后驱子系统的最大流可以通过dfs的值传回来，于是只有记录每个点有没有被搜过就行了。实现#include <bits/stdc++.h>using namespace std;/** * 最大流增广路FF算法*/namesp...

题目链接：leetdcode337思路：先序列化，再树形DP，上一个节点如果选取则下一层节点不会取，否则从下层选和不选选一个最大的传递上来。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; ...

题目链接：leetcode698思路：分支界限法首先k个子集的长度可以预先计算出来,于是可以用个dfs凑这个长度len。数组中的每个元素必然属于某个子集，只要全部的元素都能装到对应每个子集中则必然可以合法地凑出一种合法的k个子集。- 剪枝1,当第一个子集枚举最大的元素不能形成合法序列显然全体都不能凑成合法序列，因为这个最大元素显然不能凑到任何一个子集中2,当前k大的都凑好...

题目链接：leetcode416思路：动态规划背包问题，sum的一半的背包应尽可能地大，由于最优子问题地缘故，它会往sum/2的方向靠，于是跑一下背包最后判断一下这个位置是否能够平分sum。复杂度O(n∗sum)O(n*sum)O(n∗sum)class Solution {public: bool canPartition(vector<int>&...

题目描述问题描述：给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。(1) n∈set(n)；(2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3) 按此规则进行处理，直到不能再添加自然数为止。例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。注意半数集是多重集。实验任务：对于给定的自然...

目录题目描述思路实现题目描述在一个塔座上有一叠大小不等的共n 个圆盘。各圆盘从小到大编号为1，2，……，n。初始时，这些圆盘自下而上散乱地叠在一起。现要求按照以下翻转规则，经若干次翻转，将塔座上的这一叠圆盘排好序，即按自底向上，从大到小的顺序叠置。翻转规则：每次可以将最顶上的若干圆盘翻转，即按其相反的次序叠置。例如，在下面的 3个圆盘叠置状态中，中间状态是在左边状态中第3 个圆...

问题描述：在一个列车调度站中，1 条轨道连接到1 条侧轨处，形成1 个铁路转轨栈，如下图所示。 其中左边轨道为车皮入口，右边轨道为出口，编号为1，2，…，n 的n 个车皮从入口依次进 入转轨栈，由调度室安排车皮进出栈次序，并对车皮按其出栈次序重新编序a1, a2,., an 。思路：生成全排列，检验是否为出栈序列虽然逻辑简单，但复杂度太高O(n!∗n)O(n!*n)O(n!∗n)...

前言根据集合的等价关系（自反，传递，对称），可以利用栈设计一个等价类划分的算法，其中还利用到了类似于邻接表来存储每个成员的等价乙方。题目给n个成员，r组等价关系，输出集合的不同等价类思路并查集如果只是统计不同等价类的数量显然用并查集可以在O(n∗α(k))O(n*α(k))O(n∗α(k))复杂度内完成，但如果是要输出不同等价类，复杂度就会退化到O(n2)O(n^2)O(n2...

题目链接：leetcode199思路：宽搜由于每一层只能有一个结点加入答案集，这种跟层次有关的bfs都可以解决，不过每次还要多维护一个层次的标记，当下一个队头改变了层次，当前的结点就要加入答案集。深搜妙，利用到了先来先得的特型，右子树的优先级最高其次是左子树，当一层有个结点加入答案集该层其余的结点就没机会加入，用向量的长度恰好可以完成这个逻辑。具体看Code。/** *...

前言关于二叉树先、中、后遍历序列给一个中序序列以及其他一个就能够推出另一个序列，而如果单单只有先序与后序序列只能得到某两个结点的父子关系而不能确定一个唯一的二叉树。算法主要流程就是搜索，每次通过先序确定根节点，然后根据中序序列确定两个子树的规模，递归下去。复杂度分析在平均情况：T(n)=2∗T(n/2)+nT(n)=2*T(n/2)+nT(n)=2∗T(n/2)+n得：复杂度：O...

前言这个算法网上讲解有很多，就不在细说，主要是给每个点找一条增广路，核心思路是在发现对面被配对后让之前的配对点腾个位置，腾位置成功的话此时找到一条增广路。要注意的地方是建边的方向和谁配对谁要联系起来，也就是说男生A到女生B连一条有向边后你就要用男生去找女生配对实现HDU2063#include <bits/stdc++.h>using namespace std;#def...

题目链接：排列2解题思路：排序一下，每次从0到3把没有枚举的加进来，关于去重，在里面可以加一个这样的判断，如果在该位置后有一个跟它一样的字符并且该字符被放到我们的结果数组里了，我们当前这个字符就不应该再被考虑，否则就相当于这两个位置调换了一下，重复。这种题还是直接用next_permutation快点。#include &lt;cstdio&gt;#include &lt;cstring&g...

报纸页数X星球日报和我们地球的城市早报是一样的，都是一些单独的纸张叠在一起而已。每张纸印有4版。比如，某张报纸包含的4页是：5,6,11,12，可以确定它应该是最上边的第2张报纸。我们在太空中捡到了一张X星球的报纸，4个页码分别是：1125,1126,1727,1728请你计算这份报纸一共多少页（也就是最大页码,并不是用了几张纸哦）？请填写表示总页数的数字。注意：你提交...

标题：武功秘籍 小明到X山洞探险，捡到一本有破损的武功秘籍（2000多页！当然是伪造的）。他注意到：书的第10页和第11页在同一张纸上，但第11页和第12页不在同一张纸上。 小明只想练习该书的第81页到第92页的武功，又不想带着整本书。请问他至少要撕下多少张纸带走？这是个整数，请通过浏览器提交该数字，不要填写任何多余的内容。#include &amp;amp;lt;bits/stdc...

题目大意：给你n个小树枝，问你能够将其拼成的s根相同长度的大树枝，问这个长度最小为多少？解题思路：排序后dfs，记住一点的是如果第一根树枝不能拼成想要到达的长度的话后面就不用看了，剪枝AC代码如下：#include&lt;algorithm&gt;#include&lt;iostream&gt;#include&lt;stdio.h&gt;#include&lt;stdlib.h&gt;#...

题目大意：52张去除大小鬼的扑克牌，问抽到的牌型有多少种解题思路：做的时候思路还不够清晰，要加油了，第九届蓝桥杯满打满算只剩39天了！本题可以暴力，要写13个循环，太冗长。于是改用爆搜，从这13个牌型每次搜索一个牌型拿的张数，递归出口是把13种牌型选完从52张牌抽出13张的话次数就+1，本来用一个数组标记拿过的牌的和，但是发现不对，有这样一种情况  例如：1 2 3 4 四种牌型各4张，从中选4张...

题目大意：给你n个棒子，看能不能用这些棒子拼成1个正方形。解题思路：深搜，然后注意的地方就是最重要的那个剪枝要考虑清楚，排序好了后当最大的那个搜过了并且不能完成正方形就剪掉，不过我这边用x==1WA了，用i==1却AC了，有点纳闷。（ps：158ms，离大神们的几十ms的写法还有差距。（今天伟大物理学家史蒂芬霍金逝世，默哀。中学那会对物理还是蛮感兴趣的，想想现在越来越菜了，世界少了这样一个伟人还是...

题解：深搜，难点就是判断回到原点的问题，每个城市的下一次旅行地点用一张表保存，走过的城市标记一下，递归出口就是他回到原点的时候。由于要输出路径，用一个数组纪录合法答案，并搜索的时候更新它。字典序的问题就把每个城市下一次走的地点排下序就行。AC代码如下：#includeusing namespace std;int city[21][3],book[21],answer[22],n,k;

题目大意：给你一张图，图上的值表示下一次的步数（必定要走这么多步，不是1..k），问从左上角到右下角有多少条路解题思路：这题类似于HDU1078http://blog.csdn.net/calculate23/article/details/79095287，也是用dp保存当前到终点的最大值，然后dfs就搜沿一个方向的路径数的最大值，两个方向相加就是改点的最大值。如果你走到一个已经优化过的结点，他

题目大意：输入一段数字，在这段数字中任意添加加号，减号，使其能够等于结果思路：直觉上直接想到枚举尝试（类似于算24分，只不过牌变多了，运算规则变简单了），但是用过的牌（数字）不能重复使用，于是就可以用深搜解题。搜的范围大概是：得到一个数字，1.该数字加到sum中 2.该数字和sum作差 3.该数字啥都不做进入下一个搜索（不做的话要把他成为数字的尾部）附代码：#include#

题目大意：给你一个目标值和一段数字串，你要把这个串进行分割求和，让结果趋近于目标值并且不大于他思路：搜索，每次一个x代表你要分割串的头位置，即最高位，sum代表在x位置之前分割求和的结果，k代表最优答案的位数小结：一开始是想用一个栈保存最优答案的值，但是直接在每次搜的时候就改变这个栈了，结果最优答案可能被更替，导致一晚上没能解决这个问题，忘了还可以用一个中间数组进行存值，等到要改变最优值时

题目大意：给你一个结果和n个数，你要找到这n个数能使得和为结果的序列输出出来，并且序列不重复解题思路：这是一道DFS+路径的题，因为题目的序列为不上升，你就只需要判断相邻的会不会重复就行，即每次用一个变量存序列中len位置的上一个值，如果该位置往下找的数会和上一次的数一样就筛掉。（因为一开始没注意是不上升序列  还在想如果遇到像10 14 5 5 1 1 1 1 1 5 5 1 1 1 1

题目大意：在图上放置炮台，并且炮台之间不能相互威胁（即两个炮台不能中间无阻碍地放置在同行或同列），个人感觉有点像N皇后的问题，只不过进阶的东西就是多了墙解题思路：做这题时想起了当时做N皇后的解法，只不过多了一步遇到墙壁就停止，不过发现在你不放在这个位置时，准备回溯你要把之前标记的行和列全部清空，问题就来了，如果你在清空标记时遇到有一格同时被两个炮台标记怎么办，这时就换种思路，即你每当要放炮台时

直接上15ms代码，还没想好记忆化怎么弄  应该还能更快一点AC代码如下：#include#include#include#includeusing namespace std;char s[2000],sr[2000];int res,book[20],n,flag;int cmp(char a,char b){ return a>b;}void dfs(in