第 360 场 LeetCode 周赛题解

A 距离原点最远的点

在这里插入图片描述

串中的 “_” 处要么都向左走要么都向右走

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int t = 0;
        for (auto x: moves)
            if (x != 'R')
                t--;
            else
                t++;
        int res = abs(t);
        t = 0;
        for (auto x: moves)
            if (x != 'L')
                t++;
            else
                t--;
        res = max(res, abs(t));
        return res;
    }
};

B 找出美丽数组的最小和

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

贪心:升序枚举正数,用集合维护当前数组中已有的数

class Solution {
public:
    long long minimumPossibleSum(int n, int target) {
        long long res = 0;
        set<int> vis;
        for (int i = 1; vis.size() != n; i++)
            if (!vis.count(target - i)) {
                res += i;
                vis.insert(i);
            }
        return res;
    }
};

C 使子序列的和等于目标的最少操作次数

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

贪心:首先只有 n u m s nums nums 的数组和小于 t a r g e t target target 才无解,若有解则从低位到高位枚举 t a r g e t target target 的二进制表示的各位,设当前位对应 2 i 2^i 2i ,且 t a r g e t target target i i i 位为 1 1 1,有两种情况:

  • n u m s nums nums中不超过 2 i 2^i 2i 的数的和 ≥ \ge 2 i 2^i 2i :则一定存在若干个不超过 2 i 2^i 2i 的数之和恰好为 2 i 2^i 2i
  • n u m s nums nums中不超过 2 i 2^i 2i 的数的和 < < < 2 i 2^i 2i :需要把 n u m s nums nums 中一个最小的大于 2 i 2^i 2i 的数 2 j 2^j 2j 操作若干次来生成一个 2 i 2^i 2i

第二种情况会产生操作数,枚举过程种注意维护不超过 2 i 2^i 2i 的数的和。

class Solution {
public:
    int minOperations(vector<int> &nums, int target) {
        if (accumulate(nums.begin(), nums.end(), 0LL) < target)
            return -1;
        unordered_map<int, int> cnt;
        for (auto x: nums)
            cnt[x]++;
        int res = 0;
        long long ps = 0;//nums中不超过2^i的数之和
        for (int i = 0, e = 1; i < 31; i++, e <<= 1) {//逐位枚举
            ps += 1LL * cnt[e] * e;
            if (!(target >> i & 1))
                continue;
            if (ps >= e) {
                ps -= e;
                continue;
            }
            int j = i + 1;
            while (cnt[1 << j] <= 0)//找nums中大于2^i的最小的2^j
                j++;
            res += j - i;//记录操作数
            cnt[1 << j]--;
            for (int k = i + 1; k < j; k++)
                cnt[1 << k] = 1;
            ps += e;
        }
        return res;
    }
};

D 在传球游戏中最大化函数值

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

倍增:设 g [ i ] [ j ] g[i][j] g[i][j] 为球最初在 i i i 手里,传 2 j 2^j 2j 次球的过程中每次接触球玩家的编号之和。设 v [ i ] [ j ] v[i][j] v[i][j] 表示球最初在 i i i 手里,传 2 j 2^j 2j 次球后球在 v [ i ] [ j ] v[i][j] v[i][j]手里。预处理求处理 g g g v v v,之后枚举 i ∈ [ 0 , n ) i \in [0,n) i[0,n),然后枚举 k k k 二进制各位来求 f [ i ] f[i] f[i]

class Solution {
public:
    long long getMaxFunctionValue(vector<int> &receiver, long long k) {
        int n = receiver.size();
        long long g[n][35], v[n][35];
        for (int j = 0; j < 35; j++)
            for (int i = 0; i < n; i++)
                if (j != 0) {
                    g[i][j] = g[i][j - 1] + g[v[i][j - 1]][j - 1] - v[i][j - 1];
                    v[i][j] = v[v[i][j - 1]][j - 1];
                } else {
                    g[i][j] = i + receiver[i];
                    v[i][j] = receiver[i];
                }
        long long res = 0;
        for (int i = 0; i < n; i++) {
            long long cur = 0;
            int last = i;
            for (long long j = 0; j < 35; j++)
                if (k >> j & 1) {//枚举k二进制各位
                    cur += g[last][j] - last;
                    last = v[last][j];
                }
            res = max(res, i + cur);
        }
        return res;
    }
};

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

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

