上海最好的网站建设,乐事薯片软文推广,光明附近网站建设公司,上海工商局注册公司官网236. Lowest Common Ancestor of a Binary Tree
题意#xff1a;二叉树#xff0c;求最近公共祖先#xff0c;All Node.val are unique.
我的思路
首先把每个节点的深度得到#xff0c;之后不停向上#xff0c;直到val相同#xff0c;存深度就用map存吧
但是它没有向…236. Lowest Common Ancestor of a Binary Tree
题意二叉树求最近公共祖先All Node.val are unique.
我的思路
首先把每个节点的深度得到之后不停向上直到val相同存深度就用map存吧
但是它没有向上的指针要如何解决——用mapint,int存一下父节点
返回的是指针注意一下
代码 Runtime28 ms Beats 5.86% Memory17.7 MB Beats 5.56%
class Solution {
public:unordered_mapint,intdep; unordered_mapTreeNode*,TreeNode*fa;void dfs(TreeNode* root,int dp){if(rootNULL)return;dep[root-val]dp;if(root-left)fa[root-left]root;if(root-right)fa[root-right]root;dfs(root-left,dp1); dfs(root-right,dp1);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {dfs(root,0);while(dep[p-val]!dep[q-val]){if(dep[p-val]dep[q-val]) pfa[p];else qfa[q];}while(p!q){pfa[p];qfa[q];}return p;}
}; 标答 递归
情况1如果proot||qroot那就返回root这里的root是正解
情况2是指同一层级但不同的指针而root就是它们的祖先
情况3p和q都在lca1这里lca2为NULL不返回
情况4和情况3类似
代码 Runtime13 ms Beats 73.18% Memory14.2 MB Beats 49.26%
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root)return root;if(root-val p-val || root-val q-val)return root;//情况1TreeNode* lca1lowestCommonAncestor(root-left,p,q);TreeNode* lca2lowestCommonAncestor(root-right,p,q);if(lca1!NULLlca2!NULL)return root;//情况2if(lca1!NULL)return lca1;//情况3return lca2;//情况4}
};
标答 另一种的不用遍历
用stack来辅助建立每个指针的父指针这样就不用把整棵树都建完根据下面的代码来说不能用queue因为用栈代表的是DFS而queue就是层序遍历这样循环终止判断条件mp.find(p)mp.end() || mp.find(q)mp.end()就是错误的了
之后用set来每个指针向上这样就不需要dep了
代码 Runtime24 ms Beats 11.11% Memory17.3 MB Beats 7.82%
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* s; unordered_mapTreeNode*,TreeNode* mp;mp[root]NULL; s.push(root);while(mp.find(p)mp.end() || mp.find(q)mp.end()){TreeNode *ts.top(); s.pop();if(t-left){mp[t-left]t; s.push(t-left);}if(t-right){mp[t-right]t; s.push(t-right);}}setTreeNode* sett;while(p!NULL){sett.insert(p); pmp[p];}while(sett.find(q)sett.end()){qmp[q];}return q;}
}; 238. Product of Array Except Self
题意给一个数组a返回一个数组ansans[i]等于除了a[i]其他数的值
我的思路
先判断有多少个0两个的话都输出01个的话其余的是0其中一个是除它以外的积
没有0那就总积/当前的数
写完了才发现不让用除法
代码 Runtime 11 ms Beats 98.32% Memory24 MB Beats 79.45%
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int zero0;int mul1;for(int i0;inums.size();i){if(!nums[i])zero;else mulmul*nums[i];}vectorint ans(nums.size(),0);if(zero1)return ans;for(int i0;inums.size();i){if(zero!nums[i])ans[i]mul;else if(!zero)ans[i]mul/nums[i];}return ans;}
};
标答 前缀积与后缀积
就是普通的做最后把空间优化了
代码 Runtime14 ms Beats 93.5% Memory24 MB Beats 79.45%
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint output(n);output[0] 1;for(int i1; in; i){output[i] output[i-1] * nums[i-1];}int right 1;for(int in-1; i0; i--){output[i] * right;right * nums[i];}return output;}
}; 239. Sliding Window Maximum
题意滑动窗口求最大 我的思路
我记得是用队列做的因为要求最大值但是忘了只记得队列里放的是序号
用单调栈能做吗不能例如7 6 5 4 3 2 1
只放比队尾大的数 7 6 5 4 3 2 1 不行
后面想了想只放比队尾小的数 7 6 5 4 3 2 1好像可以毕竟是求最大值
标答 优先队列 O(nlogn)
初始化pair型的优先队列答案ans把k个{数字序号}放入队列ans[0]是优先队列的最大的
遍历nums数组如果优先队列不为空并且顶部的数字已经小于等于i-k了那就把顶部的数字不断弹出之后放入pair更新答案
代码 Runtime231 ms Beats 48.99% Memory148.9 MB Beats 26.27%
class Solution {
public:#define pii pairint,int vectorint maxSlidingWindow(vectorint nums, int k) {priority_queuepii,vectorpii,lesspii q;int nnums.size();vectorint ans;for(int i0;ik;i) q.push({nums[i],i});ans.push_back(q.top().first);for(int ik;in;i){while(!q.empty()q.top().secondi-k)q.pop(); //注意上面的等号queue只能有(i-k,i]之间的数q.push({nums[i],i});ans.push_back(q.top().first);}return ans;}
};
标答 双端队列
初始化双端队列dq和答案数组ans在k个数以内如果之后的数比队尾大那么把队尾的数弹出之后加入像单调栈一样队列里的值是从大到小ans[0]是队首的值遍历剩下的数组如果队首的序号超过范围里把它弹出如果新来的数比队尾大那么把队尾的数弹出最后更新答案
代码 Runtime190 ms Beats 90.70% Memory134.7 MB Beats 72.95%
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {dequeint q;vectorintans;//q里面放序号int nnums.size();for(int i0;ik;i){while(!q.empty()nums[q.back()]nums[i])q.pop_back();q.push_back(i);}ans.push_back(nums[q.front()]);for(int ik;in;i){if(q.front()i-k)q.pop_front();while(!q.empty()nums[q.back()]nums[i])q.pop_back();q.push_back(i);ans.push_back(nums[q.front()]);}return ans;}
};
标答 左指针
初始化max_idx数组模拟双端队列ans数组left指针
注意 如果直接vectorint ans(n-k1);来初始化ans可以减少内存的使用
代码 Runtime 173 ms Beats 98.6 Memory 129.7 MB Beats 99.17%
class Solution {
public:int n;vectorint max_idx;//array storing index for maxint left0;vectorint maxSlidingWindow(vectorint nums, int k) {nnums.size(); vectorint ans(n-k1);for(int i0;ik;i){while(max_idx.size()left nums[i]nums[max_idx.back()]) max_idx.pop_back();// pop back the indexes for smaller onesmax_idx.push_back(i); // push back the index for larger one}ans[0]nums[max_idx[left]]; for(int ik; in; i){while(max_idx.size()left nums[i]nums[max_idx.back()]) max_idx.pop_back();// pop back the indexes for smaller onesmax_idx.push_back(i); // push back the index for larger oneif (max_idx[left]i-k) left; ans[i-k1]nums[max_idx[left]]; }return ans;}
}; 240. Search a 2D Matrix II
题意给一个行和列都升序的矩阵找target是否在矩阵中
我的思路
和之前不一样的是最左边一列不是索引所以要nlogm
代码 Runtime 184 ms Beats 21.13% Memory 14.8 MB Beats 88.10%
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int nmatrix.size();int q0;int mmatrix[0].size();for(int q0;qn;q){int l0,rm-1;while(lr){int mid(lr)/2;if(matrix[q][mid]target) lmid1;else if(matrix[q][mid]target) return 1;else rmid-1;}}return 0;}
};
标答
因为行从小到大排列列也是从小到大排列所以可以从左上角或者右上角开始找假设从左下角开始找找小的行--找大的列O(nm)
代码 Runtime88 ms Beats 72.75% Memory14.9 MB Beats 47.68%
class Solution {
public:bool searchMatrix(vectorvectorint ma, int tar) {int mma[0].size(),nma.size();int rown-1,col0;while(row0colm){if(ma[row][col]tar)row--;else if(ma[row][col]tar)col;else return 1;}return 0;}
};
神奇的优化 在最后加上ma.clear()会使时间大幅度减少
试了试第215题第131题是可行的但第72题第53题就不行
补充知识STL中的隐性性能开销与副作用
代码 Runtime21 ms Beats 99.80% Memory14.9 MB Beats 47.68%
class Solution {
public:bool searchMatrix(vectorvectorint ma, int tar) {int mma[0].size(),nma.size();int rown-1,col0;while(row0colm){if(ma[row][col]tar){ma.clear();return 1;}if(ma[row][col]tar)row--;else col;}ma.clear();return 0;}
};
283. Move Zeroes
题意把0都放在最后 我的思路
想过荷兰国旗算法但是这样就把非0的顺序打乱了所以不会做
标答
就是简单的思维题
代码 Runtime12 ms Beats 94.45% Memory19.2 MB Beats 34.86%
class Solution {
public:void moveZeroes(vectorint nums) {int j0;for(int i0;inums.size();i){if(nums[i])nums[j]nums[i];}for(;jnums.size();j)nums[j]0;return ;}
}; 287. Find the Duplicate Number
题意一个数组有一个数出现了多次返回这个数
我的思路
开一个vis看有无重复用上了取消同步和clear
代码 Runtime37 ms Beats 100% Memory61 MB Beats 98.76%
class Solution {
public:int findDuplicate(vectorint nums) {bool vis[100005]{0};ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(int i0;inums.size();i){if(vis[nums[i]]){nums.clear();return nums[i];}vis[nums[i]]1;}return -1;}
};
标答 快慢指针
定义快指针和慢指针就是看环的接口处以及之前值相同的地方 以1 3 3 4 2 为例 第一轮 fast3(1) slow1 第二轮 fast2 slow3 第三轮 fast4 slow4 fast0 fast1slow2 fast31slow3(2) 例子 3 1 3 4 2 第一轮 fast4 slow3(1) 第二轮 fast3(2)slow4 第三轮 fast2slow2 fast0 fast3(1) slow3(2) 代码 Runtime39 ms Beats 99.99% Memory 61 MB Beats 99.82%
class Solution {
public:int findDuplicate(vectorint nums) {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);int fast 0; int slow 0;while (true){fast nums[nums[fast]];slow nums[slow];if(slow fast){break;}}fast 0;while(true){fast nums[fast];slow nums[slow];if(fast slow){nums.clear();return slow;}}}
};
其他有趣的解法LeetCode - The Worlds Leading Online Programming Learning Platform
改变数值不增加空间的因为1 nums[i] nnums.length n 1所以数组中最大的数小于nums.size()遍历数字每遍历一个数nums[i]就把nums[nums[i]]变成负的这样如果遍历到nums[nums[i]]是负的就返回nums[i]
二分查找、位运算…… 295. Find Median from Data Stream
题意返回中位数 我的思路
对顶堆
代码 Runtime276 ms Beats 74.61% Memory116.8 MB Beats 96.59%
class MedianFinder {
public:priority_queueint,vectorint,greaterint qs;//小的在最上面priority_queueint,vectorint,lessint qb;//大的在最上面MedianFinder() {}void addNum(int num) {if(qs.empty()qb.empty())qs.push(num);else if(qs.top()num) qs.push(num);else qb.push(num);while(qs.size()-1qb.size()){//4 3 or 3 3 or 3 4都可以int tmpqs.top();qs.pop();qb.push(tmp);}while(qs.size()1qb.size()){int tmpqb.top();qb.pop();qs.push(tmp);}}double findMedian() {int snqs.size(),bnqb.size();if(snbn)return qb.top();else if(snbn)return qs.top();else return 1.0*(qs.top()qb.top())/2;}
};
标答 优化
上面的对顶堆写的有可以改进的地方
1. 维持qs比qb多一个的情况不用循环【第一次进入的是qs所以qs比qb多一个】
2. 有了上面的限定奇数就只要返回qs的顶部就可以了
3. 不用创造变量tmp直接qb.push(qs.top())放进去就可以了不知道能否减少时间但确实少了
以上3个方法在一起 Runtime 253 ms Beats 95.75%
4. 耍赖方法ios::sync_with_stdio(0) Runtime 230 ms Beats 99.83% Memory 116.9 MB
代码 Runtime 253 ms Beats 95.75% Memory117 MB Beats 33.29%
class MedianFinder {
public:priority_queueint,vectorint,greaterint qs;//小的在最上面priority_queueint,vectorint,lessint qb;//大的在最上面MedianFinder() {}void addNum(int num) {if(qs.empty()||qs.top()num)qs.push(num);else qb.push(num);if(qs.size()-1qb.size()){//5 3 noqb.push(qs.top());qs.pop();}else if(qs.size()qb.size()){//3 4--4 3qs.push(qb.top());qb.pop();}}double findMedian() {int snqs.size(),bnqb.size();if(sn!bn)return qs.top();else return 1.0*(qs.top()qb.top())/2;}
};
300. Longest Increasing Subsequence
题意严格上升序列的长度
我的思路
动态规划我记得还有用队列优化二进制优化和普通dp版本
但我都忘记了 例子一 num[i] 1 10 100 1000 10000 2 3 4 5 6 7 8 dp[i] 1 2 3 4 5 2 3 4 5 6 7 8 v[i] 0 0 1 2 3 0 5 6 7 8 9 10 例子二 num[i] 5 6 7 2 1 7 8 9 4 dp[i] 1 2 3 1 1 3 4 5 2 v[i] # 0 1 # # 1 2 6 3 v[i]要找dp最大的且比自己小的 开一个空间表示比自己小的位置在哪里v[i]dp[i]dp[v[i]]1 最后遍历一遍找个最大的 On^2 ?
----(详见标答动态规划
单调栈如何单调栈5 6 7 2 部分2会把所有数字都弹出的不行
双端队列如何如果比对头小把对头弹出加入如果比队尾大加入例子一不行 vector如何直接二分插入二分就用lower_bound 1 10 100 1000 10000 1 2 100 1000 10000 1 2 3 1000 10000 1 2 3 4 10000 1 2 3 4 5 1 2 3 4 5 6……可以 代码 二分 Runtime7 ms Beats 90.93% Memory10.3 MB Beats 87.20%
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint v;for(int i0;inums.size();i){int tmplower_bound(v.begin(),v.end(), nums[i])-v.begin();if(tmpv.size())v.push_back(nums[i]);else v[tmp]nums[i];}return v.size();}
};
标答 动态规划
初始化dp[0]为1在[0, i]的序列中从右向左看如果nums[j]nums[i]且dp[j]dp[i]dp[i]dp[j];这一步就是上面思路中的v的代替品最后循环结束到dp[i]的时候
代码 Runtime 171 ms Beats 75.72% Memory10.3 MB Beats 97.68%
class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();int dp[2505]{0};int ans1;dp[0]1;for(int i1;in;i){for(int ji-1;j0;j--){//从i-1开始if(nums[j]nums[i]dp[j]dp[i])dp[i]dp[j];}dp[i];ansmax(ans,dp[i]);}return ans;}
};
标答 树状数组
前置知识——树状数组是什么 ——来源算法学习笔记(2) : 树状数组
树状数组思路
dp的第二层循环的目的是找小于等于num[i]的数字中dp[j]dp[i]的
所以建立树状数组c[i]其中i是num[i]c[i]是dp[i]从1开始
首先建树int c[maxn]c[1]1如果query(i-1)dp[i]dp[i]query(i-1)dp[i]add(i, dp[i])
或者不要dp数组了因为dp[i]刚刚遍历到为0一定query(i-1)dp[i]之后的操作也没有dp[i-1]所以可以省略
写完了发现nums[i]居然有负数记得加上偏移量
代码 Runtime 4 ms Beats 95.80% Memory 10.3 MB Beats 87.20%
class Solution {
public:#define lowbit(x) x(-x)int c[20004]{0};//c[1]不需要初始化为1int query(int a){//找[1,a]中最大的数int maxx0;for(int ia;i0;i-lowbit(i))maxxmax(maxx,c[i]);return maxx;}void add(int a,int k){for(int ia;i20004;ilowbit(i))c[i]max(c[i],k);}int lengthOfLIS(vectorint nums) {int nnums.size();int ans0;for(int i0;in;i){int maquery(nums[i]-110001);//注意这里是nums[i]-1比nums[i]小才可以add(nums[i]10001,ma1);ansmax(ans,ma1);}return ans;//因为你不知道数组nums中最大的数m是多少除非你遍历一遍//所以你不能return query(m)//所以一边遍历一边更新答案}
}; 322. Coin Change
题意给你硬币类型和目标求最少的硬币数
我的思路
不知道贪心行不行所以就用动态规划了
1. 初始化为负无穷来判断安排是否合法
2. 求最小的时候要多一步条件判断
代码 Runtime 59 ms Beats 87.21% Memory9.9 MB Beats 98.52%
class Solution {
public:int coinChange(vectorint coins, int amount) {int dp[10004];memset(dp,-0x3f,sizeof(dp)); dp[0]0;int mcoins.size();for(int i0;iamount;i){for(int j0;jm;j){if(icoins[j]dp[i-coins[j]]0){if(dp[i]0)dp[i]dp[i-coins[j]]1;else dp[i]min(dp[i],dp[i-coins[j]]1);}}}if(dp[amount]0)return -1;return dp[amount];}
};
标答 递归贪心记忆化 但是没懂
最前面的条件判断如果amount是双数但是coin里面没有双数就返回-1硬币从小到大排序
接下来看注解总之是很精密的代码
就是有一个地方不懂如果没有一开始的if判断它会超时
那有无可能 存在一个不被最开始的if检测到的-1情况会使这个代码超时
代码 Runtime3 ms Beats 99.98% Memory9.9 MB Beats 99.78%
class Solution{
bool check(vectorint coins, short index, int cnt, int target){long sum (long) coins[index]*cnt;//相乘可能超出int的范围if (sumtarget) return true;//如果数量刚好就是可以用cnt个硬币else if (sum target) {//如果sum超过了就要换个计划if (index 0) return false;//没有剩下的硬币类型了不可能了for (short i cnt; i0; i--){//预计给之后的硬币类型 i个来搞定自己留下cnt-i个long take target - (long)coins[index]*(cnt-i);//take是预计之后的硬币类型要达成的数量//为什么cnt-i会0因为可能不用这个硬币if (take 0) break;//为什么自己留下的cnt-i要从小到大遍历因为cnt-i大了take小于0更大的cnt-i就更不用看了int r take;//隐性的类型转换也要时间所以这里多一步if (check(coins, index-1, i, r)) return true; }}return false;}
public:int coinChange(vectorint coins, int amt) {if (amt1){//如果是双数short i0;for (;icoins.size();i){if(coins[i]1)break;}if (icoins.size()) return -1; }sort(coins.begin(), coins.end());int best amt/coins.back();//个数最少的int worst amt/coins.front();//个数最多的for(short ibest; iworst;i)//预计i个硬币if (check(coins, coins.size()-1, i, amt)) return i;return -1;}
};
347. Top K Frequent Elements
题意返回k个出现次数最多的数
我的思路
哈希nlogn
map默认是按key值从小到大排序的不能更改sort方式所以用vectorpii的方式了
遇到的问题错误解决方法error: reference to non-static member function must be called 要在cmp函数前面加上static
代码 Runtime 8 ms Beats 93.30% Memory13.7 MB Beats 59.82%
class Solution {
public:# define pii pairint,int static bool cmp(pii a,pii b){return a.firstb.first;}vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,intmp;vectorpii cnt; vectorint ans;int nnums.size();for(int i0;in;i)mp[nums[i]];for(autoq:mp) cnt.push_back({q.second,q.first});sort(cnt.begin(),cnt.end(),cmp);for(int i0;ik;i)ans.push_back(cnt[i].second);return ans;}
};
标答是map优先队列我觉得差不多
