头像

繁花似锦


访客:9973

离线:40分钟前



滑动窗口 + hash

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<int> S;
        for(int i=0,w = 0;i < s.size(); i ++){
            w = w * 2 + s[i] - '0';
            if(i >= k) w -= s[i-k] - '0'  << k;
            if(i >= k-1) S.insert(w);
        }

        return S.size() == (1 << k);
    }
};


活动打卡代码 LeetCode 1462. 课程安排 IV

floyd算法,传递闭包

class Solution {
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& es, vector<vector<int>>& qs) {
        vector<vector<bool>> d(n,vector<bool>(n));

        for(auto e : es) d[e[0]][e[1]] = true;
        for(int k = 0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j = 0;j<n;j++)
                    if(d[i][k] && d[k][j])
                        d[i][j] = true;

        vector<bool> res;
        for(auto q : qs) res.push_back(d[q[0]][q[1]]);
        return res;
    }
};


活动打卡代码 LeetCode 1463. 摘樱桃 II

数字三角形模型,类似题目:方格取数,传纸条

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<vector<int>>> f(n,vector<vector<int>>(m,vector<int>(m,-1))); // 三维数组初始化
        f[0][0][m-1] = grid[0][0] + grid[0][m-1];

        int res = 0;
        for(int k =1;k<n;k++)
            for(int i = 0;i<m;i++)
                for(int j = 0;j<m;j++)
                    for(int a=i-1;a<=i+1;a++)
                        for(int b = j-1;b<=j+1;b++)
                        {
                            if(a < 0 || a>=m || b <0 || b>=m) continue; // 越界
                            int t = f[k-1][a][b]; 
                            if(t==-1) continue; // 状态非法
                            if(i == j) t += grid[k][i]; // 重叠
                            else t += grid[k][i] + grid[k][j];
                            f[k][i][j] = max(f[k][i][j],t);

                            res = max(res,f[k][i][j]);
                        }

        return res;
    }
};



class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        sort(target.begin(),target.end());
        sort(arr.begin(),arr.end());

        return target == arr;
    }
};



传送门:y总讲解视频——LeetCode暑期刷题打卡2019——Week3 树专题


补数据结构-树中:想刷完leetcode中所有树的题目。(PTA也想补一下)


98. 验证二叉搜索树

二叉搜索树的特点:左 < 根 < 右,由此递归确定每个结点的值是否在合理范围内

94. 二叉树的中序遍历

手动模拟递归的过程,用栈来维护。由于中序遍历是先递归左子树,所以在栈中要先压入左子树

101. 对称二叉树

迭代的方式遍历:左半边是左根右,右半边是右根左,承接上题

105. 从前序与中序遍历序列构造二叉树

先用哈希表记录根节点在中序遍历中的位置,再递归处理左半边和右半边,通过给dfs传参数范围

102. 二叉树的层序遍历

宽搜框架,但要先记录每一层有多少个元素

236. 二叉树的最近公共祖先

算法1:递归;算法2:向上搜索(这里是O(n),听说还有LCA倍增写法,等学会了更新)

算法1:递归(递归函数主要在于出口,这里递归函数比较难想)
111.jpg

