LeetCode Array 101课程的总结

LeetCode网站上提供了一些算法入门的课程，每个课程会讲一种数据结构或者一种算法思想，并提供很多相关题目以供练习。这篇文章开始就是将我跟着学习的这些课程做一个简单的总结。不过它提供的相关练习很多是难在算法的设计上，而不是简单的数据结构的使用。虽然数据结构的使用确实离不开算法的设计，但过难的算法设计容易让人分散太多的精力，从而较少地专注在数据结构的学习上。

Intrduction to Array
  • 一般来说数组大小限定，元素类型相同
  • 读写是数据结构最基本的两个操作
  • 通过数组下标读写数组元素：Array[i]
  • 常用循环来批量读写数组
  • 当不需要用到元素下标时可以用更优雅的循环方式： for each
  • 数组的capacity和length是两个不同的概念，不过一般给的数组，length和capacity是相等的
  • max consecutive ones solution
  • for each 和 for index 速度不完全相同，但感觉还是代码优雅更重要点，不需要用到index的时候就用for each吧，具体可参见这篇文章
Inserting items
  • 增删查的数据结构操作都是基于最基础的读写操作的
  • insert的操作可以分为在数组末尾插入、在数组开头插入和在数组指定位置插入
  • 在数组末尾插入就是简单地在length下标写入，而在指定位置插入就是先把指定位置之后所有元素往后移动一个位置（ 不断读前一个位置写入后一个位置）后，再写入
Deleting items
  • 删除的操作在数组中同样有三种：删除数组尾部的元素、删除数组开头的元素和删除指定位置的元素
  • 删除指定位置的元素可以看做是将指定位置之后的元素全都向前移动一个位置（不断读后一个元素然后写入前一个位置）
  • 习题对++i和i++的使用场景有一定的练习，对边界条件也有一定的练习：基本就是数组为空和数组长度为0
  • 查就是不断地读数组中的元素，并跟指定的数进行比较（查操作也就是遍历操作）
  • 数组的查找操作也可以分为三种，如果已知下标，则查找操作退化为读操作，如果下标未知且数组无序叫线性查找，如果下标未知而数组有序叫二分查找。二分查找一般用在需要多次查找的时候，因为查找之前要先做排序，需要NlogN的时间复杂度
  • Check If N and Its Double Exist 用hashSet的方法在这里。
In-place operations ( 就地操作 )
  • 直接在输入数组上操作，不用借用新的数组
  • 就地操作经常会使用到双指针技术
  • 如果输入数组在其它地方还用到了，就不应该用就地操作去覆写它
  • Find All Numbers Disappeared in an Array的solution，不过我发现在Accepted Solutions Runtime Distribution页面，点击直方图也会显示对应运行时间的代码，只不过没有解释

基本完成了所有内容，除了一个锁着的问题。总结起来就是：

  1. 读写操作是最基础的，增删查改等操作都是基于它们的
  2. 数组的算法设计中经常用到指针的技术来减少空间复杂度
赏

谢谢你请我喝咖啡

微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家