第一周学习

1. 总结

开始了第一周的算法训练营学习，这一周感觉事情比较多，课程拖到了周末，有的不太好，下一周要每天刷算法，刷了两天题，感觉算法就是很巧妙，原来可以这样子做，有些点确实需要好好思考才可以想到，每道题换种思路就会变的更快，我是使用python写的，有的题目甚至可以一行就解决

2. 知识download.jpg

2.1 数组download-1.jpg

  • 最基础、最简单的数据结构
  • 数组用一块连续的内存空间，来存储相同类型的一组数据
  • 最大的特点就是支持随机访问，
  • 插入、删除操作比较低效，平均情况时间复杂度为 O(n)。

  • 在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。

    2.2 链表

  • 不连续的存储空间

  • 不支持随机访问
  • 增加和删除O（1）
  • 查找需要遍历整个链表，O（n）

download-2.jpg

2.3 跳表

  • 链表的应用
  • 空间换时间
  • 升维

  • O（logn）

    2.4 栈

  • 先进后出

  • 入栈 push()：O(1)
  • 出栈 pop()：O(1)
  • 取栈顶元素 top() 或 peek()：O(1)download-4.jpg

2.5 队列

  • 受限线性表：先进先出
  • 只能在一端新增删除数据
  • 入队 enqueue()：O(1)

  • 出队 dequeue()：O(1)

    download-5.jpg3. 刷题

  • 完成了作业的7道题

    3.1 26.删除排序数组中的重复项

  • 正向遍历会出错，可以逆向思维，逆向遍历

  • 可以使用双指针解决

    • 双指针很多题都可以解决

      3.2 189.旋转数组

  • nums[:]

    • nums1 = A # 更改 nums1 这一变量名所指向的对象。让 nums1 变量指向 A 所指向的对象
    • nums1[:] = A # 对 nums1 指向的对象赋值。把 A 变量指向的对象的值逐个 copy 到 nums1 指向的对象中并覆盖 nums1 指向的对象的原来值。
    • nums[:]讲解
  • python的优势：a,b = b,a

  • 可以整块的移动

    3.3 1.两数之和

  • 字典

    3.4 21.合并两个有序链表

  • 哑节点

    • 链表很多题都可以使用哑节点解决

  • 递归

    • 这个没有想到

      3.5 66.加一

  • 刚开始觉得很简单，没有考虑到9.。。的情况

  • 对999中的每一位进行处理

  • 也可先转化类型，变成999+1=10000在切成数组

    3.6 88.合并两个有序数组

  • 双指针

  • 对新数组直接排序一下
    • 突然想到一个问题，0都是在后面吗，如果出现1，2，3，0，0，1怎么办
      • 有序数组
  • 看题解提到了 归并排序