青海建设厅职称网站,网页设计总结经验,免费咨询养生顾问,网站开发现在什么软件好来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个整数 n #xff0c;以二进制字符串的形式返回该整数的 负二进制#xff08;base -2#xff09;表示。
注意#xff0c; 除非字符串就是 0#xff0c;否则返回的字符串中不…来源力扣LeetCode
描述
给你一个整数 n 以二进制字符串的形式返回该整数的 负二进制base -2表示。
注意 除非字符串就是 0否则返回的字符串中不能含有前导零。
示例 1
输入n 2
输出110
解释(-2)2 (-2)1 2示例 2
输入n 3
输出111
解释(-2)2 (-2)1 (-2)0 3示例 3
输入n 4
输出100
解释(-2)2 4提示
0 n 109
方法一模拟进位
思路与算法
对于「二进制数」我们可以很直观地得到以下结论
对于 2i如果 i 为偶数时此时 2i (−2)i对于 2i如果 i 为奇数时此时 2i (−2)i1 (−2)i
因此自然可以想到将 n 转换为 −2 的幂数和即此时 n ∑i0m\sum_{i0}^m∑i0m C×(−2)i由于 −2 进制的每一位只能为 0 或 1需要对每一位进行加法「进位」运算即可得到完整的「负二进制」数。对于「负二进制」数此时需要思考一下进位规则。对于 C×(−2)i期望得到如下变换规则 如果 C 为奇数则需要将等式变为 C × (−2)i a × (−2)i1 (−2)i此时第 i 位为 1第 i 1 位需要加上 a 如果 C 为偶数则需要将等式变为 C × (−2)i a × (−2)i1 此时第 i 位为 0第 i 1 位需要加上 a
根据以上的变换规则只需要求出 a 即可。假设当前数位上的数字为 val当前的位上保留的余数为 r在 x 进制下的进位为 a根据「进位」的运算规则可知 val a × x r此时可以得到进位 a val−rx\frac{val - r} {x}xval−r。根据题意可知「负二进制」数的每一位上保留的余数为 0 或 1因此可以计算出当前的余数 r由于在有符号整数的均采用补码表示最低位的奇偶性保持不变因此可以直接取 val 的最低位即可此时可以得到 r val 1。根据上述等式可以知道当前数位上的数字为 val 时此时在「负二进制」下向高位的进位为 a val−(val1)−2\frac{val - (val \ 1)} {-2}−2val−(val1) 。 基于以上进位规则将变换出来的数列进行进位运算即可得到完整的「负二进制」数。整个转换过程如下
将 n 转换为二进制数并将二进制数中的每一位转换为「负二进制」中的每一位变换后的数列为 bits将 bits 从低位向高位进行「进位」运算即将 bits 中的每一位都变为 0 或者 1去掉前导 0 以后将 bits 转换为字符串返回即可。
代码
class Solution {
public:string baseNeg2(int n) {if (n 0) {return 0;}vectorint bits(32);for (int i 0; i 32 n ! 0; i) {if (n 1) {bits[i];if (i 1) {bits[i 1];}}n 1;}int carry 0;for (int i 0; i 32; i) {int val carry bits[i];bits[i] val 1;carry (val - bits[i]) / (-2);}int pos 31;string res;while (pos 0 bits[pos] 0) {pos--;}while (pos 0) {res.push_back(bits[pos] 0);pos--;}return res;}
};执行用时0 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗5.9 MB, 在所有 C 提交中击败了33.33%的用户 复杂度分析 时间复杂度O( C )其中 C 32。需要对 n 转换为二进制位需要的时间复杂度为 O(logn)然后需要对其进行二进制位的中每一位进行「负二进制进位」运算由于整数有 32 位因此需要「负二进制进位」运算 32 次即可。 空间复杂度O( C )其中 C 32。需要对 n 转换为二进制位由于整数最多只有 32 位在此每次采取固定的存储空间为 O(32)。 方法二进制转换
思路与算法
当基数 x 1 时将整数 n 转换成 x 进制的原理是令 n0 n计算过程如下:
当计算第 0 位上的数字时此时 n1 ⌊ n0x{n_0} \over xxn0⌋n0 n1 × x r其中 0 ≤ r x当计算第 i 位上的数字时此时 ni1 ⌊ nix{n_i} \over xxni ⌋ni ni1 × x r其中 0 ≤ r x
按照上述计算方式进行计算直到满足 ni 0 结束。
如果基数 x 为负数只要能确定余数的可能取值上述做法同样适用。由于「负二进制」表示中的每一位都是 0 或 1因此余数的可能取值是 0 和 1可以使用上述做法将整数 n 转换成「负二进制」。具体转换过程如下
如果 n 0 则返回 “0n 1 则直接返回 “1如果 n 1 则使用一个字符串记录余数将整数 n 转换成「负二进制」重复执行如下操作直到 n 0 计算当前 n 的余数由于当前的余数只能为 0 或 1由于有符号整数均采用补码表示最低位的奇偶性保持不变因此可以直接取 C 的最低位即可此时直接用 n1 即可得到最低位的余数将余数拼接到字符串的末尾。将 n 的值减去余数然后将 n 的值除以 −2。
上述操作结束之后将字符串翻转之后得到「负二进制」数。
代码
class Solution {
public:string baseNeg2(int n) {if (n 0 || n 1) {return to_string(n);}string res;while (n ! 0) {int remainder n 1;res.push_back(0 remainder);n - remainder;n / -2;}reverse(res.begin(), res.end());return res;}
};执行用时0 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗5.8 MB, 在所有 C 提交中击败了75.00%的用户 复杂度分析 时间复杂度O(logn)其中 n 是给定的整数。整数 n 对应的「负二进制」表示的长度是 logn需要生成「负二进制」表示的每一位。 空间复杂度O(1)。除返回值外不需要额外的空间。 方法三数学计算
思路与算法
根据题意可知32 位「负二进制」数中第 i 位则表示(−2)i当 i 为偶数时则 (−2)i 2i当 i 为奇数时则 (−2)i −2i 因此可以得到其最大值与最小值分别为如下
最大值即所有的偶数位全部都为 1奇数位全为 0最大值即为 0x55555555 1,431,655,765最小值即所有的偶数位全部都为 0奇数位全为 1最小值即为 0xAAAAAAAA −2,863,311,5300x55555555, 0xAAAAAAAA 均为「十六进制」进制原码表示
令 maxVal 0x55555555由于题目中 n 给定的范围为 0 ≤ n ≤ 109因此一定满足 maxVal n。设 maxVal 与 n 的差为 diff则此时 diff maxVal − n如果我们将 maxVal 在「负二进制」表示下减去 diff那么得到的「负二进制」一定为 n 的「负二进制」。已知 maxVal 中的偶数位全为 1奇数位全为 0此时的减法操作可以用异或来实现:
对于 diff 中偶数位为 1 的位在 maxVal 中需要将其置为 0此时 maxVal 中偶数位全部为 11 ⊕ 1 0偶数位异或操作即可将需要的位置为 0对于 diff 中奇数位为 1 的位在 maxVal 中需要将其置为 1此时 maxVal 中奇数位全部为 00 ⊕ 1 1奇数位异或操作将需要的位置为 1 根据以上推论可以知道「负二进制」减法等同于 maxVal ⊕ diff。按照上述方法可以知道 n 的「负二进制」数等于 ma x Val ⊕ (maxVal − n)我们求出 n 的「负二进制」数然后将其转换为二进制的字符串即可。
代码
class Solution {
public:string baseNeg2(int n) {int val 0x55555555 ^ (0x55555555 - n);if (val 0) {return 0;}string res;while (val) {res.push_back(0 (val 1));val 1;}reverse(res.begin(), res.end());return res;}
};执行用时0 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗5.7 MB, 在所有 C 提交中击败了98.15%的用户 复杂度分析 时间复杂度O(logn)其中 n 是给定的整数。整数 n 对应的「负二进制」表示的长度是 logn需要生成「负二进制」表示的每一位。 空间复杂度O(1)。除返回值外不需要额外的空间。 authorLeetCode-Solution
