53. Maximum Subarray?

題意：一個數組，找到和最大的子串

我的思路

我記得好像On的動態規劃來做的？但是想不起來了，先死做，用 $O(n^2)$ 的前綴和——TLE超時

那就只能想想dp怎么做了

假設dp[i]表示的是以 i 為右端點的最大的子串，dp[0]是自己；

i=1時，如果dp[0]小于0，dp[1]=nums[1]，否則dp[1]=dp[0]+nums[1]

i=2時，如果dp[1]小于0，dp[2]=nums[2]，否則dp[2]=dp[2-1]+nums[2]

所以狀態轉移方程為：如果dp[i - 1]小于0，dp[ 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(vector<int>& nums) {int n=nums.size();int maxx=nums[0];for(int i=1;i<n;i++){if(nums[i-1]>0) nums[i]=nums[i]+nums[i-1];maxx=max(maxx,nums[i]);}return maxx;}
};

如果想跟快的話，取消同步 Runtime 50 ms Beats 99.91% Memory 67.7 MB Beats 81.53%

class Solution {
public:int maxSubArray(vector<int>& nums) {ios_base::sync_with_stdio(false);cin.tie(NULL);    cout.tie(NULL);int n=nums.size();int maxx=nums[0];for(int i=1;i<n;i++){if(nums[i-1]>0) nums[i]=nums[i]+nums[i-1];maxx=max(maxx,nums[i]);}return maxx;}
};

標答補充分治

看看分治的代碼

分成左右中三個部分，左邊部分是左邊最大的子串和，右邊部分得到右邊最大字串和；

左邊部分是所有包含了m-1位置的字符串的最大子串和 lmax，右邊部分是包含了m+1位置的字符串的最大字串和 rmax，返回max(lmax. rmax )，ml+mr+nums[m]兩者之中大的那一個

代碼?Runtime110 ms Beats 65.10% Memory 67.9 MB Beats 8.86%

class Solution {
public:int maxSubArray(vector<int>& nums) {return maxSubArray(nums, 0, nums.size() - 1);}
private:int maxSubArray(vector<int>& 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:vector<int> spiralOrder(vector<vector<int>>& matrix) {int dy[]={1, 0,-1,0};int dx[]={0, 1, 0,-1};bool vis[19][19]={0};int m=matrix.size(),n=matrix[0].size();int nowx=0,nowy=0,mod=0;int nx=0,ny=0;vector<int> ans;for(int i=0;i<m*n;i++){//首先循環一開始的新來的一定是可以的nowx=nx,nowy=ny;vis[nowx][nowy]=1;ans.push_back(matrix[nowx][nowy]);if(i+1==m*n)break;nx=nowx+dx[mod];ny=nowy+dy[mod];while(nx<0||nx>=m||ny<0||ny>=n||vis[nx][ny]==1){mod=(mod+1)%4;nx=nowx+dx[mod];ny=nowy+dy[mod];}}return ans;}
};

55.?Jump Game

題意：問能不能從索引0到索引n-1

我的思路

既然是問能不能到到終點，用貪心或者動態規劃都可以，上次用了動態規劃，這次就貪心吧

注意：記得?if(nums[0]==0&&n!=1)return 0;要特判

代碼?Runtime 43 ms Beats 93.40% Memory48.3 MB Beats 74.51%

class Solution {
public:bool canJump(vector<int>& nums) {int n=nums.size();if(nums[0]==0&&n!=1)return 0;for(int i=1;i<n-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還有start==end，這個-1和+1怎么做？？

點的話就找一個bool數組特判吧

代碼 Runtime19 ms Beats 99.65% Memory19.2 MB Beats 31.70%

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& in) {int vis[10004]={0};int n=in.size();int maxx=0;bool fl[10004]={0};//判點vector<vector<int>> ans;for(int i=0;i<n;i++){int st=in[i][0],en=in[i][1];maxx=max(maxx,en);if(st==en)fl[st]=1;else vis[st]++,vis[en]--;}int st=0,en=0,sum=0;int mod=1;//mod1是找正數，找到正數了切換mod-1找負數for(int i=0;i<=maxx;i++){sum=sum+vis[i];if(mod==1&&sum>0){st=i;mod=-mod;}else if(mod==-1&&sum==0){en=i;mod=-mod;ans.push_back({st,en});}else if(fl[i]&&mod==1){ans.push_back({i,i});}}return ans;}
};

標答排序

標答的時間復雜度為O(n+logn)

首先將interval排序，應該是按照覆蓋的起點排序，起點從小到大排序；

遍歷每個覆蓋域，首先是第一個覆蓋區域，初始化start和end；之后不斷地找大的end，直到目前最大的end小于新來的start，這時把起點和重點放到答案列表中，更新起點和終點

代碼?Runtime 23 ms Beats 98.10% Memory19 MB Beats 71.5%

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> ans;int n=intervals.size();sort(intervals.begin(),intervals.end());int start=intervals[0][0];int end=intervals[0][1];for(int i=1;i<n;i++){if(end<intervals[i][0]){ans.push_back({start,end});start=intervals[i][0];end=intervals[i][1];}else{end=max(intervals[i][1],end);}}ans.push_back({start,end});return ans;}
};

62.?Unique Paths

題意：機器人只能向下或者向右走，要從grid[0][0]走到grid[m-1][n-1]

我的思路

好像是組合數？按按計算器看看能不能推出來，沒推出來

好像遞歸也是能夠做出來的？不過走樓梯是一維的c[i+1]+c[i+2]得到的？

那么假設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 i=m-1;i>=0;i--)for(int j=n-1;j>=0;j--)st[i][j]+=(st[i+1][j]+st[i][j+1]);return st[0][0];}
};

