首先丑数都是只有质因子235，刚开始没明白这个题目，后来想到所有的数都可以拆成质数之积（毕竟质数的定义就是只有1和自身是因数，也就是不能再拆，想要拆到最后只有235，那形成的时候也应该只有235），那想要235就要由这三个数不停的互相累乘就可以了 class Solution { public: int GetUglyNumber_Solution(int index) { if(index <= 0)return 0; int p2=0,p3=0,p5=0;//初始化三个指向三个潜在成为最小丑数的位置 vector<int> result(index,0); result[...

写个仿函数，自定义比较规则，那个放前面更小就把哪个放前面，方便 class Solution { public: struct comp{ bool operator()(string a,string b){ return a+b<b+a; } }; string PrintMinNumber(vector<int> nums) { vector<string> str; for (int val : nums) { str.push_back(to_string(val)); } sort(str.begin(), str.end(),comp()); str...

这是个标准的动态规划，需要注意的是明确好dp的意义，因为是要连续数组，所以我们可以规定dp[i]一定包含i class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if(array.size()==1) return array[0]; int ans=array[0]; vector<int> dp(array.size(),array[0]);//dp是以i结尾的，一定包含当前的最后一个，这样我们只需要再比较一圈那个dp最大即可 for(int i=1;i<arra...

全排列与map红黑树，回头更新一下手写实现最小堆 class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { if(k>input.size()) return vector<int>(); multiset<int> s; for(int i=0;i<input.size();++i){ s.insert(input[i]); } set<int>::iterator it=s.begin(); whi...

写完看评论去才发现没用上过半的条件，做的麻烦了。其实差不多，两种方法如下： class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { sort(numbers.begin(),numbers.end()); int number=numbers[0]; int sum=0; int ans=numbers[0]; int max=0; for(int i=0;i<numbers.size();i++){ if(number==numbers[i]) sum++; else { nu...

c++ 全排列问题 回溯方法，最好使用一个vector<bool>用来表示有没有使用过。去重也是需要注意的地方</bool> class Solution { public: vector<string> ans; string path=""; void backtracking(vector<char>& dic,vector<bool> used){ if(path.size()==dic.size()){ ans.push_back(path); return; } for(int i=0;i<dic.size(...

看了评论区大佬方法，pre要加引用或者干脆设置为一个成员变量，因为回溯后还要用到pre class Solution { public: void backtra(TreeNode* cur,TreeNode*& pre){ if(!cur) return; backtra(cur->left, pre); cur->left=pre; if(pre) pre->right=cur; pre=cur; backtra(cur->right,pre); } TreeNode* Convert(TreeNode* pRootOfTree) { if(!pRootOf...

花了不少时间，首先递归不行，然后看评论方法以为会了，自己写结果发现原来的链表也不能改变，下意识地以为会销毁原来的测试现在的 /* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return pHe...

递归 class Solution { public: vector<vector<int>> ans; vector<int> path; void backtra(TreeNode* root,int expectNumber){ if(!root->left&&!root->right){ if(root->val==expectNumber){ path.push_back(root->val); ans.push_back(path); path.pop_back(); }else return; } pat...

递归与非递归 递归 后续遍历最后一位肯定是中间值，根据这个值把数组划为两半，左边肯定是左子树，都得小于中间值，右边是右子树，都得大于中间值。然后看左右字数各自也得满足上述规律。因为分割后左右子树为空也是满足条件的，但是题目说空的不是搜索树，所以要单独再写一个回溯函数。使用下标作为传递的参数可以减少vector的添加操作，节省时间（下方未使用）使用一个成员变量来存数组配合传参下标可以进一步节省内存（下方未使用） class Solution { public: //bool backtra() bool backtra(vector<int> sequence) { if(seque...

层序遍历，队列 class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { queue<TreeNode*> s; vector<int> ans; if(!root) return ans; s.push(root); while(!s.empty()){ //int size=s.size(); TreeNode* tmp; tmp=s.front(); s.pop(); ans.push_back(tmp->val); if(tmp->left) s...

刚开始代码写的很不简洁，超时了，举例子也都能过，如下： class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> s; if(pushV.size()!=popV.size()) return false; if(pushV.size()==0||popV.size()==0) return true; int j=0; for(int i=0;i<popV.size();i++){ if(s.top()==popV[i]){ s....

让都O(1)就得想办法存最小值，这个最小值还要能够随着栈操作相应的变化，所以采用一个辅助栈用来存最小值 class Solution { public: stack<int> stack,mstack; void push(int value) { stack.push(value); if(mstack.empty()){ mstack.push(value); } else mstack.push(value>mstack.top()?mstack.top():value); } void pop() { stack.pop(); mstack.pop(); } int ...

注意边界情况，如果始终保持左闭右开会造成奇数行列时（四个for循环互相推诿）漏掉。故采用以下方法 class Solution { public: vector<int> printMatrix(vector<vector<int> > matrix) { if(matrix.size()<1) return vector<int>(); if(matrix.size()==1) return matrix[0]; int down=matrix.size()-1; int right=matrix[0].size()-1; int up=...