创建商城app,整站seo哪家服务好,泉州制作网站开发,北京高端定制网站建设53. Maximum Subarray
题意#xff1a;一个数组#xff0c;找到和最大的子串
我的思路
我记得好像On的动态规划来做的#xff1f;但是想不起来了#xff0c;先死做#xff0c;用的前缀和——TLE超时
那就只能想想dp怎么做了
假设dp[i]表示的是以 i 为右端点的最大的…53. Maximum Subarray
题意一个数组找到和最大的子串
我的思路
我记得好像On的动态规划来做的但是想不起来了先死做用的前缀和——TLE超时
那就只能想想dp怎么做了
假设dp[i]表示的是以 i 为右端点的最大的子串dp[0]是自己
i1时如果dp[0]小于0dp[1]nums[1]否则dp[1]dp[0]nums[1]
i2时如果dp[1]小于0dp[2]nums[2]否则dp[2]dp[2-1]nums[2]
所以状态转移方程为如果dp[i - 1]小于0dp[ i ]nums[ i ]否则dp[ i ]dp[i -1]nums[ i ]
On解决同时dp换成nums还能更省空间
代码 Runtime 87 ms Beats 78.76% Memory67.9 MB Beats 8.86%
class Solution {
public:int maxSubArray(vectorint nums) {int nnums.size();int maxxnums[0];for(int i1;in;i){if(nums[i-1]0) nums[i]nums[i]nums[i-1];maxxmax(maxx,nums[i]);}return maxx;}
}; 如果想跟快的话取消同步 Runtime 50 ms Beats 99.91% Memory 67.7 MB Beats 81.53%
class Solution {
public:int maxSubArray(vectorint nums) {ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int nnums.size();int maxxnums[0];for(int i1;in;i){if(nums[i-1]0) nums[i]nums[i]nums[i-1];maxxmax(maxx,nums[i]);}return maxx;}
};
标答补充 分治
看看分治的代码
分成左右中三个部分左边部分是左边最大的子串和右边部分得到右边最大字串和
左边部分是所有包含了m-1位置的字符串的最大子串和 lmax右边部分是包含了m1位置的字符串的最大字串和 rmax返回max(lmax. rmax )mlmrnums[m]两者之中大的那一个
代码 Runtime110 ms Beats 65.10% Memory 67.9 MB Beats 8.86%
class Solution {
public:int maxSubArray(vectorint nums) {return maxSubArray(nums, 0, nums.size() - 1);}
private:int maxSubArray(vectorint nums, int l, int r) {if (l r) return INT_MIN;int m l (r - l) / 2, ml 0, mr 0;int lmax maxSubArray(nums, l, m - 1);int rmax maxSubArray(nums, m 1, r);for (int i m - 1, sum 0; i l; i--) {sum nums[i];ml max(sum, ml);}for (int i m 1, sum 0; i r; i) {sum nums[i];mr max(sum, mr);}return max(max(lmax, rmax), ml mr nums[m]);}
}; 54. Spiral Matrix
题意 我的思路
死做
代码 Runtime 0 ms Beats 100% Memory6.9 MB Beats 61.55%
class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {int dy[]{1, 0,-1,0};int dx[]{0, 1, 0,-1};bool vis[19][19]{0};int mmatrix.size(),nmatrix[0].size();int nowx0,nowy0,mod0;int nx0,ny0;vectorint ans;for(int i0;im*n;i){//首先循环一开始的新来的一定是可以的nowxnx,nowyny;vis[nowx][nowy]1;ans.push_back(matrix[nowx][nowy]);if(i1m*n)break;nxnowxdx[mod];nynowydy[mod];while(nx0||nxm||ny0||nyn||vis[nx][ny]1){mod(mod1)%4;nxnowxdx[mod];nynowydy[mod];}}return ans;}
}; 55. Jump Game
题意问能不能从索引0到索引n-1
我的思路
既然是问能不能到到终点用贪心或者动态规划都可以上次用了动态规划这次就贪心吧
注意记得 if(nums[0]0n!1)return 0;要特判
代码 Runtime 43 ms Beats 93.40% Memory48.3 MB Beats 74.51%
class Solution {
public:bool canJump(vectorint nums) {int nnums.size();if(nums[0]0n!1)return 0;for(int i1;in-1;i){nums[i]max(nums[i]i,nums[i-1]);if(nums[i]i)return 0;}return 1;}
}; 56. Merge Intervals
题意返回重叠部分 我的思路
应该是要维护两端端点的好像是-1 1什么的
做着做着发现这个interval还有startend这个-1和1怎么做
点的话就找一个bool数组特判吧
代码 Runtime19 ms Beats 99.65% Memory19.2 MB Beats 31.70%
class Solution {
public:vectorvectorint merge(vectorvectorint in) {int vis[10004]{0};int nin.size();int maxx0;bool fl[10004]{0};//判点vectorvectorint ans;for(int i0;in;i){int stin[i][0],enin[i][1];maxxmax(maxx,en);if(sten)fl[st]1;else vis[st],vis[en]--;}int st0,en0,sum0;int mod1;//mod1是找正数找到正数了切换mod-1找负数for(int i0;imaxx;i){sumsumvis[i];if(mod1sum0){sti;mod-mod;}else if(mod-1sum0){eni;mod-mod;ans.push_back({st,en});}else if(fl[i]mod1){ans.push_back({i,i});}}return ans;}
};
标答 排序
标答的时间复杂度为O(nlogn)
首先将interval排序应该是按照覆盖的起点排序起点从小到大排序
遍历每个覆盖域首先是第一个覆盖区域初始化start和end之后不断地找大的end直到目前最大的end小于新来的start这时把起点和重点放到答案列表中更新起点和终点
代码 Runtime 23 ms Beats 98.10% Memory19 MB Beats 71.5%
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint ans;int nintervals.size();sort(intervals.begin(),intervals.end());int startintervals[0][0];int endintervals[0][1];for(int i1;in;i){if(endintervals[i][0]){ans.push_back({start,end});startintervals[i][0];endintervals[i][1];}else{endmax(intervals[i][1],end);}}ans.push_back({start,end});return ans;}
}; 62. Unique Paths
题意机器人只能向下或者向右走要从grid[0][0]走到grid[m-1][n-1]
我的思路
好像是组合数按按计算器看看能不能推出来没推出来
好像递归也是能够做出来的不过走楼梯是一维的c[i1]c[i2]得到的
那么假设c是方案数就先按照下面这个图建立一个二维数组做
【看标答这种方法居然是dp】 代码 Runtime 0 ms Beats 100% Memory6 MB Beats 87.9%
class Solution {
public:int uniquePaths(int m, int n) {int st[104][104]{0};st[m-1][n-1]1;for(int im-1;i0;i--)for(int jn-1;j0;j--)st[i][j](st[i1][j]st[i][j1]);return st[0][0];}
}; 标答 组合数
在这个图上一共要走mn-2步其中有m-1步是向下的n-1步是向右的这可以转换成m-1个向下和n-1个向右的排序图源知乎 代码 Runtime 0 ms Beats 100.00% Memory 6 MB Beats 87.9%
class Solution {
public:int uniquePaths(int m, int n) {int N nm-2; // total steps n-1 m-1int r min(n,m)-1;
// will iterate on the minimum for efficiency (total) C (min(right, down)double res 1;// compute nCrfor(int i1; ir; i, N--)res res*(N)/i;return (int)res;}
}; 64. Minimum Path Sum
题意二维地图只能向下或者向右走找到所有路径上的最小的值。
我的思路
这个肯定是dp吧还是相同的道理但是要注意边缘处理
dp[i][j]num[i][j]min(dp[i1][j]dp[i][j1]) 代码 Runtime 6 ms Beats 88.72% Memory 9.7 MB Beats 89.19%
class Solution {
public:int minPathSum(vectorvectorint grid) {int mgrid.size(),ngrid[0].size();for(int im-1;i0;i--){for(int jn-1;j0;j--){if(im-1 jn-1)continue;if(im-1)grid[i][j]grid[i][j1];else if(jn-1)grid[i][j]grid[i1][j];else grid[i][j]min(grid[i1][j],grid[i][j1]);}}return grid[0][0];}
}; 70. Climbing Stairs
题意爬楼梯只能走1或2步问到终点要走多少步
我的思路
n1c1n2c2n3c3c[i]c[i-1]c[i-2]
代码 Runtime 0 ms Beats 100% Memory 5.9 MB Beats 94.85%
class Solution {
public:int climbStairs(int n) {if(n3) return n;int a1,b2,c0;for(int i3;in;i){cab;ab;bc;}return c;}
}; 72. Edit Distance
题意三个操作插入一个字母删除一个字母替换一个字母问从字符串1变成字符串2最少需要多少步
我的思路
应该是用动态规划
假设
