小胡同的诗

注：转自栈的面试题—对栈进行升序排列题目描述请编写一个程序，按升序对栈进行排序，要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。vector数组numbers中的第一个元素就是栈顶元素，升序排列，即栈顶元素最大解题思路看到这个题，因为可以申请一个栈用来存放临时数据，所以我们可以这样想：由于栈先进后出的特性，先将原来栈中的数据存放到临时数据栈中，并且保证临时栈中的数据是降序排列的，这一过程完成之后，再将临时数据栈中的元素依次push到返回栈中即可。具体实现步骤：（

题目链接：hdu4763题面题目大意找到字符串中的最长公共前后缀，并且这个前后缀的字串在除了前后缀的中间部分也要存在这个子串。例如：EAEBE，其中，E 表示这个子串，输出 E 的最大长度，如果不存在输出 0 。解题思路KMP利用求失配函数得到串的最长公共前后缀，然后从 2i 的位置到 len-i 的位置开始枚举中间是否存在子串，判断条件是： fail[j]==ifail[j]==ifail[j]==i。含义是失配指针能够索引到公共前缀后一个位置，然后从 j 位置到达 i 表示 0 - j

题目链接：leetcode138题面题目大意构造一个和原链表一模一样的链表，包括 random 指针。注意的是，操作结束后，原链表的结构不能被破坏。解题思路map根据结构，我们可以先构造出和原链表一模一样的链表，并使每个节点一一对应，这边可以使用一个 map 。然后遍历原链表的所有节点，对于原链表的random 指针我们可以根据查询 map 的内容进行相应的 random 指针修改。时间复杂度 O(nlogn)O(nlogn)O(nlogn)，空间复杂度 O(n)O(n)O(n)。把

题目链接：leetcode96题面题目大意求 n 个数字构成的二叉搜索树的种类数量解题思路与本题等价的题目有：凸多边形划分三角形的数量、一串数字通过栈构成的出栈序列数量、2n 长度的 01 串的种类（限制是前缀 1 的数量不少于 0 ）等，最终其实可以归结于 Catalan 数的计数问题。以下主要介绍两种动态规划思想的递推，为了方便讲解，问题不妨假设转化为数字的进栈出栈问题：递推我们考虑，对于一串规模为 n 的数字，对于状态 f[i]f[i]f[i] 表示把第 iii 个数字为开头的出栈

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

题目链接：leetcode747题目大意解题思路问题中有说一定存在最大值，意思是这个最大值是唯一的。确定了问题主要是寻找最大值和次大值就可以愉快地解决了，主要思路有如下两种：线性扫描直接 for 一遍即可，如果只是考虑比较的次数，最差会达到 2∗n−22*n-22∗n−2时间复杂度 O(n)O(n)O(n)，空间复杂度 O(n)O(n)O(n)锦标赛树这个树是树形选择排序的前置技能，也是堆排序的弱化版，因为空间复杂度较高，但优点是能够减少比较次数。对于本题，仅仅只要寻找最大值和次大值，构造

题目链接：leetcode94题目大意给定一个二叉树，返回它的中序 遍历。非递归实现解题思路栈+模拟大致的思路就是不断往左子树切换，直到左边为空后把当前的节点输出，然后转到右子树。如果右子树为空说明需要回溯，弹栈即可。代码实现/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; *

题目链接：leetcode86题目大意给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例:输入: head = 1->4->3->2->5->2, x = 3输出: 1->2->2->4->3->5相对位置不变相当于稳定地区分，比如两个相等的数原本的位置划分后不能更改这个相对位置，不同的数更是如此。解题思路双指针可以维护两个链

题目链接：leetcode82题目大意给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。示例一：输入: 1->2->3->3->4->4->5输出: 1->2->5示例二：输入: 1->1->1->2->3输出: 2->3简而言之就是删掉原始序列中，所有出现次数大于1的元素。解题思路直接删除AC 的代码就是这个方法，但逻辑可能略显冗余。先建一个头节点使链表变成带头

