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

LeetCode题解:1238. 循环码排列,归纳法,详细注释

原题链接:
https://leetcode.cn/problems/circular-permutation-in-binary-representation/

前置条件:

  1. 在解题之前,请先一定要阅读89.格雷编码的题解
  2. 格雷编码可以满足题目的条件“p[i]p[i+1] 的二进制表示形式只有一位不同”,以及“p[0]p[2^n -1] 的二进制表示形式也只有一位不同”
  3. 我们需要将格雷编码转换成以start开头的一串编码即可
  4. 为何要用异或:
    • 格雷编码的第一个是0,可以得知0 ^ start = start
    • 回顾一下异或操作,可以知道如果对每一位都进行异或操作,每一位之间的逻辑关系的变化是同步的
    • 也就是说,p[i]p[i+1]的相互关系,以及p[0]p[2^n -1] 的相互关系不会改变
      a | b | a XOR b
      —|—|---------
      0 | 0 | 0
      0 | 1 | 1
      1 | 0 | 1
      1 | 1 | 0

解法一:两次循环:

  1. 按照89.格雷编码的方法求出格雷编码
  2. 将格雷编码的每一位都按位异或start,即可求得结果
/*** @param {number} n* @param {number} start* @return {number[]}*/
var circularPermutation = function (n, start) {/* * 第一步,先求格雷编码*/let result = [0] // 存储结果,第一个整数为0// 一共计算n位格雷码序列,需要循环n次for (let i = 0; i < n; i++) {// 每次计算时,已有的序列不变// 只需要计算已有序列的逆序列,每个再加前缀1// 需要缓存已有序列的长度,用于计算下一段序列const len = result.length// 由于是逆序计算,因此要从len - 1开始加前缀for (let j = len - 1; j >= 0; j--) {// 加前缀1后,把新值存入结果result.push(result[j] | (1 << i))}}/* * 第二步,将格雷编码的每一项都按位异或start*/for (let i = 0; i < result.length; i++) {result[i] ^= start}return result
}

解法二:

  1. 可以在解法一的基础上,将第二步的异或操作,放到第一步的第二层循环中,具体方法如下:
    • 每次查找result中的元素时,将其异或start,将其转为格雷编码
    • 给格雷编码加上前缀1
    • 存入result时,将其异或start,转为以start开头的编码
/*** @param {number} n* @param {number} start* @return {number[]}*/
var circularPermutation = function (n, start) {let result = [start] // // 存储结果,第一个整数为start// 一共计算n位编码,需要循环n次for (let i = 0; i < n; i++) {// 每次计算时,已有的序列不变// 只需要计算已有序列的逆序列,每个再加前缀1// 需要缓存已有序列的长度,用于计算下一段序列const len = result.length// 由于是逆序计算,因此要从len - 1开始加前缀for (let j = len - 1; j >= 0; j--) {// 加前缀1后,把新值存入结果result.push(// 将编码异或start,转为格雷编码((result[j] ^ start) |// 为格雷编码加上前缀1(1 << i)) ^// 将格雷编码异或start,转为以start开头的编码start)}}return result
}

相关文章:

LeetCode题解:1238. 循环码排列,归纳法,详细注释

原题链接&#xff1a; https://leetcode.cn/problems/circular-permutation-in-binary-representation/ 前置条件&#xff1a; 在解题之前&#xff0c;请先一定要阅读89.格雷编码的题解格雷编码可以满足题目的条件“p[i] 和 p[i1] 的二进制表示形式只有一位不同”&#xff0c…...

全新后门文件Nev-3.exe分析

一、 样本发现&#xff1a; 蜜罐 二、 内容简介&#xff1a; 通过公司的蜜罐告警发现一个Nev-3.exe可执行文件文件&#xff0c;对该样本文件进行分析发现&#xff0c;该可执行程序执行后会从远程服务器http://194.146.84.2:4395/下载一个名为“3”的压缩包&#xff0c;解压后…...

线性回归系数解释

线性回归系数解释线性回归系数1、R2R^2R2&#xff08;R方&#xff0c;R-Square&#xff09;2、Adj−R2Adj-R^2Adj−R2&#xff08;调整后的 R 方&#xff09;3、标准误差4、FFF 值5、FFF 显著度6、置信区间7、PPP 值线性回归系数 回归模型得到后会有多个系数&#xff0c;这些系…...

22.2.27打卡 Codeforces Round #852 (Div. 2) A~D

A Yet Another Promotion 题面翻译 题目描述 共 ttt 组数据&#xff0c;每组数据中&#xff0c;你需要买 nnn 公斤苹果&#xff0c;第一天单价为 aaa &#xff0c;但每买 mmm 公斤赠送一公斤&#xff1b;第二天单价为 bbb 。求最小花费。 输入输出格式 第一行一个正整数 …...

如何查看Spring Boot各版本的变化

目录 1.版本 2.基础特性和使用 3.新增特性和Bug修复 1.版本 打开Spring官网&#xff0c;点进Spring Boot项目我们会发现在不同版本后面会跟着不同的标签&#xff1a; 这些标签对应不同的版本&#xff0c;其意思如下&#xff1a; GA正式版本&#xff0c;通常意味着该版本已…...

程序员是否要加入创业公司?

我从1月份入职到2月份离职&#xff0c;历时一个半月。短暂的体验了一段创业生活&#xff0c;更准确的说是一段“待在”创业团队的生活&#xff0c;因为我发现创业本身跟我关系不大。一个半月的就业经历&#xff0c;对任何人来说都不是一个好选择&#xff0c;当然也不是我所期望…...

