/* unordered_map<int, int> mp mp.find(val)!=mp.end() mp.count(val)!=0 */ class Solution { public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ vector<int> twoSum(vector<int>& numbers, int target) { unordered_map<int,int> mp; for(int i=...

/* 简单dp dp[i]:以array[i]结尾的数组和; 两种状态：要么选择前面dp[i-1],要么不选,取最大值, dp[i] = max（dp[i-1]+ array[i], array[i]) *max_element():求数组中最大值 */ class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int ret = array[0]; int tmp = 0; for(auto k : array){ if(tmp + k < 0){ tmp = 0; }else{ ...

/* total 标记是否需要替换数字 最大贪心，前面为一半不一样数字，后面为超过一半的相同数字，最终记录的数字为最多的那个 因此如果超过一半数字存在，无论如何排列最终都会记录下排列最多的数字。 但是最后还要遍历数组看是否超过一半。 当比较下一个数字时，total 为 0时候替换数字为当前数字。 时间O(n) 空间：O(1) */ class Solution { public: int MoreThanHalfNum_Solution(vector<int> vt) { if(!vt.size()) return 0; int f, total = 0; for(int i = ...

/* 递归：f(s,pos),从pos开始到字符串末尾进行种类获取 每层递归确定一个字符，注意递归结束要返回原位置，防止重复，错误 用set集合存储自动把重复的删除且排序。 return {} vector<string>(ret.begin(), ret.end()) insert(); */ class Solution { public: void perm(int pos, string s, set<string> &ret){ if(pos + 1 == s.length()){//遍历到最后一个结束 ret.insert(s); return; }...

/* convert : 链表化子树，并返回头指针 last : 记录链表化的尾节点 按照中序遍历顺序赋值； 当前节点指向其前驱节点 root->left = last; 前驱节点指向当前节点 last->right = root; */ class Solution { public: TreeNode* last = NULL; TreeNode* Convert(TreeNode* root) { if(!root) return NULL; TreeNode *p = Convert(root->left);//链表化左子树并获得其头指针，为了判断返回链表化后的头指针...

/* p->next = r; // 带 -> 理解为指向 p结点 指向 r 结点 ，p 指针本身不变化 r = r->next; // 不带 -> 理解为赋值; r 代表 r的next r 指针变化后移 }; 重新声明空间构造，random 指向的结点 不容易找到。 在原有链表上先复制出新的节点，根据原有链表关系找到新复制的节点 */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return NULL; RandomListNode *p = pH...

/* 两个递归口，之间是递归先后关系 递归口的前后语句（操作）代表边走边操作（从前往后），后面的语句代表每个递归口退出都要进行操作（从后往前操作）， */ class Solution { public: vector<vector<int> > ans; vector<int> path; void dfs(TreeNode* cur, int value){ if(!cur || value < 0) return; value -= cur->val; path.push_back(cur->val); if(value == 0 &...

/* 每次递归划分出左右子树进行判断 根据最后一个元素根节点，划分左子树，剩下的为右子树，判断右子树是否符合条件。 然后递归判断左右子树. 边界条件：eg当left=2，sequence[left]=5,right=3,sequence[right]=5； i=3,递归进去左子树f(sequence,3,2); */ class Solution { public: bool f(vector<int> &sequence, int left, int right){ if(left>=right)return true;//left>=right,当没有左子树...

/* 层次遍历 */ class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> vt; if(!root)return vt;//push()进去的不能为空 queue<TreeNode*> q; q.push(root); while(!q.empty()){ TreeNode* tmp=q.front();q.pop(); vt.push_back(tmp->val); if(tmp->left)q.push(tmp->...

/* 模拟出栈入栈 用一个栈s保存入栈序列， 当找到出栈的元素后出栈，符合出栈序列就出栈，不符合继续入栈。 直到入栈序列全部遍历完，s中是否还有元素 */ class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { if(pushV.size()!=popV.size())return false; int i=0,j=0; stack<int> s;//s保存入栈序列 while(i<pushV.size()){//当入栈序列全部遍历完结束 if(pus...

/* 一个外循环下四个内循环。 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 top 上边边界 bottom下边边界 left：左边边界 right：右边边界 边界条件：当底部和顶部相等时，当左边和右边相等时只遍历一遍 当左右上下，任何两边指针相等时结束 */ class Solution { public: vector<int> printMatrix(vector<vector<int> > matrix) { vector<int> ans; int left=0,right=matrix[0].size...

/* f():将树镜像翻转返回指针 递归出口：当pRoot==NULL return NULL;return pRoot; 左右子树翻转f(pRoot->left);f(pRoot->right) tmp=pRoot->right;保存一个子树的指针交换时防止被覆盖 pRoot->right = f(pRoot->left); pRoot->left = f(pRoot->right); */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * @param pRo...

/* f：判断A,B是否相等 递归出口：当A==NUll 返回 false; B==NUll返回true 当A->val==B->val 判断左右子树f(A->left,B->left)，f(A->right,A->right)； 否则返回false HasSubtree 还要循环判断A中结点，与B中每一个结点比较,即f（A中任意一个结点，B） 返回当前结点，返回左右结点判断情况。 */ class Solution { public: bool dfs(TreeNode *r1,TreeNode *r2){ if(!r2)return true;//B树分...

class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode *head=new ListNode(0);//创建一个头结点，归一化操作，否则第一个加入的节点还要单独做。 ListNode *p=head;//两个指针一个指向头结点，一个指向尾节点。 while(pHead1&&pHead2){ if(pHead1->val<pHead2->val) { p->next=pHead1;//p链接值小的指针 pHead1=pHead1->...