相关文章

0821|C++day1 初步认识C++

一、思维导图 二、知识点回顾 【1】QT软件的使用 1&#xff09;创建文件 创建文件时&#xff0c;文件的路径一定是全英文 2&#xff09;修改编码 工具--->选项--->行为--->默认编码&#xff1a;system 【2】C和C的区别 C又叫C plus plus&#xff0c;C是对C的扩充&…

基于React实现日历组件详细教程

前言 日历组件是常见的日期时间相关的组件&#xff0c;围绕日历组件设计师做出过各种尝试&#xff0c;展示的形式也是五花八门。但是对于前端开发者来讲&#xff0c;主要我们能够掌握核心思路&#xff0c;不管多么奇葩的设计我们都能够把它做出来。 本文将详细分析如何渲染一…

WPF基础入门-Class2-样式

WPF基础入门 Class2&#xff1a;样式 1、内联样式&#xff1a;优先度最高 <Grid><StackPanel><!--内联样式优先度高--><Button Background"Red" Height"10" Width"100"FontSize"20"Content"SB">…

Fabric.js 元素选中状态的事件与样式

本文简介 带尬猴&#xff01; 你是否在使用 Fabric.js 时希望能在选中元素后自定义元素样式或选框&#xff08;控制角和辅助线&#xff09;的样式&#xff1f; 如果是的话&#xff0c;可以放心往下读。 本文将手把脚和你一起过一遍 Fabric.js 在对象元素选中后常用的样式设置…

vue2.6及以下版本导入 TDesign UI组件库

TDesign 官方文档:https://tdesign.tencent.com/vue/components/button 我们先打开一个普通的vue项目 然后 如果你是 vue 2.6 或者 低于 2.6 在终端执行 npm i tdesign-vue如果你是 2.7 或者更高 执行 npm i tdesign-vuenaruto这里 我们 以 2.6为例 因为大部分人 用vue2 都是…

【TI毫米波雷达笔记】UART串口外设配置及驱动(以IWR6843AOP为例)

【TI毫米波雷达笔记】UART串口外设初始化配置及驱动&#xff08;以IWR6843AOP为例&#xff09; 最基本的工程建立好以后 需要给SOC进行初始化配置 int main (void) {//刷一下内存memset ((void *)L3_RAM_Buf, 0, sizeof(L3_RAM_Buf));int32_t errCode; //存放SOC初…

软件设计师学习笔记5-流水线技术

目录 1.流水线的概念 2.流水线计算 2.1流水线周期及执行时间 2.2流水线吞吐量 1.流水线的概念 考点&#xff1a;相关参数计算&#xff1a;流水线执行时间计算、流水线吞吐率、流水线加速比、流水线效率(后两者的计算中级不考) 流水线是指在程序执行时多条指令重叠进行操作…

Tomcat10安装及配置教程win11

Tomcat10安装及配置教程win11 Tomcat下载链接 Tomcat官网 Tomcat官网地址 https://tomcat.apache.org/ Tomcat的版本列表 点击上图中左侧红框内**Which version?**即可得下图 下载Tomcat 点击上图中左侧红框内红框内tomcat版本即可得下图&#xff0c;下载zip包 解压zip包…

网络安全基础知识

网络安全 1、网络安全的介绍 1.1 什么是网络安全 1.2 什么是信息系统 1.3 信息系统安全三要素 1.4 什么是网络空间安全 fireye攻击地图:https:www.fireeye.com/cyber-map/threat-map.html/. https://cybermap.kaspersky.com 1.5 安全事件分类 1.6 安全事件 勒索加密是黑客攻…

Scikit-Learn中的特征选择和特征提取详解

