119 Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

link

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

解题思路

由多项式的展开规律可知，n次多项式的第i项系数为C_n^i；由此可以写出递推式如下：

\begin{equation}\begin{aligned}C_{n}^{i}&=\frac{n!}{i!\times (n-i)!}\\&=\frac{n!}{(i-1)!\times (n-i+1)!}\times \frac{n-i+1}{i}\\&=C_{n}^{i-1}\times \frac{n-i+1}{i}\end{aligned}\end{equation}

```C++ class Solution { public: vector getRow(int rowIndex) { vector ans(rowIndex+1); ans[0]=1; for(int i=1;i<=rowIndex;i++){ ans[i]=1LLans[i-1](rowIndex-i+1)/i;//乘以1LL先将计算结果转换为long long，等号赋值时再转换回INT } return ans; } };

# 48 Rotate Image

You are given an `n x n` 2D `matrix` representing an image, rotate the image by **90** degrees (clockwise).

You have to rotate the image [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm), which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

<a href="https://leetcode.cn/problems/rotate-image/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=1hi0xhg">link</a>

## 解题思路

对于矩阵中的每一行旋转，可得如下等式

$$M[row][:]=M[:][n-row+1]$$

对于矩阵中的每一列旋转，可得如下等式

$$M[:][column]=M[column][:]$$

所以，对于row行column列的元素有

$$M[row][column]=M[column][n-row+1]$$

从上述等式，可以发现，我们可以通过水平轴翻转加主对角线翻转的方式达到旋转90度的效果

```c++
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

59. Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:

Input: n = 1
Output: [[1]]

```c++ class Solution { public: vector<vector> generateMatrix(int n) { int top=0,right=n-1,left=0,down=n-1; int k=1; vector<vector> ans(n,vector(n)); while(k<=(n*n)){ for(int i=left;i<=right;i++,k++) ans[top][i]=k; top++; for(int i=top;i<=down;i++,k++) ans[i][right]=k; right--; for(int i=right;i>=left;i--,k++) ans[down][i]=k; down--; for(int i=down;i>=top;i--,k++) ans[i][left]=k; left++; } return ans; } };