[11] Container With Most Water [Medium]

O(n^2)的暴力解法直接TLE。

正确的解法是Two Pointers。 O(n)的复杂度。保持两个指针i,j；分别指向长度数组的首尾。如果ai 小于aj，则移动i向后（i++）。反之，移动j向前（j--）。如果当前的area大于了所记录的area，替换之。这个想法的基础是，如果i的长度小于j，无论如何移动j，短板在i，不可能找到比当前记录的area更大的值了，只能通过移动i来找到新的可能的更大面积。

class Solution {
public:
int maxArea(vector& height) {
int i = ;
int j = height.size() - ;
int ans = ;
while(i < j) {
int area = (j - i) * min(height[i], height[j]);
ans = max(ans, area);
if (height[i] <= height[j]) {
++i;
}
else {
--j;
}
}
return ans;
}
};

[15] 3Sum [Medium]

它要求返回结果不重复，所以去重。不能用unique，会TLE，直接在循环里面跳过。

先排序，两根指针，夹逼定理

class Solution {
public:
vector> threeSum(vector& nums) {
vector> result;
if (nums.size() < ) { return result; } sort(nums.begin(), nums.end()); for (int i = ; i < nums.size(); ) { int j = i + ; int k = nums.size() - ; while (j < k) { if (nums[i] + nums[j] + nums[k] == ) { result.push_back(vector{nums[i], nums[j], nums[k]});
++j, --k;
while (j < k && nums[j-] == nums[j]) { ++j; }
while (j < k && nums[k+] == nums[k]) { --k; }
}
else if (nums[i] + nums[j] + nums[k] < ) {
++j;
while (j < k && nums[j-] == nums[j]) { ++j; }
}
else {
--k;
while (j < k && nums[k+] == nums[k]) { --k; }
}
}
++i;
while (nums[i-] == nums[i]) { ++i; }
}
return result;
}
};

[16] 3Sum Closest [Medium]

三个数求和，返回离target最近的和。

Two Pointers， 跟15题一样， 先排序，两根指针左右夹逼。

class Solution {
public:
int threeSumClosest(vector& nums, int target) {
int result = ;
int min_gap = INT_MAX;
sort(nums.begin(), nums.end());
for (int i = ; i < nums.size() - ; ++i) { int start = i + , end = nums.size() - ; while (start < end) { int temp = nums[i] + nums[start] + nums[end]; int gap = abs(temp - target); if (gap < min_gap) { min_gap = gap; result = temp; } if (temp == target) break; if (temp > target) {
--end;
}
else if (temp < target) {
++start;
}
}
}
return result;
}
};

[17] 4Sum [Medium]

四个数求和，求出和target相等的元组， 思路和3sum一个样，包括和去重的方式都一样。

还是先排序，然后两根指针。

class Solution {
public:
vector> fourSum(vector& nums, int target) {
vector> result;
if (nums.size() < ) { return result; } sort(nums.begin(), nums.end()); for (int i = ; i < nums.size()-; ) { for(int j = i+; j < nums.size()-; ) { int start = j + , end = nums.size() - ; while (start < end) { int sum = nums[i] + nums[j] + nums[start] + nums[end]; if (sum == target) { result.push_back(vector{nums[i], nums[j], nums[start], nums[end]});
++start, --end;
while (start < end && nums[start-] == nums[start]) {
++start;
}
while (start < end && nums[end+] == nums[end]) {
--end;
}
}
else if (sum < target) {
++start;
while (start < end && nums[start-] == nums[start]) {
++start;
}
}
else {
--end;
while (start < end && nums[end+] == nums[end]) {
--end;
}
}
}
++j;
while (nums[j-] == nums[j]) { ++j; }
}
++i;
while(nums[i-] == nums[i]) { ++i; }
}
return result;
}
};

[45] Jump Game II [Hard]

这个题需要记忆。再考肯定不会。。。要记忆。。。

给你一个数组，数组元素的值是从当前index最多能往前面移动的步数，求到数组末尾最少移动的步数。

我是参考了这个：https://www.tianmaying.com/tutorial/LC45

