Leetcode 中 Array Matrix相关的题目

这类题目不算难题，仔细分析题目，第一次作对的概率还是很大的。 即便没有思路，看一下答案和讲解，再次见到也很容易写出。 1. Container With Most Water
两个指针，算面积。竖边长度小的指针往中间移动
2. Valid Sudoku
创建bool三个数据结构，row，col，block分别表示某行/列/块中某个数出现过没有。 3. Trapping Rain Water
每一个柱子，除去最后一个和第一个，都有可能积水。如果它左边和右边都有比他大的柱子，那么他积水的体积取决于那两者的最小值。否则不积水 6. Spiral Matrix
提出层的概念， 每一层的层号（从0开始从外向内），每遍历一层，就去掉外层，行列数分别减2，[k,k]相当于该层左上角元素坐标。这样就好理解了 8. Rotate Image
此题与上一题很相似，但不用递归而是迭代更好些。思路是把每一层的环形表示成四个等长数组（上右下左）依次赋值。也是要先定义层的概念，设为k， 从0到n/2.这样每一层的左上角就是[k][k],这一层top行待换的元素是[k][k]..[k][n-k-1];右侧待换元素是[k][n-k-1]...[n-k-1][n-k-1]... .用offset来表示当前元素到这一组数据首元素的距离 7. Spiral Matrix II
此题比上两题简单，只需一个指针依次遍历即可。注意四个while的用法，向右-向下-向左-向上的顺序访问。 9. Merge Intervals
先按照start排序，插入第一个interval然后依次遍历一遍即可。主要是判断当前interval的start是否比已有的最后一个interval的end小，如果是的话不插入当前intervel，而是把已有的最后一个interval的end值修改位较大的end值。
10. Insert Interval
Insert比Merge 要难。 首先要找到插入点，其次要看是否需要merge。 假设当前考察的Interval[s1,e1], 要插入的是[s2,e2]. 如果e1<s2 那么把[s1,e1]插入结果，考察下一个。否则如果e2<s1, 插入[s2,e2]. 剩下的一切情况都是要merge的 取s1 s2的最小值，e1，e2的最大值，插入。
11. Set Matrix Zeros
此题思路很简单。 遍历矩阵，若[i,j]==0那么 [i,0] 和 [0,j]都要设为0。 再遍历一遍 若[i,0]或者[0,j]为0，要把[i,j]置为0. 需要注意的事一开始要把[0,j][i,0]上有无0记录一下，否则会和后面的操作混淆。 12. Maximum Rectangle
找出面积最大的全是1的矩形。先把每一行上的1累积，这样只需要访问一个点[i][j]就可以知道第i行第j列左边有几个连续的1，然后在考察这一列从上到下的累积。 13. Pascal's Triangle
先手动定义第一行 第二行，剩下的每行第一个和最后一个都是1，中间元素A[i]=B[i-1]+B[1]B是上一行元素数组 14. Pascal's Triangle II
和上题思路一样只不过不要求所有的行，那么可以只用一个数组来完成，注意要从数组的后面加到前面 15. Unique path
从matrix的左上角到右下角，每次只能往下或者往右走一步，How many possible unique paths are there? 16. Unique path II
加入了障碍。1是有障碍，0是没有
17. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).