【教3妹学编程-算法题】按距离统计房屋对数目 II

瑟瑟发抖

3妹:2哥2哥,国家又降息啦,贷款市场报价利率(LPR)为:1年期LPR为3.45%,与前值持平;5年期以上LPR为3.95%,较前值下调25个基点。 你的房贷是不是可以又少了?
2哥 : 是啊,一个月能省还好几百呢。
3妹:省下来的钱用来干嘛,不如请我吃饭吧,嘿嘿。😁
2哥 : 也不是不可以,正好我也好久没吃大餐了,走,去搓一顿!
3妹:走着!话说2哥,你买的房子离你公司距离那么远,你准备去住吗?
2哥:暂时不住,近的我也买不起啊。工作可以换的嘛,哈哈
3妹:有道理。
2哥:说到房屋的距离,我今天看到一个关于“房屋的距离”的题目,让我们一起来做下吧~

吃瓜

题目:

给你三个 正整数 n 、x 和 y 。

在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 1 <= i < n ,都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。

对于每个 k(1 <= k <= n),你需要找出所有满足要求的 房屋对 [house1, house2] ,即从 house1 到 house2 需要经过的 最少 街道数为 k 。

返回一个下标从 1 开始且长度为 n 的数组 result ,其中 result[k] 表示所有满足要求的房屋对的数量,即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。

注意,x 与 y 可以 相等 。

示例 1:
image.png
输入:n = 3, x = 1, y = 3
输出:[6,0,0]
解释:让我们检视每个房屋对

  • 对于房屋对 (1, 2),可以直接从房屋 1 到房屋 2。
  • 对于房屋对 (2, 1),可以直接从房屋 2 到房屋 1。
  • 对于房屋对 (1, 3),可以直接从房屋 1 到房屋 3。
  • 对于房屋对 (3, 1),可以直接从房屋 3 到房屋 1。
  • 对于房屋对 (2, 3),可以直接从房屋 2 到房屋 3。
  • 对于房屋对 (3, 2),可以直接从房屋 3 到房屋 2。
    示例 2:

image.png
输入:n = 5, x = 2, y = 4
输出:[10,8,2,0,0]
解释:对于每个距离 k ,满足要求的房屋对如下:

  • 对于 k == 1,满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。
  • 对于 k == 2,满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。
  • 对于 k == 3,满足要求的房屋对有 (1, 5),以及 (5, 1) 。
  • 对于 k == 4 和 k == 5,不存在满足要求的房屋对。
    示例 3:
    image.png
    输入:n = 4, x = 1, y = 1
    输出:[6,4,2,0]
    解释:对于每个距离 k ,满足要求的房屋对如下:
  • 对于 k == 1,满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。
  • 对于 k == 2,满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。
  • 对于 k == 3,满足要求的房屋对有 (1, 4), 以及 (4, 1)。
  • 对于 k == 4,不存在满足要求的房屋对。

提示:

2 <= n <= 10^5
1 <= x, y <= n

思路:

思考

分类讨论+撤销操作
首先,如果没有额外加一条在 x 和 y 之间的边,那么对于房子 i:

它到它左侧房子的最短距离分别是 1,2,3,⋯ ,用差分数组把 [1,i−1]都加一。
然后考虑 x 和 y 加的这条边带来的影响。假设 x≤y,如果 x+1≥y,那么这条边不影响最短距离. 否则分类讨论

java代码:

class Solution {
    public long[] countOfPairs(int n, int x, int y) {
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }

