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

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...