以前在acwing看过，但是找不到视频了，大家知道的可以告诉我呵呵，就是左右旋转，然后沿45度对角线再翻转；

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix[0].size();

        for (int i = 0; i < n; i ++ )
        {

            for (int j = 0; j < n / 2; j ++ )
            { 
                swap(matrix[i][j], matrix[i][n - 1 - j]);
            }
        }

        for (int i = 0; i < n - 1; i ++ )
        {
            for (int j = 0; j < n - 1 - i; j ++ )
            {
                swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);
            }
        }

    }
};

输入数组是一棵树的层序遍历，返回重建的二叉树，递归方法。

测试样例；
11
3 9 20 -1 -1 15 7 -1 -1 -1 -1
中序遍历答案
9 3 15 20 7

#include<iostream>
#include<queue>
using namespace std;

int n, num;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode* root)
{
    if (!root) return;
    dfs(root->left);
    cout << root->val << ' ';
    dfs(root->right);
}

TreeNode* make(int p[], int u)
{
    if (u > n || p[u] == -1) return nullptr;

    TreeNode* root = new TreeNode(p[u]);

    root->left = make(p, u * 2);
    root->right = make(p, u * 2 + 1);
    return root;
}

int main()
{
    cin >> n;
    int p[n + 1];

    for (int i = 1; i <= n; i ++ ) cin >> p[i];

    TreeNode* root = make(p, 1);

    dfs(root);

    return 0;


}

手撕代码：检测温度身高需要间隔几天，如果一直没有升高，就为0。温度全为整数。input: 75, 76, 58, 54, 59, 80, 48, 49 output:1, 4, 2, 1, 1, 0, 1, 0
//1.可以直接模拟。
//2.单调栈。记录一下

#include<iostream>
#include<stack>
using namespace std;
const int N = 1010;
// 8
// 75 76 58 54 59 80 48 49 
//1, 4, 2, 1, 1, 0, 1, 0
int n;
int p[N], l[N];

int main()
{
    cin >> n;
    stack<int> sta;
    for (int i = 1; i <= n; i ++ ) cin >> p[i];

    for(int i = n; i >= 1; i -- )
    {
        while (!sta.empty() && p[sta.top()] <= p[i]) sta.pop();

        if (sta.empty()) l[i] = n + 1;
        else l[i] = sta.top();

        sta.push(i);

    }

    for (int i = 1; i <= n; i ++ ) 
    {

      int num = l[i] == n + 1 ? 0 : l[i] - i;
      cout << num << " ";
    }

    return 0;

}

记录一下，面试可能还有插入排序、快排的链表实现

#include<iostream>
using namespace std;
const int N = 1010;

int n;
int p[N];

void sort()
{
    for (int i = 1; i < n; i ++ )
    {
        int temp = p[i];
        int j = i - 1;
        while (j >= 0 && p[j] >= temp)
        {
            p[j + 1] = p[j];
            j --;
        }
        p[j + 1] = temp;
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ ) cin >> p[i];

    sort();

    for (int i = 0; i < n; i ++ ) cout << p[i] << " ";
    cout << endl;
}

看华为面试题有一个，判断五子棋谁赢， bfs，记录一下，看不到样例，也不知道通不通过，

自己写的一个输入样例
输入 棋盘大小N=10， 1表示白旗，2表示黑棋，0表示空白位置。

10
1111100000
0120000000
0012000000
0001200000
0000020000
0000000000
0000000000
0000000000
0000000000
0000000000

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n;
vector<string> v;

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int bfs(int x, int y)
{
    if (v[x][y] - '0' == 0) return 0;

    char kind = v[x][y]; // 1 表示白， 2表示黑；

    //记录2个值，方向上旗子的个数，当前走的8个方向;
    int dir_num[4] = {1, 1, 1, 1};

    int mp[n][n];
    memset(mp, -1, sizeof mp);

    queue<pair<int, int>> q;
    q.push(make_pair(x, y));

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        int _x = t.first, _y = t.second;

        if (_x == x && _y == y)
        {
            for (int i = 0; i < 8; i ++ )
            {
                int a = _x + dx[i], b = _y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < n && v[a][b] == kind)
                {
                    q.push(make_pair(a, b));
                    mp[a][b] = i;
                }
            }
        }
        else
        {
            if(v[_x][_y] == kind)
            {

                dir_num[mp[_x][_y] % 4] += 1;
                int a = _x + dx[mp[_x][_y]], b = _y + dy[mp[_x][_y]];
                if (dir_num[mp[_x][_y] % 4] == 5) return (kind - '0');
                else if (a >= 0 && a < n && b >= 0 && b < n && v[a][b] == kind)
                {
                    q.push(make_pair(a, b));
                    mp[a][b] = mp[_x][_y];
                }
            }
        }

    }




    return 0;

}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        string s;
        cin >> s;
        v.push_back(s);
    }
    int flag = 1;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
        {
            int num = bfs(i, j);
            if (num == 1)
            {
                cout << "white" << endl;
                flag = 0;
                break;
            }
            else if (num == 2)
            {
                cout << "black" << endl;
                flag = 0;
                break;
            }
        }
        if (!flag) break;
    }
    if (flag) cout << "none" << endl;
    return 0;


}

------更新ACWING学习的方法----
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n;
vector<string> v;

int dx[] = {-1, -1, 0, 1}, dy[] = {0, 1, 1, 1};