        diff = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            add(1, i - 1, 1);
            add(1, n - i, 1);
            if (x + 1 >= y) {
                continue;
            }
            if (i <= x) {
                update(i, x, y, n);
            } else if (i >= y) {
                update(n + 1 - i, n + 1 - y, n + 1 - x, n);
            } else if (i < (x + y) / 2) {
                update2(i, x, y, n);
            } else if (i > (x + y + 1) / 2) {
                update2(n + 1 - i, n + 1 - y, n + 1 - x, n);
            }
        }

        long[] ans = new long[n];
        long sumD = 0;
        for (int i = 0; i < n; i++) {
            sumD += diff[i + 1];
            ans[i] = sumD;
        }
        return ans;
    }

    private int[] diff;

    private void add(int l, int r, int v) {
        if (l > r) return;
        diff[l] += v;
        diff[r + 1] -= v;
    }

    private void update(int i, int x, int y, int n) {
        add(y - i, n - i, -1); // 撤销 [y,n]
        int dec = y - x - 1; // 缩短的距离
        add(y - i - dec, n - i - dec, 1);

        int j = (x + y + 1) / 2 + 1;
        add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
        add(x - i + 2, x - i + y - j + 1, 1);
    }

    private void update2(int i, int x, int y, int n) {
        add(y - i, n - i, -1); // 撤销 [y,n]
        int dec = (y - i) - (i - x + 1); // 缩短的距离
        add(y - i - dec, n - i - dec, 1);

        int j = i + (y - x + 1) / 2 + 1;
        add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
        add(i - x + 2, i - x + y - j + 1, 1);
    }
}

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

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

相关文章

十六、多边形填充和绘制

项目功能实现&#xff1a;对多边形进行轮廓绘制和填充 按照之前的博文结构来&#xff0c;这里就不在赘述了 一、头文件 mult-drawing.h #pragma once#include<opencv2/opencv.hpp>using namespace cv;class Mult_Drawing { public:void mult_drawing(); };#pragma onc…

IO进程线程第6天

1.使用有名管道完成两个进程的相互通信 send.c代码如下&#xff1a; #include <myhead.h>int main(int argc, const char *argv[]) {pid_t pidfork();if(pid>0){//父进程//从管道1中读取数据int fd-1;if((fdopen("./mkfifo1",O_RDONLY))-1){perror("…

已解决的问题:BIOS中Enter键失效_BIOS中回车键没反应

问题&#xff1a; 未解决的问题&#xff1a;BIOS中enter键失效_bios回车键没反应-CSDN博客 问题复现&#xff1a; Windows7 关机 开机按F2进入BIOS 调整Boot Mode&#xff0c;按Enter建&#xff0c;Enter键失效 按F10&#xff0c;按Enter键&#xff0c;Enter键失效 按E…

Leetcode - 周赛385

目录 一&#xff0c;3042. 统计前后缀下标对 I 二&#xff0c;3043. 最长公共前缀的长度 三&#xff0c;3044. 出现频率最高的质数 四&#xff0c;3045. 统计前后缀下标对 II 一&#xff0c;3042. 统计前后缀下标对 I 该题数据范围小&#xff0c;可直接暴力求解&#xff0c;…