/*
将每个位置都看作一个点，并从第i个点向它之后的nums[i]个点都连一条长度为1的有向边，而现在的问题就是从0号点到达size-1号点需要的最短距离，这就是一个很简单的最短路问题，实际上由于边的长度均为1，而且不存在环，我们可以用宽度优先搜索（时间复杂度为O(n^2)，即边数)来进行相关的计算。

不难发现，这道题目转换出的最短路问题存在三个条件：

边的长度均为1
不存在环
连出的边是连续的
我们是不是可以用这三个“很强”的条件来做一些优化呢，答案自然是肯定的！

——如果令f[i]表示从0号点到达i号点的最短路径，那么对于任意i<j，有f[i]<=f[j]，即f是非递减的，这个结论的证明是显然的，在此不作过多赘述。

在有了这样的结论之后，我们就会发现，其实对于f数组来说，它会是一段段的存在，先是一个0，然后是一段1，然后是一段2，依此类推，那么现在问题来了，每一段的长度是多少呢？

这个问题很好回答，如果我们令l[k]表示f数组中值为k的一段的左边界，r[k]表示f数组中值为k的一段的有边界，那么有

l[k] = r[k - 1] + 1，这是显然的
r[k] = max{i + nums[i] | l[k - 1] <= i <= r[k - 1]}，由于f值为k的位置一定是从f值为k-1的位置走来的，所以只需要看从所有f值为k-1的位置里最远可以到达的地方即可。
也就是说，我们可以在对nums的一遍扫描中，依次求出所有的l[k]和r[k]，而f数组也就自然求解出来了——答案也就得到了。
*/

class Solution {
public:
int jump(vector& nums) {
int k = , l = , r = ;
while (r < nums.size()-) {
int next_r = r;
for (int i = l; i <= r; ++i) next_r = max(next_r, nums[i]+i);
++k; l = r + ; r = next_r;
}
return k;
}
};

[48] Rotate Image [Medium]

题目要求一个方阵顺时针旋转90°。

经过研究发现顺时针旋转90°，相当于先转置，再每行逆序。要学会矩阵转置的写法。

class Solution {
public:
void rotate(vector>& matrix) {
const int N = matrix.size();
//trans
for (int i = ; i < N; ++i) {
for (int j = i+; j < N; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}

     //reverse  
     for (int i = ; i < N; ++i) {  
         int start = , end = N - ;  
         while (start < end) {  
             swap(matrix\[i\]\[start++\], matrix\[i\]\[end--\]);  
         }  
     }  
 }  

};

[54] Spiral Matrix [Medium]

打印旋转矩阵。 设置有用的四个变量 beginx, beginy, endx, endy。然后用一个i去遍历。

class Solution {
public:
vector spiralOrder(vector>& matrix) {
vector ans;
if (matrix.size() == ) {
return ans;
}
const int m = matrix.size();
const int n = matrix[].size();
int beginx = , beginy = ;
int endx = n-, endy = m - ;
while (true) {
for (int i = beginx; i <= endx; ++i) { ans.push_back(matrix[beginy][i]); } ++beginy; if (beginy > endy) break;

         for (int i = beginy; i <= endy; ++i) {  
             ans.push\_back(matrix\[i\]\[endx\]);  
         }  
         --endx;  
         if (beginx > endx) break;

         for (int i = endx; i >= beginx; --i) {  
             ans.push\_back(matrix\[endy\]\[i\]);  
         }  
         --endy;  
         if (beginy > endy) break;

         for (int i = endy; i >= beginy; --i) {  
             ans.push\_back(matrix\[i\]\[beginx\]);  
         }  
         ++beginx;  
         if (beginx > endx) break;  
     }  
     return ans;  
 }  

};

[56] Merge Intervals [Hard]

合并线段(数轴) 参考57题。 在 Insert Interval的基础上，一个新的interval集合，然后每次从旧的里面取一个interval出来，然后插入到新的集合中。

/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector merge(vector& intervals) {
vector ans;
if (intervals.size() == ) {
return ans;
}
ans.push_back(intervals[]);
for (int i = ; i < intervals.size(); ++i) { insert_interval(ans, intervals[i]); } return ans; } vector insert_interval(vector& intervals, Interval newInterval) {
vector::iterator it = intervals.begin();
while (it != intervals.end()) {
if (it->start > newInterval.end) {
break;
}
else if (it->end < newInterval.start) { it++; continue; } else { newInterval.start = min(newInterval.start, it->start);
newInterval.end = max(newInterval.end, it->end);
intervals.erase(it);
}
}
intervals.insert(it, newInterval);
return intervals;
}
};

[57] Insert Interval [Hard]

先判断是否能放在最前面，然后在现有的intervals中一个一个遍历。有覆盖就更新newInterval，然后把原本的那段删除。

