思路： 题目的主要信息：  数组有n个无序数字，其中有一个数字只出现了1次，其他数字都出现了k次 需要找到只出现了一次的数字 k>1，k无特殊情况，只需要考虑空数组  方法一：排序法具体做法：首先对数字进行排序，使之呈现递增的状态，这样相同的数字必然相邻。因为其他数字至少出现大于1次，因此首尾如果与旁边不同则刚好是首尾，如果是在中间则需要比较是否与前后都不同才行，如此遍历一次即可。 class Solution { public: int foundOnceNumber(vector<int>& arr, int k) { if(arr.size() == 0) re...

思路： 题目的主要信息：  求n对括号的全部合法组合，左右括号之间任意组合，只要合法就行 需要输出所有的结果  方法一：暴力构造+栈验证具体做法：首先构造一个"(((((((......))))))"形式的字符串，然后调用STL的next_permutation函数遍历其每一个排列组合，并验证其是否合法，如果合法则可以加入返回的vector中。验证合法时，使用辅助栈，遇到左括号则入栈，遇到右括号则弹出一个栈中内容，若是栈为空的时候遇到了右括号，则没有左括号来匹配，即非法。 class Solution { public: bool isValid(string str){ ...

思路： 平衡二叉树的性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。则可以相当将问题不断分成子问题，使用递归。 方法一：自顶向下考察具体做法：写两个函数，一个递归遍历二叉树所有结点，判断该结点下的子树是否为平衡二叉树，另一个函数则递归计算该结点深度。图中为判断函数的递归图，其中计算深度函数递归也是如此。  public class Solution { public boolean IsBalanced_Solution(Tr...

思路： 题目的主要信息：  对于一个给定无序数组，返回最小的k个元素 k和数组有特殊情况需要单独讨论，且数组最大10000  方法一：堆排序具体做法：使用Java自带的PriorityQueue模拟一个大顶堆，堆的大小限定在最大k：遍历数组，前k个元素直接入堆，后续元素如果比堆顶元素大，则弹出堆顶，再入堆。最后将所有堆中的元素加入到ArrayList即可返回。  import java.util.ArrayList; import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbe...

思路： 题目的主要信息：  将二叉树镜像，即将其所有左右子树交换  我们可以考虑自底向上依次交换二叉树的左右结点。 方法一：递归具体做法：采用递归的方法，首先深入到二叉树的叶子结点，交换其左右，然后依次往上交换。 class Solution { public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == NULL) //空树返回 return NULL; TreeNode* left = Mirror(pRoot->left); //先递归子树 TreeNode* right = Mirror(pRoot->right); p...

思路： 题目的主要信息：  给定两棵二叉树树的层次遍历序列 判断二叉树B是否为A树的子树 约定空树不是任意一个树的子结构  方法一：两层先序遍历具体做法：对A树的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是A树与B树同步先序遍历，遍历完一个B树或者有不相等的结点为止。  class Solution { public: bool function(TreeNode* root1, TreeNode* root2){ if(root1 == NULL && root2 != NULL) //当一个结点存在另一个不存在时 return ...

思路： 题目的主要信息：  对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数（与斐波那契数列不一样） n为正整数，求青蛙跳上n级台阶的方案数  方法一：暴力解法 具体做法： 对于n个阶梯，如果青蛙第一次选择跳1阶，那么它有还剩下n-1阶，如果选择跳2阶，那么它还剩下n-2阶以此类推，后面剩下的都是子问题，则数学化公式即为： f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n) 我们可以用一个辅助数组...

思路： 题目的主要信息：  斐波那契数列每项的公式为:，从0开始，， 求出斐波那契数列的第n项 n最大不超过39，结果不会超出int的范围，不用考虑long long  方法一：递归具体做法：根据公式，每次返回，结束递归的点就是1或者0 class Solution { public: int Fibonacci(int n) { if (n <= 1) //从0开始，第0项是0，第一项是1 return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); //根据公式递归调用函数 return 0; } };复杂度分析：  时间复杂度...

题目的主要信息：  矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复 找到矩阵中有没有给定元素即可  方法一：暴力法 具体做法： 从上到下每行，每行中从左至右遍历二维数组，依次查找。 class Solution { public: bool Find(int target, vector<vector<int> > array) { if(array.size() == 0) //优先判断特殊 return false; int n = array.size(); if(array[0].size() == 0) return fal...

思路： 题目的主要信息：  找到两个数a与b的最大公约数 a与b最小为1，无特殊情况  最常规的求公因数，以下罗列几种方法。方法一：穷举法具体做法：优先考虑a与b一个是另一个因子的情况，可以直接返回。然后找到较小值，由小到大穷举2到较小值的所有数字，遇到公约数更新答案。 class Solution { public: int gcd(int a, int b) { if(a % b == 0) //当一个数是另一个数因数时 return b; if(b % a == 0) return a; int n = a > b ? b : a; //等于较小值 int res = 1; for...

思路： 题目的主要信息：  一棵树树的结点数为n 其中序遍历递增  但是题中并没有提到结点中的数据如何，只要数据任意组合的话，任何二叉树都可以有一个中序递增序列，因此这道题就化为结点数为n的二叉树有多少种，这就变成了算法中的卡特兰数（Catalan数）的问题：  如果没有结点，只有空树一种形态，则 如果一个结点，也只有一种形态， 如果两个结点，共有两种形态， 如果三个结点，共有五种形态， 一般地，如果n个结点，我们有  这就是卡特兰数。 方法一：动态规划累加法具体做法：我们可以用dp数组记录从1到n的，两层循环依次算到.其中python版本因为涉及大整数运算，会超时。Python版本（超时） ...

思路： 题目的主要信息：  在文本串T中找到模板串S出现的次数 S不为空 要求时间空间最多为  方法一：暴力法（不会超时，但不符合要求）具体做法：遍历文本串，每次截取下标后m个与文本串比较，如果相同则答案加一。需要注意后面要留出m位防止访问越界。 class Solution { public: int kmp(string S, string T) { int n = T.length(); int m = S.length(); int res = 0; for(int i = 0; i <= n - m; i++){ //遍历文本串 if(T.substr(i, m) == S) ...

思路： 题目的主要信息：  n长度的数组，每个元素表示从该数下标位置最多可往后跳跃多少个 从1开始，无0的情况  方法一：动态规划（可能会超时）题目要求的是找出从1跳到n最快的路径，即所需步数最短，我们可以想到遍历所有的路径，从中找出步数最短的路径。具体做法：我们可以用dp[i]表示第i个元素到最后一个元素所需要的步数(下标从1开始），起点是n-1到n需要步数为1，依次自顶向下计算：对于第i个元素，如果（数组下标从0开始），则可以一步到位；否则我们遍历i之后的元素，找到最小到n的步数，即（j为往后遍历的数量），并使之加1。（该方法经多次测试，有超时的风险，可能超时，可能不超时） class S...

思路： 题目的主要信息：  n个活动，有各自的区间 一个主持人不能在相交的区间工作 将相交的区间分成一组，最后组数即是主持人的数量 数字为int型的范围，可能会出现负数  方法一：排序+遍历比较具体做法：利用辅助数组单独各个活动开始的时间和结束时间，然后分别进行排序。遍历个活动，如果某个活动开始的时间大于之前活动结束的时候，当前主持人就够了，活动结束时间往后一位，若是出现之前活动结束时间晚于当前活动开始时间的，需要增加主持人。 class Solution { public: int minmumNumberOfHost(int n, vector<vector<int> &...