基于springboot+vue的电影评论网站(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

Node.js中如何处理异步编程

在Node.js中&#xff0c;处理异步编程是至关重要的技能。由于Node.js的单线程执行模型&#xff0c;异步编程可以极大地提高程序的性能和响应速度。本文将介绍几种常见的异步编程处理方式&#xff0c;并附上示例代码&#xff0c;帮助您更好地理解和应用异步编程技术。 回调函数…

Nginx-----------高性能的 Web服务端 nginx编译安装 、平滑升级(一)

一、Nginx高性能的 Web服务端 Nginx是由1994年毕业于俄罗斯国立莫斯科鲍曼科技大学的同学为俄罗斯rambler.ru公司开发的&#xff0c;开发工作最早从2002年开始&#xff0c;第一次公开发布时间是2004年10月4日&#xff0c;版本号是0.1.02019年3月11日F5与NGINX达成协议,F5 将收购…

小折叠也能成为主力机,全新小折叠旗舰华为Pocket 2正式发布

2024年2月22日&#xff0c;华为在三亚举办华为Pocket 2时尚盛典&#xff0c;正式发布其全新小折叠旗舰华为Pocket 2。一直以来&#xff0c;华为致力于萃取各界艺术灵感&#xff0c;不断探寻科技美学的可能性&#xff0c;华为Pocket系列更是秉承将奢雅美学与尖端科技融为一体的理…

第三百六十回

文章目录 1. 概念介绍2. 实现方法2.1 环绕效果2.2 立体效果 3. 示例代码4. 内容总结 我们在上一章回中介绍了"自定义SlideImageSwitch组件"相关的内容&#xff0c;本章回中将介绍两种阴影效果.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在本…

ProtoBuf认识与Windows下的安装

protobuf简介 Protobuf 是 Protocol Buffers 的简称&#xff0c;它是 Google 公司开发的一种数据描述语言&#xff0c;是一种轻便高效的结 构化数据存储格式&#xff0c;可以用于结构化数据&#xff0c;或者说序列化。它很适合做数据存储 或 RPC 数据交换格 式 。可用于通讯…

2024最佳住宅代理IP服务商

跨境出海已成为了近几年的最热趋势&#xff0c;大批量的企业开始开拓海外市场&#xff0c;而海外电商领域则是最受欢迎的切入口。新兴的tiktok、Temu&#xff0c;老牌的Amazon、Ebay&#xff0c;热门的Etsy、Mecari等等都是蓝海一片。跨境入门并不难&#xff0c;前期的准备中不…

H桥逆变方式介绍(单极性)

H桥逆变电路实现的就是一个从DC——AC的过程 这个电路有两个时序&#xff0c;Q6Q4是一个导通时序&#xff0c;Q5Q7是一个导通时序 左边两个是高频20KHZ的、互补的sPWM波&#xff0c;右边是低频的50HZ的PWM波 三角波一般叫载波&#xff0c;正弦波叫调制波&#xff08;单片机内…

串的相关题目

于是他错误的点名开始了 我发现有关hash得题目有些是可以通过map数组来完成的&#xff1a;何为map数组&#xff0c;我们先思考一下最简单的桶的排序&#xff0c;桶排序是将我们需要数字最为下标输进数组中&#xff0c;而数组是存放的数字是这个数字出现的次数&#xff0c;但是由…

PLC_博图系列☞基本指令“异或“运算

PLC_博图系列☞基本指令“异或“运算 文章目录 PLC_博图系列☞基本指令“异或“运算背景介绍X&#xff1a;“异或”运算说明参数示例真值表 关键字&#xff1a; PLC、 西门子、 博图、 Siemens 、 异或 背景介绍 这是一篇关于PLC编程的文章&#xff0c;特别是关于西门子的…

06 内存管理

目录 c/c内存分布c语言中动态内存管理方式c中动态内存管理方式operator new与operator delete函数new和delete的实现原理定位new表达式(placement-new)常见题 1. c/c内存分布 看一段代码 int globalVar 1; static int staticGlobalVar 1; void Test() {static int staticV…

基于springboot+vue的教学资源库系统(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

linux操作系统day2(io文件处理)

二进制文件读写&#xff1a; fread()/fwrite() 读&#xff1a; size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream); 功能&#xff1a; 从指定的stream流对象中获取nmemeb个大小为size字节的数据块到ptr 所在的本地内存中。 参数&#xff1a; pt…

【Python Scrapy】分布式爬虫利器

在当今信息爆炸的时代&#xff0c;获取大规模数据对于许多应用至关重要。而分布式爬虫作为一种强大的工具&#xff0c;在处理大量数据采集和高效爬取方面展现了卓越的能力。 本文将深入探讨分布式爬虫的实际应用场景&#xff0c;通过代码示例演示其在提升爬取效率、保障系统稳定…

3个wordpress中文企业主题模板

农业畜牧养殖wordpress主题 简洁大气的农业畜牧养殖wordpress主题&#xff0c;农业农村现代化&#xff0c;离不开新农人、新技术。 https://www.jianzhanpress.com/?p3051 老年公寓wordpress主题 浅绿色简洁实用的老年公寓wordpress主题&#xff0c;适合做养老业务的老年公…

day09-MongoDB

文章目录 day09-MongoDB一、回顾1.1. 行为实战核心要点说明 二、评论系统2.1 MongoDB2.1.1 MongoDB简介①简介②体系结构与术语 2.1.2 安装与连接2.1.3 Springboot整合MongoDB①引入依赖②添加服务端配置③准备实体类④测试-新增⑤测试-查询⑥测试-更新测试-删除 2.2 app端评论…