標答組合數

在這個圖上，一共要走m+n-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 = n+m-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 i=1; i<=r; ++i, N--)res = res*(N)/i;return (int)res;}
};

64.?Minimum Path Sum

題意：二維地圖，只能向下或者向右走，找到所有路徑上的最小的值。

我的思路

這個肯定是dp吧；還是相同的道理，但是要注意邊緣處理

dp[i][j]=num[i][j]+min(dp[i+1][j]，dp[i][j+1])

代碼?Runtime 6?ms Beats 88.72% Memory 9.7 MB Beats 89.19%

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();for(int i=m-1;i>=0;i--){for(int j=n-1;j>=0;j--){if(i==m-1 && j==n-1)continue;if(i==m-1)grid[i][j]+=grid[i][j+1];else if(j==n-1)grid[i][j]+=grid[i+1][j];else grid[i][j]+=min(grid[i+1][j],grid[i][j+1]);}}return grid[0][0];}
};

70.?Climbing Stairs

題意：爬樓梯，只能走1或2步，問到終點要走多少步

我的思路

n=1，c=1；n=2，c=2；n=3，c=3；c[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(n<3) return n;int a=1,b=2,c=0;for(int i=3;i<=n;i++){c=a+b;a=b;b=c;}return c;}
};

72.?Edit Distance

題意：三個操作：插入一個字母，刪除一個字母，替換一個字母；問從字符串1變成字符串2最少需要多少步？

我的思路

（因為之前沒保存，就只貼圖片了）?

標答動態規劃

如果word1[0..i-1）+word2[j-1]=word2[0..j），要在i中插入word2[j-1]，所以dp[i][j]=dp[i][j-1]+1

Q：為什么是dp[i][j]=dp[i][j-1]+1?

????????因為word1[0..i-1）+word2[j-1]=word1[0..i）=word2[0..j），有word2[0..j）之前先有word2[0..j-1）所以知道了word1[0..i-1）如何轉換成word2[0..j-1），因此word1[0..i）轉換為word2[0..j）就是在word1[0..i-1）上增加了一步操作

?所以當word1[i - 1] != word2[j - 1]時，從三種操作中找出最小的那個

代碼?Runtime 23 ms Beats 32.61% Memory7.3 MB Beats 81.80%（ON^2）

class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size(), n=word2.size();int dp[505][505]={0};for(int i=1;i<=m;i++)dp[i][0]=i;//注意初始化的范圍for(int i=1;i<=n;i++)dp[0][i]=i;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];//注意這里的等于號elsedp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;}}return dp[m][n];}
};

接下來把二維數組改成一維數組，從上面的代碼可以看到，只需要dp[i - 1][j - 1]，dp[i][j - 1]?和?dp[i - 1][j]，所以可以用pre數組來代替dp[i-1]

class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();vector<int> pre(n + 1, 0), cur(n + 1, 0);for (int j = 1; j <= n; j++) {//因為是dp[i-1]的初始化，所以長度為word2的長度pre[j] = j;}for (int i = 1; i <= m; i++) {cur[0] = i;for (int j = 1; j <= n; j++) {if (word1[i - 1] == word2[j - 1]) {cur[j] = pre[j - 1];} else {cur[j] = min(pre[j - 1], min(cur[j - 1], pre[j])) + 1;}}fill(pre.begin(), pre.end(), 0);swap(pre, cur);}return pre[n];}
};

最后可以直接將pre數組省略成pre

！代碼?Runtime 7 ms Beats 90.23% Memory 6.3 MB Beats 97.78%

class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size(), pre;vector<int> cur(n + 1, 0);for (int j = 1; j <= n; j++) //初始化cur[j] = j;for (int i = 1; i <= m; i++) {pre = cur[0];cur[0] = i;for (int j = 1; j <= n; j++) {int temp = cur[j];if (word1[i-1] == word2[j-1])cur[j] = pre;else cur[j] = min(pre, min(cur[j - 1], cur[j])) + 1;pre = temp;}}return cur[n];}
};

73.?Set Matrix Zeroes

題意：set its entire row and column to?0

我的思路

方案一創建一個vis用來記錄0，之后按照vis來修改，空間是O(mn)【這肯定做得出來】

方案二設計一個創建一個長為n行的數組a，長為m的數組b；a記錄下0在哪幾行出現，b記錄一下0在哪幾列出現，之后修改，空間 Om+n 同時也符合"devise a constant space solution"

代碼?Runtime 12 ms Beats 80.19% Memory13.3 MB Beats 74.42%

class Solution {
public:void setZeroes(vector<vector<int>>& ma) {int m=ma.size(),n=ma[0].size();bool a[204]={0};bool b[204]={0};for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(ma[i][j]==0){a[i]=1,b[j]=1;}}}for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(a[i]||b[j]) ma[i][j]=0;return ;}
};

標答 O(1)空間復雜度

先把行全部處理了，之后再把列全部處理了

首先遍歷行

代碼?Runtime 3 ms Beats 99.86% Memory13.3 MB Beats 45.87%

void setZeroes(vector<vector<int> > &matrix) {int col0 = 1, rows = matrix.size(), cols = matrix[0].size();for (int i = 0; i < rows; i++) {if (matrix[i][0] == 0) col0 = 0;for (int j = 1; j < cols; j++)if (matrix[i][j] == 0)matrix[i][0] = matrix[0][j] = 0;}for (int i = rows - 1; i >= 0; i--) {for (int j = cols - 1; j >= 1; j--)if (matrix[i][0] == 0 || matrix[0][j] == 0)matrix[i][j] = 0;if (col0 == 0) matrix[i][0] = 0;}
}