wordpress网站制作app,中国贸易网官网手机版,丹江口网站建设,石家庄 外贸网站建设公司排名题目链接
3133. 数组最后一个元素的最小值
题目描述
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums #xff0c;对于所有 0 i n - 1 #xff0c;满足 nums[i 1] 大于 nums[i] #xff0c;并且数组 nums 中所有元素的按位 AND 运算结果为…题目链接
3133. 数组最后一个元素的最小值
题目描述
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums 对于所有 0 i n - 1 满足 nums[i 1] 大于 nums[i] 并且数组 nums 中所有元素的按位 AND 运算结果为 x 。
返回 nums[n - 1] 可能的 最小 值。
示例 1
输入n 3, x 4
输出6
解释
数组 nums 可以是 [4,5,6] 最后一个元素为 6 。
示例 2
输入n 2, x 7
输出15
解释
数组 nums 可以是 [7,15] 最后一个元素为 15 。
提示
1 n, x 108
求解思路
数组中各项的值按运算最后得到x由于运算两项都为1结果才是1因此可以得出数组nums中每一项的二进制位都包含x的二进制位即x二进制位中取1的位置任一数组元素在该位置都会取1。因为数组nums递增我们可以在x的二进制位为0的位置依次填入数字。例如第0项可以不做填入第1项在最低为填入1。要找数组第n-1项的最小值就相当于在x的0位置上填入n-1如果0的位数不够就在前面补0。i表示x二进制表示的第i位j表示n-1二进制表示的第j位。while循环直到把n-1全部填入为止。如果x的第i位为0则将n-1的第j位填入。
实现代码
class Solution {public long minEnd(int n, int x) {--n; //填入的数值为n-1long ans x;int i 0, j 0;while ((n j) 0) {// 如果x的第i位是0if ((ans i 1) 0) {// 将n-1的第j位填入ans | (long) (n j 1) i;j ;}i ;}return ans;}
}
