专业做物业网站的公司吗,wordpress实现代码块,微信做单网站,港南网站建设. - 力扣#xff08;LeetCode#xff09;
题目
给你两个正整数 n 和 k。你可以选择 n 的 二进制表示 中任意一个值为 1 的位#xff0c;并将其改为 0。
返回使得 n 等于 k 所需要的更改次数。如果无法实现#xff0c;返回 -1。
示例 1#xff1a; 输入#xff1a; n …. - 力扣LeetCode
题目
给你两个正整数 n 和 k。你可以选择 n 的 二进制表示 中任意一个值为 1 的位并将其改为 0。
返回使得 n 等于 k 所需要的更改次数。如果无法实现返回 -1。
示例 1 输入 n 13, k 4输出 2解释最初n 和 k 的二进制表示分别为 n (1101)2 和 k (0100)2我们可以改变 n 的第一位和第四位。结果整数为 n (0100)2 k。示例 2 输入 n 21, k 21输出 0解释n 和 k 已经相等因此不需要更改。示例 3 输入 n 14, k 13输出 -1解释无法使 n 等于 k。
解题方案
1. 逐位遍历 依次取n和k最后一位进行比较 如果last_n last_k 则不需要修改继续遍历如果lask_n ! last_k: 如果last_n 1, last_k 0, 则需要改变操作操作数1如果last_n 0, last_k 1, 则无法通过指定操作使n变成k, 直接返回-1 class Solution:def minChanges(self, n: int, k: int) - int:if n k:return -1if n k:return 0mod 0while k 0 or n 0:last_n n 1 # 取n的最后一位last_k k 1 # 取k的最后一位n n 1k k 1if last_n last_k:print(last_n, last_k, n, k, mod)continueelif last_k 1:return - 1else:mod 1 print(last_n, last_k, n, k, mod)return mod
分析复杂度 时间复杂度是n和k位数的最大值 空间复杂度是
2. 位操作 如果把n和k的二进制为1的位分别看做一个集合那么k应该是n的一个子集。 1. 按位或操作如果操作结果等于k则n可以通过修改某些位置上1为0得到k反之则不能直接返回-1. 2. 已知n可以通过修改某些位置上1为0得到k接下来进行异或操作n和k不同的位为1即需要修改的位为1统计操作结果中1的位数即可 class Solution:def minChanges(self, n: int, k: int) - int:return (n ^ k).bit_count() if (n k) k else -1
分析复杂度
时间复杂度 O(1)空间复杂度 O(1)