int bfs(int x, int y)
{
    if (v[x][y] - '0' == 0) return 0;

    char kind = v[x][y];

    for (int i = 0; i < 4; i ++ )
    {
        int l = 0, r = 0;
        while (true)
        {
            int a = x + dx[i] * (r + 1), b = y + dy[i] * (r + 1);
            if (a < 0 || a >= n || b < 0 || b >= n) break;
            if (v[a][b] != kind) break;
            r ++ ;
        }

        while (true)
        {
            int a = x - dx[i] * (l + 1), b = y - dy[i] * (l + 1);
            if (a < 0 || a >= n || b < 0 || b >= n) break;
            if (v[a][b] != kind) break;
            l ++ ;
        }
        if (l + r + 1 == 5) return kind - '0';
    }

    return 0;

}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        string s;
        cin >> s;
        v.push_back(s);
    }
    int flag = 1;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
        {
            int num = bfs(i, j);
            if (num == 1)
            {
                cout << "white" << endl;
                flag = 0;
                break;
            }
            else if (num == 2)
            {
                cout << "black" << endl;
                flag = 0;
                break;
            }
        }
        if (!flag) break;
    }
    if (flag) cout << "none" << endl;
    return 0;


}-

无脑分组法

手动无脑分组，再也没有写诗的感觉

1、给一个根p，就放p进组；
2、给一个节点a，放就放p,a进组；
3、如果又给了一个节点b，那么以p为根的组，组员数目为3，那就不仅要放p,b进组，还要放p，a，b进组。
4、w表示最终价值。

C++ 代码

#include<iostream>
#include<vector>
using namespace std;

int s[70];
int mp[70];
int v[70][70], w[70][70];
int f[32010];


int main()
{
    int n, m;
    cin >> n >> m;
    int group = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (c == 0)
        {
            group ++;
            mp[i] = group;
            s[group] = 1;
            v[group][1] = a;
            w[group][1] = b * a;
        }
        else if(a + v[mp[c]][1] <= n)
        {

            int temp_g = mp[c];
            s[temp_g] += 1;
            v[temp_g][s[temp_g]] = a + v[temp_g][1];
            w[temp_g][s[temp_g]] = b * a + w[temp_g][1];

            if (s[temp_g] == 3)
            {
                s[temp_g] += 1;
                v[temp_g][4] = v[temp_g][2] + a;
                w[temp_g][4] = w[temp_g][2] + b * a;
            }
        }
    }

    for (int i = 1; i <= group; i ++ )
    {
        for (int j = n; j >= 0; j -- )
        {
            for (int k = 1; k <= s[i]; k ++ )
            {
                if (j >= v[i][k])
                {
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }

    cout << f[n];

    return 0;
}

笔记

记录一下
38行k遍历的是son节点在不同体积下的价值，把son节点不同体积看成分组下的每个元素；
49行不能是f[u][j] = max(f[u][j], f[u][j - v[u]] + w[u])，是应为f[u][j]代表不选的的情况，而u节点默认是一定选的;
54行，如果root条件不满足，那么它的子节点满足也没用（应为选了子节点就要选它的根节点），所以直接在当前节点置零

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int h[N], e[N], ne[N], idx;
int n, m;
int v[N], w[N];
int f[N][N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int son = e[i];
        dfs(son);

        for (int j = m - v[u]; j >= 0; j -- )
        {

            for (int k = 0; k <= j; k ++ )
            {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }

        }
    }

    for (int j = m; j >= v[u]; j -- )
    {
        f[u][j] = f[u][j - v[u]] + w[u];
    }

    for (int j = 0; j < v[u]; j ++ )
    {
        f[u][j] = 0;
    }
}

int main()
{
    int root, a, b, c;
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a >> b >> c;
        v[i] = a, w[i] = b;
        if (c == -1) 
        {
            root = i;
        }
        else 
        {
            add(c, i);
        }
    }
    dfs(root);
    cout << f[root][m];

    return 0;

}

#include<iostream>
#include<vector>
using namespace std;

vector<int> add (vector<int> &A, vector<int> &B)
{
    int t = 0; //表示每个位的数
    vector<int> C;
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t = t / 10;
    }
    if (t) C.push_back(1);
    return C;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    auto C = add(A, B);

    for (int i = C.size() - 1; i>=0 ; i -- )cout << C[i];

}

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
const int N = 100010;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
bool st[N];

int dist[N];
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;

}

void spfa()
{

    memset(dist, 0x3f, sizeof dist);

    queue<int> q;
    q.push(1);
    dist[1] = 0;
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }

    }

    if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << dist[n];

}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;

        add(a, b, c);
    }
    spfa();

    return 0;
}

#include<iostream>
using namespace std;

const int N = 100010;
int a[N], p[N]; //p[i]表示所有长度i的子序列中，结尾最小的数

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int len = 0; //len表示当前找到的最长子序列长度；
    p[0] = -2e9;

    for (int i = 0; i < n; i ++ ) // 遍历每个a[i]看能接在哪个长度后面。
    {
        int l = 0, r = len; 
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (p[mid] < a[i]) l = mid;
            else r = mid - 1;
        } // 二分找比a[i]小且接近的数p[r]，r表示a[i]能接在长度r的子序列后面。

        // 跟新len，这里r+1不一定比len大，应为不一定是接在最后一个长度。
        // len表示当前找到的最长子序列长度；
        // 比如长度1,2,3, 当a[i]只接在1,2后面时，max可以保证不会长度不会被更新。
        len = max(len, r + 1); 
        p[r + 1] = a[i]; // r 表示最接近a[i]的长度； p[r + 1] 表示下一个长度的结尾数；
    }

    cout << len << endl;
    return 0;

}