第 117 场 LeetCode 双周赛题解

A 给小朋友们分糖果 I

在这里插入图片描述

动态规划:设 p [ k ] [ i ] p[k][i] p[k][i] 为将 i i i 个糖果分给 k k k 个小朋友的方案数,先求 p [ 2 ] [ i ] p[2][i] p[2][i] ,再求 p [ 3 ] [ n ] p[3][n] p[3][n]

class Solution {
public:
    using ll = long long;

    int distributeCandies(int n, int limit) {
        ll p[4][n + 1];
        memset(p, 0, sizeof(p));

        for (int i = 0; i <= n; i++) {
            p[2][i] = min(limit, i) - max(0, i - limit) + 1;
        }
        ll res = 0;
        for (int i = 0; i <= limit && i <= n; i++)
            if (n - i <= 2 * limit)
                res += p[2][n - i];
        return res;
    }
};

B 给小朋友们分糖果 II

在这里插入图片描述

A A A

class Solution {
public:
    using ll = long long;

    long long distributeCandies(int n, int limit) {
        ll p[4][n + 1];
        memset(p, 0, sizeof(p));

        for (int i = 0; i <= n; i++) {
            p[2][i] = min(limit, i) - max(0, i - limit) + 1;
        }
        ll res = 0;
        for (int i = 0; i <= limit && i <= n; i++)
            if (n - i <= 2 * limit)
                res += p[2][n - i];
        return res;
    }
};

C 重新排列后包含指定子字符串的字符串数目

在这里插入图片描述

动态规划:设 p [ i ] [ c l ] [ c t ] [ c e ] p[i][cl][ct][ce] p[i][cl][ct][ce] 为用 i i i 个字符组成的 l , t , e l,t,e l,t,e 3 3 3 种字符数分别为 c l , c t , c e cl,ct,ce cl,ct,ce 个的字符串数目, l l l 字符数 > 1 >1 >1 的字符串状态算在 c l = 1 cl=1 cl=1 的状态内,类似 t t t 字符数 > 1 >1 >1 的字符串状态算在 c t = 1 ct=1 ct=1 的状态内, e e e 字符数 > 2 >2 >2 的字符串状态算在 c e = 2 ce=2 ce=2 的状态内,答案即为 p [ n ] [ 1 ] [ 1 ] [ 2 ] p[n][1][1][2] p[n][1][1][2]

class Solution {
public:
    using ll = long long;
    ll mod = 1e9 + 7;

    int stringCount(int n) {
        ll p[n + 1][2][2][3];
        memset(p, 0, sizeof(p));
        p[0][0][0][0] = 1;//空串
        for (int i = 1; i <= n; i++) {
            for (int l = 0; l < 2; l++) {
                for (int t = 0; t < 2; t++) {
                    for (int e = 0; e < 3; e++) {
                        p[i][l][t][e] = p[i - 1][l][t][e] * 23 % mod;//第i个字符为非l,e,t的字符
                        if (l) {//第i个字符为l
                            p[i][l][t][e] += (p[i - 1][l - 1][t][e] + p[i - 1][l][t][e]) % mod;
                            p[i][l][t][e] %= mod;
                        }
                        if (t) {//第i个字符为t
                            p[i][l][t][e] += (p[i - 1][l][t - 1][e] + p[i - 1][l][t][e]) % mod;
                            p[i][l][t][e] %= mod;
                        }
                        if (e) {//第i个字符为e
                            p[i][l][t][e] += p[i - 1][l][t][e - 1];
                            p[i][l][t][e] %= mod;
                            if (e == 2) {
                                p[i][l][t][e] += p[i - 1][l][t][e];
                                p[i][l][t][e] %= mod;
                            }
                        }
                    }
                }
            }
        }
        return (p[n][1][1][2] + mod) % mod;
    }
};

D 购买物品的最大开销

在这里插入图片描述
在这里插入图片描述

贪心 + 优先级队列:每次购买当前各商店最右商品价格最小的最右商品即可获得最大总开销,用优先级队列维护各商店最右商品价格最小值

class Solution {
public:
    using ll = long long;
    
