【LeetCode】力扣364.周赛题解

在这里插入图片描述
Halo,这里是Ppeua。平时主要更新C++,数据结构算法,Linux与ROS…感兴趣就关注我bua!
img

1.最大二进制奇数

🍉题目:image-20230924231011246

🍉例子:

image-20230924231101415

🍉 题解:

首先看题目,最大二进制奇数,在一个二进制表示法当中,只要最后一位为1,这个数就是奇数,将一个字符串中原有的一重新排列组合,将1尽可能的放到高位.最后留一位放在低位即可.

假设给定字符串中1的数量为cnt.那么我们想要达到的就是如下关系

d034fb0f22b9e1f048a60c95179d9e8

🍉代码解析:

具体思路如下:

  1. 遍历当前字符串,若为1则cnt++,并将当前位置置为0;

  2. 之后将低位也就是字符串的最后一位制成1,保证是奇数;

    这里不需要考虑字符串没有1的情况,因为题给条件保证一定有一个1

  3. 从高位遍历,依次将当前为置为1,直到cnt为0则停止

class Solution {
public:string maximumOddBinaryNumber(string s) {int  cnt=0;for(auto &ss:s){if(ss=='1')cnt++;ss='0';}s[s.size()-1]='1';cnt--;for(int i=0;i<s.size()-1;i++){if(cnt>0){s[i]='1';cnt--;}else break;}return s;}
};

2. 2865. 美丽塔 I

🍉 题目:

image-20230925150702686

🍉示例:

image-20230925150842337

🍉题意:

先来分析下题目表达的意思:

给定一个maxHeights数组在其中选一个数为美丽塔的塔尖.塔的两边呈递减状态.

题给的maxHeights数组可以理解为是可以在这个地方建造美丽塔的最高高度,也就是塔高的上界.

当选择第i位maxHeights[i]为塔尖的时,则有[0][i-1]均小于maxHeights[i]、[i+1][n-1]均小于maxHeights[i].

对于[0]~[i-1]:则有s[i]<=s[i+1] (s为答案数组)

对于[i+1]~[n-1]:则有s[i+2]<=s[i+1] (s为答案数组)

具体关系如下图所示.

d7095ad16d241b02bd896186d382d98

根据数据范围来推算法

我们需要学会一个方法: 根据数据范围来推导使用什么算法,c++中1s可以处理的次数为1e7,也就是超过这个时间就会报超时

具体的有如下关系,(数据来自acwing)

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下,C++代码中的操作次数控制在 1e7 为最佳。

下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:

n≤30, 指数级别, dfs+剪枝,状态压缩dp
n≤100 => O(n3),floyd,dp
n≤1000 => O(n2),O(n2logn),dp,二分
n≤10000 => O(n∗√n),块状链表
n≤100000 => O(nlogn) => 各种sort,线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平面交、二分
n≤1000000 => O(n), 以及常数较小的 O(nlogn) 算法 => hash、双指针扫描、kmp、AC自动机,常数比较小的 O(nlogn) 的做法:sort、树状数组、heap、dijkstra、spfa
n≤10000000 => O(n),双指针扫描、kmp、AC自动机、线性筛素数
n≤109 => O(√n),判断质数
n≤1018 => O(logn),最大公约数

在做题中有意识的先看数据范围,可以极大的帮助解题

那么我们先看这一题的数据范围

image-20230925153647661

1 e 3 1e^3 1e3,也就是采用o( n 2 n^2 n2)的时间复杂度都可以通过.观察题目来看,我们直接暴力模拟两层循环即可.

注意,这里的数据大小范围为 1 e 9 1e^9 1e9,而int的范围大概为 2 e 9 2e^9 2e9左右.如果使用int来存储最终数据,很容易造成溢出,所以我们使用long long来存储

🍉 题解:

观察题目要求会发现,如果顺序遍历这个数组,很容易出现在出现一个极小的数字,从而影响了前面整个塔的建设.