/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector insert(vector& intervals, Interval newInterval) {
vector::iterator it = intervals.begin();
while (it != intervals.end()) {
if (it->start > newInterval.end) {
break;
}
else if (it->end < newInterval.start) { ++it; continue; } else { newInterval.start = min(it->start, newInterval.start);
newInterval.end = max(it->end, newInterval.end);
intervals.erase(it);
}
}
intervals.insert(it, newInterval);
return intervals;
}
};

[59] Spiral Matrix II [Medium]

跟前一题Spiral Matrix的区别是前一题是遍历， 这个题是造一个矩阵出来。 思路写法都一样。

class Solution {
public:
vector> generateMatrix(int n) {
vector> matrix(n, vector(n, ));
if (n == ) {
return matrix;
}
int number = ;
int beginx = , beginy = , endx = n - , endy = n - ;
while (true) {
for (int i = beginx; i <= endx; ++i) { matrix[beginy][i] = number++; } ++beginy; if (beginy > endy) { break; }

         for (int i = beginy; i <= endy; ++i) {  
             matrix\[i\]\[endx\] = number++;  
         }  
         --endx;  
         if (beginx > endx) { break; }

         for (int i = endx; i >= beginx; --i) {  
             matrix\[endy\]\[i\] = number++;  
         }  
         --endy;  
         if (beginy > endy) { break; }

         for (int i = endy; i >= beginy; --i) {  
             matrix\[i\]\[beginx\] = number++;  
         }  
         ++beginx;  
         if (beginx > endx) { break; }  
     }  
     return matrix;  
 }  

};

[73] Set Matrix Zeroes [Medium]

如果矩阵中一个元素为0， 那么把该元素所在的行和列都置零。O(1)的空间复杂度

思路：有个简单的O(m+n)的空间复杂度的，就是设两个布尔数组，来控制行和列是否为0.

但是如果要降低到O(1)的话，就可以牺牲第0行和第0列来存这两个数组。提前用两个变量保存好第0行，第0列是否置0.

class Solution {
public:
void setZeroes(vector>& matrix) {
const int m = matrix.size();
if (m == ) return;
const int n = matrix[].size();
bool row_has_zero = false;
bool col_has_zero = false;
for (size_t i = ; i < m; ++i) {
if (matrix[i][] == ) {
col_has_zero = true;
break;
}
}
for (size_t j = ; j < n; ++j) {
if (matrix[][j] == ) {
row_has_zero = true;
break;
}
}

     for (size\_t i = ; i < m; ++i) {  
         for (size\_t j = ; j < n; ++j) {  
             if (matrix\[i\]\[j\] == ) {  
                 matrix\[i\]\[\] = ;  
                 matrix\[\]\[j\] = ;  
             }  
         }  
     }

     for (size\_t i = ; i < m; ++i) {  
         for (size\_t j = ; j < n; ++j) {  
             if (matrix\[i\]\[\] ==  || matrix\[\]\[j\] == ) {  
                 matrix\[i\]\[j\] = ;  
             }  
         }  
     }

     if (col\_has\_zero == true) {  
         for (size\_t i = ; i < m; ++i) {  
             matrix\[i\]\[\] = ;  
         }  
     }

     if (row\_has\_zero == true) {  
         for (size\_t j = ; j < n; ++j) {  
             matrix\[\]\[j\] = ;  
         }  
     }  
     return;  
 }  

};

[118] Pascal's Triangle [Easy]

class Solution {
public:
vector> generate(int numRows) {
vector> ans;
if (numRows == ) return ans;
for (size_t i = ; i < numRows; ++i) { vector ans_row(i+, );
if (i == || i == ) {
ans.push_back(ans_row);
continue;
}
for (size_t j = ; j < i ; ++j) {
ans_row[j] = ans[i-][j-] + ans[i-][j];
}
ans.push_back(ans_row);
}
return ans;
}
};

[119] Pascal's Triangle II [Easy]

只要求O(k)的额外空间。我自己写的解法用了两个数组，其实一个就够了。

class Solution {
public:
vector getRow(int rowIndex) {
vector ans(rowIndex+, );
vector help(rowIndex+, );
if (rowIndex == || rowIndex == ) {
return ans;
}
for (size_t i = ; i < rowIndex+; ++i) {
help = ans;
for (size_t j = ; j < i; ++j) {
ans[j] = help[j-] + help[j];
}
ans[i] = ;
}
return ans;
}
};

一个数组的还没看懂（好困，睡了==）

class Solution {
public:
vector getRow(int rowIndex) {
vector A(rowIndex+, );
A[] = ;
for(int i=; i=; j--)
A[j] += A[j-];
return A;
}
};