1. 01 matrix
   Given a matrix consisting of 0 and 1, find the distance from each element to the nearest 0. The distance between two adjacent elements is 1.

The solution is obtained by dynamic programming

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // Initialize the array of dynamic programming, and set all distance values to a large number
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX / 2));
        // If the element of (i, j) is 0, the distance is 0
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    dist[i][j] = 0;
                }
            }
        }
        // Only move horizontally to the left and vertically upward. Pay attention to the calculation order of dynamic programming
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }
        // Only move horizontally to the right and vertically down. Pay attention to the calculation order of dynamic programming
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i + 1 < m) {
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        return dist;
    }
};

1. Diameter of binary tree
   Given a binary tree, you need to calculate its diameter and length. The diameter length of a binary tree is the maximum of any two node path lengths. This path may or may not pass through the root node.

Depth first traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // Null node accessed, return 0
        }
        int L = depth(rt->left); // The depth of the subtree with the left son as the root
        int R = depth(rt->right); // The depth of the subtree whose right son is the root
        ans = max(ans, L + R + 1); // Calculation d_node is L+R+1 and updates ans
        return max(L, R) + 1; // Returns the depth of the subtree whose node is the root
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

1. Remove box
   Give some boxes of different colors. The color of the box is represented by numbers, that is, different numbers represent different colors. You will go through several rounds of operations to remove the box until all the boxes are removed. In each round, you can remove k consecutive boxes with the same color (k > = 1), and after this round, you will get k * k points. When you remove all the boxes, find the maximum sum of points you can get.

This problem can be solved by dynamic programming. dp[l][r][k] represents the interval from L to r, and the maximum integral sum when there are k same elements after r. This is necessary because the score depends not only on the subsequence, but also on the impact of the previous movement on the current array, which may make the final subsequence not a continuous substring

class Solution {
public:
    int dp[100][100][100];

    int removeBoxes(vector<int>& boxes) {
        memset(dp, 0, sizeof dp);
        return calculatePoints(boxes, 0, boxes.size() - 1, 0);
    }

    int calculatePoints(vector<int>& boxes, int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        if (dp[l][r][k] == 0) {
            dp[l][r][k] = calculatePoints(boxes, l, r - 1, 0) + (k + 1) * (k + 1);
            for (int i = l; i < r; i++) {
                if (boxes[i] == boxes[r]) {
                    dp[l][r][k] = max(dp[l][r][k], calculatePoints(boxes, l, i, k + 1) + calculatePoints(boxes, i + 1, r - 1, 0));
                }
            }
        }
        return dp[l][r][k];
    }
};

1. Number of provinces

Take DFS/BFS traversal

class Solution {
public:
    void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = 1;
                dfs(isConnected, visited, provinces, j);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> visited(provinces);
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, provinces, i);
                circles++;
            }
        }
        return circles;
    }
};

1. Student attendance record
   If A student has no more than one 'A' (absence) and no more than two consecutive 'L' (late) in his attendance record, the student will be rewarded.
   You need to judge whether the student will be rewarded according to his attendance record.

Go through it and judge it

class Solution {
public:
    bool checkRecord(string s) 
    {
        int absent = 0, lateContinue = 0;

        for (auto c : s)
        {
            if (c == 'A')
            {
                lateContinue = 0;
                absent++;
                if (absent > 1) return false;
            }
            else if (c == 'L')
            {
                lateContinue++;
                if (lateContinue > 2) 
                    return false;
            }
            else
            {
                lateContinue = 0;
            }
        }

        return true;
    }
};