也就是后续的高度会影响前面已经确定的结果,如果顺序遍历问题一下复杂起来了.所以我们选择从塔尖开始向前遍历.也就是逆序遍历.

d42bb99836b3da141b6f4d874d54a96

整体思路如下:

设定一个值来存储已遍历区间的最小值(我们可以将这个最小值初始化为此时塔尖的高度:因为这半个区间中的所有高度都要小于等于塔尖)

若当前值小于等于这个最小值,则可以加入到答案中(因为我们是逆序遍历,此时说明他是非递增)

若当前值大于这个值,则将最小值加入到答案中.(maxHeights[cur]>=min,就会出现上图的情况)

左右两边进行一个对称的操作,之后将和加入到答案数组即可.(ans[i]表示以i位为塔尖此时的高度和)

最后对数组排序取出最后一个值,即为最大值.

0adfabbbf61439216dde06b26fbde17

class Solution {
public:long long maximumSumOfHeights(vector<int>& maxHeights) {//存储最大高度和vector<long long>ans;int n = maxHeights.size();for (int i = 0; i < n; i++){long long sum = maxHeights[i];int min_heightl = maxHeights[i];int min_heightr = maxHeights[i];for (int j = i-1; j >=0; j--){min_heightl = min(min_heightl, maxHeights[j]);sum += min_heightl;}for (int j = i + 1; j < n; j++){min_heightr = min(min_heightr, maxHeights[j]);sum += min_heightr;}ans.push_back(sum);}sort(ans.begin(), ans.end());return ans[n - 1];}
};

3. 2866. 美丽塔 II

🍉题目

image-20230925150702686

🍉示例:

image-20230925150842337

🍉题意:

这题和美丽塔I的题目完全一样,唯一的区别就是

image-20230926195712817

数据范围从 1 0 3 10^3 103,变成了 1 0 5 10^5 105这意味着不能使用O( n 2 n^2 n2)的算法了.我们需要真正的解决这道题.

🍉 题解:

这里我们可以用前后缀差分的方法,和我们之前美丽塔I的思想类似,也是从分别算出塔的两边再相加.但不同的是:我们仅遍历数组一遍来算出以当前位置为塔尖的(左边或者右边)的和

具体的我们利用单调栈来解决这道题:

以下以右边为例:

假设有数组[1,3,9,5,4,7]

我们第一个遇到的数字是7,此时把他加入到和中.

下一个遇到的数数字是4.因为是递减的排列,所以我们从右向左看.他很明显会被7给遮住.

10bc0b648e121663d1420ce6bf7e093

所以我们将7踢出栈撤销之前更新的答案(也就是减去这个7),再将4入栈.并更新答案.

此时最关键的是,7是被压缩到4同样的高度,而不是被删掉了,也就是此时栈中有两个4.

那我们如何去记录这个栈中有x个y呢?

我们可以在栈中不存数字,存对应数字的数组下标.我们将栈中初始化一个数组大小n,此时只需要用前一个栈中下标减去要入栈的下标,就知道答案需要更新x个y了

0031dd4fa1673d77fce7a910c3498a7

右边栈初始值是n,左边栈初始值是-1.

注意用来存储当前和的数组需要用longlong 否则会爆

class Solution {
public:long long maximumSumOfHeights(vector<int>& maxHeights) {long long sum=0;int n=maxHeights.size();stack<int>right;right.push(n);vector<long long>rsum(n+1);rsum.reserve(n+1);//存储答案数组会爆intvector<long long>lsum(n+1);lsum.reserve(n+1);//差分后缀for (int i = n - 1; i >= 0; i--) {while (right.size() > 1 && maxHeights[i] <= maxHeights[right.top()]) {int value = right.top();right.pop();sum -= (long long)(right.top() - value) * maxHeights[value];}sum += (long long)(right.top() - i) * maxHeights[i];right.push(i);rsum[i] = sum;}long long ans=sum;stack<int>left;sum=0;left.push(-1);for(int i=0;i<n;i++){while(left.size()>1&&maxHeights[i]<=maxHeights[left.top()]){   int value=left.top();left.pop();sum-=(long long)(value-left.top())*maxHeights[value];   }sum+=(long long)(i-left.top())*maxHeights[i];ans=max(ans,sum+rsum[i+1]);left.push(i);lsum[i]=sum;}return ans;}
};

image-20230905164632777

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MQ - 31 基础功能: 优先级队列的设计

文章目录 导图概述什么是优先级队列如何设计实现优先级队列业务实现优先级队列的效果内核支持优先级队列RabbitMQ 中优先级队列的实现总结导图 概述 当我们需要在业务中对消息设置优先级,让优先级高的消息能被优先消费,此时就需要用到消息队列中优先级队列的特性。 为了了解…

前后端分离vue简介

vue简介 vue是一个渐进式js框架&#xff0c;用于构建用户界面&#xff0c;其主要特点是易学易用、轻量、灵活和高效。Vue.js由前Google工程师尤雨溪&#xff08; Evan You&#xff09;在2014年创建&#xff0c;它的核心库只关注视图层&#xff0c;是一款非常优秀的MVVM框架&…

Azure AD混合部署,通过 Intune 管理设备,实现条件访问

一、设备同步到AAD上面 1、配置 AAD Connect 2、选择 3、下一步 4、配置本地 企业管理员 5、配置成功 二、通过 组策略把设备同步到 Intune 上面 1、创建一条组策略 2、设置 &#xff08;1&#xff09;计算机配置 → 管理模板 → Windows 组件 → MDM → 使用默认 Azure AD …

增强for循环和一般for循环的对比使用

文章底部有个人公众号&#xff1a;热爱技术的小郑。主要分享开发知识、学习资料、毕业设计指导等。个人B站主页热爱技术的小郑 &#xff0c;视频内容主要是对应文章的视频讲解形式。有兴趣的可以关注一下。为何分享&#xff1f; 踩过的坑没必要让别人在再踩&#xff0c;自己复盘…

spring源码解析——IOC之自定义标签解析

概述 之前我们已经介绍了spring中默认标签的解析&#xff0c;解析来我们将分析自定义标签的解析&#xff0c;我们先回顾下自定义标签解析所使用的方法&#xff0c;如下图所示&#xff1a; 我们看到自定义标签的解析是通过BeanDefinitionParserDelegate.parseCustomElement(ele…

【赘婿国漫】从网络文学,到热播动漫,种马文属性或许是最大优点

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析国漫资讯。 《赘婿》第一季结束以来&#xff0c;有关该剧的讨论就一直没有停止过。这部由网络小说改编而来的国漫&#xff0c;虽然收获了不俗的收视成绩&#xff0c;但也引发了许多争议。在原著作者的控制范围之外&#x…

智慧银行:数字化金融时代的引领者

在当今数字化的时代&#xff0c;金融行业正经历着一场前所未有的变革。传统的银行模式已经不再适用&#xff0c;取而代之的是智慧银行的新兴概念。智慧银行不仅仅是数字化的银行&#xff0c;更是一个全新的金融服务范式&#xff0c;将科技与金融相结合&#xff0c;为客户提供更…

技术干货 | JMeter实现参数化的4种方式

参数化释义 什么是参数化&#xff1f;从字面上去理解的话&#xff0c;就是事先准备好数据&#xff08;广义上来说&#xff0c;可以是具体的数据值&#xff0c;也可以是数据生成规则&#xff09;&#xff0c;而非在脚本中写死&#xff0c;脚本执行时从准备好的数据中取值。 参数…

方法的重载

方法的重载 在同一个类中&#xff0c;定义了多个同名的方法&#xff0c;这些同名方法名具有同样的功能每个方法具有不同的参数类型或者参数个数&#xff0c;这些同名的方法就构成了重载关系。 简记&#xff1a;同一个类中&#xff0c;方法名相同&#xff0c;参数不同的方法。与…

编程每日一练(多语言实现):判断偶数

文章目录 一、实例描述二、技术要点三、代码实现3.1 C 语言实现3.2 Python 语言实现3.3 Java 语言实现 一、实例描述 利用单条件单分支选择语句判断输入的一个整数 是否是偶数。 运行程序&#xff0c;输入一个 整数18&#xff0c; 然后按回车键&#xff0c;将提示该数字是偶数…

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 试题 B: 双子数

[蓝桥杯 2023 国 B] 双子数 试题 B: 双子数 【问题描述】 若一个正整数 x x x 可以被表示为 p 2 q 2 p^2 \times q^2 p2q2&#xff0c;其中 p p p、 q q q 为质数且 p ≠ q p \neq q pq&#xff0c;则 x x x 是 一个 “双子数”。请计算区间 [ 2333 , 233333333333…

1.算法——数据结构学习

算法是解决特定问题求解步骤的描述。 从1加到100的结果 # include <stdio.h> int main(){ int i, sum 0, n 100; // 执行1次for(i 1; i < n; i){ // 执行n 1次sum sum i; // 执行n次} printf("%d", sum); // 执行1次return 0; }高斯求和…

vue3 - 按需导入使用Element Plus图标、iconify图标、本地SVG/PNG图标

GitHub Demo 地址 在线预览 vue3 - 按需导入使用Element Plus图标、iconify图标、本地SVG/PNG图标 [GitHub Demo 地址](https://github.com/iotjin/jh-vue3-admin)[在线预览 ](https://iotjin.github.io/jh-vue3-admin) 一、iconify插件安装使用效果图 二、通过自动导入使用ic…

基于微信小程序的音乐播放器设计与实现(源码+lw+部署文档+讲解等)

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…

在虚拟机上安装win10/ubuntu的教程

以下内容源于网络资源的学习与整理&#xff0c;如有侵权请告知删除。 一、下载软件资源 1、首先下载虚拟机Vmware_Pro17软件并正确安装&#xff1a;网盘链接 2、然后下载操作系统的镜像文件&#xff1a;MSDN, 我告诉你 - 做一个安静的工具站 二、在虚拟机上安装ubuntu系统 1…

共享门店模式:一种新兴的商业模式

共享门店模式是一种利用实体店铺的空间和资源&#xff0c;让多个品牌或商家在同一地点共同运营的商业模式。这种模式可以提高店铺的利用率&#xff0c;降低经营成本&#xff0c;增加客流量&#xff0c;实现资源的最大化利用。如果你是一个有创业想法的企业家&#xff0c;或者你…

2023-9-26 JZ52 两个链表的第一个公共节点

题目链接&#xff1a;两个链表的第一个公共节点 import java.util.*; /* public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;} }*/ public class Solution {public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {ListNo…

数据统计和分析怎么做?spss如何做好数据分析?

为什么要做数据分析?数据分析有什么意义&#xff1f;数据分析可以为企业和组织提供多方面的帮助&#xff0c;包括提高工作效率、优化业务流程、升职加薪、提高管理效率以及改进汇报效果等方面。 IBM SPSS Statistics 26是一款功能强大的统计分析软件&#xff0c;适用于Mac操作…

LabVIEW风力涡轮机的雷电流测量系统中集成高速摄像机

LabVIEW风力涡轮机的雷电流测量系统中集成高速摄像机 随着全球风电装机容量的快速增长&#xff0c;雷电活动对风力发电机组造成的损害受到更多关注&#xff0c;特别是在雷电活动强烈的地区。在冬季闪电期间&#xff0c;风力涡轮机等高层结构会受到向上的雷击。众所周知&#x…

JetBrains 产品安装插件(plugins)的两种方式

安装分为在线、离线两种方式&#xff1a; 在线方式&#xff1a; File > Settings > Plugins 搜索插件 Install 即可 离线方式&#xff1a; 官网&#xff1a;https://plugins.jetbrains.com/ 搜索到插件后&#xff0c;点击 "Get"&#xff0c;选择自己安装的…