首页 > 其他分享 >2024-06-19:用go语言,给定一个起始下标为 0 的整数数组 nums 和一个整数 k, 可以执行一个操作将相邻两个元素按位AND后替换为结果。 要求在最多执行 k 次操作的情况下, 计算数组

2024-06-19:用go语言,给定一个起始下标为 0 的整数数组 nums 和一个整数 k, 可以执行一个操作将相邻两个元素按位AND后替换为结果。 要求在最多执行 k 次操作的情况下, 计算数组

时间:2024-06-19 17:35:34浏览次数:28  
标签:nums mask 整数 按位 数组 ans 操作

2024-06-19:用go语言,给定一个起始下标为 0 的整数数组 nums 和一个整数 k,

可以执行一个操作将相邻两个元素按位AND后替换为结果。

要求在最多执行 k 次操作的情况下,

计算数组中所有元素按位OR后的最小值。

输入:nums = [3,5,3,2,7], k = 2。

输出:3。

解释:执行以下操作:

1.将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]) ,得到 nums 为 [1,3,2,7] 。

2.将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]) ,得到 nums 为 [1,3,2] 。

最终数组的按位或值为 3 。

3.是 k 次操作以内,可以得到的剩余元素的最小按位或值。

答案2024-06-19:

chatgpt

题目来自leetcode3022。

大体步骤如下:

1.使用一个循环从最高位(第 29 位)到最低位(第 0 位)来考虑每个比特位。

2.对于每个比特位 b,首先创建一个掩码 mask,初始为 0。在每次循环中通过将 1 左移 b 位来设置当前考虑的比特位为 1。

3.创建计数变量 cnt 来记录操作次数,初始设为 0。也创建一个变量 and 初始化为 -1(所有位均为 1)。

4.遍历数组中的每个数字 x:

  • 将当前 and 与 x 按位与并存储结果到 and 中。

  • 如果 and 不为 0,增加操作次数 cnt;否则重置 and 为 -1,准备处理下一段。

5.如果计数 cnt 大于 k,则将答案 ans 的第 b 位设置为 1,同时更新掩码 mask,排除当前位。

6.重复以上步骤直至处理到最低位(第 0 位)。

7.返回最终结果 ans,即所有元素按位 OR 后的最小值。

总的时间复杂度:O(N), 其中 N 为数组的长度,因为对每个元素进行了一次遍历。
总的额外空间复杂度:O(1),因为只使用了常数个额外变量来存储操作的中间结果,没有使用随数组长度变化的额外空间。

Go完整代码如下:

package main

import (
	"fmt"
)

func minOrAfterOperations(nums []int, k int) (ans int) {
	mask := 0
	for b := 29; b >= 0; b-- {
		mask |= 1 << b
		cnt := 0  // 操作次数
		and := -1 // -1 的二进制全为 1
		for _, x := range nums {
			and &= x & mask
			if and != 0 {
				cnt++ // 合并 x,操作次数加一
			} else {
				and = -1 // 准备合并下一段
			}
		}
		if cnt > k {
			ans |= 1 << b  // 答案的这个比特位必须是 1
			mask ^= 1 << b // 后面不考虑这个比特位
		}
	}
	return
}

func main() {
	nums := []int{3, 5, 3, 2, 7}
	k := 2
	fmt.Println(minOrAfterOperations(nums, k))
}

在这里插入图片描述

Python完整代码如下:

# -*-coding:utf-8-*-

def min_or_after_operations(nums, k):
    ans = 0
    mask = 0
    for b in range(29, -1, -1):
        mask |= 1 << b
        cnt = 0  # 操作次数
        and_op = -1  # -1 的二进制全为 1
        for x in nums:
            and_op &= x & mask
            if and_op != 0:
                cnt += 1  # 合并 x,操作次数加一
            else:
                and_op = -1  # 准备合并下一段
        if cnt > k:
            ans |= 1 << b  # 答案的这个比特位必须是 1
            mask ^= 1 << b  # 后面不考虑这个比特位
    return ans

nums = [3, 5, 3, 2, 7]
k = 2
print(min_or_after_operations(nums, k))

在这里插入图片描述

标签:nums,mask,整数,按位,数组,ans,操作
From: https://www.cnblogs.com/moonfdd/p/18256759

相关文章

  • 掌握Numpy数组对象ndarray
    Python提供了一个array模块。array和list不同,array直接保存数值,和C语言的一维数组比较类似。但是由于Python的array模块不支持多维,也没有各种运算函数,因此不适合做数值运算。NumPy弥补了Python不支持多维等不足之处,它提供了一种存储单一数据类型的多维数组--ndarray。本次将实......
  • React之类组件与函数组件的区别
         类组件和函数组件在React中是两种定义UI组件的方式,它们在语法、生命周期方法、状态管理等方面存在一些差异函数组件定义:函数组件是通过一个普通的JavaScript函数定义的,接受props作为参数,并返回一个React元素。特点:简洁、易于阅读和测试。无法使用生命......
  • Visual Studio + Qt项目 数组超界不会报错。 堆栈 Cookie 检测代码检测到基于堆栈
    使用vs+Qt项目时,数组超界不会崩溃和报错的问题。 开启以下2个即可。  注意:1.启用了地址擦除系统会造成QT的异常崩溃,原因未知。2.有时会报cookie的错误,数组超界了,在退出函数时才会报错。   ......
  • java object多大 java对象内存模型 数组有多长(八)多线程
    在javaobject多大java对象内存模型数组有多长(四)已经访问的对象记录优化中,用byte数组处理,现在它将暴露在多线程中 1对byte数组加volatile2可见性:用Unsafe控制ConcurrentHashMap内并发数组元素的可见性中的方法来byte数组元素的读写 原子性1)compareandsetbyte 2......
  • LeetCode80. 删除有序数组中的重复项 II题解
    LeetCode80.删除有序数组中的重复项II题解题目链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/题目描述:给你一个有序数组nums,请你原地删除重复出现的元素,使得出现次数超过两次的元素只出现两次,返回删除后数组的新长度。不要使用额外的数......
  • LeetCode26. 删除有序数组中的重复项题解
    LeetCode26.删除有序数组中的重复项题解题目链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array题目描述:给你一个非严格递增排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一......
  • Vue 3中的reactive:响应式对象和数组
    ......
  • 编写函数int fun(int lim,int aa[MAX]),该函数的功能是求出小于或等于lim的所有素数并
    编写函数intfun(intlim,intaa[MAX]),该函数的功能是求出小于或等于lim的所有素数并放在aa数组中,该函数返回所求的素数的个数。#include<stdio.h>#defineMAX100intisPrime(intnum){if(num<2){return0;}for(inti=2;i*i<=num;......
  • 数组趣味玩法:在Java SE中尝试创新玩法
    哈喽,各位小伙伴们,你们好呀,我是喵手。运营社区:C站/掘金/腾讯云;欢迎大家常来逛逛  今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。  我是一名后端开发爱好者,工作日常接触到最多的......
  • 深入探究:Java SE中的数组高级用法
    哈喽,各位小伙伴们,你们好呀,我是喵手。运营社区:C站/掘金/腾讯云;欢迎大家常来逛逛  今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。  我是一名后端开发爱好者,工作日常接触到最多的......