题意思路：将这n个单词按照以下方式合并： 1.从左往右合并单词，将合并后的单词作为第一个单词再与后面单词合并 2.如果最左边单词结尾字母与其后面一个的单词的开始字母相同，则最左边单词的结尾字母与之后一个单词的开始字母都会抵消掉而消失，重复上述操作直到某一个单词为空或者最左端的结尾字母与之后单词的开始字母不同。例如 与合并之后会得到方法一：双指针模拟指针从第一个单词的右边结尾字母开始， 指针从第二个单词的左边开始字母开始 如果相同则， 直到i与j指向的字符不同则合并第一个字母从开头到i的部分和第二个字母从j到结尾的部分 复杂度分析 时间复杂度：O()，为字符的长度； 空间复杂度：O()，不需要...

题意思路： 给定一个double类型的数组arr，其中的元素可正可负可0，返回子数组累乘的最大乘积。 方法一:暴力枚举 每次选取当前元素的所有子数组判断得到的最大值 复杂度分析 时间复杂度：O()，表示数组的长度。 空间复杂度：O()。除了几个临时变量外，没有额外的空间。 class Solution { public: double maxProduct(vector<double> arr) { double ans=arr[0]; for(int i=0;i<arr.size();i++){//循环每个元素 ...

题意思路：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。 方法一:暴力枚举每次选择枚举滑动窗口的起点，向后枚举个数字得到窗口中的最大值 复杂度分析 时间复杂度：O()，表示数组的数量，为滑动窗口大小 空间复杂度：O()，存储结果的必要数组不算开辟额外空间 class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { int maxNUM=0; vector<int> ...

题意思路：给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 方法一:中序递归遍历二叉树中序递归就是二叉搜索树的第个结点； 若二叉树为空则结束返回，否则： （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 通过搜索顺序寻找第个结点 复杂度分析 时间复杂度：O()，表示二叉树结点数...

题意思路：从上到下按层打印二叉树，同一层结点从左至右输出,每一层输出一行。也就是对二叉树做一遍层次遍历 方法一:使用队列模拟二叉树的层次遍历 二叉树的层次遍历 ，顾名思义就是指从二叉树的第一层（根结点）开始， 从上至下逐层遍历，在同一层中，则按照从左到右的顺序对结点逐个访问。 1)先将根结点加入队列，然后将当前队列中的所有结点遍历，这时队列中的所有结点都是同一层，将遍历结果加入答案，将遍历后结点加入队列。 2）然后不断枚举每个结点的子树，直至完成逐层的层次遍历。 复杂度分析 时间复杂度：O()，表示二叉树结点数量，层次遍历所有结点。 空间复杂度：O()，队列存放每一层结点答案 图文详解： ...

题意思路：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 方法一 ：数学 枚举 丑数是只包含质因子2、3和5的数，可以从小到大枚举满足条件的数 先将满足条件的最小的数加入数组存储 直到第N个数。 图解： 复杂度分析 时间复杂度：O(N)，N为第N个数，遍历枚举； 空间复杂度：O(N)，存储与读取数据。 代码： class Solution { public: int GetUglyNumber_Solution(int index) { ...

题意思路： 输入一个链表，反转链表后，输出新链表的表头。 方法一：调整链表指针，反转链表 pre指针指向已经反转好的链表的最后一个节点，初始化为null； cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向头指针； next指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存 图解： 复杂度分析 时间复杂度：O(N)，N链表的长度，遍历链表； 空间复杂度：O(1)，未开辟新空间. /* struct ListNode { int val; struct ListNode *next; ListNo...

题意思路：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 方法一:暴力枚举 遍历一遍数组顺序，使数组中奇数分为一类，偶数分为一类，最后将奇数位于偶数前面 复杂度分析 时间复杂度：O(N)，N数组的长度，遍历数组； 空间复杂度：O(N)，数组存储与读取数据。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arra...

题意思路： 输入:["PSH1","PSH2","POP","POP"]返回:1,2解析:"PSH1":代表将1插入队列尾部"PSH2":代表将2插入队列尾部"POP“:代表删除一个元素，先进先出=>返回1"POP“:代表删除一个元素，先进先出=>返回2 方法一:栈实现队列 push操作就直接往stack1中添加， pop操作需要分为两步： 如果stack2为空，那么需要将stack1中的数据转移到stack2中， 利用栈的先进后出的性质，通过...

题意思路：一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 方法一：hash 将数组中所有元素遍历并映射到hash中统计数量，可以使用map保存数字和出现次数。 如果出现次数超过一次则删除数字 最后统计数组中只出现一次的两个数字。 复杂度分析 时间复杂度：O(NlogN)，N数组的长度，遍历数组，map插入删除时间复杂度为logN； 空间复杂度：O(N)，数组存储与读取数据。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * ...

题意思路：统计一个数字在升序数组中出现的次数。 方法一:暴力枚举题意很简单，寻找一个数字的出现次数，一个朴素的想法就是暴力一边数组中这个数字的出现次数 复杂度分析 时间复杂度：O(N)，N数组的长度，遍历数组； 空间复杂度：O(1)，未开辟新空间. class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int res=0; for(int i:data){//遍历数组 if(i==k)res++;//统计k的出现次数 } ...

题意思路：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000 方法一:排序寻找中位值题目保证给定数组总是存在多数元素，所有可以将数组排序后，此时数组中出现次数超过一半的数字一定是已排序数组的中位数。 图解： 复杂度分析 时间复杂度：O(NlogN)，N数组的长度，遍历数组，排序NlogN； 空间复杂度：O(1)，未开辟新空间。 代码： class Solut...

题意思路：操作给定的二叉树，将其变换为源二叉树的镜像。也就是将二叉树的每个节点的左子树换成右子树，右子树换成左子树 方法一:递归处理先处理当前root的左右节点，使当前节点的左子树与右子树交换，达到镜像目的， 然后再递归处理左子树和右子树即可。 特例当pRoot为空时，直接返回pRoot。复杂度分析 时间复杂度：O(N)，N为树的节点数目，遍历数组； 空间复杂度：O(N)，数组存储与读取数据。 图解： /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *rig...

题意思路： 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 方法一:暴力枚举通过遍历数组求出最小的元素 复杂度分析 时间复杂度：O(N)，N数组的长度，遍历数组； 空间复杂度：O(1)，未开辟新空间 代码： class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int res=INT_MAX; for...