「每日LeetCode」2020年9月17日
本文最后更新于:2023年3月19日 晚上
剑指 Offer 64. 求 1+2+…+n、剑指 Offer 56 - II. 数组中数字出现的次数 II、剑指 Offer 56 - I. 数组中数字出现的次数
剑指 Offer 64. 求 1+2+…+n
求 1+2+...+n
,要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句(A?B:C)。
示例 1:
1 |
|
示例 2:
1 |
|
限制:
1 <= n <= 10000
思路
递归
使用 js 隐式转换,判断 n 是否大于 0,Boolean(0)为 false,&&断路,终止递归。
幂运算、位移动
根据等差数列求和公式,首项加尾项乘以项数除以 2,可以得到为(1+n)n/2 = (n^2+n) /2,题目要求不出现乘除法,可以使用幂运算及位移动来代替。n^2=n**2,/2=>>2,所以 (n^2+n) /2 = (n ** 2 + n) >> 1
reduce
本质其实还是循环,循环加数组下标,其实加的是 0-9,所以起始值要设为 n。
解答
递归
1 |
|
幂运算、位移动
1 |
|
reduce
1 |
|
剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums
中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1:
1 |
|
示例 2:
1 |
|
限制:
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
思路
MAP
存储每个数计数,等于 3 时删除,最后 map 中只剩下结果,返回即可。
数学
假设对于 a、b、c、d 来说,d 出现了 1 次,其他数字出现 3 次。那么求 d 的值的表达式是:2 _ d = 3_(a + b + c + d) - (3a + 3b + 3c + d)
为了计算(a + b + c + d),可以将数组去重后,再求和。去重借助的是集合(Set)。
位运算
最符合题目要求的解决方法就是:位运算。能在不开辟额外空间的情况下,完成要求。
按照位数(最高 32 位)去考虑,这种方法的关键就是找到对于只出现一次的数字,它的哪些二进制位是 1。
整体算法流程如下:
从第 1 位开始
创建掩码(当前位为 1,其他为 0),count 设置为 0
将每个数字和掩码进行&运算,如果结果不为 0,count 加 1
如果 count 整除 3,说明出现一次的数字这一位不是 1;否则,说明出现一次的数字这一位是 1
继续检查第 2 位,一直到 32 位,结束
状态机
暂时不学
解答
MAP
1 |
|
数学
1 |
|
位运算
1 |
|
剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n),空间复杂度是 O(1)**。
**示例 1:
1 |
|
示例 2:
1 |
|
限制:
2 <= nums.length <= 10000
思路
两个相同数异或得到的值为 0,因此可以知道,对 nums 进行累计异或得到的 s 一定是两个不同的数 a、b 的异或值
创建一个数组记录结果
对每一个数进行与运算,可以将数分为 1、0 两个组,其中 a、b 两个只出现一次的数必定出现在不同的组
进行异或运算,其他出现过两次的数一定会为 0,最后只剩下只出现一次的一个数
解答
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!