面试题05.08绘制直线问题详解(考察点为位运算符)

server/2024/12/22 13:45:37/

目录

一·题目:

二·详细思路汇总:

三·代码解答(带注释版):


一·题目:

leetcode原题链接:. - 力扣(LeetCode) 

二·详细思路汇总:

这里先剧透一下简单版思路哦:1.数组-1初始化;

                                                   2.定位找到x1,x2指向的整型;

                                                3.根据x1,x2是否指向同一整型,完成对x1左侧,x2右侧更改操作。

思路:大概就是把一维数组按照题目给的一行(W/32)有几个数把它类似的铺成二维数组的形式,然后根据(y这里从0行开始)行数,然后对应的x1,x2是对应的这一行的

比特位区间,原来所有的bite位是0,这要把这块区间内的0变为1然后得到此区间对应的十进制数字,再次更改,最后把它放入一个返回数组中即可(注:这里为了方便起见,我们

把返回数组都设为-1,因为如果x1和x2这个区间内包含了不止一个int数,那么最后都被改成1,由补码变成原码就是-1,简单来说就是省事),然后呢这就理解题意结束了,下面说一下

本题详解思路:

1.这里又要分情况就是【x1,x2】,也就是这个区间包含了一个数还是很多,即x1与x2指向同一个整形还是不同整型(如果是这种情况,我们给返回数组初始化-1就有作用了)

1.1 先假设不在同一个数身上:且x1,x2 分别指向不同的两个数的中间比特位上,这里我们分为两步,第一步是处理x1左边,第二步是处理x2右边----->

那么可以考虑把x1所在的整型的前部的bite位改为0,可是原来它是1,因此这里有点经验的话,我们就可以想到按位与,这时也会联想到通过位移操作符和1配合完成,此时

就把x1所在整型的前方bite位改成了0,而x2所在比特位后面还是1,下面就是对它的操作,这时还是用上面的方法,只不过,我们要改变后面就不能改变了x1前面(也就是刚改的0)、

此时1位移的就是x2所在整型前面的bite位(因为它们不都指向一个整型),最后就可以得到这个区间改完了,(最后一起判断-1改0)

2.2 也就是它们指向的是同一个整型那么此时可以说我们设置的都是-1便没有发挥作用,我们还是像上面一样两步走去改,这时改的时候区别的只是x2从上面那一步1移位到x2前面

一直到此整型第一个比特位处,而这个情况是移到x1指向的比特位处了(下面代码可以看成),其他几乎没变化。

3.也就是我们把【x1,x2】这个区间没有降落到的整型改回0即可。

 

三·代码解答(带注释版):

class Solution {
public://返回与x1所在整型的&的值int corresx1(int x){int cor=0;for(int i=0;i<=31-(x%32);i++){cor+=1<<i;}return cor;}//返回与x2所在整型的&的值int corresx2(int x1,int x2,int start,int end){int cor=0;int terminate=0;if(start==end) terminate=31-(x1%32);else terminate=31;for(int i=31-(x2%32);i<=terminate;i++){cor+=1<<i;}return cor;}vector<int> drawLine(int length, int w, int x1, int x2, int y) {vector<int> ret(length,-1);//把x1,x2精确定位到整型处:int flag = y * w / 32;int head = x1 / 32 + flag;int rear = x2 / 32 + flag;//分别处理x1前方和x2后方:ret[head] = ret[head]&corresx1(x1);ret[rear] = ret[rear] &corresx2(x1,x2,head,rear);//不合适的-1转回0:for(int i=0;i<length;i++){if(i<head||i>rear&&ret[i]==-1) {ret[i]=0;}}return ret;}
};


http://www.ppmy.cn/server/126132.html

相关文章

【STM32-HAL库】自发电型风速传感器(使用STM32F407ZGT6)(附带工程下载链接)

一、自发电型风速传感器介绍 自发电型风速传感器&#xff0c;也称为风力发电型风速传感器或无源风速传感器&#xff0c;是一种不需要外部电源即可工作的风速测量设备。这种传感器通常利用风力来驱动内部的发电机构&#xff0c;从而产生电能来供电测量风速的传感器部分。以下是自…

相互作用感知的 3D 分子生成 VAE 模型 - DeepICL 评测

DeepICL 是一个基于相互作用感知的 3D 分子生成模型&#xff0c;能够在目标结合口袋内进行相互作用引导的小分子设计。DeepICL 通过利用蛋白质-配体相互作用的普遍模式作为先验知识&#xff0c;在有限的实验数据下也能实现高度的泛化能力。 一、背景介绍 DeepICL 来源于韩国科学…

图论系列(dfs岛屿) 9/26

一、统计封闭岛屿的数目 二维矩阵 grid 由 0 &#xff08;土地&#xff09;和 1 &#xff08;水&#xff09;组成。岛是由最大的4个方向连通的 0 组成的群&#xff0c;封闭岛是一个 完全 由1包围&#xff08;左、上、右、下&#xff09;的岛。 请返回 封闭岛屿 的数目。 输…

【设计模式-中介者模式】

定义 中介者模式&#xff08;Mediator Pattern&#xff09;是一种行为设计模式&#xff0c;通过引入一个中介者对象&#xff0c;来降低多个对象之间的直接交互&#xff0c;从而减少它们之间的耦合度。中介者充当不同对象之间的协调者&#xff0c;使得对象之间的通信变得简单且…

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-30

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-30 目录 文章目录 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-30目录1. Proof Automation with Large Language Models概览&#xff1a;论文研究背景&#xff1a;技术挑战&#xff1a;如何破局…

矩阵的特征值和特征向量

矩阵的特征值和特征向量是线性代数中非常重要的概念&#xff0c;用于描述矩阵对向量的作用&#xff0c;特别是在矩阵对向量的线性变换中的表现。它们帮助我们理解矩阵在某些方向上的缩放或旋转效果。 1. 特征值和特征向量的定义&#xff1a; 给定一个 n n n \times n nn 的…

每天五分钟玩转深度学习框架pytorch:多种定义损失函数的方法

本文重点 再编译神经网络的时有两个必要的元素,其中一个是损失函数,另外一个是优化器。前面的专栏我们已经介绍了优化器,本节课程我们介绍损失函数。损失函数属于神经网络训练的第5步。 nn.Module 和 nn.functional的损失函数 我们前面介绍过nn.Module和nn.functional的区…

ArcGIS与ArcGIS Pro去除在线地图服务名单

我们之前给大家分享了很多在线地图集&#xff0c;有些地图集会带有制作者信息&#xff0c;在布局制图的时候会带上信息影响出图美观。 一套GIS图源集搞定&#xff01;清新规划底图、影像图、境界、海洋、地形阴影图、导航图 比如ArcGIS&#xff1a; 比如ArcGIS Pro&#xff1a…