题意：  求两个字符串的最长公共子串。  方法一：暴力法  对于str1和str2的最长公共子串，最直接的办法就是穷举他们的子串并判断是否是公共拥有的。 思路：（1）穷举两字符串起始位置 （2）寻找以该起始位置开始的公共子串，判断是否是最长的并更新代码如下： class Solution { public: /** * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ string LCS(string str...

题意：  给定一个整数数组和目标值 求用该数组的数构成目标值的最小数量。  方法一：  解题方法首先看起来像是贪心，但是因为给定的aim需要相等，所以可以使用动态规划，其存在的最优子结构如下： 一维数组dp[i]代表的是，aim为i的情况下的最少货币数，j是数组arr的索引。最初将dp[i] (i>0)初始化为INT_MAX-1   (1) dp[i]=0           while i=0;   (2) dp[i]=min(dp[i],dp[i-arr[j]]+1)  while i>0;(其中使用dp[i-arr[j]]时保证i>=arr[j])  (1)式显然，(2...

方法一：哈希表  1.使用一个哈希表来映射原节点和新节点 2.通过将原节点和新节点的键值对添加进去代表当前节点已经复制 3.利用next和random的指向递归遍历链表代码如下： class Solution { public: unordered_map<RandomListNode*, RandomListNode*> hash; RandomListNode* Clone(RandomListNode* pHead) { //当前为空或者当前节点已复制，结束当前递归循环。 if(pHead==nullptr) return nullptr; if(hash.count(pHe...

方法一：递归DFS  使用DFS递归加回溯的方法。图解过程如下：  代码如下： class Solution { public: vector<vector<int>> ans; vector<int> path; vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { //DFS+回溯 dfs(root,expectNumber); return ans; } void dfs(TreeNode* root,int expectNumber){ if(root...

方法一：递归  较自然的思路，遵循后序遍历的规则:左子树->右子树->根节点。因此当前序列的最后一个值即为根节点，且左子树<根节点<右子树。每次遍历当前序列，根据大小顺序判断是否符合条件，同时得到左右子树序列，并递归调用函数判断子树序列是否符合条件。class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.size()==0) return false; return helper(sequence,0,sequence.size()-1); } ...

方法一：BFS  题目很简单，从上往下层层遍历并打印节点值即可，用一个队列来存储节点，遍历打印当前节点的值，并将子节点入队。class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { queue<TreeNode*> q; vector<int> ans; if(root==nullptr) return {}; q.push(root); while(!q.empty()){ TreeNode* cur=q.front(); q.pop(); ans.push_ba...

方法一：模拟栈的压入、弹出  利用一个辅助栈来模拟栈的压入和弹出。遍历popV序列，并每次判断当前是直接从栈中弹出，还是需要先压入一些序列后再弹出。代码如下 class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { int n=pushV.size(); //用栈s来模拟压栈和出栈序列 stack<int> s; int j=0; //找到pushV中与popV[0]相同的数 while(j<n&&pushV[j]!=popV[0]) j...

方法一：  将链表中的值提取出来，然后分配新的链表节点组成新链表。代码如下： class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode *p,*t; int q; //存链表节点的值 stack<int> s; p=pHead; //遍历链表，将链表节点的值压栈 while(p!=NULL){ s.push(p->val); p=p->next; } ListNode* ret=new ListNode(0); p=ret; //从栈中取出节点值重新分配节点并构建新链表 whil...

方法一：  暴力方法，有较大改进空间。使用两个额外数组，分别用来存奇数和偶数，遍历原数组，根据数的奇偶将其存入不同的数组，最后将两个数组整合到一起即可。class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> reOrderArray(vector<int>& array) { // write code here vector<int> ...

解题方法：  如下图所示，我们使用将push操作放到stack1中，将pop操作放到stack2中，当pop操作且stack2为空时，将stack1中所有元素转入stack2中即可。图解如下：    代码如下： class Solution { public: void push(int node) { stack1.push(node); } int pop() { if(stack2.empty()){ //pop时 stack2为空，将stack1中所有元素转入到stack2中 while(!stack1.empty()){ stack2.push(stack1.top()); stac...

方法一：  直接使用哈希表，用哈希表的额外内存空间来记住当前数字出现的次数，出现两次的会被删除，只剩下两个出现一次的数字。  代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> FindNumsAppearOnce(vector<int>& array) { // write code here //使用哈希表的方式 unordere...

方法一：  暴力，从头开始找到第一个值为k的元素，再计算连续的k的个数即可。缺点：没有利用好有序数组的特性。  代码如下： class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int ans; for(int i=0;i<data.size();i++){ if(data[i]==k){ int j=i+1; //从第一个为k的元素起，找到第一个不为k的元素止。 while(j<data.size()&&data[j]==k) j++; return j-i; } } ...

解题思路：  本题主要在于找出顺时针旋转90°后的矩阵与原矩阵对应位置之间的关系和规律。  方法一：  找出整体的规律，并使用一个辅助数组来存储新的矩阵。 从上图中的矩阵旋转来看：原矩阵元素的列数变成新矩阵元素的行数；原矩阵元素的行数是第2行，旋转后元素的列数是从右往左倒数第2列。因此对于原矩阵mat[i][j]，旋转后该值应该在新矩阵ans[j][n-i-1]的位置。class Solution { public: vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n...

方法一：暴力解法  最直接粗暴的方法，但是时间复杂度很高。按照子串起始位置和结束位置，遍历所有可能的子串，即 left:0->n-1, right:left+1->n-1。再每次通过while循环判断该子串是否是回文串。 第一层循环为子串起始位置，第二层循环为子串结束位置，第三层循环为判断字符串是否为回文串。class Solution { public: int getLongestPalindrome(string A, int n) { // write code here int max=1; for(int left=0;left<n;left++){ for(in...