2023软件测试工程师全新技术栈,吃透这些,起薪就是25k~

相信每个准备软件测试面试的同学&#xff0c;不管你是大学刚毕业&#xff0c;满心憧憬着进入公司实习、非计算机行业转行软件测试、自学测试就业还是培训后就业&#xff0c;都会面临着众多的疑问和不解&#xff0c;那就是该怎么走出着第一步&#xff0c;今天本文一次性告诉你&a…...

【ChatGPT情商大考验】ChatGPT教我谈恋爱

❤️觉得内容不错的话&#xff0c;欢迎点赞收藏加关注&#x1f60a;&#x1f60a;&#x1f60a;&#xff0c;后续会继续输入更多优质内容❤️&#x1f449;有问题欢迎大家加关注私戳或者评论&#xff08;包括但不限于NLP算法相关&#xff0c;linux学习相关&#xff0c;读研读博…...

C++类内存结构模型

内存分区 内存全局数据区&#xff0c;代码区&#xff0c;栈区&#xff0c;堆区。 定义一个类 类的成员函数被放在代码区 类的静态成员变量被放在全局数据区&#xff08;不占用类的存储空间&#xff09; 非静态成员在类的实例内&#xff0c;实例在栈区或者堆区 虚函数指针&…...

HTML#4超链接标签,列表标签,表格标签和布局标签

一. 超链接标签介绍<a> 定义超链接,用于连接到另一个资源herf: 指定访问资源的URLtarget: 指定打开资源的方式代码<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>超链接标签</title> <…...

本科课程【数字图像处理】实验汇总

文章目录 实验1 - 腐蚀与膨胀实验2 - 图像增强实验3 - 图像的几何变换实验4 - 图像的蒙纱效果实验5 - 空洞填充实验6 - 取阈值的邻域平均算法实验7 - 图像的平移与伸缩变换实验1 - 腐蚀与膨胀 实验目的 分析掌握腐蚀与膨胀的基本原理,编写腐蚀与膨胀的算法,并掌握开闭运算的规…...

nginx安装lua、jwt模块,通过lua验证jwt实现蓝绿发布样例

文章目录前言一、基础组件下载二、组件安装1.luajit安装2.lua-nginx-module安装3.lua-resty-core安装4.lua-resty-lrucache安装5.ngx_devel_kit安装6.nginx加载lua模块7.lua-cjson安装8.lua-resty-string安装9.lua-resty-jwt安装10.lua-resty-hmac安装三、验证jwt中属性实现蓝绿…...

【redis的几种数据结构及在Java里的应用案例】

Redis是一款高性能的key-value存储系统&#xff0c;支持多种数据结构&#xff0c;包括字符串、列表、哈希表、集合和有序集合等。下面是Redis的几种数据结构及在Java中的应用案例&#xff1a; string 字符串(String) 字符串是Redis中最基本的数据类型&#xff0c;用于存储字符…...

【mybatis】 01- mybatis快速入门

数据库创建(注意&#xff1a;最好先创建好数据库设置utf8再进行表创建) create database mybatis; use mybatis;drop table if exists tb_user;create table tb_user(id int primary key auto_increment,username varchar(20),password varchar(20),gender char(1),addr varch…...

【C语言每日一题】杨氏矩阵(源码以及改进源码)

【C语言每日一题】—— 杨氏矩阵&#x1f60e;&#x1f60e;&#x1f60e; 目录 &#x1f4a1;前言&#x1f31e;&#xff1a; &#x1f49b;杨氏矩阵题目&#x1f49b; &#x1f4aa; 解题思路的分享&#x1f4aa; &#x1f60a;题目源码的分享&#x1f60a; &#x1f4…...

JavaScript 面向对象【快速掌握知识点】

目录 类和对象 属性和方法 继承 多态 封装 类和对象 类是用于定义对象的模板或蓝图&#xff1b;它包含对象的属性和方法&#xff0c;我们可以使用class关键字来定义类。 class Person {constructor(name, age) {this.name name;this.age age;}sayHello() {console.log(H…...

Qt——自定义Model

众所周知&#xff0c;Qt提供了一套Model/View框架供开发者使用&#xff0c;Model用来提供数据&#xff0c; View则用来提供视觉层的显示。实际上这是一套遵循MVC设计模式的GUI框架&#xff0c;因为Qt还提供了默认的Delegate作为Controller来作为控制器。 MVC的好处这里就不多说…...

用 .NET 启动你的 DJI Ryze Tello 无人机

大疆的 DJI Ryze Tello 是入门级的无人机&#xff0c;不仅在 STEM 教育中有非常广泛的应用&#xff0c;也可以作为编程入门的首选。通过 UDP 协议调用 DJI Ryze Tello SDK 可以让 DJI Ryze Tello 无人机执行起飞&#xff0c;降落&#xff0c;转向以及不同的花式动作。本文将会通…...

sed 功能详解

介绍sedsed是一种流编辑器&#xff0c;它一次处理一行内容&#xff0c;把当前处理的行存储在临时缓冲区中&#xff08;buffer&#xff09;,称为"模式空间"&#xff0c;接着sed命令处理缓冲区中的内容&#xff0c;处理完成后&#xff0c;把缓冲区的内容送往屏幕&#…...

整数二分思路详解

题目描述 给定一个按照升序排列的长度为n的整数数组&#xff0c;以及 q 个查询。 对于每个查询&#xff0c;返回一个元素k的起始位置和终止位置&#xff08;位置从0开始计数&#xff09;。 如果数组中不存在该元素&#xff0c;则返回“-1 -1”。 输入格式 第一行包含整数n和q&a…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...