当前位置: 首页 > article >正文

[LeetCode热门100题]|137,260,268,面试17.19

1、137 只出现一次数字||

        1、题目描述

137 只出现一次数字||https://leetcode.cn/problems/single-number-ii/description/

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

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

 

        2、算法思路

        -2^{31} \leq \text{nums}[i] \leq 2^{31} - 1,所有我们只需要给一个32的空间,并且用一个表示符号位就可以。

        并且统计每个位置上的1是否是3的倍数,不是的话那个 i 位置上就是1

        用a[i]表示a第i个位置的元素,n=nums.length-1,x表示有n个数的第i个位置是上1

itotal结果
313n个0+a[i]%3a[i]
303x个1+a[i]%3a[i]
........3(n-x)个0+3x个1+a[i]%3a[i]
03(n-x)个0+3x个1+a[i]%3a[i

        3、算法代码

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i=0;i<32;++i){
            int total = 0;
            for(int num:nums){
                total +=((num >>i) &1);
            }
            if(total % 3 != 0){
                ans |= (1 <<i);
            }
        }
        return ans;
    }
}

        4、结果运行

2、260只出现一次数字|||

        1、题目描述

260. 只出现一次的数字 III - 力扣(LeetCode)https://leetcode.cn/problems/single-number-iii/description/

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

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

        2、算法思路

  • 先得出a^b=temp
  • temp不可能是0,所有肯定a和b是最少有一个地方不一样,因为是异或,所有temp出现1的地方就是a和b的差别
  • 找出第temp数的第diff个位置是1的地方,就可以知道a和b的第diff个位置的元素不一样,肯定是一个diff位置是0,另一个就是1
  • 把数组中的元素的第diff位置为1的地方放在ret[1],并且给他们异或,因为有2个相同的元素可以刚刚好消除掉,剩下的放入ret[0]也是进行异或操作

        3、算法代码

class Solution {
        public static int[] singleNumber(int[] nums) {
        //1、先把所有的数字异或在一起,然后得出 a^b=temp
        int temp = 0;
        for (int x:nums) temp ^= x;
        //找出temp一个位置是1的地方
        int diff = 0;
        while (true){
            if (((temp >> diff) & 1)==1) break;
            else diff++;
        }
        //然后把第diff位的为1的放在一个ret[1],第diff位置为0反在ret[0]然后全部都异或剩下的就是需要返回
        int[] ret = new int[2];
        for (int x:nums){
            if (((x >> diff)&1)==1)ret[1] ^=x;
            else ret[0] ^=x;
        }
       return ret;


    }
}

        4、结果运行

3、268丢失的数字

可以看我的这篇文章

力扣热门100题【面试题01.01,268】-CSDN博客https://blog.csdn.net/EdgeAI/article/details/146182204?spm=1001.2014.3001.5501

        1、题目描述

268. 丢失的数字 - 力扣(LeetCode)https://leetcode.cn/problems/missing-number/description/给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

        2、算法代码

class Solution {
    public int missingNumber(int[] nums) {
        int ret = 0;
        for(int x:nums) ret ^=x;
        for(int i=0;i<=nums.length;i++)ret ^=i;
        return ret;
    }
}

        3、结果运行

4、面试17.19消失的两个个数字(结合260和268)

这道题目结合260和268一起做很更加简单,这就是为什么我把它放在最后。

        1、题目描述

        2、算法思路

  • 找出缺少的两个数字等到他们的异或
  • 找出他们异或的位置不一样的位置,可以是任何地方位置是1的地方,为了方便我就寻找右边第一个是1的位置
  • 并且按照题目260,只出现一次的数字||| 把他们的第diff个位置为0的异或以后放在ret[0],第diff个位置为1的异或以后放在ret[1]
  • 这个时候数字还没有抵消因为没有一样的,所以这个时候我们遍历1 到 N 所有的整数就可以抵消掉

        3、算法代码

class Solution {
    public int[] missingTwo(int[] nums) {
        //先把缺少的2个数字找出来
        int temp = 0;
        for(int x:nums) temp ^=x;
        for(int i=1;i<=nums.length+2;i++) temp ^=i;

        //目前的temp中有缺少的2个数字的异或
        //先找出从右往左 找出temp的第一个1
        int diff = 0;
        while(true){
            if(((temp >> diff)&1)==1) break;
            else diff++;
        }

        //按照 diff 位置的不同 把第diff位置为0的分成一部分,为1的分成一部分
        int[] ret = new int[2];
         for(int n : nums){
            if(((n >> diff) & 1) == 1) ret[1] ^= n;
            else ret[0] ^= n;
         }
        for(int i = 1; i <= nums.length + 2; i++){
            if(((i >> diff) & 1) == 1) ret[1] ^= i;
            else ret[0] ^= i;
        }
        return ret;
    }
}

        4、结果运行


http://www.kler.cn/a/587752.html

相关文章:

  • 用Lua脚本实现Redis原子操作
  • Google Filament 渲染引擎(2)-Backend 核心类介绍
  • C语言实现冒泡排序,超详解
  • Scheme语言的区块链
  • 【后端开发面试题】每日 3 题(十一)
  • Spring Boot实战:MySQL与Redis数据一致性深度解析与代码实战
  • 一.ffmpeg打开麦克风,录制音频并重采样
  • 地理信息系统(ArcGIS)在水文水资源及水环境中的应用:实践技术与案例分析深度剖析
  • 深入解析 TCP/IP 协议:架构、原理与应用
  • kmp报错→Cannot find skiko-windows-x64.dll.sha256
  • C++ 中的 RTTI(Run-Time Type Information,运行时类型识别)
  • 虚拟电商-数据库分库分表(二)
  • 16.使用读写包操作Excel文件:XlsxWriter 包
  • 中科院自动化所人形机器人研究进展:全面综述与展望
  • Git LFS (Large File Storage) 简介
  • Linux中Gdb调试工具常用指令大全
  • Vue.js 项目部署全解析:从开发到上线的关键旅程题
  • Elasticsearch集群与日志系统实战部署指南
  • JVM内存结构笔记03-方法区
  • Mysql查看执行计划、explain关键字详解(超详细)