力扣刷题日常(一)

简介: 力扣刷题日常(一)

136.只出现一次的数字

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。


你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间


示例 1

输入:nums = [2,2,1]

输出:1


示例 2

输入:nums = [4,1,2,1,2]

输出:4


示例 3

输入:nums = [1]

输出:1

 本题采用位运算进行解答,首先介绍一下异或运算


不同为1,相同为0


  1. 0^1=1
  2. 1^1=0


0与任何数进行异或等于任何数。任何数与本身运算等于0,异或满足交换律和集合率


  1. 0^N=N
  2. N^N=0
  3. A^B=B^A
  4. A^(B^C)=(A^B)^C


本题求出现一次的数,出现偶数次的数异或为0,最后0与出现一次的数异或则等于该数。下面是程序代码:


def singlenumber(nums):
    er=0
    for i in range(0,len(nums)):
        er=er^nums[i]
    return er

260.只出现一次的数字III

给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。


你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。


示例 1:

输入:nums = [1,2,1,3,2,5]

输出:[3,5]

解释:[5, 3] 也是有效的答案。


示例 2:

输入:nums = [-1,0]

输出:[-1,0]


示例 3:

输入:nums = [0,1]

输出:[1,0]

这一题是求只出现一次的两个数,那么我们 应该如何去求解,首先,如果还是按上题思路,我们假定一个er为0,只出现一次的数分别为a,b,对数组中的每个元素都进行异或,那么最终得到的结果将是er=a^b,无法求求出两个元素。


如何求解,首先两个元素是不一样的数字,所以他们两个异或结果不会是0,也就是er=a^b!=0


这个时候我们可以将整个数组分为两部分,取er最右边为1的二进制数,也就是a和b在这个位置不一样,我们可以根据这个数将其余出现两次的元素分为两部分一部分是该位置元素为1,一部分是该位置元素为0。我们分别对这两部分数求异或即可得到对应的出现一次的数。


def singleNumber(nums):
        er=0
        for i in range(0,len(nums)):
            er=er^nums[i]
        #求解二进制最右边为1
        rightone=er&(~er+1)  #对原二进制数求反加1与原二进制进行与运算
        er1=0
        for i in range(0,len(nums)):
            if(rightone&nums[i]==0):
                er1^=nums[i]
        a=er1^er
        return [a,er1]
相关文章
|
3天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
12 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
3天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
10 0
|
3天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
9 0
|
3天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
14 1
|
3天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
9 0
|
3天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
9 0
|
3天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
10 0
|
6天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
12 1
|
6天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
12 0
|
15天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
14 0