当前位置: 首页 > 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…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

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

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

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...