网站建设开发,企业网站建设 电脑配置,东莞网站制作个性化,马鞍山天立建设网站目录
1. 两数之和
1.1 题目解析
1.2 解法
1.3 代码实现
2. 只出现一次的数字II
2.1 题目解析
2.2 解法
2.3 代码实现 1. 两数之和
371. 两整数之和 - 力扣#xff08;LeetCode#xff09;
给你两个整数 a 和 b #xff0c;不使用 运算符 和 - #xff0c;计算并…目录
1. 两数之和
1.1 题目解析
1.2 解法
1.3 代码实现
2. 只出现一次的数字II
2.1 题目解析
2.2 解法
2.3 代码实现 1. 两数之和
371. 两整数之和 - 力扣LeetCode
给你两个整数 a 和 b 不使用 运算符 和 - 计算并返回两整数之和。
示例 1
输入a 1, b 2
输出3示例 2
输入a 2, b 3
输出5
提示
-1000 a, b 1000 1.1 题目解析
本题要求在不使用加减运算符的情况下计算两个整数的和。换句话说要实现“加法”的本质操作无进位相加 进位叠加。 常规解法 最直观的想法是直接写 return a b;但是题目显然禁止这样。 既然不能用 -我们需要模拟“加法”的底层过程。二进制加法本质上有两部分 无进位相加用 异或运算 (XOR) 实现因为相同位相加结果为 0不同为 1。 进位部分用 与运算 (AND) 再左移一位实现因为只有 11 才会产生进位。
这个过程需要循环直到没有进位为止。
思路转折 加法能拆解为两个基本的位运算 → 迭代模拟 → 得到最终和。 这种思路的优点复杂度始终是 O(1)因为整数位数是固定的32 位。 1.2 解法
用 a ^ b 表示“当前无进位的和”用 (a b) 1 表示“进位”不断迭代直到进位为 0。 公式
sum a ^ b
carry (a b) 1
a sum
b carryi初始化 a, b。
ii计算无进位和a ^ b。
iii计算进位(a b) 1。
iiii更新 a 和 b。
iiiii重复直到进位 b 0。
iiiiii返回最终结果 a。 1.3 代码实现
class Solution {public int getSum(int a, int b) {while (b ! 0) {int sum a ^ b; // 无进位和int carry (a b) 1; // 进位a sum;b carry;}return a;}
}复杂度分析 时间复杂度O(1)因为整数位数有限最多 32 次迭代。 空间复杂度O(1)只用常数额外变量。 2. 只出现一次的数字II
137. 只出现一次的数字 II - 力扣LeetCode
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1
输入nums [2,2,3,2]
输出3示例 2
输入nums [0,1,0,1,0,1,99]
输出99
提示
1 nums.length 3 * 104-231 nums[i] 231 - 1nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次 2.1 题目解析
在一个数组里所有数字都出现三次只有一个数字出现一次找出它。 换句话说本质是如何在三次重复噪声中唯一识别出那个单独元素。
常规解法 直观做法是用哈希表统计频次再找频次为 1 的元素。 哈希表能解决但空间复杂度是 O(n)题目要求 O(1)。 因此必须用位运算直接利用二进制规律。
思路转折 每个数的二进制位若出现三次总和必能被 3 整除。 只有那个单独出现一次的数会在某些二进制位上让总和不能整除 3。 所以逐位统计 → 取余 → 重建结果。 这种方法复杂度 O(32n) O(n)空间 O(1) 2.2 解法
按位统计每个二进制位出现的次数模 3 去掉“三次噪声”剩下的位拼接成结果。 公式
bitSum[i] Σ(num i 1)
if bitSum[i] % 3 ! 0 → 结果的第 i 位 1i初始化结果变量 ret 0。
ii遍历 32 位因为 int 是 32 位。
iii对于每一位统计所有数在该位上的 1 的个数。
iiii如果该位 1 的个数 % 3 ≠ 0说明唯一数在该位上有 1。
iiiii把该位写入 ret。
iiiiii返回 ret。
正确性三次重复的性质
题目保证除一个元素外其余元素都出现三次→ 如果我们单独看数组中某一位 i每个出现三次的数会在这位上贡献 0000 或 1113。 换句话说 三次重复的数对第 i 位的总和一定是 3 的倍数。 2.3 代码实现
class Solution {public int singleNumber(int[] nums) {int ret 0;for (int i 0; i 32; i) {int sum 0;for (int num : nums) {sum (num i) 1; // 统计第 i 位}if (sum % 3 ! 0) {ret | (1 i); // 恢复结果的第 i 位}}return ret;}
}复杂度分析 时间复杂度O(32n) ≈ O(n)。 空间复杂度O(1)。
