题目主要信息:  给定一组可能有重复数字的数组，输出该数组的全部排列 输出结果按照字典序升序排列  具体思路: 这道题类似没有重复项数字的全排列，但是因为交换位置可能会出现重复交换的情况，出现的结果需要去重，因此不便于使用交换位置的方法，我们就使用临时变量去组装一个排列的情况：每当我们选取一个数组元素以后，就确定了其位置，相当于对数组中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。  终止条件： 临时数组中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。 返回值： 每一层给上一层返回的就是本层级在临时数组中添加的元素，递归到末尾的...

题目主要信息:  给定一个数组，求这组数字的全排列 数组无重复元素 以数字在数组中的位置靠前为优先级，按字典序排列输出  具体思路: 全排列就是对数组元素交换位置，使每一种排列都可能出现。因为题目要求按照字典序排列输出，那毫无疑问第一个排列就是数组的升序排列，它的字典序最小，后续每个元素与它后面的元素交换一次位置就是一种排列情况，但是如果要保持原来的位置不变，那就不应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变，不会漏情况。如下图所示：  如何保证每个元素能和从自己开始后的每个元素都交换位置，这种时候我们可以考虑递归。为什么可以使用递归？我们可以看数组[1,2,3,4],如...

题目的主要信息：  给定一个只包含正整数的数组，从中取出若干个数，使取出的数之和与剩余数字之和相等  方法一：递归及优化 具体做法： 我们可以求得数组的累加和sum，即只要从数组中选出一个子集的元素，元素之和为sum的一半，那剩余的元素之和就是另一半，则题目就变成了从数组中选择若干个数使其和为目标值。 我们可以考虑递归选择，每次对于当前元素，可以选择加入子集或是不加入，相应修改距离目标值剩余的值，进入子问题（即后续数组中寻找和为目标剩余值），直到数组结尾或是找到或找不到。 很遗憾，这种方法超时了。 class Solution { public: bool recur(vector<in...

题目的主要信息：  给定一个无序数组，找出其中最短的子数组，将这个子数组排序后，整个数组都是升序数组 返回该子数组的长度  方法一：排序比较法 具体做法： 既然要满足将子数组排序后整个数组都是升序数组，我们可以拷贝一份数组进行排序，这样我们就有一份原数组和一份排序后的数组。分别从首尾开始往中间找，分别找到第一个不同的元素，将这之间的子数组排序就是完整的升序数组了，因为两边都一样。因此这个区间的长度就是我们要找的子数组的长度。 class Solution { public: int findUnsortedSubarray(vector<int>& nums) { vect...

题目的主要信息：  给定一个非负整数数组，数组中每个元素值表示可以往后续跳跃的最大步数，即到达某个元素值时可以往后跳跃1到该值之间任意步数 需要从数组第一个元素跳到数组最后一个元素，其中每经过一个元素，该元素的值作为积分，求最大积分值 如果数组为空或者到达不了末尾返回-1  方法一：动态规划 具体做法： 可以使用动态规划，创建一个数组，其中dp[i]表示到达下标为i的末尾元素能够达到的最大积分，全部初始化为-1.很明显，dp数组边界值第一个元素就是原数组的第一个元素值。 后续遍历数组，补全dp数组。在遍历过程中，到达某个元素，可以遍历它要跳跃的1～nums[i]步幅，即它后续的dp值都可以被更...

题目的主要信息：  给定一个逆波兰表达式，求表达式的值 给定的表达式以字符串数组给出，字符串只含有数组和加减乘除四个符号 除法进行整型运算  方法一：栈 具体做法： 逆波兰表达式可以看成一种后序表达式，只需要在遇到符号的时候计算它前面两个数字即可，因此可以使用栈的先进后出原理。 遍历整个字符串数组，遇到数字就将其从字符串转变成int数字，然后加入栈中等待计算。遇到符号先取出栈中最后一位，然后与取出后的最后一位计算，结果存入最后一位，如下图所示：  class Solution { public: int evalRPN(vector<string>& tokens) { s...

题目的主要信息：  一串只由ATCG字母组成的字符串，求其中出现次数超过1的长度为10的片段 输出顺序需要按照在原始字符串中第一次的出现顺序  方法一：暴力查找 具体做法： 字符串的find函数，查找出子串在原串中是否出现，如果查找到了返回的就是该子串第一次出现的位置。因此我们可以遍历字符串所有长度为10的子串，然后在原串中查找它出现的位置，如果它出现的位置不是现有子串的位置，说明前面出现过了，这个子串就是出现次数超过1的，我们可以记录输出它。 但是，又要面临一个去重和输出顺序的问题，因此可以使用容器map，key值记录第一次出现的下标，map就会按照下标排序，同时如果相同下标出现还会自动去重...

题目的主要信息：  一个整数数组，除了一个元素只出现了一次，其他元素都出现了两次 需要找出这个只出现一次的数组  方法一：哈希表 具体做法： 我们可以使用哈希表记录数组元素出现的次数，利用其快速访问特点快速去重。哈希表key值记录遇到的数组元素，第一次遇到次数计为1，后续如果再在哈希表中找到这个数字说明第二次遇到，则可以去除哈希表这个key值。 遍历结束后，如果哈希表不为空，说明找到了这个出现次数为1的数字，因为出现次数为2的都被去掉了，哈希表唯一一个元素就是。  class Solution { public: int singleNumber(vector<int>& ...

数组题目介绍 数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍数组与其他数据结构结合的问题。 问题类型与技巧   数组与哈希表的问题 最常见的数组与哈希表结合就是使用哈希表统计数组元素出现的频率，或者去重等任务，一般来说直接使用一个哈希表可以解决。   数组与二叉树的问题 二叉树遍历的结果需要存储在数组中，有时候需要在二叉树中查找的结果也会存储在数组中，也能根据数组还原构建二叉树，此时更多遵循二叉树的遍历规则。   数组与栈或队列的问题 有时候涉及先进先出或者先进...

数组题目介绍 数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍数组与各类算法结合的问题B篇。 问题类型与技巧   数组与贪心算法的问题 贪心算法的宗旨在于每次每次都能到达最大或者最小，即在数组中找到某个公式的最值，让我们能很快解决这个问题。   数组与动态规划的问题 动态规划最常与数组问题结合，其中最重要的就是找到状态变化的状态转移方程，以及初始条件，一般来说都会创建额外的辅助空间，然后根据初始条件和状态转移方程计算填满辅助数组。   经典题型   题目①买卖股票...

数组题目介绍 数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍数组与各类算法结合的问题A篇。 问题类型与技巧   数组与递归的问题 常规的数组遍历肯定用不上递归，但是如果需要在数组中查找几个特定的元素，一般会用到递归。递归一般从数组开头作为入口，查找到某个元素，将该元素后续的子数组送入子问题中继续查找某个元素，直到找全符合条件的元素或者到达数组尾才结束递归。这其中还可能会涉及回溯与枝剪等算法。   数组与双指针的问题 数组中一般不直接出现指针，我们将使用两个下标称...

数组题目介绍 数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍数组与排序结合的问题。 问题类型与技巧   直接对数组排序 这类题目可能是题目本身要求就是要对数组进行排序，也有可能是需要经过排序在有序数组上才能解决问题。一般排序可以选择sort函数（可能需要重载比较），也可以自己写其他排序方法。   利用各类排序思想解决数组问题 这类题目主要是利用快排、归并排序等排序方法的思想，来使数组有序，或者获取与次序有关的信息。一般归并排序思想出现于有两个数组的情况。   经...

数组题目介绍 数组是最基本的数据结构，题目设计范围广泛，可以是操作原数组、查找、排序等，也可以和贪心算法、动态规划、递归、二分法等算法结合，还可以和哈希表、二叉树等数据结构结合。本篇总结主要介绍直接在数组上操作的题目。 问题类型与技巧   数组的变型操作：可以是数组元素中的旋转、交换、移动。 这类题型比较多，最重要的方法是找规律，不管是一维数组还是二维数组，观察变化后的数组与原数组的差异，思考如何最方便的变换。常用的技巧可能有：翻转使用双指针交换、旋转可能会用到多次翻转、矩阵可能与转置有关、另外开辟一个数组空间来存储中间值或者结果值等。   根据数组的下标，构造原地哈希。 如果数组中的元素与下...

题目主要信息:  给出一个数组表示连续多日的股票价格 你可以选择在某一天买入股票，在另一天卖出股票，买卖都只有一次机会，不能在同一天 假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0 可以看成查找数组中b-a的最大值，其中b必须在a的后面  具体思路: 如果我们在某一天卖出了股票，那么要想收益最高，一定是它前面价格最低的那天买入的股票才可以。因此我们可以利用贪心思想解决，每次都将每日收入与最低价格相减维护最大值。  step 1：首先排除数组为空的特殊情况。 step 2：将第一天看成价格最低，后续遍历的时候遇到价格更低则更新价格最低，每次都比较最大收益...