概要 机器学习在现代技术中扮演着越来越重要的角色。不论是在商业界还是科学领域&#xff0c;机器学习都被广泛地应用。在机器学习的过程中&#xff0c;我们需要从原始数据中提取出有用的特征&#xff0c;以便训练出好的模型。但是&#xff0c;如何选择最佳的特征是一个关键问…

解决MASM32代码汇编出错: error A2181: initializer must be a string or single item

最近用MASM32编程更新SysInfo&#xff0c;增加对IPv6连接信息的收集&#xff0c;使用到了 typedef struct _MIB_TCP6ROW_OWNER_MODULE {UCHAR ucLocalAddr[16];DWORD dwLocalScopeId;DWORD dwLocalPort;UCHAR ucRemoteAddr[16];DWORD …

【腾讯云 TDSQL-C Serverless 产品测评】“橡皮筋“一样的数据库『MySQL高压篇』

【腾讯云 TDSQL-C Serverless 产品测评】"橡皮筋"一样的数据库 活动介绍服务一览何为TDSQL &#xff1f;Serverless 似曾相识&#xff1f; 降本增效&#xff0c;不再口号&#xff1f;动手环节 --- "压力"山大实验前瞻稍作简介资源扩缩范围&#xff08;CCU&…

飞天使-k8s基础组件分析-服务与ingress

文章目录 服务的介绍服务代理服务发现连接集群外服务服务发布无头服务 服务&#xff0c;pod和dns的关系端口转发通过expose 暴露应用服务案例INGRESSMetalLB使用参考文档 服务的介绍 服务的作用是啥&#xff1f; 提供外部调用&#xff0c;保证podip的真实性看看服务解决了什么…

实时同步ES技术选型:Mysql+Canal+Adapter+ES+Kibana

基于之前的文章&#xff0c;精简操作而来 让ELK在同一个docker网络下通过名字直接访问Ubuntu服务器ELK部署与实践使用 Docker 部署 canal 服务实现MySQL和ES实时同步Docker部署ES服务&#xff0c;canal全量同步的时候内存爆炸&#xff0c;ES/Canal Adapter自动关闭&#xff0c…

Modbus转Profinet网关连接三菱变频器博图快速配置

本案例将分享如何使用兴达易控的modbus转profinet网关&#xff08;XD-MDPN100&#xff09;来连接西门子1200系列plc&#xff0c;并实现三菱变频器的485通讯兼容转modbusTCP通信。通过在博图中进行配置&#xff0c;我们可以实现设备之间的连接和通信。 首先&#xff0c;我们需要…

《QT+PCL 第五章》点云特征-PFH

QT增加点云特征PFH 代码用法代码 #include <pcl/io/pcd_io.h> #include <pcl/features/normal_3d.h> #include <pcl/features/pfh.h>int main

自动驾驶感知传感器标定安装说明

1. 概述 本标定程序为整合现开发的高速车所有标定模块,可实现相机内参标定和激光、相机、前向毫米波 至车辆后轴中心标定,标定参数串联传递并提供可视化工具验证各个模块标定精度。整体标定流程如下,标定顺序为下图前标0-->1-->2-->3,相同编号标定顺序没有强制要求…

android外卖点餐界面(期末作业)

效果展示&#xff1a; AndroidMainFest.xml <?xml version"1.0" encoding"utf-8"?> <manifest xmlns:android"http://schemas.android.com/apk/res/android"xmlns:tools"http://schemas.android.com/tools"><a…

2023年最新版IDEA安装(超详细)

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【JavaSE_primary】 写在前面&#xff0c;IDEA的安装是建立在JDK安装好了的前提下&#xff0c;否则IDEA是无法使用的&#xff0c;具体JDK…

回归预测 | MATLAB实现GA-APSO-IBP改进遗传-粒子群算法优化双层BP神经网络多输入单输出回归预测

回归预测 | MATLAB实现GA-APSO-IBP改进遗传-粒子群算法优化双层BP神经网络多输入单输出回归预测 目录 回归预测 | MATLAB实现GA-APSO-IBP改进遗传-粒子群算法优化双层BP神经网络多输入单输出回归预测效果一览基本介绍模型描述程序设计参考资料 效果一览 基本介绍 MATLAB实现GA-…