题目链接：leetcode63题目大意给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。示例1：输入:[[1,1,1],[1,0,1],[1,1,1]]输出:[[1,0,1],[0,0,0],[1,0,1]]示例2：输入:[[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]解题思路1. 暴力模拟遍历 m*n 个点

题目链接：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"解题思路数学

题目链接：leetcode31题目大意实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1解题思路next_permutation利用『algorithm』包下的 API ，当返回为false时说明完全逆序，反转

题目链接：fzu2306解题思路：每个小的最好能依赖于比他大的而自己形成一队，而由于队列的关系，那个大的此时也依赖于下一个，于是最好的排列一定是一大一小交叉的，双指针可以有效地实现这个逻辑。Code：#include <cstdio>#include <algorithm>using namespace std;const int maxn = (int)...

上来拿个1<<10勋章…题目链接：woj107DescriptionConsider a 3 by 3 arrangement of the digits 1 to 9, as illustrated in the following diagram:1 3 58 7 64 9 2Figure 1The arrangement can by modified by ...

题目链接：fjut3097题目大意：RT，大致就是给你n长度的数字序列，以及q组含左右端点的区间查询，问区间内的数字种类解题思路：我们利用C数组表示从1~i的区间的数字的种类数，这样就可以通过getsum(right) - getsum(left-1)求得区间[left,right]的情况。但问题就转化成如何维护这个C数组，这里我们发现，但凡某个数字在k位置之前还发现有一个跟它一样(假设这个位...

链接：https://leetcode-cn.com/problems/3sum题目详情：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：...

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

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

思路：预处理一下点的顺序，然后询问的时候从Tag左边右边分别找k个点，只后双指针扫一遍就能得到最近的k个序列#include <bits/stdc++.h>using namespace std;struct node{ #define MAXN 1005 int pos; int id; bool operator < (const n...

题目链接：51Nod思路：处理回文的东西许多时候要考虑反转一下与原串相比。对于本题，发现一个结论：原串与逆序串的LCS扣除后剩下的串长度恰好是我们要构造对称的最少长度，因为这样找LCS相当于回文串中找后面的一个匹配，当然LCS是不连续的，而回文要求连续，这样扣除一下恰好会是一个连续的结果。#include <bits/stdc++.h>using namespace std;...

题目链接：Leetcode493思路：同求逆序数一样的更新查询，关键在于离散化部分，我们要得到原序列与2倍序列所对应的位置，并且为了最后能够常数时间查到原序列对应位置的2倍序列的数值的位置，用个哈希函数id%nid\%nid%n表示同位置的对应的位置，设一个rnk1表示原序列位置，rnk2表示2倍序列的位置，题就解决了。关于离散化那个用二分处理的可能不好操作，用结构体排序会快点Code：c...

题目：之前介绍过在一个数组上的三数和问题，根据排序后的单调性，我们可以利用双指针来寻找到三个数和为k的三元组，对于四元组实际上多一维进行枚举（四数和问题），这里还有个hash表的解法。那么，回归三数和问题，如果三个数分别处在三个数组中呢？所求的三元组要处于三个数组。思路：我们同样用双指针的思路：首先我们要对三个数组排序接着枚举A数组构造k=answer−A[s]k=answer-A[s]k...

题目链接：Leetcode32思路：动态规划，复杂度O(n)O(n)O(n)注意状态要设计成以i位置为结尾的最长合法长度而不能只单单设计前i个字符的最长合法串，否则转移方程很难得到，状态转移时注意前不要越界，特别是第三个caseclass Solution {public: int longestValidParentheses(string s) { //...

题目链接：Leetcode198Code：class Solution {public: int rob(vector<int>& nums) { //dp[i]表示偷盗到第i家获得的最大收益 if (nums.size() == 0) return 0; if (nums.size() == 1) return ...

题目链接：Leetcode56思路：贪心，先按左端点排序并且在左端点相同的情况下右端点靠近左边的排前面，然后用双指针访问所有区间，当左端点大于前面的右端点说明两个区间互斥了，要把之前的并区间推入答案集中，由于是按左端点为第一关键字的排序，所以后面的只要更新右端点就够了。最后可能会没有更新，所以人为地加一个最大地区间保证这个区间之前地全部更新。这题实际上是让你求区间的并集，如果求交集呢？见Lee...

题目链接：Leetcode986思路：贪心，由于排好序了，直接双指针扫，思路和归并排序合并比较类似，注意往后移动的条件是尾部，因为一个矩形的结束条件是尾部比完了，不能写成是头部class Solution {public: vector<vector<int>> intervalIntersection(vector<vector<int>...

问题描述：给你n个闭区间，输出这n个开区间的所有交区间，可能存在一个子区间有多次重复，一个交区间的定义是至少有两个大区间都包含它，并且答案集中要尽可能地把所有区间合并。注：为了避免歧义，头对尾交于一个点则不算交。思路：这是对于力扣986地一个拓展，如果问题约束到一个交区间最多只有两个大区间包含它，那么就可以先把区间预处理成像力扣986那样的两个递增区间，用双指针求交集。对于这个问题我们也是要...

目录题目思路个人思路书中给的解法笔记实现效果展示总结题目思路个人思路暴力分类O(m2)O(m^2)O(m2)的复杂度进行分类，O(n)O(n)O(n)的复杂度进行比较，总复杂度O(m2n)O(m^2n)O(m2n)广义表结构体：struct node { int sz; //以当前结点的前驱结点为前缀的向量个数 linklist *head; //存相同前缀的...

题目描述09年统考的源题，虽然都能得到**O(n)**的复杂度，不过满分做法是双指针，也就是指针扫一遍，其余做法均10分。输入一个链表，输出该链表中倒数第k个结点。思路：比较直观的想法是辅助空间或者是借助栈、递归等方式实现，不过正解还是双指针，发现408很喜欢靠双指针的思想，用来优化线性复杂度。做法如下：指针1顺序扫到正数第k个节点，从这时候开始指针2跟着指针1往后扫，当指针1到达尾部时，...

题目详情：输入两个链表，找出它们的第一个公共结点。思路：1，由于从公共节点开始之后都是公共节点，也就是说不管两个链的长度是否一样，反过来的公共长度一定一样，于是用两个栈来从后往前匹配，找到最后一个公共节点即为原链的第一个公共节点。2，和思路一很类似，先让两个开始匹配的指针水平线相同，也就是长的那个要走到与短的那个链有相同长度的位置，之后就从前往后匹配。之所以这样子做是因为：假设k为公共长度...

链接：和为S的连续序列题目详情：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!分析：很容易...

模拟栈操作入栈前进行判断，空间复杂度大了O(n)class Solution {public: bool isPopOrder(vector&lt;int&gt; pushV,vector&lt;int&gt; popV) { if (pushV.size() != popV.size()) { return false; ...

搜索仍是重点，不过没上一届那么多了。基础的模运算和细节处理标题： 购物单 小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。 这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。 小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。 现在小明很心烦，请你帮他计算一下，...

题目链接：Magic Odd Square题目大意：给你一个奇数N，构造一个n∗nn*nn∗n的矩阵并填上1−N∗N1 - N*N1−N∗N这些数字，使得每一行，每一列，主对角线，副对角线和都是奇数。思路罗伯特法构造奇数阶幻方因为N为奇数，设N=2∗k+1(k为自然数)，其幻和为N∗(N2+1)/2，即：(2∗k+1)∗(2∗k2+2k+1)。显然，奇数∗奇数=奇数设N=2*k+1(k为...

题目链接：hihocoder1349题目大意：有一段由全体自然数组成的字符串 “0123456789101112…”，查询下标为N的字符。解题思路：思维题，先将自然数按数位分组:{0 - 9} ; {10 - 99} ; {100 - 999} …发现每组的长度分别为 10 x 1, 90 x 2, 900 x 3 … 然后查找出N属于的组数。接着考虑它是改组数字的第几个数字，然后考虑是这个...

题目链接：hdu3333题目大意：给一段n长度的数字序列，以及q长度的区间询问，问区间不同数字大小之和。解题思路：跟区间数种类这题类似只不过种类数改成不同种类数字之和。树状数组改成维护不同种类数字之和。注意数字之和会爆int，C数组设置成long longAC代码：#include &lt;cstdio&gt;#include &lt;cstring&gt;#include &lt;...

　　题意：若数组中一个数前的所有数都比这个数小，那么定义它为一个record。若去掉某一个元素使剩下的数组中record最多，求这个元素　　分析：对每个元素，考虑去掉它的情况。若第i个元素前有i-1个小于它的元素，则去掉该元素后这个数组前i个元素的record总数-1.若第i个元素前有i-2个小于它的元素，那么去掉前i个元素中大于第i个元素的那个元素后，前i个元素的record总数+1.若第i个...

题目链接：hdu4546题目大意：给n长度的数字序列，从中取出k个元素(0&lt;k&lt;=n)求和，找出k个元素之和为第m小的和值。解题思路：第一次做这样组合的题，第一直觉会想用爆搜穷举出所有组合，然后扔进multiset中维护这些值，搜索的复杂度是指数级，内存也超限。发现找到第m个小的可以直接用优先队列来模拟，因为m&lt;10000，所以可以模拟到第m大就结束(其实用multiset也...

前言线性代数中对于一段数字序列的排列情况有这样一个定义：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素...

问题： 对于一个任意的自然数，问是否能将其拆分成2个或2个以上的连续自然数之和，写出所有的等式。解题思路： 第一种解法是推导出数学公式，因为连续的自然数可以用等差数列Sn求和公式，判断可行性。公式推导以及证明过程:数学解法；第二种解法是直接穷举解法，不过对于较大的数字复杂度O(n^2)可能不够解决，由于连续的自然数一定是递增状态，我们可以用尺取法，也就是双指针法将复杂度降低到O(n)双指针解...