最小路径和

问题描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:
输入:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum

思路

基本思路是动态规划。

• 从题目中描述可以看到，每次只能向下或者向右移动一步，所以状态转移方程应该为
  grid[i][j]+=min(grid[i][j-1],grid[i-1][j])
• 本题要求的路径是从左上角到右下角,第一行,和第一列要单独考虑

题解

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        if(m == 0)
            return 0;
        int n=grid[0].size();
        for(int i=1;i<n;i++){
            grid[0][i]+=grid[0][i-1];
        }
        for(int i=1;i<m;i++){
            grid[i][0]+=grid[i-1][0];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]+=min(grid[i][j-1],grid[i-1][j]);
            }
        }
        return grid[m-1][n-1];
    }
};

从中序与后序遍历序列构造二叉树

问题描述：

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

3

/ \
9 20

/  \

15 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

思路：

题解：

旋转图像

问题描述：

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。

说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-image

思路：

本题将图像顺时针旋转90°。
第一步：将二维矩阵转置（将矩阵的行与列交换）
第二部：将矩阵按行翻转

翻转函数：

头文件：#include
reverse(vec.begin(),vec.end());

题解：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                int tmp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=tmp;
            }
        }
       for(int i=0;i<n;i++){
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};

生命游戏

问题描述:

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live（1）即为活细胞， 或 dead（0）即为死细胞。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例:
输入:
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出:
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]
进阶:
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/game-of-life

思路：

题解：

螺旋矩阵

问题描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/spiral-matrix

思路

变量说明：
vector ret 为最后返回的结果，u为螺旋矩阵按照顺时针旋转时开始的上边界，d为下边界，l为左边界，r为右边界

按照顺时针旋转的顺序，向右：i从l到r，ret.push_back(matrixu)，重新定义上边界，u++，如果u>d,跳出循环；向下：i从u到d， ret.push_back(matrixi)，重新定义右边界，r--，如果r>l，跳出循环;向左：i从r到l，ret.push_back(matrixd)，重新定义下边界，d--，如果u>d,跳出循环;向上：i从d到u，ret.push_back(matrixi)，重新定义左边界，l++，如果r>l，跳出循环。

题解

class Solution {，
public:
    vector<int> spiralOrder(vector<vector<int>> &matrix) {
        vector<int> ret;
        int n = matrix.size();
        if (n == 0) return ret;
        int u, d, l, r;
        u = 0;
        l = 0;
        d = n - 1;
        r = matrix[0].size() - 1;
        while (true) {
            for (int i = l; i <= r; i++) {
                ret.push_back(matrix[u][i]);
            }
            u++;
            if(u>d) break;
            for(int i=u;i<=d;i++){
                ret.push_back(matrix[i][r]);
            }
            r--;
            if(r<l) break;
            for(int i=r;i>=l;i--){
                ret.push_back(matrix[d][i]);
            }
            d--;
            if(d<u) break;
            for(int i=d;i>=u;i--){
                ret.push_back(matrix[i][l]);
            }
            l++;
            if(l>r) break;
        }
        return  ret;
    }
};