当前位置: 首页 > news >正文

【LeetCode - 每日一题】1073. 负二进制数相加 (2023.05.18)

1073. 负二进制数相加

题意

  • 基数为 -2 。
  • 实现两个 0/1 数组串的加法。

解法

这是一道模拟题。

arr1[i]arr2[i] 是数组 arr1arr2 从低到高的第 i 位数。

首先回顾普通的二进制数的相加,从低位开始计算,在计算的同时维护用一个变量 carry 维护进位信息,因此,对于第 i 位的结果 ans[i] = arr1[i] + arr2[i] + carry。若 ans[i] = 0, 1,则更新 carry = 0,ans[i] = 0, 1;若 ans[i] = 2, 3,则更新 carry = 1,ans[i] = ans[i] - 2。

类比到基数为 -2 的二进数相加上,从低位开始计算,在计算的同时用一个变量 carry 维护进位信息,同样地,对于第 i 为的结果 ans[i] = arr1[i] + arr2[i] + carry。则此时的 carry 的范围变成了 [-1, 0],ans[i] 的范围变成了 [-1, 0, 1, 2]。若 ans[i] = 0, 1,则更新 carry = 0,ans[i] = 0, 1;若 ans[i] = 2,则更新 carry = -1(因为相邻位的正负号是反的,所以进位一定是 -1 ),ans[i] = ans[i] - 2;若 ans[i] = -1,此时是一种特殊情况,需要单独讨论:

当 ans[i] = -1 时,需要将其进行转换。又注意到:
(-2)i+1 + (-2)i = - (-2)i,所以将 ans[i] 赋为 -1 和将 ans[i] 和 ans[i+1] 都加 1 的效果是一样的,因此更新 carry = 1,ans[i] = 1。

