网站源码使用,企业网站源码下载站长之家,凡科快图电脑版,常州淄博网站优化34. Find First and Last Position of Element in Sorted Array
题意#xff1a;找到非递减序列中目标的开头和结尾
我的思路
用二分法把每一个数字都找到#xff0c;最后返回首尾两个数
代码 Runtime12 ms Beats 33.23% Memory14 MB Beats 5.16%
class Solution {…34. Find First and Last Position of Element in Sorted Array
题意找到非递减序列中目标的开头和结尾
我的思路
用二分法把每一个数字都找到最后返回首尾两个数
代码 Runtime12 ms Beats 33.23% Memory14 MB Beats 5.16%
class Solution {
public:void bins(int l,int r,int tar,vectorint nums,vectorint ans){while(lr){int midl(r-l)/2;if(nums[mid]tar) rmid-1;else if(nums[mid]tar)lmid1;else{ans.push_back(mid);bins(l,mid-1,tar,nums,ans);bins(mid1,r,tar,nums,ans);return ;}}}vectorint searchRange(vectorint nums, int target) {int nnums.size();vectorint ans;bins(0,n-1,target,nums,ans);if (ans.empty())return {-1,-1};else sort(ans.begin(),ans.end());return {ans[0],ans[ans.size()-1]};}
};
标答
可以直接找到序列的头部数字和数字加一的序列的头部数字
代码 Runtime 3 ms Beats 96.59% Memory13.7 MB Beats 11.32%
class Solution {
public:pairint,int bins(vectorint nums,int tar,int l,int r){int ans-1;while(lr){int mid(lr)/2;if(tarnums[mid]) lmid1;else if(tarnums[mid]) rmid-1;else{//如果等于的话ansmid;rmid-1;}}if(ans-1)return {l,0};return {ans,1};}vectorint searchRange(vectorint nums, int target) {int n(int)nums.size()-1;pairint,int st; pairint,int en;st bins(nums,target,0,n);en bins(nums,target1,0,n);if(!st.second) return {-1,-1};return {st.first,en.first-1};}
}; 35. Search Insert Position
题意给定一个有序数组和一个元素找到给序号没找到返回他应该插在哪里
我的思路
二分查找我记得二分查找应该是有upper_bound和lower_bound直接用的
注意lower_bound函数是返回指针用于在指定区域内查找不小于目标值的第一个元素也就是说[1,2,3,5]数组中target为4的情况下返回的是序号为3[1,2,3,4]数组中target为4的情况下返回的是序号为3
upper_bound为大于目标元素的第一个数/位置[1,2,3,5]数组中target为4的情况下返回的是序号为3[1,2,3,4]数组中target为4的情况下返回的是序号为4
代码 3ms Beats 88.42% 9.63mb Beats 47.66%
class Solution {
public:int searchInsert(vectorint nums, int target) {return lower_bound(nums.begin(), nums.end(), target) - nums.begin();}
}; 39. Combination Sum
题意给定一个不同整数数组和一个目标返回一个单独的集合使得集合内部和等于target同一个数字可以用多次
我的思路
好像是动态规划做的和背包问题差不多但是我忘记了orz
标答 动态规划
首先创建一个dp的vector每个dp的内容是答案的格式也就是vectorvectorintdp表示的是从第一个数开始到target的每个数为target时的答案
状态转移方程为 dp[j]dp[j-i]i (这里的时集合加入的意思) 代码 Runtime 18 ms Beats 34.7% Memory14.3 MB Beats 40.40%
class Solution {
public:vectorvectorint combinationSum(vectorint candidates, int target) {vector vector vectorint dp(target1);//首先要开辟空间不然会runtime errordp[0]{{}}; //初始化for(int i:candidates){//对于每一个在候选名单里的for(int ji;jtarget;j){//对于每个在数组里的ifor(auto v:dp[j-i]){//v是每一个答案中的集合v.push_back(i);dp[j].push_back(v);//要把更新的集合放回dp[j]中}}}return dp[target];}
}; 标答 递归
递归的方法好像速度更快首先将数组排序之后递归递归的引入参数为numnext是nums的索引也就是遍历了nums的每一个数字psol是每一个集合表示拿或者不拿的可能性target是目标result是最后的答案
注意在一开始要排序这么做是为了剪枝操作
因为 if(target0)return; 这一操作同样可以退出递归但是如果target-candidates[next]0 的时候推出递归那么可以剪枝大大提升速度如果要达成这target-candidates[next]0退出的操作那么就必须要nums排序这一才能加快速度
注意psol传入时要引用不然会拖慢时间
代码 Runtime2 ms Beats 91.39% Memory10.7 MB Beats 84.74%
class Solution {
public:void search(vectorint candidates, int next, int target, vectorint pol, vectorvectorint result){if(target0){//说明结束了result.push_back(pol);return;}if(nextcandidates.size()||target-candidates[next]0) return;pol.push_back(candidates[next]);//这是拿了,注意拿了还可以接着拿search(candidates,next,target-candidates[next],pol,result);pol.pop_back();search(candidates,next1,target,pol,result);//这是没拿没拿就走了}vectorvectorint combinationSum(vectorint candidates, int target) {sort(candidates.begin(),candidates.end());vectorint pol;vectorvectorint result;//初始化search(candidates,0,target,pol,result);return result;}
}; 41. First Missing Positive
题意给出未排序的nums返回未在这些数字中的正整数
我的思路
好像博弈论中有这个算法还涉及位运算但是忘记了【好吧答案中没有位运算】
num的长度只有1e5所以只能写一个O n的算法了
代码 Runtime 38 ms Beats 98.63% Memory41.3 MB Beats 34.99%
class Solution {
public:int firstMissingPositive(vectorint nums) {bool vis[100005]{0};int nnums.size();for(int i0;in;i){if(nums[i]100000||nums[i]0)continue;vis[nums[i]]1;}for(int i1;i100001;i){if(vis[i]0)return i;}return 0;}
};
另一道题 涉及位运算
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列找出 0 .. n 中没有出现在序列中的那个数。
输入: [3,0,1] 输出: 2
输入: [9,6,4,2,3,5,7,0,1] 输出: 8
运用位运算来完成思路为temp ^ nums[ i ] ^ (i 1),这里的temp值从0开始因为nums 的值是从0开始而i 1则是为了取到自然数1,2,3,4,5...等。运算规则如下假如目标数组nums 值 为 0124 自然数对应为1,2,3,4
0 ^ 1 ^ 0 1
1 ^ 2 ^ 1 2
2 ^ 3 ^ 2 3
3 ^ 4 ^ 4 3
返回值为3 缺失的数字即为3
class Solution {
public:int firstMissingPositive(vectorint nums) {int temp 0;for(int i 0;i nums.size();i){temp temp ^ (i 1) ^ (nums[i]);}return temp;}
}; 42. Trapping Rain Water
题意给一组正整数数组表示宽度为1的砖块的高度问能存多少水
我的思路
费案1
单调栈同时要记录下每个砖块的距离所以栈里面存的是序号一层一层的扫描首先是y等于1之间的砖块之后是y2之间的砖块
假设是9 6 2 0 3 0 2 5 就是先9和6和3和0放入栈中【如果一开始是0就不放进去了】
height【i】3来了把0弹出来那么就直接弹出之后栈顶是2在计算0的那一个步骤ans加上min(目前栈顶2height【i】3)的数值ans2
目前栈顶是2发现小于等于height【i】3那么就直接弹出之后栈顶是6在计算2的那一个步骤ansid的差2 * (height【i】3 - 上一个弹出的数2)的数值ans2当前栈为9 6 3
height【i】0不弹出
height【i】2把0弹出来直接弹出之后栈顶是3在计算0的那一个步骤ansid的差1 * (height【i】2 - 上一个弹出的数0)ans2目前栈为9 6 3 2
height【i】5目前栈顶是2发现小于等于height【i】5直接弹出之后栈顶是3在计算0的那一个步骤所以ansansi7 - top的序号6-1 *height【i】 - 上一个弹出的值2ans0当前栈为9 6 3 ans不对 费案2
用减法先减去砖块占用水的体积
例如1 0 2 0 3 0 2 5 从右向左mx5扫完一遍了假设-1的位置有无限高的墙
所以ans【7--1-1】*5-所有砖块的体积不对 标答 双指针法 竖着加的
和上面的减法的思路差不多但他是一个个竖着加起来
lmax代表最左边的墙rmax代表最右边的墙前两个if表示的是目前的lmax和rmax都不是最高的应该要更新第三个条件如果rmax大于lmaxans加上lmax-h[lpos]第四个条件如果lmax大于rmaxans加上rmax-h[rpos]为什么那么做因为如果整个盆子左边高于右边那么右侧的水肯定能装住如果整个盆子右边高于左边那么左侧的水肯定能装住。 代码 Runtime6 ms Beats 97.75% Memory19.8 MB Beats 53.37%
注意 lposrpos的等号
class Solution {
public:int trap(vectorint h) {int nh.size()-1;int lmaxh[0],rmaxh[n];int lpos1,rposn-1,ans0;while(lposrpos){ //等号if(rmaxh[rpos]){rmaxh[rpos];rpos--;}else if(lmaxh[lpos]){lmaxh[lpos];lpos;}else if(rmaxlmax){ans(lmax-h[lpos]);lpos;}else{ans(rmax-h[rpos]);rpos--;}}return ans;}
}; 标答 前缀和 竖着加的
dp[i]表示从左到右以左边的边作为最高的边每个横坐标 i 能装多少水之后从右到左以右边的边作为最高的边res在每个横坐标 i 上加上min ( 当前的最高 - dp[i] )
代码 Runtime 12 ms Beats 78.67% Memory19.8 MB Beats 53.37%
class Solution {
public:int trap(vectorint h) {int nh.size(),dp[20004]{0};int curmax-1,ans0;for(int i0;in;i){curmaxmax(curmax,h[i]);dp[i]curmax-h[i];}curmax-1;for(int in-1;i0;i--){curmaxmax(curmax,h[i]);ansmin(dp[i],curmax-h[i]);}return ans;}
}; 标答 单调栈 横着加的
和费案1的思路相仿。栈中的数字越来越小如果来了一个大的数把这个数弹出设cur是这个弹出的数diff的序号的差ansmin(当前栈顶的数height[i] ) - 上一个弹出的数*序号的差 为什么想费案1的时候没有想出来呢 height【i】5目前栈顶是2发现小于等于height【i】5直接弹出之后栈顶是3在计算0的那一个步骤所以ansansi7 - top的序号6-1 *height【i】 - 上一个弹出的值2ans0当前栈为9 6 3 因为从最上面的图中可以看出之前的步骤都是ansmin(当前栈顶的数height[i] ) - 上一个弹出的数但是当h[i]5时ans当前栈顶的数 上一个弹出的数没有办法把公式统一起来所以没做出来明明只要加上取最小就可以了 为什么是取最小呢 原理和标答1的原理是差不多的因为答案是和两侧最小的那一条有关 补充 1. 费案1中的栈根本不需要pair结构因为有序号有数组就知道了数值了 2. if(st.empty())break;这条语句是指左边没有边可以作为盘子的左边了装不下水了所以break了 代码 Runtime 12 ms Beats 78.67% Memory19.8 MB Beats 53.37%
class Solution {
public:int trap(vectorint h) {stackint st;int nh.size(),ans0;for(int i0;in;i){while(!st.empty()h[st.top()]h[i]){//弹出操作int tempst.top();st.pop();if(st.empty())break;//注意这句话int chai-st.top()-1;//注意这里是-1ans(min(h[i],h[st.top()])-h[temp])*cha;}st.push(i);}return ans;}
}; 45. Jump Game II
题意有n个序号从0开始的数组你可以从num[i]向右跳到【num[i]num[ij]】之间
我的思路
动态规划dp表示需要最少的次数一开始初始化为无穷dp[n-1]0最外层循环是i从n-1到0第二层循环是j从1到num[i]找到循环中最小的dp[ij]dp[i]min( dp[ i j ] 1 )返回答案dp[0]
但不幸的是n是1e4nums是1e3时间复杂度1e7
代码 Runtime128 ms Beats 39.88% Memory16.8 MB Beats 41.3%
class Solution {
public:int jump(vectorint nums) {int nnums.size();int dp[10004];for(int i0;in;i)dp[i]9999;dp[n-1]0;for(int in-2;i0;i--){int minn9999;for(int j1;jnums[i] ijn;j) minnmin(minn,dp[ij]);dp[i]minn1;}return dp[0];}
};
要优化的话肯定是优化第二个循环快速找到某个范围内的最小值想到树状数组去看了看树状数组的板子找到的树状数组代码维护的是【1i】范围的最小值网上说只有树状数组套树状数组或者线段树才可以达到动态维护区间最小值
但是线段树要从1开始建立同时修改的时候不是单纯的增减而是直接替换所以线段树也不适合
标答 贪心 为什么可以用贪心算法呢 乍一看想到动态规划去了才发现忽略了最大步长的信息没有的话就是DP了因此不需要考虑跳多了的情况而且题面能够保证绝对能到达所以不用担心0步长的情形跳不出去啦。 因此本题可以直接使用贪心算法向后遍历找出能够跳的最远的选择。 贪心最麻烦的地方就是全局最优解的证明我这里给出一个简单的思路从同一个起点出发如果当前选择不是贪心选择的那么下一个选择必然比贪心方案跳的更近。完成一次跳跃后有两种情形贪心方案的第二次选择的位置是否存在于当前方案的第二次选择中。存在则最多选择这个方案此时当前方案会比贪心方案段第二次选择一样但是第一次选择短了不存在那么肯定是会短的两次选择都短。 参考链接https://blog.csdn.net/cary_leo/article/details/115451900 简单来说就是比谁跳的远
代码 Runtime 8 ms Beats 95.22% Memory16.6 MB Beats 64.1%
class Solution {
public:int jump(vectorint nums) {int nnums.size(),ans0;for(int i1;in;i){//要么选择在这一格跳走要么就留在这里nums[i]max(nums[i-1],nums[i]i);//nums代表在i位置可以到达的最远的位置}int st0;while(stn-1){ans; stnums[st];}return ans;}
};
46. Permutations
题意有一个数组里面的数字各不相同返回所有排列
我的思路
用dfs做没写出来我好像还记得C库中有个直接全排列的调用
标答 dfs 回溯法
照着我写坏的和表达对照一下我用了两次dfs一次是没取走数字一次是取走了数字不需要没取走数字的那一组因为他会因为个数不够而不能加入最终答案的vector所以只要取走的那一次dfs就可以了
代码 Runtime 6 ms Beats 18.86% Memory8.2 MB Beats 11.7%
class Solution {
public:void dfs(vectorint nums,vectorint pol,vectorvectorint ans,vectorint vis){if(pol.size()nums.size()){ans.push_back(pol);return;}for(int i0;inums.size();i){if(vis[i]) continue;vis[i]1;pol.push_back(nums[i]);dfs(nums,pol,ans,vis);pol.pop_back();vis[i]0;}}vectorvectorint permute(vectorint nums) {vectorint pol; vectorvectorint ans; vectorint vis((int)nums.size(),0);dfs(nums,pol,ans,vis);return ans;}
};
标答 dfs 交换
确实不断交换就可以排序完成了还不会有多余的没到个数的pol和上一个做法不同
代码 Runtime 5 ms Beats 29.21% Memory 7.5 MB Beats 81.96%
class Solution {
public:vectorvectorint result;void permutation(vectorint nums,int i,int n){if(in){result.push_back(nums);return ;}for(int ji;jn;j){swap( nums[i],nums[j]);permutation(nums,i1,n);//注意这里是i1swap( nums[i],nums[j]);}}vectorvectorint permute(vectorint nums) {permutation(nums,0,nums.size()-1);return result;}
}; 48. Rotate Image
题意将整个矩阵顺时针旋转90度注意不要新开一个矩阵
我的思路
按照这个顺序一个圈层只要3组交换就可以了实际操作的时候注意 i 和 j 的范围 例子1初始 1 2 3 4 5 6 7 8 9 第一次 7 2 3 8 5 6 9 4 1 第二次 7 2 1 8 5 4 9 6 3 第三次 7 4 1 8 5 2 9 6 3 例子2初始 4 8 3 6 第一次 3 8 6 4 第二次 3 4 6 8 第三次 循环直接结束了 代码 Runtime 0 ms Beats 100% Memory 7.2 MB Beats 14.63%
class Solution {
public:void rotate(vectorvectorint matrix) {int nmatrix.size();for(int i0;in/2;i){//圈层for(int ji;jn-i;j){swap(matrix[j][i],matrix[n-1-i][j]);}for(int ji1;jn-i;j){swap(matrix[n-1-i][j],matrix[n-1-j][n-1-i]);}for(int ji1;jn-1-i;j){swap(matrix[i][j],matrix[j][n-1-i]);}}}
};
标答 思维
先对角反转之后逆向 例子1初始 1 2 3 4 5 6 7 8 9 第一次 1 4 7 2 5 8 3 6 9 第二次 7 4 1 8 5 2 9 6 3 代码 Runtime 0 ms Beats 100% Memory7.3 MB Beats14.63%
class Solution {
public:void rotate(vectorvectorint matrix) {int n matrix.size();int m matrix[0].size();vectorvectorint temp(n, vectorint(m, 0));for(int i0; in; i){for(int j0; ji; j){swap(matrix[i][j], matrix[j][i]);}}for(int i0; in; i){reverse(matrix[i].begin(), matrix[i].end());}}
}; 49. Group Anagrams
题意给一组字符串把字母相同的字符串放在一组里
我的思路
只能想到死做就是map映射key是字典序排列value是vectorstring之后遍历map组成答案
代码 Runtime 30 ms Beats83.8% Memory20.8 MB Beats 30.73%
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {mapstring,vectorstring mp;int nstrs.size();for(int i0;in;i){string tmpstrs[i];sort(tmp.begin(),tmp.end());mp[tmp].push_back(strs[i]);}vector vectorstring ans;for(auto q:mp)ans.push_back(q.second);return ans;}
};
优化
看了标答确实是这样做的但是sort和map和遍历可以优化map改成unorder_mapfor(auto q:mp)加上引用【这一步突然时间少一半】
代码 Runtime 15 ms Beats 99.87% Memory19.5 MB Beats 84.31%
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring,vectorstring mp;int nstrs.size();for(int i0;in;i){string tmpstrs[i];sort(tmp.begin(),tmp.end());mp[tmp].push_back(strs[i]);}vector vectorstring ans;for(auto q:mp)ans.push_back(q.second);return ans;}
}; 51. N-Queens
题意皇后攻击的范围是所属的横线、竖线、斜线在n*n的棋盘上摆放皇后使得n个皇后不会互相攻击
我的思路
递归
代码 Runtime4 ms Beats 78.35% Memory7.8 MB Beats 36.39%
class Solution {
public:bool check(int n,int id, int j, vectorintpol){for(int i0;ipol.size();i)if(pol[i]j) return 0;for(int i0;ipol.size();i){if(pol[i]-i j-id)return 0;}for(int i0;ipol.size();i){if(pol[i]i jid)return 0;}return 1;}void se(int n,int id, vectorintpol, vectorvectorstring result) {if(pol.size()n){vectorstring mp;for(int j0;jn;j){//列string s (n, .);s[pol[j]]Q;mp.push_back(s);}result.push_back(mp);return;}for(int j0;jn;j){//列if(!check(n,id,j,pol))//判断这一列上有无其他数字判断斜线上有无其他数字;如果不可以放在这里就跳过continue;pol.push_back(j);se(n,id1,pol,result);pol.pop_back();}}vectorvectorstring solveNQueens(int n) {vectorint pol; vectorvectorstring result;//假设返回的vectorint表示每一行的皇后放在第n列se(n,0,pol,result);//id代表在第几行return result;}
};
优化 位运算 没看懂
10394 用位运算速解 n 皇后问题 - 知乎 (zhihu.com)
class Solution {
public:vector vector string ans;void solve(int n, int row, int colMask, int leftDiagMask, int rightDiagMask, vector string board) {if (row n) {ans.push_back(board);return;}int rowState (colMask | leftDiagMask | rightDiagMask) ((1 n) - 1);int safePos rowState ^ ((1 n) - 1);while (safePos) {int queenPos safePos (-safePos);safePos - queenPos;if (!(queenPos rowState)) {board[row][log2(queenPos)] Q;solve(n, row 1, colMask | queenPos, (leftDiagMask | queenPos) 1, (rightDiagMask | queenPos) 1, board);board[row][log2(queenPos)] .;}}}vectorvectorstring solveNQueens(int n) {vector string board(n, string (n, .));solve(n, 0, 0, 0, 0, board);return ans;}
};
