题目136只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
用例
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
解题思路
- 哈希表计数
- 对数组内元素求和,利用set记录不同的数,2倍set的和减去数组和即为所求
- 利用异或性质 x^x=0
代码
1 | from functools import reduce |
类似的题目
137只出现一次的数字 II
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
代码
1 | class Solution: |
260只出现一次的数字 III
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
代码
1 | class Solution: |
268缺失数字
给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
代码
1 | class Solution: |
287寻找重复数
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
说明:
- 不能更改原数组(假设数组是只读的)。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字,但它可能不止重复出现一次。
解题思路
利用排序或者哈希表都可以实现,代码给出利用快慢指针的查找方法
1 | class Solution: |
454四数相加 II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间,最终结果不会超过 231 - 1 。
用例
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解题思路
哈希表记录两数组的求和结果,记录出现的次数
代码
1 | class Solution: |
132312模式
给定一个整数序列:a1, a2, …, an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak < aj。设计一个算法,当给定有 n 个数字的序列时,验证这个序列中是否含有132模式的子序列。
注意:n 的值小于15000。
用例
输入: [1, 2, 3, 4]
输出: False
输入: [3, 1, 4, 2]
输出: True
解题思路
从后向前维护一个单调递减的栈
代码
1 | class Solution: |
发布时间: 2020-05-14
最后更新: 2020-05-15
本文标题: leetcode-day3
本文链接: http://huangketsudou.github.io/2020/05/14/leetcode-day3/
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处