/**
 * 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 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root==p || root==q) return root;

        auto left = lowestCommonAncestor(root->left,p,q);
        auto right = lowestCommonAncestor(root->right,p,q);
        if(!left) return right;
        if(!right) return left;
        return root;
    }
};

算法2:向上搜索(更优化的写法是LCA倍增?)

/**
 * 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 {
public:

    unordered_map<int,TreeNode*> fa;
    unordered_map<int,bool> vis;

    void dfs(TreeNode* root)
    {
        if(root->left){
            fa[root->left->val] = root;
            dfs(root->left);
        }
        if(root->right){
            fa[root->right->val] = root;
            dfs(root->right);
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root->val] = NULL;
        dfs(root); // 向上搜索,建立父指针
        while(p != NULL){
            vis[p->val] = true;
            p = fa[p->val];
        }

        while(q != NULL){
            if(vis[q->val]) return q;
            q = fa[q->val];
        }

        return NULL;
    }
};

543. 二叉树的直径

递归定义:返回当前结点向下走的最大深度

124. 二叉树中的最大路径和

递归定义:返回当前节点最大路径和,承接上题

173. 二叉搜索树迭代器

因为是二叉搜索树,有如下特点:左 < 根 < 右,按照中序遍历的方式即可

297. 二叉树的序列化与反序列化

序列化:将值转换为字符串

-------------------------------------------------------------------------------update : 2020/6/5


700. 二叉搜索树中的搜索

递归查找

701. 二叉搜索树中的插入操作

递归插入左子树或右子树

450. 删除二叉搜索树中的节点

情况1:当前结点没有左右子树,直接删除
情况2:当前结点只有左子树或右子树,直接返回左子树或右子树
情况2:当前结点既有左子树又有右子树,将当前结点与左子树中的最大元素交换,或右子树中的最小元素交换

/**
 * 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 {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == NULL) return NULL;

        if(key < root->val) root->left = deleteNode(root->left,key);
        else if(key > root->val) root->right = deleteNode(root->right,key);
        else
        {
            if(!root->left && !root->right) return NULL;
            else if(!root->left) return root->right;
            else if(!root->right) return root->left;
            else
            {
                TreeNode* temp = root->right;
                while(temp->left) temp = temp->left;
                swap(root->val,temp->val);
                root->right = deleteNode(root->right,key);
            }
        }

        return root;
    }
};

-------------------------------------------------------------------------------update : 2020/6/6




次小生成树,dfs部分不太明白

s=抄代码中

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 510, M = 10010;

int n,m;
struct Edge
{
    int a,b,w;
    bool f; // 是树边还是非树边
    bool operator< (const Edge &t)const
    {
        return w < t.w;
    }
}edge[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N],e[N * 2],w[N * 2],ne[N *2],idx; // 无向图建两条边

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

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void dfs(int u,int fa,int maxd1, int maxd2,int d1[],int d2[])
{
    d1[u] = maxd1, d2[u] = maxd2;
    for(int i=h[u];~i; i = ne[i])
    {
        int j = e[i];
        if(j != fa) // 避免死循环
        {
            int td1 = maxd1, td2 = maxd2;
            if(w[i] > td1) td2 = td1, td1 = w[i];
            else if(w[i] <td1 && w[i] > td2) td2 = w[i];
            dfs(j,u,td1,td2,d1,d2);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i] = {a,b,w};
    }

    sort(edge, edge + m);
    for(int i=1;i<=n;i++) p[i] = i;

    LL sum = 0;
    for(int i=0;i<m;i++)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int pa = find(a), pb = find(b);
        if(pa != pb)
        {
            p[pa] = pb;
            sum += w;
            add(a,b,w),add(b,a,w);
            edge[i].f = true;
        }
    }

    // 预处理树上两点间的最大值
    for(int i=1;i<=n;i++) dfs(i,-1,-1e9,-1e9,dist1[i],dist2[i]); // 加-1参数,避免死循环

    LL res = 1e18;
    for(int i=0;i<m;i++)
        if(!edge[i].f)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            LL t;
            if(w > dist1[a][b])
                t = sum + w - dist1[a][b];
            else if(w > dist2[a][b])
                t = sum + w - dist2[a][b];
            res = min(res,t);
        }

    printf("%lld\n",res);

    return 0;
}


活动打卡代码 AcWing 346. 走廊泼水节

最小生成树 + 维护size的并查集

res += (size_[a] * size_[b] - 1 ) * (w + 1);

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
struct Edge
{
    int a,b,w;
    bool operator< (const Edge &t)const
    {
        return w < t.w;
    }
}e[N];
int p[N],size_[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;

        for(int i=0;i<n-1;i++)
        {
            int a,b,w;
            cin >> a >> b >> w;
            e[i] = {a,b,w};
        }

        sort(e,e+n-1);
        for(int i=1;i<=n;i++) p[i] = i,size_[i] = 1;

        int res = 0;
        for(int i=0;i<n-1;i++)
        {
            int a = find(e[i].a), b = find(e[i].b), w= e[i].w;

            if(a != b)
            {
                res += (size_[a] * size_[b] - 1 ) * (w + 1);
                size_[b] += size_[a];
                p[a] = b;
            }
        }

        cout<<res<<endl;
    }
}


活动打卡代码 AcWing 1145. 北极通讯网络

kruskal算法

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 510, M = N * N;

#define x first
#define y second
typedef pair<long,long> PII;

int n,k,idx;
PII village[N];
struct Edge
{
    int a,b;
    double w;
    bool operator<(const Edge &t)const
    {
        return w < t.w;
    }
}e[M];
int p[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

double kruskal()
{
    for(int i=1;i<=n;i++) p[i] = i;

    sort(e,e+idx);

    double res = 0;
    int cnt = n;
    for(int i=0;i<idx;i++)
    {
        if(cnt <= k) break; // 当连通块的数量降为k时就是答案
        int a= find(e[i].a),b = find(e[i].b);
        double w = e[i].w;

        if(a != b)
        {
            p[a] = b;
            res = w;

            cnt --;
        } 

    }

    return res;
}

int main()
{
    cin >> n >> k;

    for(int i=1;i<=n;i++)
    {
        cin >> village[i].x >> village[i].y;
    }

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            double dist = (village[i].x - village[j].x) * (village[i].x - village[j].x) + 
                (village[i].y - village[j].y) * (village[i].y - village[j].y);
            dist = sqrt(dist);
            e[idx ++ ] = {i,j,dist};
        }


    printf("%.2lf",kruskal());

    return 0;

}


活动打卡代码 AcWing 1146. 新的开始

prim算法,增加超级源点

#include <iostream>
#include <cstring>

using namespace std;

const int N = 310;

int n;
int w[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[0] = 0;

    int res = 0;
    for(int i=0;i<n+1;i++) // 增加了超级源点,有n+1个点
    {
        int t = -1;
        for(int j=0;j<=n;j++)
            if(!st[j] && (t==-1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;
        res += dist[t];

        for(int j=0;j<=n;j++) dist[j] = min(dist[j], w[t][j]);
    }

    return res;
}

int main()
{
    cin >> n;

    for(int i=1;i<=n;i++)
    {
        cin >> w[0][i];
        w[i][0] = w[0][i]; // 无向边
    }

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

    cout<<prim();

    return 0;
}



模板题

858. Prim算法求最小生成树(时间复杂度:$O(N ^ 2)$)
859. Kruskal算法求最小生成树(时间复杂度:$O(MlogM)$)(常用)

应用题

1140. 最短网络
1141. 局域网(总边权固定,去掉的边权最大,等价于留下的边权最小)
1142. 繁忙的都市(另类生成树:最大的边权最小)
1143. 联络员(先加必加边,后加可选边)
1144. 连接格点(重点关注建边过程:从一个点的四个方向建边)


P2872 [USACO07DEC]Building Roads S(坐标相乘爆int,需要开大)
P2121 拆地毯(做不超过K条边的kruskal算法,由此证明kruskal算法只做一部分也是正确的)