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}$$

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex+1);
        ans[0]=1;
        for(int i=1;i<=rowIndex;i++){
            ans[i]=1LL*ans[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, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

link

解题思路

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

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

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

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

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

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

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

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]]

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int top=0,right=n-1,left=0,down=n-1;
        int k=1;
        vector<vector<int>> ans(n,vector<int>(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;
    }
};