C++LeetCode数据结构基础详解

目录
  • 一、只出现一次的数字
  • 二、多数元素
  • 三、三数之和
  • 总结

一、只出现一次的数字

遍历一遍数组利用异或的特性来实现（相同为0，相异为1 ）

例如[4,1,2,1,2] 4和1异或为5 5和2异或为7 7和1异或为6 6和2异或为4 这样就能找出唯一的数字了

public int singleNumber(int[] nums) {
        int res=0;
        for(int i=0;i<nums.length;i++){
           res=res^nums[i];
        }
        return res;
    }

二、多数元素

这题可以利用排序就返回中间位置元素，就是数量超过一半的数字，但是时间复杂度为O(nlogn),

利用摩尔投票法，实现遍历一遍数组就能找到多数元素，

具体实现：定义两个变量计数位和标记位，将计数位初始化为1 ，将标记位为数组第一个元素 如图[2,2,1,1,1,2,2]

public int majorityElement(int[] nums) {
    //摩尔投票法  也叫同归于尽法
    int count=1;
    int res=nums[0];
    for(int i=1;i<nums.length;i++){
        if(res==nums[i]){
            count++;
        }else{
            count--;
            if(count==0){
                res=nums[i];
                count=1;
            }
        }
    }
    return res;
 }

三、三数之和

三数之和有点类似与两数之和，但是难度确增加了不少

思路是先对数组进行排序，之后定义双指针**，左指针为i+1,右指针为最后一个数组元素，进行求和找和第一个数字相等的数**