    long long maxSpending(vector<vector<int>> &values) {
        int m = values.size(), n = values[0].size();
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> heap;//最小堆
        for (int i = 0; i < m; i++)
            heap.emplace(values[i][n - 1], i, n - 1);
        ll res = 0;
        for (int i = 1; i <= m * n; i++) {
            auto [v, r, c] = heap.top();
            heap.pop();
            res += 1LL * i * v;
            if (c)//该商店还有剩余商品
                heap.emplace(values[r][c - 1], r, c - 1);
        }
        return res;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/134174.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于Python+OpenCV+SVM车牌识别系统-车牌预处理系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介简介系统流程系统优势 二、功能三、系统四. 总结 一项目简介 ## PythonOpenCVSVM车牌识别系统介绍 简介 PythonOpenCVSVM车牌识别系统是一种基于计算机视…

【C++】this指针讲解超详细!!!

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

postman接口自动化测试

Postman除了前面介绍的一些功能&#xff0c;还有其他一些小功能在日常接口测试或许用得上。今天&#xff0c;我们就来盘点一下&#xff0c;如下所示&#xff1a; 1.数据驱动 想要批量执行接口用例&#xff0c;我们一般会将对应的接口用例放在同一个Collection中&#xff0c;然…

Dubbo从入门到上天系列第五篇:Dubbo3与JDK17不兼容问题展示

文章目录 一&#xff1a;JDK 与 Dubbo版本对应问题说明 1&#xff1a;问题1 2&#xff1a;问题2 二&#xff1a;Spring与JDK版本对应关系 1&#xff1a;对应关系详图 2&#xff1a;JDK与Major对应关系图 大神链接&#xff1a;作者有幸结识技术大神孙哥为好友&#xff0c…

asp.net学生宿舍管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net 学生宿舍管理系统是一套完善的web设计管理系统&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为vs2010&#xff0c;数据库为sqlserver2008&#xff0c;使用c#语言 开发 asp.net学生宿舍管理系统1 应用技…

C语言达到什么水平才能从事单片机工作

C语言达到什么水平才能从事单片机工作 从事单片机工作需要具备一定的C语言编程水平。以下是几个关键要点&#xff1a;基本C语言知识&#xff1a; 掌握C语言的基本语法、数据类型、运算符、流控制语句和函数等基本概念。最近很多小伙伴找我&#xff0c;说想要一些C语言学习资料&…

5G+智慧港口建设解决方案

一、智慧港口建设背景 智慧港口是随着时代进步发展起来的一种现代港口运输的新业态&#xff0c;它是以现代化基础设施为基础&#xff0c;促使大数据、云计算、物联网、移动互联网、智能控制等新一代信息技术与港口运输业务深度融合&#xff0c;以港口运输组织服务创新为动力&am…

Jenkins 质量扫描

代码质量扫描工具&#xff08;SonarQube&#xff09; 质量评审 SonarQube有四个关键组件 ◼ SonarQube Server运行有三个组件 ◆ Web Server&#xff1a;UI ◆ Search Server&#xff1a;为UI提供搜索功能&#xff0c;基于ElasticSearch ◆ Compute Engine Server&#xff1a…

Goland报错:Cannot resolve symbol ‘XXX‘。一键解决该问题。

Goland报错&#xff1a;Cannot resolve symbol XXX。一键解决该问题。 问题是&#xff1a;Cannot resolve symbol XXX解决方法是&#xff1a; 问题是&#xff1a;Cannot resolve symbol ‘XXX’ 问题的背景&#xff1a; 我写了两个包&#xff0c;分别是main 、utils包。main包…

MATLAB 全景图切割及盒图显示的实现步骤

参考&#xff1a;MATLAB 全景图切割及盒图显示的实现步骤 | w3cschool笔记 在摄像领域中全景图是一种可以将周围360度景象全部收录的一种拍照技术&#xff0c;但全景图的实际观感并不是那么好&#xff08;可以看下文的全景图的样例&#xff09;。我们可以通过matlab来进行全景…

CIFAR-100数据集的加载和预处理教程

一、CIFAR-100数据集介绍 CIFAR-100&#xff08;Canadian Institute for Advanced Research - 100 classes&#xff09;是一个经典的图像分类数据集&#xff0c;用于计算机视觉领域的研究和算法测试。它是CIFAR-10数据集的扩展版本&#xff0c;包含了更多的类别&#xff0c;用…

Git GUI、SSH协议和IDEA中的Git使用详解

目录 前言 一、Git GUI的使用 1. 什么是Git GUI 2. 常见的Git GUI工具 3.使用 4.使用Git GUI工具的优缺点 优点&#xff1a; 缺点&#xff1a; 二、SSH协议 1.什么是SSH协议 2.SSH的主要特点和作用 3.SSH密钥认证的原理和流程 4. SSH协议的使用 三、IEDA使用git …

SQL SELECT INTO 语句

SQL SELECT INTO 语句 使用 SQL&#xff0c;您可以将信息从一个表中复制到另一个表中。 SELECT INTO 语句从一个表中复制数据&#xff0c;然后将数据插入到另一个新表中。 SQL SELECT INTO 语法 我们可以把所有的列都复制到新表中&#xff1a; SELECT * INTO newtable [IN ex…

python OrderedDict类(有序字典)

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 创建有序字典 import collectionsdic collections.OrderedDict() dic[k1] v1 dic[k2] v2 dic[k3] v3 print(dic)#输出&#xff1a;OrderedDict([(k1, v1), (…

深度学习之基于Django+Tensorflow商品识别管理系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 项目简介 本系统是一个基于DjangoTensorflow的商品识别管理系统。通过深度学习技术&#xff0c;实现商品的自动识别…

vue 项目配置跨越

要在vue开发中实现跨域需要先进入到vue项目根目录&#xff0c;找到vue.config.js文件&#xff0c;然后在proxy中设置跨域&#xff1a; devServer: { proxy: { /api: { target: http://47.93.220.246:8300, changeOrigin: true, pathRewrite: { ^/api: , }, }, }, }, 在vue中使用…

51单片机应用从零开始(一)

1. 单片机在哪里 单片机是一种集成电路芯片&#xff0c;通常被嵌入到电子设备中用于控制和处理数据&#xff0c;例如家电、汽车、电子玩具、智能家居等。因此&#xff0c;你可以在许多电子设备中找到单片机的存在。单片机通常被放置在设备的主板或控制板上。 2. 单片机是什么…

Flink 基础 -- 尝试Flink

官网 文档 v1.18.0 下载 数据流上的状态计算(Stateful Computations over Data Streams) Apache Flink是一个框架和分布式处理引擎&#xff0c;用于无界和有界数据流的有状态计算。Flink被设计成可以在所有常见的集群环境中运行&#xff0c;以内存中的速度和任何规模执行计…

超详细介绍对极几何和立体视觉及 Python 和 C++实现

您是否想过为什么戴着特殊的 3D 眼镜观看电影时可以体验到美妙的 3D 效果?或者为什么闭上一只眼睛很难接住板球?这一切都与立体视觉有关,立体视觉是我们用双眼感知深度的能力。这篇文章使用 OpenCV 和立体视觉为计算机提供这种感知深度的能力。代码以 Python 和 C++ 形式提供…