递归求解 求子集时可以先规定一个quota，从1开始直到集合长度，每次只把quota数量的元素压入向量中。 代码如下： class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > ret; int n = S.size(); vector<int> tmp; ret.push_back(tmp); // 先压入空集 ...

递归求解 此题想法就是从空字符串开始先填一个 "("，然后下一个可以是 "(" 或者 ")"，当然每有一个 "(" 时，后面都需要对应一个 ")" ，依次往后填充即可。 // 这一句就是限制有一个"("时，后面必然会填充一个")" if(left<right) dfs(str+")",left,right-1,ret); // 这一句可以保证先填充"("，并且可以多次填充"(" if(left>0) dfs(str+"(",left-1,right,ret); 完整代码： class Solution { public: /** * * @param...

递归求解 看题解的时候发现的一个容易理解的代码，标记一下，用递归来解决每一次找小于255的数。 参考来源 class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ vector<string> restoreIpAddresses(string s) { // write code here vector<string> ret; findFitNum(s,re...

动态规划 到达楼顶花费的最小值可以想成从楼顶往下2层或者从楼顶往下1层上来花费的最小值，由此递推，可设dp[i]为从第i楼往上走花费的最小值，则dp[i]的递推式为： dp[i]=min{dp[i−1],dp[i−2]}+cost[i]dp[i] = min \{ dp[i-1],dp[i-2]\}+cost[i] dp[i]=min{dp[i−1],dp[i−2]}+cost[i] 前面的min是找出到第i楼的最小花费，后面cost[i]则是从i楼向上走所需的花费。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改...

动态规划 设dp[i]为目标为i时需要的最少货币数，则dp的转移方程为dp[j] = min(dp[j], dp[j-arr[i]]+1)。 意思就是说比较当前目标值需要的货币数与当前目标值减去一个货币之后所需货币数加一（因为要达到这个目标值还需要加上这个被减去的货币）。 显然目标值为0时，需要的货币数为0，又因为是在dp里找最小值，所以从dp[1]一直到dp尾元素都需要初始化为一个很大的数。 代码如下： class Solution { public: /** * 最少货币数 * @param arr int整型vector the array * @p...

递归判断 很简单的想法，若root1和root2的值相同，判断root1的左子树和root2的左子树是否一致，以及他们的右子树是否一致；若root1的值和root2的值不一致，判断root1的左子树是否含有root2，或者root1的右子树是否含有root2。 代码如下： /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root1 T...

用字符串来比较 在遍历链表的同时，分别采用头插和尾插的方法构造2个字符串，然后比较这两个字符串是否相等即可。 代码如下： /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 the head * @return bool布尔型 */ bool isPail(ListNode* head) { // write code...

C++ 中序遍历 因为是一颗搜索二叉树，所以使用中序遍历的话就是对这些数进行从小到大的遍历，其中发生错误的两个点就是一个大的数换到了前面，一个小的数换到了后面。 故而，要找出这两个数，思路就是先找到中序遍历中当前节点值小于前一个节点值的节点（类似线索二叉树），它的前一个节点值就是我们要找的换到前面的一个大的数。 然后就是在此之后找出小的那个数，显然就是找出此后的最小的值就行。 代码如下： /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ cla...

根据题目要求时间复杂度O(logn)可以知道使用二分法，然后递归是最容易想到的，每次对x都除2，然后根据中点和x的大小关系来判断该往中点下方继续除还是从中点上方除，直到： 中点的平方与x相等 中点的平方小于x但中点加一的值的平方大于x 既此中点就是x的平方根。 需要注意的是中点的平方很大，需要用long int型存，当然在递归函数里需要一个static型的变量来存结果。 代码如下： public: /** * * @param x int整型 * @return int整型 */ int sqrt(int x) { ...

使用位运算的方法 把数组中每一个数看成一个二进制的数，由于其中一些数出现了k次，所以将这些二进制数每一位都对应相加（此时的相加按照十进制加法来计算），得到一个数，将其每位都模k，显然余数不为零的这一位的下标和只出现一次的数的二进制表示法里1的下标是一致的。最后就是根据这些下标把只出现一次的数转换回来。 比如，一个数组[5,4,1,1,5,1,5]，其中5，1都出现了3次，4出现了1次，把其改成2进制数组为[0101,0100,0001,0001,0101,0001,0101]，然后将它们每一位对应相加会得到一个数0406，然后每一位都模k，变成0100，即为4。 代码如下： public: ...

假设从第一天开始买入，买入价格设为in，之后的每一天，只要那天比买入价格高就卖出，计算利润profit，若比买入价格in低就设买入价格为此时的股票价格。 由于每次遇到高价就要计算一次利润，和之前的算得的profit进行比较，profit只存最大值，故而一次循环之后profit必然为最大利润。 代码如下： public: /** * * @param prices int整型vector * @return int整型 */ int maxProfit(vector<int>& prices) { /...