// 官方解法
class Solution {
public:vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {vector<int> ans;int idx1 = arr1.size() - 1, idx2 = arr2.size() - 1;int carry = 0;while(idx1 >= 0 || idx2 >= 0 || carry) 	// carry 要放在 while 循环条件里{int x = carry;if(idx1 >= 0){x += arr1[idx1];}if(idx2 >= 0){x += arr2[idx2];}idx1 --;idx2 --;if(x >=2){ans.push_back(x - 2);carry = -1;}else if (x >= 0){ans.push_back(x);carry = 0;}else{ans.push_back(1);carry = 1;}}// 删去前置 0 while(ans.size() > 1 && ans.back() == 0){ans.pop_back();}reverse(ans.begin(), ans.end());return ans;}
};

相关文章:

【LeetCode - 每日一题】1073. 负二进制数相加 (2023.05.18)

1073. 负二进制数相加 题意 基数为 -2 。实现两个 0/1 数组串的加法。 解法 这是一道模拟题。 设 arr1[i] 和 arr2[i] 是数组 arr1 和 arr2 从低到高的第 i 位数。 首先回顾普通的二进制数的相加&#xff0c;从低位开始计算&#xff0c;在计算的同时维护用一个变量 carry…...

软件上线会面临哪些缺陷?这四种你一定很熟悉

上线对任何软件产品来说都是一件大事&#xff0c;确保一切正常并且向用户发布高质量的软件非常重要。劣质、过早、不稳定、难以使用的产品会产生大量经济损失&#xff0c;也可能使用户对品牌本身失去信任。一直以来&#xff0c;我们都说应该测试&#xff0c;应该将缺陷修复到可…...

html监听界面被隐藏或显示

vue相比于小程序和uni-app 显然少了两个有点用的生命周期 onShow 应用被展示 onHide 应用被隐藏 但其实这个 要做其实也很简单 JavaScript中 有对应的visibilitychange事件可以监听 我们Html参考代码如下 <!DOCTYPE html> <html lang"en"> <head>…...

Springboot启动失败 DB连不上竟然是maven配置的问题

Springboot启动失败&#xff1a;Failed to instantiate [javax.sql.DataSource]。 最开始以为是DB版本后&#xff0c;需要升级驱动版本&#xff0c;但更新驱动版本还是不行&#xff0c;而且另外一个项目同样驱动同样配置可以启动。 后面发现代码读取不到yml文件中的配置信息。…...

P9234 [蓝桥杯 2023 省 A] 买瓜 题解

题目传送门 前言 说实话这题根本用不到什么折半……&#xff0c;今天看机房大佬写了半天加了一堆剪枝还以为很难&#xff0c;其实是你们想复杂了 20分钟不到从看题到代码实现 这题其实只需要可行性剪枝加排序 哦还有个后缀和 进入正题 小木棍子都听说过吧 没错就是小波上…...

ThingsBoard自定义分发节点duplicate to related

------------------------------------内容仅博主所有,订阅者请勿泄露,感谢--------------------- 1、概述 大家好,我又更新干货了,还是那句话,我绝不像某些博主“拿我格子衫”分享那些照抄官网翻译的东西来骗订阅,我觉得那是浪费时间,要搞就搞干货,今天给大家分享Th…...

vim自动更新ctags与taglist

vim的 ctags 和 taglist 在默认情况下是不进行自动更新的&#xff0c;这对于编写代码是非常不方便的&#xff0c;好在vim的脚本还是很强大的&#xff0c;于是在vimrc中添加如下函数&#xff1a; function! UpdateCtags()let curdirgetcwd()while !filereadable("./tags&qu…...

linux查看日志常用命令,动态日志命令

linux查看日志命令&#xff0c;动态日志命令&#xff1a; tail&#xff1a; -n是显示行号&#xff1b;相当于nl命令&#xff1b;例子如下&#xff1a; tail -100f test.log 实时监控100行日志。 tail -n 10 test.log 查询日志尾部最后10行的日志。 tail -…...

分段存储管理方式

目录 一、分段存储管理方式的引入的需求: 1.方便编程 2.信息共享 3.信息保护 4.动态增长 5.动态链接 二、分段系统的基本原理 1.分段 2.段表 3.地址变换机构 4.分页与分段的主要区别 三、信息共享 四、段页式存储管理方式 1.基本原理 2.地址变换过程 分段与分页…...

将nacos从本地切换到远程服务器上时报错:客户端端未连接,Client not connected

报错信息&#xff1a; 09:34:38.438 [com.alibaba.nacos.client.Worker] ERROR com.alibaba.nacos.common.remote.client - Send request fail, request ConfigBatchListenRequest{headers{charsetUTF-8, Client-AppNameunknown, Client-RequestToken65c0fbf47282ae0a7b85178…...

系统掌握入河排污口设置论证技术、方法及报告编制框架

在短时间内较系统的掌握入河排污口设置论证技术、方法及报告编制框架&#xff0c;学习内容以城镇生活污水厂、造纸项目、石化项目、制药项目案例为线索&#xff0c;系统讲解入河排污口设置论证报告书编制过程&#xff0c;并以水质模型为手段&#xff0c;讲解水质影响预测模型的…...

服务端渲染

服务端渲染 和 前后端分离&#xff01; 渲染 什么是渲染呢 ? 其实很简单, 就是把数据反应在页面上&#xff0c;说白了, 就是利用 js 的语法, 把某些数据组装成 html 结构的样子, 放在页面上展示。 举个例子 : 1. 准备一段 html 结构 <h1>hello world</h1> <di…...

干货丨警惕!14个容易导致拒稿的常见错误

Hello,大家好&#xff01; 这里是壹脑云科研圈&#xff0c;我是喵君姐姐~ 从做研究、到写论文、再到投稿&#xff0c;每一步都是巨大的挑战。以下列举了一些在这些过程中可能导致拒稿的常见错误&#xff0c;希望能帮助大家避开。 01 格式问题 1.没有遵守投稿须知 期刊提供了…...

Web基础 ( 二 ) CSS

2.CSS 2.1.概念与基础 2.1.1.什么是CSS Cascading Style Sheets 全称层叠样式单 简称样式表。 是告诉浏览器如何来显示HTML的元素的特殊标记 2.1.2.编写方式 2.1.2.1.外部文件 在html文件的<head>中加入<link>结点来引入外部的文件 <link rel"stylesh…...

MSQL系列(一) Mysql实战-索引结构 二叉树/平衡二叉树/红黑树/BTree/B+Tree

Mysql实战-索引结构 二叉树/平衡二叉树/红黑树/BTree/BTree 我们在项目中都会使用索引&#xff0c;所以我们要了解索引的存储结构&#xff0c;今天我们就着重讲解下Mysql的索引结构存储模型&#xff0c;并且看下 二叉树&#xff0c;平衡二叉树&#xff0c;红黑树&#xff0c;B…...

理论力学专题:张量分析

张量方法的引入 自然法则与坐标无关&#xff0c;坐标系的引入方便分析&#xff0c;但也掩盖了物理本质指标符号哑标和自由标 Einstein求和约定&#xff1a;凡在某一项内&#xff0c;重复一次且仅重复一次的指标&#xff0c;表示对该指标在它的取值范围内求和&#xff0c;并称这…...

索引失效情况

左或者左右模糊匹配&#xff0c;like %xx&#xff0c;like %xx% select * from student where name like %三; 原因&#xff1a;B是按照索引值有序排列&#xff0c;只能根据前缀比较来确定数据&#xff0c;一旦左边是模糊的&#xff0c;显然无法确定到底是哪个索引值 对索引字…...

pv操作练习题

信号量解决五个哲学家吃通心面问题 题型一 有五个哲学家围坐在一圆桌旁&#xff0c;桌中央有盘通心面&#xff0c;每人面前有一只空盘于&#xff0c;每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面&#xff0c;每个哲学家必须获得两把叉子&#xff0c;…...

【小菜鸡刷题记】--字符串篇

【小菜鸡刷题记】&#xff1a;字符串 剑指 Offer 05. 替换空格剑指 Offer 58 - II.左旋转字符串剑指 Offer 20.表示数值的字符串剑指 Offer 67. 把字符串转换成整数 特此声明&#xff1a;题目均来自于力扣 剑指 Offer 05. 替换空格 题目链接 请实现一个函数&#xff0c;把字符…...

Sonar加入jenkins流水线

前提&#xff1a;已搭建sonarqube 1、配置sonarqube server jenkins 中manage jenkins-configure System配置sonarqube server 2、准备sonar环境 在jenkins项目的构建环境步骤中&#xff0c;勾选prepare SonarQube environment token需要提前在凭据里添加一个token 3、执行s…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...