题意： 给定数组和目标值，利用二分查找在数组中寻找目标值。 方法一： 解题思路： 首先用left和right表示查找范围，用mid=(left+right)/2进行二分查找，如果nums[mid]==target，则直接返回mid；如果nums[mid]>target，则将right更新为mid；如果nums[mid]<target，则将left更新为mid。 边界条件：1.如代码16行，能有效判断数组只有一个数的情况，以及剪枝。2.当数组中仅剩两个数时，直接判断这两个数中是否存在等于target的。 代码如下： class Solution { public: /...

题意： 返回二叉树的中序遍历序列。 方法一：递归 解题思路： 按照左子节点->根->右子节点的顺序，用递归的方式进行遍历。 代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型vector */ //s存中序遍历结果 vector<int> ans; //辅助函数 void hel...

题意： 给定一个整数数组和整数，其中数组中有一个数只出现一次，其他数都出现次，求这个只出现一次的数。 方法一： 解题思路： 在为偶数时，将所有数异或就能得到答案，因为偶数个相同数异或结果为，最终只留下了要求的数，时间复杂度，空间复杂度。 在为奇数时，若利用计数的方式来求答案，那么空间复杂度会来到，不满足题目要求。由于题目要求时间复杂度，空间复杂度。所以选择采用位运算的方式，即计算所有数在每一位的1的数目，再将该数模，最后再复原得到答案。由于int数组最多32位，所以时间复杂度是，空间复杂度是，满足要求。 图解如下： 代码如下： class Solution { public: ...

题意： 给定一个整数序列，取一个连续的子序列，要求满足：最多改变一个数，使该子序列严格上升。 方法一： 解题思路： 遍历数组的元素，记为nums[i]，如果nums[i+1]>nums[i-1]+2的话，无论nums[i]为什么数，那么nums[i-1],nums[i],nums[i+1]在最多一次的合理替换中可以变成一个严格上升的序列。寻找到在nums[i]左边以nums[i-1]结束的最长严格上升连续序列，以及在nums[i]右边找到以nums[i+1]开始的最长严格上升连续序列，将两者加起来为一个严格上升连续序列，遍历数组元素nums[i]求出最大值即可。 代码如下： cl...

题意： 给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。 方法一：动态规划 解题思路： 求解最长回文子序列，有明显的子问题重叠，使用动态规划，考虑以下最优子结构：（1）dp[i][j]-----序列s[i]-->s[j]的最长回文子序列的长度。（2）dp[i][i]=1（3）dp[i][j]=0(j<i)（4）dp[i][j]=dp[i+1][j-1]+2 (if s[i]==s[j])（5）dp[i][j]=max(dp[i+1,j],dp[i,j-1]) (if s[i]!=s[j]) (2)显然，（3）是对（4）的边界条件的兼容，（4）易得，（5）由...

题意： 给 n 个信封的长度和宽度。如果信封 A 的长和宽都小于信封 B ，那么信封 A 可以放到信封 B 里，请求出信封最多可以嵌套多少层。 方法一:动态规划 如下方法二中的解题思路,不同之处是在于寻找dp中不小于letters[i][1]的最小值直接简单遍历寻找. class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param letters intvector<vector<>> * @return int */ ...

题意： 将整数n划分成k份，每份不能为空，求划分的种数。 方法一：回溯法 解题思路： 分析数划分的规律，n=7，k=3，如图： 根据上图我们总结一下此种划分的规律：（1）右边的数大于等于左边的数（2）每一个位置都是从最小可能的数开始增加到最大可能的数。因此按照这种规律可以保证划分的唯一性和完备性。 使用深度优先遍历和回溯法的思想来解决本题：用数组nums存储划分的值，辅助函数helper是实现深度优先和回溯，按照上述的规律实现，增加回溯时的剪枝条件left>=nums[cur-1]和i<=left/(k-cur)以减少搜索深度，去掉不必要的搜索。 代码如下： class ...

题意： 给定一个数组代表股票每天价格，最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费），求最多可以赚多少钱。 方法一： 解题思路： 参考题目NC134的解法，利用几个状态变量来记录遍历数组时的状态，动态求得股票的最大收益。 定义四个状态变量，分别是firstBuy,firstSell,secondBuy,secondSell.（1） firstBuy---第一次买入股票后的最大收益（2） firstSell---第一次卖出股票后的最大收益（3） secondBuy---第二次买入股票后的最大收益（4） secondSell---第二次卖出股票后的最大收益 对于...

题意： 给定一个数组代某一股票价格，不限股票交易次数，不计算手续费，求最多可以赚多少钱。 方法一：贪心 解题思路： 由于是无限次数交易，因此贪心的策略是：如果后一天的价格高于前一天，就应当加上该差价；否则不变。 代码：设置last为前一天的价格，起始值为101，因此股票价格范围是[1,100]，ans为最大收益，初始值为0；遍历数组prices，如果当前值x大于last，则把x-last加到ans中，更新last。最终得到的ans即为最大收益。 图解如下： 输入数据：[2,3,5,1,4,2,8] 对于最大收益，如下图折线图所示，每逢折线上升（红色线段）买进卖出即可，遇价格下降不操作...

题意： 输入一个单链表，将该单链表奇数节点放在前半部分，偶数节点放在后半部分，不改变奇数节点和偶数节点之间的相对顺序，返回新的链表。 方法一： 解题思路： 一次遍历，奇数的节点组成一个链表，偶数的节点组成一个链表，然后将链表合并即可。 oddHead,oddTail记录奇数节点链表的头尾节点;evenHead,evenTail记录偶数节点链表的头尾节点；遍历时更新oddTail,evenTail；合并时将evenHead接在oddTail之后。 图解如下： 代码如下： /** * struct ListNode { * int val; * struct List...

题意： 给定一个数组，每一个数组元素对应另外一个数组值，求另外一个数组值的总和。 要求：每一个数组对应的值不小于1；任意两个相邻的数组元素，大的数组元素对应的值更大，相同无限制。 方法一：贪心 题目主要的难点是在于实现“任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果”，因此我们利用贪心的思路：从左往右遍历一遍，如果右边评分比左边评分高，右边糖果数就更新为左边糖果数+1；再从右向左遍历一边，如果左边评分比右边评分高，此时更新为max(左边糖果数,右边糖果数+1)。 代码如下： class Solution { public: /** * pick candy ...

题意： n个人成环，编号从1到n，从1开始报数，报数到m的人离开，由下一个人继续从1开始报数，循环n-1轮之后只剩下一个人，求这个人的初始编号是多少。 方法一： 思路分析： 因为最后只剩下一个人，所以我们可以从最后剩下的编号入手，看能不能倒推得到最开始的编号。首先画出图尝试找一下规律。 如上图所示，我们倒推：第四轮结束，最后留下来的人的编号为 1；第三轮结束，最后留下来的人的编号为 1+2=3; 3%2=1,编号为1；第二轮结束，最后留下来的人的编号为 1+2=3;第一轮结束，最后留下来的人的编号为 3+2=5(因为5>4) 所以5%4=1;第一轮开始，最后留下来的人的编号为 1...

题意： 设计一个结构，要求可以加入新数，并可以随时返回该结构中所有数据的中位数。 方法一:暴力解法 使用一个,是一个有序的元素可重复的数据结构,由平衡二叉树实现的,所以添加元素的时间复杂度为.返回中位数时由于multiset迭代器只能执行++,--的操作,不能直接自增一个量,所以时间复杂度是. 增加操作直接即可,寻找中位数通过的长度寻址到最中间一个数或者两个数.class Solution { public: multiset<int> dataStream; /** * the medians * @param operations int整型vecto...

题意： 给定一个非负整数，求该数的阶乘末尾0的数量。 方法一: 分析：末尾为0的数量应当取决于质因数5和2的数量，而对于阶乘的数字，显然2的数量在任何情况下都是大于5的数量的，因此直接计算质因数5的数量即可。 尝试直接寻找5的数量，遍历含质因数5的数，超时间复杂度。 代码如下: class Solution { public: /** * the number of 0 * @param n long长整型 the number * @return long长整型 */ long long thenumberof0(long lo...