0619学习

agile Posted on Jun 20 2023

面试 leetcode学习

-   螺旋矩阵-54
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

---

```C#
public IList<int> SpiralOrder(int[][] matrix)
{
    var list = new List<int>();

var row = matrix.Length;
    var column = matrix[0].Length;

var indexMinRow = 0;
    var indexMaxRow = row - 1;
    var indexMinColumn = 0;
    var indexMaxColumn = column - 1;
    while (true)
    {
        if (indexMinColumn <= indexMaxColumn)
        {
            for (int i = indexMinColumn; i <= indexMaxColumn; i++)
            {
                list.Add(matrix[indexMinRow][i]);
            }

indexMinRow++;
        }
        else
        {
            break;
        }

if (indexMinRow <= indexMaxRow)
        {
            for (int i = indexMinRow; i <= indexMaxRow; i++)
            {
                list.Add(matrix[i][indexMaxColumn]);
            }

indexMaxColumn--;
        }
        else
        {
            break;
        }

if (indexMinColumn <= indexMaxColumn)
        {
            for (int i = indexMaxColumn; i >= indexMinColumn; i--)
            {
                list.Add(matrix[indexMaxRow][i]);
            }

indexMaxRow--;
        }
        else
        {
            break;
        }

if (indexMinRow <= indexMaxRow)
        {
            for (int i = indexMaxRow; i >= indexMinRow; i--)
            {
                list.Add(matrix[i][indexMinColumn]);
            }

indexMinColumn++;
        }
        else
        {
            break;
        }
    }

return list;
}
```

-   旋转图像-48
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

---

```C#
public void Rotate(int[][] matrix)
{
    var size = matrix.Length;
    var min = 0;
    var max = size - 1;
    while (min < max)
    {
        for (var i = min; i < max; i++)
        {
            var left = matrix[min][i];
            var maxIndex = max - i + min;
            matrix[min][i] = matrix[maxIndex][min];
            matrix[maxIndex][min] = matrix[max][maxIndex];
            matrix[max][maxIndex] = matrix[i][max];
            matrix[i][max] = left;
        }

min++;
        max--;
    }
}
```

---
首先，需要理解基础的对称操作，对于 nxn 的矩阵 matrix，各种对称的转移式如下：

```
上下对称：matrix[i][j] -> matrix[n-i-1][j]，（列不变）
左右对称：matrix[i][j] -> matrix[i][n-j-1]，（行不变）
主对角线对称：matrix[i][j] -> matrix[j][i]，（行列互换）
副对角线对称：matrix[i][j] -> matrix[n-j-1][n-i-1] （行列均变，且互换）
```

那么，对于顺时针 90° 旋转，即本题，先写出转移式： matrix[i][j] -> matrix[j][n-i-1]， 可以观察到，我们希望原来的列j不变，且要交换行列位置。 因此可以分解为：上下对称 + 主对角线对称 或者 主对角线对称 + 左右对称， 注意分解顺序是不能换的。

对于顺时针 180° 旋转，可视为两次顺时针 90° 旋转：
```
顺时针 90° + 顺时针 90° 
= 上下对称 + 主对角线对称 + 主对角线对称 + 左右对称
= 上下对称 + 左右对称 （主对角线对称抵消）
```

这里也可根据顺时针 180° 的转移式： matrix[i][j] -> matrix[n-i-1][n-j-1]， 分解为 主对角线对称 + 副对角线对称。

再往后，顺时针 270°，这个可以分解为：

```
顺时针 180° + 顺时针 90° 
= 左右对称 + 上下对称 + 上下对称 + 主对角线对称
= 左右对称 + 主对角线对称 （上下对称抵消）
```

另外，也可转换为逆时针 90° 来做。
最后，顺时针 360° 即原图。

对于逆时针也是同样的道理，比如逆时针 90° 旋转，转移式为： matrix[i][j] -> matrix[n-j-1][i]， 可以观察到，我们希望原来的行i不变，且要交换行列位置。 因此可以分解为：左右对称 + 主对角线对称 或者 主对角线对称 + 上下对称。

```C#
public void Rotate2(int[][] matrix)
{
    var size = matrix.Length;
    //上下翻转
    for (var i = 0; i < size / 2; i++)
    {
        for (var j = 0; j < size; j++)
        {
            (matrix[i][j], matrix[size - 1 - i][j]) = (matrix[size - 1 - i][j], matrix[i][j]);
        }
    }

//左大右小斜对角线翻转
    for (int i = 0; i < size; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
        }
    }
}

public void Rotate3(int[][] matrix)
{
    var size = matrix.Length;
    //左右翻转
    for (var i = 0; i < size; i++)
    {
        for (var j = 0; j < size / 2; j++)
        {
            (matrix[i][j], matrix[i][size - j - 1]) = (matrix[i][size - j - 1], matrix[i][j]);
        }
    }

//右大左小斜对角线翻转
    for (var i = 0; i < size; i++)
    {
        for (var j = 0; j < size - i - 1; j++)
        {
            (matrix[i][j], matrix[size - j - 1][size - i - 1]) = (matrix[size - j - 1][size - i - 1], matrix[i][j]);
        }
    }
}
```