public List<List<Integer>> threeSum(int[] nums) {
        //排序加双指针
        Arrays.sort(nums);
        List <List<Integer>>  list=new ArrayList<>();
        if(nums==null||nums.length<3){
            return list;
        }
        for(int i=0;i<nums.length-2;i++){
            if(nums[i]>0){
                break;
            }
            if(i>0&&nums[i]==nums[i-1]){//去掉重复元素
                continue;
            }
            int left=i+1; int right=nums.length-1;
            while(left<right){
                int temp=-nums[i];
                if(nums[left]+nums[right]==temp){
                    list.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    left++;
                    right--;
                    while(left<right&&nums[left]==nums[left-1]) left++;
                    while(left<right&&nums[right]==nums[right+1]) right--;
                }else if(nums[left]+nums[right]>temp){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return list;
     }

注意：

1 .给数组排序之后判断元素是否大于0，大于直接返回，后面元素一定大于0

2. 去掉重复的元素，如果值相同继续指针移动

3. Arrays.asList() 是将数组转换成List集合的方法

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C++实现LeetCode(191.位1的个数)

    [LeetCode] 191.Number of 1 Bits 位1的个数 Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). For example, the 32-bit integer '11' has binary representation 00000000000000000000000

  • C++实现LeetCode(207.课程清单)

    [LeetCode] 207. Course Schedule 课程清单 There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given

  • C++实现LeetCode(211.添加和查找单词-数据结构设计)

    [LeetCode] 211.Add and Search Word - Data structure design 添加和查找单词-数据结构设计 Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string c

  • C++实现LeetCode(203.移除链表元素)

    [LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • C++LeetCode数据结构基础详解

    C++LeetCode数据结构基础详解

    目录 一.只出现一次的数字 二.多数元素 三.三数之和 总结 一.只出现一次的数字 遍历一遍数组利用异或的特性来实现(相同为0,相异为1 ) 例如[4,1,2,1,2] 4和1异或为5 5和2异或为7 7和1异或为6 6和2异或为4 这样就能找出唯一的数字了 public int singleNumber(int[] nums) { int res=0; for(int i=0;i<nums.length;i++){ res=res^nums[i]; } return res; } 二.多数元素

  • C语言编程数据结构基础详解小白篇

    C语言编程数据结构基础详解小白篇

    目录 数据结构的基本信息 数据结构 逻辑结构 1,集合结构 2,线性结构 3,树结构 4,图结构或网结构 存储结构 顺序储存结构 链式储存结构 抽象数据类型 介绍 数据结构的基本信息 数据:是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称.如:字符串,实数整数.... 数据元素:是数据的基本单位,在计算机中通常被作为一个整体进行考虑与处理.如组成通讯录的每一个人的信息,数据元素可以完整的描述一个对象. 数据项:是组成数据元素的,具有独立意义的,不可分割的最小单位(也就是

  • Python基础详解之描述符

    一.描述符定义 描述符是一种类,我们把实现了__get__().__set__()和__delete__()中的其中任意一种方法的类称之为描述符. 描述符的作用是用来代理一个类的属性,需要注意的是描述符不能定义在被使用类的构造函数中,只能定义为类的属性,它只属于类的,不属于实例,我们可以通过查看实例和类的字典来确认这一点. 描述符是实现大部分Python类特性中最底层的数据结构的实现手段,我们常使用的@classmethod.@staticmethd.@property.甚至是__slots__

  • python库JsonSchema验证JSON数据结构使用详解

    目录 简单实例 type关键字 object关键字 属性 properties 必需属性 大小 数组属性 items List validation Tuple validation 长度 唯一性 通用关键字 元数据 枚举值 组合模式 anyOf oneOf allOf $schema关键字 正则表达式 构建复杂的模式 重用 JSON Schema是一个用于验证JSON数据结构的强大工具, 我查看并学习了JSON Schema的官方文档, 做了详细的记录, 分享一下. 我们可以使用JSON Sc

  • Ajax基础详解教程(一)

    Ajax基础详解教程(一)

    什么是Ajax? 在研究ajax之前首先让我们先来讨论一个问题 --什么是Web 2.0 .听到 Web 2.0 这个词的时候,应该首先问一问 "Web 1.0 是什么?" 虽然很少听人提到 Web 1.0,实际上它指的就是具有完全不同的请求和响应模型的传统 Web.比如,到 hdu.edu.cn 网站上点击一个按钮.就会对服务器发送一个请求,然后响应再返回到浏览器.该请求不仅仅是新内容和项目列表,而是另一个完整的 HTML 页面.因此当 Web 浏览器用新的 HTML 页面重绘时,可

  • Ajax基础详解教程(二)

    Ajax基础详解教程(二)

    在上篇文章给大家介绍了Ajax基础详解教程(一),讲到Ajax中open方法的第三个参数异步和同步的问题,今天呢,就来继续往下唠,先接着上回的代码 var oBtn = document.getElementById('btn'); oBtn.onclick = function(){ var xhr = null; if(window.XMLHttpRequest){ xhr = new XMLHttpRequest(); }else{ xhr = new ActiveXObject('Mic

  • Java 基础详解(泛型、集合、IO、反射)

    计划把 Java 基础的有些部分再次看一遍,巩固一下,下面以及以后就会分享自己再次学习的一点笔记!不是有关标题的所有知识点,只是自己觉得模糊的一些知识点. 1.对于泛型类而言,你若没有指明其类型,默认为Object: 2.在继承泛型类以及接口的时候可以指明泛型的类型,也可以不指明: 3.泛型也数据库中的应用: 写一个 DAO 类对数据库中的数据进行增删改查其类型声明为 <T> .每张表对应一个类,对应每一张表实现一个类继承该 DAO 类并指明 DAO 泛型为该数据表对应的类,再实现一个与该表匹

  • java实现队列数据结构代码详解

    什么是队列结构 一种线性结构,具有特殊的运算法则[只能在一端(队头)删除,在另一端(队尾)插入]. 分类: 顺序队列结构 链式队列结构 基本操作: 入队列 出队列 给出一些应用队列的场景 1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点. 2):售票口的人买票的顺序的按照先来先买的顺序售票. 3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候. 队列是先进先出的! 我们设置一个叫做LinkQueue<T>的泛型集合类,该类里面有 Node

  • Java数据结构-HashMap详解

    Java数据结构-HashMap 1. HashMap数据结构 没有哈希冲突时,为数组,支持动态扩容 哈希冲突时,分为两种情况: 1.当冲突长度小于8或数组长度小于64(MIN_TREEIFY_CAPACITY默认值为64)时,为数组+链表(Node) 2.当冲突长度大于8时,为数组+红黑树/链表(TreeNode). 红黑树用于快速查找,链表用于遍历. 2. 红黑树 HashMap中的TreeNode是红黑树的实现. TreeNode几个方法 1. 左旋转 static <K,V> Tree

  • Pandas时间序列基础详解(转换,索引,切片)

    时间序列的类型: 时间戳:具体的时刻 固定的时间区间:例如2007年的1月或整个2010年 时间间隔:由开始时间和结束时间表示,时间区间可以被认为是间隔的特殊情况 实验时间和消耗时间:每个时间是相对于特定开始时间的时间的量度,(例如自从被放置在烤箱中每秒烘烤的饼干的直径) 日期和时间数据的类型及工具 datetime模块中的类型: date 使用公历日历存储日历日期(年,月,日) time 将时间存储为小时,分钟,秒,微秒 datetime 存储日期和时间 timedelta 表示两个datet

随机推荐