algorithm004-03/algorithm004-03

极客大学「算法训练营第四期 - 3 班」作业提交仓库

讲师课件下载地址

请大家通过该链接查看讲师课件并进行下载：链接:https://pan.baidu.com/s/1uoU_2toXHYw_eQOHMpogfQ 密码:94kd

仓库目录结构说明

1. Week_01/ 代表第一周作业提交目录，以此类推。
2. Week_01/id_089代表学号为 089 的学员第一周的作业提交目录，以此类推。
3. 每个目录下面均有一个 NOTE.md 文档，你可以将自己当周的学习心得以及做题过程中的思考记录在该文档中（该项不属于作业内容，是可选项）。

作业提交规则

算法题作业的提交

1. 先将本仓库 fork 到自己的 GitHub 账号下。
2. 将 fork 后的仓库 clone 到本地，然后在本地新建、修改自己的代码作业文件，注意： 仅允许在和自己学号对应的目录下新建或修改自己的代码作业。作业完成后，将相关代码 push 到自己的 GitHub 远程仓库。
3. 提交 Pull Request 给本仓库，Pull 作业时，必须备注自己的学号和提交第几周的作业，如089-Week 02，是指学号为089的学员提交的第二周的算法题作业。
4. 代码文件命名规则：**LeetCode_题目序号_学号，比如学号为 089 的学员完成 LeetCode_33_108 的第 2 题 后，请将代码文件名保存为 LeetCode_2_089.py (假设你使用的是 Python 语言)。
5. 务必按照Pull Request的备注形式和作业文件的命名进行提交，班主任会严格按照命名形式统计大家的作业。

学习总结的提交

1. 除代码作业外，我们要求学员每周提交一篇当周的学习感想，直接发一个独立的 issue 即可，issue 标题格式为【学号-周】总结题目】。例如【089-week 03】二叉树的更多理解是指学号089的学员提交的第三周的学习总结。可参考：#1

Review 与点评

1. 我们要求学员每周至少Review并点评其他5位同学的作业，点评直接回复在代码作业或学习总结下面都可。

注意事项

1. 作业公布地址： 我们会在置顶的 issue 中公布当周的算法练习题以及其他注意事项。
2. 如果对 Git 和 GitHub 不太了解，请参考 Git 官方文档 或者极客时间的《玩转 Git 三剑客》视频课程。从来没用过github的学员看这里的git_quick_guide，或许会对你有帮助奥。https://github.com/algorithm004-01/algorithm004-01/tree/master/Utils

algorithm004-03's Issues

【423-Week 预习周】 预习周的总结

预习周总结

关于上课

• 预习
• 互动跟着老师的思路一起思考问题
• 课后作业 (切题)

理想结果

• 对算法理解达到顶尖水平
• 从容应对一线互联网公司的算法面试
• LeetCode 300+ 题量

学习方法

学习方法源自Outlier(异类)这本书
精通一个领域需要通过:

• Chunk it up(庖丁解牛, 脉络连接)Link
• DataStruct 数据结构
  • 一维
    • 基础: 数组(array), 链表(linked list)
    • 高级: 栈(stack), 队列(queue), 双端队列(deque), 集合(set), 映射(hash or map), etc
  • 二维
    • 基础: 树(tree), 图(graph)
    • 高级: 二叉搜索树 (binary search tree, read-black tree, AVL), 堆(heap), 并查集(disjoint set), 字典树(Trie), etc
  • 特殊
    • 位运算(Bitwise), 布隆过滤器(BloomFilter)
    • LRU Cache
• Algorithm 算法 Link
  • If-else, switch -> branch
  • for, while loop -> Iteration
  • 递归Recursion(Divide & Conquer, Backtrace)
  • 搜索Search: 递归优先搜索DFS, 广度优先搜索BFS, A*, etc
  • 动态规划 DP
  • 二分查找 Binary Search
  • 贪心 Greedy
  • 数学 Math, 几何 Geometry

  • Attention: 在脑中回忆每种算法的**和代码模板, 只有动手做知识体系才能成为自己的本能

• Deliberate Practicing 可以练习
  • 职业化运动,基本功是区别业余选手和职业选手的根本,基础动作的分解训练和反复练习是关键

  • 我们最大的误区就是 只做一遍,这是完全不够的

  • 切题四件套
  • Clarification (反复沟通题目,确保自己理解正确)
  • Possible Solutions (多想几个解法, 分析时间空间复杂度,找到最优解法)
  • Codeing
  • Test
  • 五遍刷题法
  • 第一遍 5-15min: 读题思考,如果实在没有思路不要纠结直接看解法,然后背诵默写
  • 第二遍 直接写代码不要再看解法了,在LeetCode上提交,对比多种解法,体会和优化
  • 第三遍 一天后
  • 第四遍 一周后
  • 第五遍 面试前一周到两周恢复性训练
• Feedback
• 主动反馈: 主动学习高手的代码, LeetCode, GitHub上,以及优秀的源码
• 被动反馈: code review,高手来看你的代码,可遇不可求

工具环境的准备及**:

IDE, 快捷键, 自顶向下的编程

时间复杂度:

• Big O notation
• 常见的时间复杂度
  • O(1) Constant Complexity
  • O(log n) Logarithmic Complexity
  • O(n) Linear Complexity
  • O(n^2) N square Complexity
  • O(2^n) Exponential Growth
  • O(n!) Factorial
• additional -> 最好,最坏,平均,均摊 时间复杂度
• 主定理

【713-Week 预习周】预习周的总结

• 最大误区: 只做一遍
• 拆分知识点
• 刻意练习 => 过遍数
  • 五遍刷题法则
  • 弱项,缺陷
  • 不舒服,不爽是成长的点
• 寻求反馈

所有复杂的算法本质是找重复的单元是什么

---

数据结构

• 一维
  • 基础
    • 数组 array
    • 链表 linked list
  • 高级
    • 栈 stack
    • 队列 queue
    • 双端队列 deque
    • 集合 set
    • 映射 hashmap
• 二维
  • 基础
    • 树 tree
    • 图 graph
  • 特殊
    • 二叉搜索树 binary search tree
    • 堆 heap
    • 字典树 trie
    • 并查集 disjoint set
• 特殊
  • 位运算 bitwise
  • 布隆过滤器 bloom filter
  • LRU cache

算法

• if-else 逻辑切换
• loop 循环
• recursive 递归 -> 自己调用自己, 处理不当容易栈溢出
  • Divide & conquer 分治
  • backtrace 回溯
• 搜索
  • DFS(deep first search) 深度优先搜索
  • BFS(breadth first search) 广度优先搜索
  • A* 启发式搜索
• 动态规划 DP(Dynamic Programming)
• 二分查找 binary search
• 贪心 greedy
• 数学 Math, 几何 Geometry

反馈

• 主动式(自己寻找)
  • 高手代码(LeetCode, GitHub)
  • 第一视角直播
• 被动式
  • 高手给你指点
  • code review

切题四件套 遇题四步思考方式

• Clarification 明确题目
• Possible Solutions 所有可能解题方法,分析时间/空间复杂度, 找最优化
• Coding 编码
• Test Cases 测试用例

五遍做题法

第一遍

• 5分钟 读题+思考
• 直接看解法: 多种解法, 比较优劣
• 背诵&默写好的写法

第二遍

• 马上自己写, LeetCode提交
• 多种解法比较, 体会, 优化

第三遍

• 过了24h之后再做一遍
• 不同解法熟练程度的专项练习

第四遍

• 过了一周之后再训练

第五遍

• 面试前一周康复性训练

---

备注

• git提交作业方法
  • https://shimo.im/docs/9ty8pjk6ckxGrkQt/read
• 脑图
  • https://naotu.baidu.com/home
• 入学考试
  • https://exam.kaoshixing.com/exam/wrong_topic

[118-Week 预习周] 预习周的总结

Assignments

1. Data Structure Mindmap
2. Algorithm Mindmap
   Note: both files are protected, the password to access them is geekbang

---

Week_00 Recap

Systematic Thought Process

• Clarification to make sure you understand the problem correctly
• Get all the possible solutions
  • compare (time and space complexity)
  • find the most optimal solution
• Coding
• Test cases

How to Leetcoding

For each problem, do it at least 5 times:

1. Spend 5 min (no more than 15 min) to read problems and think. If I can't do it, check the solutions directly (focus on top 3 solutions) and compare different solutions. Memorize the good solutions
2. Try it myself right after => Submit to Leetcode till it's accepted => Optimize the solutions
3. Try it again after a day
4. Try it again after a week
5. Practise a week before the interview

Deliberate Practicing

To become an expert in an area:

• Chunk it up: divide and conquer, connect dots, make mindmaps
• Deliberate Practicing: step outside the comfort zone, dissect the drills and practice repeatedly, quantity matters, need at least do it 5 times
• Constructive Feedback

Inspired from the books below

1. Outliers
   Actually this book is a tad overrated, check out the article below
   Scientists Debunk The Myth That 10,000 Hours Of Practice Makes You An Expert
2. Peak
   This book provides a better explanation and review on 'Deliberate Practice'

Set up Environment Properly

My Environment:

• Favorite IDE: Emacs + Org Mode
• Productive IDE: Jetbrains Suite + Leetcode plugin
• Terminal: iTerm2 + zsh(oh my zsh) + Agnoster Theme + Syntax Highlighting
• Code Style: PEP8 (Python), Google Java Style Guide
• Top-Down Coding
  • newspaper metaphor
  • Solve the top level main stream problem first, then clean up with supporting functions

Big O and Some good references

• Big O Cheat Sheet
• Big O Cheat Sheet
• Big O Cheat Sheet
• Algorithm Visualizer

【618-week01】忌空想 勤动笔

忌空想 勤动笔

本人是从业12年的老码农了，但工作中多写业务和框架，对纯算法接触比较少，数据结构仅知道一些比较基本的。

第一周的课程内容比较简单，可以顺利接受，就算是复习吧。鉴于这段时间工作不忙，有时间把所有作业都过一遍。

有些比较简单的，就不多赘述了，但是的确有些题目比较考验思路。我的经验是，如果大脑空想不出，拿起纸笔、开始推导和演算，很多想法就这么出来的。比如"合并有序链表和数组"、“移动0”，都是在纸上推导出算法并加以改进的。"设计循环双端队列"的数组环状指针，也是一画图就想明白的。

和做数学题一样，纸笔是我们最好的武器，代码是我们思考的最终成果。

当然也有难度的题，"接雨水"就是。自己只想出暴力法，其他思路不清晰，于是看了题解，直接看栈的方法，这里我先看别人的思路说明，觉得理解了，然后自己推导再写代码，而非直接看别人的代码。说到这里，感觉题解的代码虽然精简，但是可读性不是很好，自己在写的时候，我会顺着题解的思路，自己写代码，最终的代码行会多一些，变量也多了一些，但是我觉得这样可以更好让读者理解思路。

至于动态规划的解法，虽然还不明白什么是动态规划，但是就这题本身而言，“找到每个格子左右两边的最大高度”这句话是点睛之句，事实上看了这句话之后，自己也能很快写出和题解类似的解法了，可见思路还是最重要的。

再说大一点，工作那么多年，一直是这么个方法：遇到一个设计问题，先思考、再画图，不断迭代，搞清楚了，再动手写代码，验证原型后，再完善代码细节。算法本质也是如此。

改写代码

关于Deque等数据结构，本来就熟悉，多年前就在工作中使用新的api了(其实应该这样说，尽量使用语义清晰、不晦涩的api，自己api也是如此)。

	Deque<String> deque = new LinkedList<>();

	deque.addFirst("a");// deque.push("a");
	deque.addFirst("b");// deque.push("b");
	deque.addFirst("c");// deque.push("c");
	System.out.println(deque);

	String str = deque.peekFirst();// String str = deque.peek();
	System.out.println(str);
	System.out.println(deque);

	while (deque.size() > 0) {
		System.out.println(deque.removeFirst());// System.out.println(deque.pop());
	}

	System.out.println(deque);

Queue源码分析

工作中对于队列用得比较多的地方就是线程池了，线程池里要求的队列为阻塞队列，简单地说，阻塞队列满时，添加方法会阻塞，空时获取时会阻塞，且它是线程安全的。这里对并发编程知识不做过多阐述，直接看两个最常见的实现ArrayBlockingQueue和LinkedBlockingQueue。

以下不对并发编程的相关代码做分析，大致上只要知道，他们都是通过ReentrantLock控制同步，Condition控制线程的等待和唤醒。

ArrayBlockingQueue内部通过一个数组存储元素，所以它是有界的，满了也不扩容。初始时，putIndex和takeIndex都是0，每次put，元素放入putIndex，然后putIndex++，移出则从takeIndex获取，然后takeIndex++。如果索引到了尾部，则归0，不用担心覆盖0，此时0位置的元素肯定已经被移出了。

LinkedBlockingQueue内部是链表，所以它是无界的，可以添加任意多的元素，只要内存足够。内部有头尾节点指针，具体不阐述了，比较简单。

PriorityQueue源码分析

内部通过一个queue数组存放元素，通过资料查阅直到这个数组描述的是一个二叉小顶堆，这个概念先不细究（目前真不懂，但后面再理解也行，毕竟其机制与PriorityQueue关系不大）。

第一个元素直接放入数组头，后续的元素存放时，会通过siftUp方法调整queue内部元素的顺序，保证最小的元素在数组头，同理移出元素后，通过siftDown调整queue内部元素的顺序，也一样确保最小的元素在数组头。

对于二叉小顶堆，插入和移出一个元素的时间复杂度都是O(logn),但是peek是O(1),因为不涉及移出元素。

[118-Week01] Recap

[118-Week01] Recap

1. Practice

• There's really no shortcut to it, just practice relentlessly by following the 5-step method. Peace out AI...

  

2. Time-Space Tradeoff

• Using more space for better performance is a common practice

• Skip List is a good example here, use additional references to speed up the lookup process

  

• Definition from wikipedia:

  • A space–time or time–memory trade-off in computer science is a case where an algorithm or program trades increased space usage with decreased time.
  • Here, space refers to the data storage consumed in performing a given task, and time refers to the time consumed in performing a given task.

3. Common Techniques.

• Iterate an array with two pointers without lookup elements repetitively

  • It uses nested loop, so its time complexity is at least O(n^2)

  for i in range(len(arr) - 1):
      for j in range(i+1, len(arr)):
          # do something
          pass

• Use two pointers on either side of array, then converge to the middle

  • It doesn't use nested loop, so its time complexity starts from O(n)

  i = 0
  for j in range(len(arr)-1, i, -1):
      #do something
      i += 1

  • Alternatively use while loop

  i, j = 0, len(arr)-1
  while i < j:
      # do something
      i += 1
      j -= 1

• Fast and Slow Pointers

  • Used to find if there's a loop in the linked list
  • Space complexity is O(1)

  fast = node.nxt
  slow = node.nxt.nxt
  # check if fast and slow will meet

• Find all the solutions, start with Brute Force if possible

• Try to find a solution progressively (Climbing Stairs):

  • What's the simplest case
  • Generalization: find the most recent and repeatable sub-problem and its solution
  • In the end, all the algorithms can be converted to if...else, for, while or recursion

4. Linked List

• A truly dynamic linear data structure

• Time complexity of common operations

  Operations	Linked List	Array
  Add Last	O(1)	O(1)
  Remove Last	O(1)	O(1)
  Add any	O(1)	O(n)
  Remove any	O(1)	O(n)
  Random Lookup	O(n)	O(1)

• Implement a Linked List in Python

  • Will only implement initialization, delete and add
  • Add Last, Remove Last can be built from general add and remove methods

  class LinkedList:
      
      class _Node:
          # internal Node class
          def __init__(self, val=None, nxt=None):            
              self.val = val
              # use nxt here for next as next is a keyword in Python
              self.nxt = nxt
              
      def __init__(self):
          self._dummy_head = self._Node() 
          # create a dummy head of None, pointing to None
          self._size = 0
          # size of the Linked List initiated to 0
          
      def add(self, idx, e):
          # report error if index is illegal
          if not(0 <= idx < self._size):
              raise ValueError("Add Failed. Illegal Index Position")
              
          # iterate from the dummy head to idx
          curr = self._dummy_head
          for i in range(idx):
              curr = curr.next
          new_node = self._Node(e)
          # key: first connect new_node next, then reconnect original idx
          new_node.nxt = curr.nxt
          curr.nxt = new_node
          # resize the linked list
          self._size += 1
          
      def remove(self, idx):
          # report error if index is illegal
          if not(0 <= idx < self._size):
              raise ValueError("Add Failed. Illegal Index Position")
          # iterate from the dummy head to idx
          curr = self._dummy_head
          for i in range(idx):
              curr = curr.nxt
          delete_node = curr.nxt
          # jump over delete_node
          curr.nxt = curr.nxt.nxt
          delete_node.nxt = None
          self._size -= 1
          

5. Stack

• FILO

• Time complexity is O(1) for pop and append

• Time complexity is O(n) for lookup, as elements in stacks are orderless

• In Python, list can be used to implement a stack Python Doc

• Implement a stack in Python using list

  • list.pop()remove the top element from the stack
  • list.append() add the element to the top of the stack

• Implement a stack in Python

  class Stack:
      def __init__(self):
          self._data = list()
          
      def push(self, ele):
          self._data.append(ele)
          
      def pop(self):
          if not len(self._data) > 0:
          	raise ValueError("Stack is empty")
          self._data.pop()

6. Queue

• FIFO

• Time complexity is O(1) for enqueue and dequeue

• Time complexity is O(n) for lookup, as elements in queues are orderless

• Python has a built-in queue library

  • Queue classes are usually used in threaded programming
  • queue.Queue() FIFO queue, the regular queue as we know
  • queue.SimpleQueue it's also a FIFO queue, but it cannot be used for task tracking
  • queue.LifoQueue() LIFO queue, similar to a stack
  • queue.PriorityQueue() , Priority queue, kept sorted with heapq

• Common built-in Queue methods

  • Queue.qsize() get the size of the queue
  • Queue.empty() check if a queue is empty
  • Queue.full()check if a queue is full
  • Queue.put()Put item into the queue => enqueue
  • Queue.get()Remove and return the removed element from queue => dequeue

• A queue can also be simply implemented with list in python

  class Queue:
      def __init__(self):
          self._data = list()
          
      def enqueue(self, ele):
          # add data to the front of queue
          self._data.insert(0, ele)
          
      def dequeue(self):
          if not len(self._data) > 0:
          	raise ValueError("Queue is empty")
          self._data.pop()        

7. Deque

• double-end queue

• Can perform enqueue and dequeue on both top and tail

• Python has a built-in deque data structure in collections library Deque

• Common methods

  • append(ele), add element to the right side of the deque

  • appendleft(ele), add element to the left side of the deque

  • pop() Remove and return an element from the right side of the deque. If deque is empty, raise IndexError

  • popleft() Remove and return an element from the left size of the deque. If deque is empty, raise IndexError

    Additionally, python deque and extend iterables (list, tuple etc.)

  • extend(iterable) extend the right side of the deque by appending elements from the iterable

  • extendleft(iterable) extend the left side of the deque by appending elements form the iterable

• Use Python to rewrite Deque, it's quite different from Java, so just for reference

  from collections import deque
  d = deque()
  # python can extend a whole iterable into a deque
  d.extend(["a", "b", "c"])
  print(d)
  # for peek, python deque doesn't have built-in method, but there's no need
  # simply look it up as a list
  # peekFirst is equivalent to d[0], peekLast is equivalent to d[-1]
  str = d[0]
  
  while not d.empty():
      d.pop()
  print(d)

8. Priority Queue

• Elements in Priority Queues have priorities, it's more similar to a tree-like data structure.
• There are multiple ways to implement it, e.g. heap, BST, AVL, Red-Black Tree etc.
• Time Complexity is O(1) to add element
• Time Complexity is O(logN) to remove element
• For priority queues, it's important to keep the elements in order.
  • Assume using a maxheap to represent a priority queue
  • Enqueue:

    • step1: when add an element, add it to the last of queue

    • step2: then need to use sift up to make sure all elements are in order

def _sift_up(self, k):
    while k > 0 and self._data.get(k) > self._data.get(self._parent(k)):
    self._data.swap(k, self._parent(k))
    k = self._parent(k)

• Dequeue

  • step 1: remove the the max element

  • step 2: after removing max element, perform sift down to make sure the elements are in order

def _sift_down(self, k):
    while self._left_child(k) < self._data.get_size():
        j = self._left_child(k)
        if j + 1 < self._data.get_size() and self._data.get(j + 1) > self._data.get(j):
            # right child is greater
            j = self._right_child(k)
        # self._data.get(j) is the max(left.child, right.child)
        if self._data.get(k) > self._data.get(j):
            break
        self._data.swap(k, j)
        k = j

• Python uses heapq to keep the priority queues in order. Here, they use the min heap rather than max heap. some commonly useful methods

  • heapq.heapify(x): transform a list into a heap, in-place, complexity is O(n)

  • heapq.heappush(heap, item): push the item into the heap, keeping the heap in order

  • heapq.headpop(heap)Pop and return the smallest item from the heap, keeping the heap in order

算法训练营（第4期）第二周作业

要求

1. 每周从覃超老师布置的题目中，至少完成并提交两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章或总结，切忌流水账。

作业提交 Deadline

2019年10月27日 23:59 （以当地时间为准）
未按时提交作业，会在个人作业总分中 -3 分

本周作业概述

本周需要完成学习的视频内容：

• 第 5 课 | 哈希表、映射、集合
• 第 6 课 | 树、图、二叉树、二叉搜索树
• 第 7 课 | 泛型递归、树的递归
• 第 8 课 | 分治、回溯

以上两课视频后，覃超老师都给出了大家可以练手的算法题。

本周算法习题库：

第五课

写一个关于HashMap的小总结
说明：对于不熟悉Java语言的同学，此项作业可选做。
请大家将HashMap的小总结放在本周学习总结中一并提交
https://leetcode-cn.com/problems/valid-anagram/description/
https://leetcode-cn.com/problems/group-anagrams/
https://leetcode-cn.com/problems/two-sum/description/

第六课

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

第七课

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
https://leetcode-cn.com/problems/combinations/
https://leetcode-cn.com/problems/permutations/
https://leetcode-cn.com/problems/permutations-ii/

第八课

https://leetcode-cn.com/problems/majority-element/description/
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
https://leetcode-cn.com/problems/n-queens/

【503-预习周】 预习周的总结

精通算法学习方法论

• Chunk it up 切碎知识点
  • 分解数据结构
  • 分解算法
• Deliberate Practicing 刻意练习
  • 最大误区：只练习一遍
  • 切题四件套
    1. Clarification：审题，真正理解题目意思
    2. Possible solutions：思考尽可能的解法，分析并比较每种解放的时间、空间复杂度，找出最优解法
       • optimal（加强）****
       • compare (time/space)
    3. Coding（多写）：思考完后才开始写代码
    4. Test cases: 写完后，列举几个测试用例，验证代码正确性
  • 五步刷题法
    • 每道算法题至少练习 5 遍 （五毒神掌）
    1. 第一遍
       • 5~15分钟：读题 + 思考
       • 直接看解法：注意！多解法，比较解法优劣
       • 背诵、默写好的解法
    2. 第二遍
       • 马上自己写 —> LeetCode 提交
       • 多种解法比较、体会 —> 优化！
    3. 第三遍
       • 过了一天后，再重复做题
       • 不同解法的熟练程度 —> 专项练习
    4. 第四遍
       • 过了一周：反复回来练习相同题目
    5. 第五遍
       • 面试前一周恢复性训练
• Feedback 反馈
  • 主动型反馈
    • 学习高手的代码
      • GitHub
      • LeetCode
      • 源码
  • 被动式反馈
    • 让别人对自己的代码 code review

工欲善其事，必先利利其器器

• 对常用工具进行配置
• 刻意练习基本功和编程指法
• ⾃自顶向下的编程⽅方式

时间复杂度

• Big O notation：大 O 表示法
• 常见的算法时间复杂度
  • O(1): Constant Complexity 常数复杂度
  • O(log n): Logarithmic Complexity 对数复杂度
  • O(n): Linear Complexity 线性时间复杂度
  • O(n^2): N square Complexity 平⽅方
  • O(n^3): N square Complexity ⽴立⽅方
  • O(2^n): Exponential Growth 指数
  • O(n!): Factorial 阶乘

• 主定理 Master Theorem
  • 参考资料
    • Master Theorem
    • 主定理

【313-Week 预习周】 预习周的总结

精通一个领域

• 切碎知识点
• 刻意练习
• 反馈

五步刷题

• 过遍数：（五毒神掌）
• 练习缺陷、弱点的地方

作业

数据结构与算法脑图

【028-预习周】预习周的总结

预习周
数据结构：

一维
基础：数组、链表
高级：栈、队列、双端队列、集合、映射等

二维
基础：树、图
高级：二叉搜索树、堆、并查集、字典树

特殊
位运算、布隆过滤器
LRU Cache

算法：
if-else,switch
for,while loop
递归

搜索：
深度优先搜索、广度优先搜索、A*
动态规划
二分查找
贪心算法
数学、几何

化繁为简：找到重复单元
Delibrate Practise 刻意练习
基本功是区别业余和职业转手的根本

五遍刷题法
练习弱项
Feedback 反馈
即时反馈
主动性反馈(自己去找)：高手代码 第一视角直播
被动式反馈：code review、教练打给你看

切题四件套
1、多看题目，确保自己理解正确
2、想所有可能的解法
所有可能的解法过一下，比较时间、空间复杂度
找出最优解法
3、写代码
4、例举测试样例

五遍刷题法
1、5分钟 读题+思考 => 基础弱可以10～15分钟 实在没有思路 => 直接看解法，比较多种解法的优劣性
2、自己写代码 每种解法都要比较
3、过一天后，再重新做一遍前一天做过的题目
4、过一周后，反过来练习
5、面试前一周恢复性训练

还是得多多练习，加强对ide的快捷键的使用

【093 Week 预习周】预习周总结

三班一组刘志青

学习感想和疑问：
本周课程比较简单，基本上都能看得懂。
除了最后空间复杂度听了也是一头雾水，
主理论（Master theorem）也没弄清楚 。思考题更是懵逼。
明天再来看一遍再看下一课。
顺便把思考题一道一道完成。
自己用的是python，加了LeetCode插件，貌似和老师讲解用的vs code不大相符，操作起来稍微费了点时间，但最终解决了。

1.老师推荐使用谷歌，但是境内一般网络无法正常使用谷歌。个人自己搭建了一个vps，但是流畅性很差。期望老师什么时候也能普及一下相关设置或者工具。
2.关于github的使用，如clone到本地，然后本地在push到自己的github，再个人github去push到班级github，这里能不能有说明教程？或者附上相关教程的链接？不然github和git不熟的同学就交不了作业。。。

---

以下是学习笔记

老师的要求
基础知识预习和查看—看ppt，去github或者找老师要；
学习课程，参与互动，一起思考；
课后习题完成；

期待实现的培训效果

对于算法数据结构的理解--职业顶尖级别
拿下一线互联网公司面试和offer
LeetCode 300+的积累（基础要求200+，挑战要求500+）

学习方法来源：《异类》（原名outliers）
（精通任一个领域）学习方法总结如下：
1.Chunk it up 切碎知识点
2.Deliberate practicing 刻意练习
3.Feedback 反馈

数据结构和数据类型：
一维：
基础：数组array（string），链表 linked list
高级：栈stack，队列queue，双端队列deque，集合set，映射map（hash or map）etc
二维：
基础：树tree， 图 graph
高级：二叉搜索树 binary search tree（特殊 red-black tree， AVL），堆 heap，并查集disjoint set，字典上trie，etc
特殊：
位运算：bitwise，布隆过滤器BloomFitter
LRU Cache

八种常见算法：
基础三种：

• If-else,switch —>branch
• For, while loop —>iteration
• 递归recursion(Divide & Conquer, Backtrace)
  高级三种：
• 搜索search; 深度优先搜索Depth first search, 广度优先搜索Breadth first search， A*, etc
• 动态规划：Dynamic Programming
• 二分查找 binary Search
• 贪心算法 greedy
• 数学 math，几何 geometry

最大误区：做LeetCode只做一遍就是最大误区，需要多做几遍，用不同方法。

刷题应该用如下方法，简称五毒神掌。

刷题第一遍
• 5分钟:读题 + 思考
• 直接看解法:注意!多解法，比较解法优劣 • 背诵、默写好的解法
刷题第二遍
• 马上自己写 —> LeetCode 提交
• 多种解法比较、体会 —> 优化!
刷题第三遍
• 过了一天后，再重复做题
• 不同解法的熟练程度 —> 专项练习
刷题第四遍
一周后，反复回来联系相同题目
刷题第五遍
面试前一周恢复性训练

切题四件套：
Clarification：反复明确题目要求
Possible solutions
--compare（Time/space）
--optimal（加强）
Coding（开始写代码）
Test cases(测试用例)

【203-Week 01】周总结+源码分析

解题思路

• 找最近重复子问题
• 升维+空间换时间（例：跳表）
• 左右夹逼：左右边界向中间收敛
• 如果一个问题具有最近相关性，考虑用 栈 来解决

以上是老师讲的解题思路，特别是第一条，基本上贯穿在所有的算法中，计算机能处理的就是 if else for loop recursion 以不变应万变

改写代码

Java没有在工作中使用过，只是会了基本的语法，不过文档都基本上都能看懂，甚至不用看文档，只看Deque的类方法名就能猜出它的作用了，这块相对比较容易

    Deque<String> deque = new LinkedList<String>();
    deque.addFirst("a"); 
    deque.addFirst("b"); 
    deque.addFirst("c"); 
    System.out.println(deque);

    String str = deque.peekFirst(); 
    System.out.println(str); 
    System.out.println(deque);

    while (deque.size() > 0) {
        System.out.println(deque.removeFirst()); 
    }
    System.out.println(deque);

源码分析

1. Queue源码分析

Queue 在java中是一个接口，继承自 Collection 接口，咱就先不看继承的接口了，在源码里 Queue 只有6个方法，分别是：

• boolean add(E e) : 向队列里添加元素
• boolean offer(E e): 也是向队列里添加元素，如果使用有容量限制的队列，那么使用这个方法更好
• E remove(): 返回并删除队头元素，即队列的 pop 操作
• E poll(): 也是返回并删除队头元素，与 remove() 方法的区别是，这个方法在找不到元素的时候不会抛出异常，只会返回 null
• E element(): 返回队头元素，但不删除，如果找不到则抛出异常
• E peek(): 返回队头元素，但不删除，如果找不到则返回 null 不抛出异常

Java中很多基础类都是有实现这个接口，各种队列，链表，栈等等，说明这些数据结构都有相同的操作

2. PriorityQueue源码分析

PriorityQueue底层是一个对象数组 transient Object[] queue; 由于对Java不熟， transient 关键字不是很理解，后来查了资料，这个关键字是为了让成员变量不被序列化，不过这个不深究，目前也搞不懂为啥要加这个

PriorityQueue有重载6个不同的构造函数，要嘛初始化容量，要嘛初始化比较器，初始化容量是必须的，如果不指定的话，类本身有一个默认的容量 DEFAULT_INITIAL_CAPACITY = 11 至于这个初始化容量为什么是11就不懂了

如果没有指定 Comparator 的话，将会采用元素的自然排序

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     */
    private final Comparator<? super E> comparator;

PriorityQueue的 add 方法和 offer 方法是一样的，实际上是前者调用后者；

    /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        return offer(e);
    }

    /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

offer() 这个插入元素的方法，首先会计算队列的容量是不是够用，如果不够的话就 grow 一下，队列内为空的时候，直接插入元素，放在数组第一个位置，后面再插入其他的元素的话就要调用 siftUp 进行比较排序了，要嘛使用元素的自然排序，要嘛使用比较器排序，删除操作也要进行同样的处理，所以优先队列的插入和删除操作时间复杂度都是 O(logn)

peek() 操作只是取得队头元素，并不删除元素，时间复杂度是O(1)

poll() 操作既要取得队头元素，还要把队头元素从队列中删除，时间复杂度是O(logn)

【253-week01】第一周总结

第一周总结
第一周的知识我们学校刚学过，听过老师讲的课后仍感觉还有很多需要提高。
首先老师一直强调的算法其实就是loop ，ifelse 和递归这个我渐渐的明白了，算法其实就是在这些小模块的基础上构建起来的。算法的魅力也在于可以用这些简单的语句解决各种复杂的问题。
还有就是老师说的写题不能只写一遍，我一定会谨遵教诲，多谢多练。
最后我觉得这周是第一周，我刚刚适应这种上完课就写作业，作业还不少的模式。虽然这周很累，以后以一定会更累，但我还是要打好基础认真学习。在刻苦中提高，在勤奋中奋进。

算法训练营（第4期）预习周作业（选做）

作业：绘制自己的数据结构和算法脑图

要求：用脑图的方式把知识的脉络串联起来，不管对于学习新知识还是巩固已有知识，都是一种很好的学习方式。同学们可以将目前自己所掌握的数据结构和算法知识绘制成脑图，在绘制过程中可以查阅资料，补充目前掌握欠缺的部分，找到自己薄弱的地方。后面再通过课程的学习和刻意练习，动态地将自己绘制的脑图逐步补充、完善，从而达到真正的融会贯通。

脑图绘制工具不限。

算法训练营（第4期）第一周作业

要求

1. 每周从覃超老师布置的题目中，至少完成并提交两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章或总结，切忌流水账。

作业提交 Deadline

2019年10月20日 23:59 （以当地时间为准）
未按时提交作业，会在个人作业总分钟 -3 分

本周作业概述

本周需要完成学习的视频内容：

• 第 3 课 | 数组、链表、跳表
• 第 4 课 | 栈、队列、优先队列、双端队列

以上两课视频后，覃超老师都给出了大家可以练手的算法题。

其中，第 4 课的课后作业（第2节视频后）还包括：

• 用add first或add last这套新的API改写Deque的代码
• 分析Queue和Priority Queue的源码

请大家将此部分作业，放在本周学习总结中一并提交

本周算法习题库：

第三课课后习题：

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
https://leetcode-cn.com/problems/rotate-array/
https://leetcode-cn.com/problems/merge-two-sorted-lists/
https://leetcode-cn.com/problems/merge-sorted-array/
https://leetcode-cn.com/problems/two-sum/
https://leetcode-cn.com/problems/move-zeroes/
https://leetcode-cn.com/problems/plus-one/

第四课课后习题：

https://leetcode.com/problems/design-circular-deque
https://leetcode.com/problems/trapping-rain-water/
用add first或add last这套新的API改写Deque的代码
分析Queue和Priority Queue的源码

改写代码和分析源码这两项作业，需要在你的本周学习总结中一并提交。

【033-Week 预习周】 预习周的总结

数据结构的分类

• 一维数据结构
• 二维数据结构
• 特殊数据结构

学习方法

• 分解的、刻意的、大量反复的练习基本功
• 练习缺陷、弱点的地方
• 寻求反馈

LeetCode刷题技巧

• Clearification、Possible Solutions、Coding、Test Cases
• 五遍刷题法

总之，要想变的专业，就要刻意的，反复的不断练习最基础的部分，熟练掌握后才能应用自如。

【738-Week 01】周总结 + 改写Deque + Queue和Priority Queue源码分析

NOTE

周总结

本周是算法课堂的第一周。在本周里面，感受到了本门课的训练强度。按照覃超老师提供的五步刷题法建议，我对视频里面的实战题目，对全部课后题都按照五步刷题法的要求去完成。

1. 通过一周的训练，我对 数组/链表/栈/队列 的算法更加熟练了。也学习了一些解题的基本思路。大致有：

• 快慢指针法

• 左右指针夹逼法

• 递归法

• 空间换时间法

• 升维提升运行效率法

• 遇到最近相关性问题，可以直接考虑栈解决

2. 做题过遍数很重要，一道题做一次肯定不够，经过多次练习，会不对加深对题目的理解，以及这类题的理解。

3. 一道题目不要局限于一个解法，最基本的暴力法解决虽然看起来比较拙，但是它能够训练最基本的变成功力。而多思考其他方法，能够达到刻意训练洋葱降低编程时间复杂度的良好习惯。

4. 通过作业里面的源码分析，对Priority Queue的底层理解更加透彻了，也从源码学习到堆的操作技巧。

本周题目代码连接:

https://github.com/zhengxin12345/algorithm004-03/tree/master/Week%2001/id_738

---

改写Deque

Deque<String> deque = new LinkedList<String>();
//deque.push("a")
//deque.push("b")
//deque.push("c")

deque.addFirst("a"); 
deque.addFirst("b"); 
deque.addFirst("c"); 
System.out.println(deque);

//String str = deque.peek(); 
String str = deque.peekFirst(); 
System.out.println(str); 
System.out.println(deque);

while (deque.size() > 0) {
    //System.out.println(deque.pop()); 
    System.out.println(deque.removeFirst()); 
}
System.out.println(deque);

分析Queue源码

• 【Queue源码】
• 【Queue文档】
• 通过上面的源码链接，我们可以看到

1. Queue只是一个接口，继承了Collection接口
2. Queue里面的元素使用了泛型，可为任意类型元素
3. 方法作用：

//往队列头部添加元素，如果成功返回True
//如果添加失败，抛出以下异常
//IllegalStateException : 此时队列容量满,添加不进去
//ClassCastException : 添加的元素类型和队列定义的泛型E不一致
//NullPointerException : 如果队列不允许加入null元素，但是add了一个Null元素
//IllegalArgumentException 如果待添加的元素自身的某些属性，阻止了该元素加入队列
boolean add(E e);  
//查找元素e是否在队列里面，如果是则返回True，否则返回False
boolean offer(E e); 
//返回并删除队列头部元素，如果队列为空抛出异常：NoSuchElementException
E remove();
//返回并删除队列头部元素，如果队列为空返回Null
E poll();
//返回队列头部元素(注意不删除)，如果队列为空抛出异常：NoSuchElementException
E element();
//返回队列头部元素(注意不删除)，如果队列为空返回Null
E peek();

4. 实现Queue的类
   通过 【Queue文档】,可以查阅到实现Queue的类有：

AbstractQueue<E>, ArrayBlockingQueue<E>, ArrayDeque<E>, ConcurrentLinkedQueue<E>, DelayQueue<E,extends,Delayed>, LinkedBlockingDeque<E>, LinkedBlockingQueue<E>, LinkedList<T>, PriorityBlockingQueue<E>, PriorityQueue<E>, SynchronousQueue<E>

分析Priority Queue源码

从【分析Queue源码】可以看到，PriorityQueue实现了Queue接口。

• 【PriorityQueue文档】
• 源码分析

1. 继承AbstractQueue类，实现Serializable接口，也就是说可被序列化
2. 提供了多种PriorityQueue的方式

PriorityQueue()：默认创建一个容量为11的空优先队列

PriorityQueue(Collection<? extends E> c)：初始化优先队列，并将集合c的元素添加到优先队列中

PriorityQueue(int cap)：初始化一个容量为cap的空优先队列

PriorityQueue(int cap, Comparator<? super E> comp)：初始化一个容量为cap的空优先队列，并指定队列元素的优先排列规则Comparator

public PriorityQueue(PriorityQueue<? extends E> c)：将参数的优先队列c的元素复制到该优先队列中，并且该优先队列的初始容量为1或者c的容量的1.1倍：

this(Math.max(1, (int) (1.1 * c.size())),
            (Comparator<? super E>)c.comparator());

public PriorityQueue(SortedSet<? extends E> c)：将SortedSet中的元素初始化到优先队列中，优先队列的Comparator为SortSet的Comparator，并且优先队列的容量为1或者SortedSet的1.1倍:
           this(Math.max(1, (int) (1.1 * c.size())),(Comparator<? super E>)c.comparator());

3. PriorityQueue实现了iterator方法
4. 其他普通的public这里就不赘述了，具体看doc文档
5. PriorityQueue的底层数据结构为数组：并且在初始化的时候已经固定了容量

this.storage = (E[]) new Object[cap];

5. PriorityQueue添加元素的时候，会比较队列已经存储的元素数量size和队列的大小queue.length，当队列 size >= queue.length的时候，会进行扩容

6. 对新加入队列的元素，会对元素进行比较，插入到合适的队列位置中。如果队列的comparator为null，则调用siftUpComparable否则调用siftUpUsingComparator

private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

    @SuppressWarnings("unchecked")
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

7. 基本操作remove，add方法都依赖于siftUp或者siftDown操作

8. 下面重点关注siftUpComparable的底层实现：

    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

这段代码的逻辑，明显看到，PriorityQueue的逻辑结构是一颗完全二叉树，而且是小顶堆（因此如果要变成大顶堆，要自己实现comparator.compare），而底层结构是一个数组。

siftUpComparable就是当前元素与父节点不断比较如果比父节点"小"就交换然后继续向上比较，否则停止比较的过程。

9. 有siftUp方法必然对应有siftDown方法：

private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

这个方法就是从堆的第一个元素往下比较，如果比左右孩子节点的最小值大则与最小值交换，交换后继续向下比较，否则停止比较。

10. 分析了上面2个siftUp和siftDown方法，我们就可以来继续看队列的添加删除方法了

• add
  追踪代码最后定位到实际代码是：

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

所以add的操作就是：在处理完队列容量之后，对待加入的元素进行在最后一个位置进行siftUp操作，也就是说，将待加入的元素放到树的最后一个叶子节点位置，然后通过调整小顶堆，将元素挪动到合适的位置

• remove/poll：删除指定元素/移出队列第一个元素，原理相同。

private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i) // removed last element
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

同样,remove最后定位到removeAt方法，可以看到，小顶堆的基本操作：将第i个位置值替换为堆中最后个节点的值，然后将替换后的值，进行堆调整，堆的调整先向下调整，如果向下不需要调整则向上调整，最后重新形成一个合格的小顶堆。

---

【668-week01】第一周总结

学习完第一周的课程，做了课后的作业。对数组、链表、堆、栈有了最本质的理解，深入了解了每个类型的数据结构对应的好的操作与耗时的操作。课堂上超哥说的最触动内心的一句话是：题目只做一遍，确实如此。就最简单的斐波那契数列的实现来看，时间久了再拿过来思考，拿过来写代码，发现很多细节很陌生，代码写的也很冗余。同时学习到了超哥教的刷题的模式：读题、思考、实现（有思路）、看题解、默写背诵、熟练、闭卷写。这个步骤还是有些不适应，拿到题后，还是希望思考，不断的花时间，不断的死磕。有时候会花很长的时间心里才会愿意去看题解，这样下来每道题的总花费时间就很多。总体感觉第一周的学习时间很紧张，主要是与自己解题的模式有关系。总结下来，学到的学习方法与个人感悟如下。

学习方法：

1. 升维、空间换时间的**
2. 寻找事物的最近相关性
3. 栈结构类似于生活中的洋葱结构
4. 双指针法的灵活使用

个人感悟：

1. 有些题目花了很长时间去想、去研究、去较劲、去硬想；后面需要慢慢地调整，慢慢适应超哥教的刷题模式
2. 有些题目看到官方的题解，处理的**确实巧妙，内心不由的感叹。相较于自己暴力的解法好的太多
3. 比较好的题解，觉得需要将其彻底理解，然后再去学习其具体的实现，如果有些实现不理解对应的处理**，只记忆实现，后面会忘记的很快。为了便于自己的理解与记忆，有时我会修改题解中一些实现细节
4. 感觉任何一道题，想要研究透彻，都需要花上大把的时间，不停的想，不停的实现

【653-Week 01】周总结

【653-Week 01】周总结

感言：第一周新的开始

1. 学习体验

对于大部分人而言，学习是一个追求未知的过程，追求知识常常使人感到充实，我也是这样的人。

说起来也是工作几年的人了，但是对于算法与数据结构常常是皮毛而已，总是不能触及到正确的学习方式，也打不开正确的使用姿势。然而一周的课下来我慢慢的尝试了自己做了一些题，渐渐的发现了，以前理解很困难的题，现在慢慢的可以做了，有的题竟然可以自己一遍手写过，虽说难度是easy，但是也提升的了自信心。学习过程就是一个征服未知的过程，过程中需要一些成就感，达到不断的自我激励，这样学习更有动力。在这里不得不说，老师的讲授的内容很管用，无论从内容的安排上还是，还是学习技巧都很用心，即便我这样对算法了解很少的人都能很容易理解。在这里希望与大家共勉，一起进步。

说一说学习了那些知识，本周学习了

1. 用双指针来解决 数组去重 问题
2. 用Hashmap 来解决 匹配性 问题
3. 学习算法的基本方式，拆分知识点，刻意练习，查找重复性 ，五遍刷题法 ，理解其中的思维方式 。
4. 常用数据结构 的方法，特点

2. 改写Deque

        Deque<String> deque = new LinkedList<>();

        deque.addFirst("c");
        deque.addLast("b");
        deque.addLast("a");

//        deque.push("a");
//        deque.push("b");
//        deque.push("c");

        System.out.println(deque);

        String str = deque.getFirst();
        System.out.println(str);
        System.out.println(deque);

        while (deque.size()>0) {
            System.out.println(deque.pollFirst());
        }
        System.out.println(deque);
    }

3. Queue源码分析

// 趁着代码量少赶紧手写一遍 😏
public interface Queue<E> extends Collection<E> {
  // 首先 queue是一个继承自collection的接口
  // collection 接口中的add ，remove 操作在执行失败都会抛出异常
  // 但是 queue 接口中的 offer ， poll 不会抛出异常，区别仅此而已，但是具体实现要看子类，不能一概而论，
  
  // 添加元素，失败即抛出异常
  boolean add(E e);
  // 添加元素
  boolean offer(E e)
  // 移除并获取队首元素，失败即抛出异常
  E remove();
  // 移除并获取队首元素
  E poll();
  // 获取队首元素，失败即抛出异常
  E element();
  // 获取队首元素
  E peek();
}

4. PriorityQueue 源码分析

首先看了一下源码里面的注释说明

首先 priorityqueue 是一个二叉平衡堆(说实话堆还不了解，😳 希望以后能掌握)，他的主要特点是按照元素E的优先级进行入队，出队，所以其出队，出队的操作 add，offer，remove，poll，都不是常数时间而是logn ，而取元素 peek，element 则是常数时间。

4.1 常见方法分析

// 构造器 随着传入不同数据结构配置不同的 Comparator 
public PriorityQueue(SortedSet<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }   

// 扩容，如果以前容积小于 64（base低） 那么就 double，如果以前容积大那么就右移1位，增加 50%
  private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }
	// 通过优先级筛选，说实话目前还是不太看得懂，可能自己对堆不是很了解造成的，希望以后慢慢补上
  @SuppressWarnings("unchecked")
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

【273-周01】总结

做题技巧总结：

1. 活用数据结构，思考每道题背后能够使用的数据结构
2. 如果看到一道题没思路，可以先直接考虑暴力求解的方式
3. 思考一道题时，寻找它与其他题的共同特征，也就是重复子问题。
4. 每道题需要反复多做，理解背后的**，多看别人的题解以及优化思路
5. 优化思路都是升维/空间换时间。（目前还不是很理解）

个人总结：
对于之前的自己，做LeetCode时只考虑代码能否access，即便没思路也硬憋，只想着能否通过完全不管优化策略，也因此常常一道题刷一上午，身心疲惫然后放弃算法学习。这显然是低效率的学习，通过算法训练营老师的指导，明白了刷题的思路和学习的方式，希望能走在正确的方向上更快提升自我。
总结一周学到主要是：高效学习方式、做题的思维方式、正确的刷题姿势。我个人认为相比起数据结构的知识，学到了**是更加重要与可贵的。

【143-Week 预习周】预习周的总结

目标

• 熟悉算法与数据结构；
• 熟悉常用工具IDE,快捷键；
• 学习方法---五遍题法；
• 编程**；

脑图

略

IDE，快捷键

略

五遍刷题法

1. 第一遍
   读题 + 思考：不超过5分钟，思考各种可能，再选择最优可能。如果不会直接看解法。再看英文版选择自己熟悉的语言前三评价最高的解法。看懂后，可以背诵、默写。

2. 第二遍
   自己写，不参考任何资料，提交 LeetCode多种解法都试着写一写，在完成的情况下，进行性能优化。

3. 第三遍
   隔天重复做题，练习不同解法的熟练程度 ，有问题或不顺处进行专项练习。
   4.第四遍
   隔一周，反复回来练习相同题目。应该正好在课程第二周前进行总结和交作业。
   5.第五遍
   面试前一周或自己控制时间，进行恢复性训练

编程**-自顶向下编程

先抽象出整体步骤，检查有无逻辑遗漏。代码体现在确定出方法间的调用关系和参数。再利用编辑器自带的代码生成工具，生成相应函数，补全各个方法中的具体细节。最后调试，以及做测试用例生成

【633-week预习周-预习周总结】

1. 脑图
2. 过变数
3. 预习
4. 作业

【078-Week 01】周总结

1.方法总结：
1）“五毒神掌”的实操第一周，这周进行前三步，下周强化练习。
2）读题没有思路就找最小重复的单元，分析找到规律。
3）优化算法：升维**，空间换时间。
4）习题中多次用到的夹逼定理，双端指针的方法，以及作业中也有尝试到。
2.课后习题：
1）用 add first 或 add last 这套新的 API 改写 Deque 的代码：
Deque deque = new LinkedList();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);

    String str = deque.getFirst();
    System.out.println(str);
    System.out.println(deque);

    while (deque.size() > 0) {
        System.out.println(deque.removeFirst());
    }
    System.out.println(deque);

2）分析 Queue 和 Priority Queue 的源码（目前还没整理完成，在后面在comment中补充）

【523-周01】跳楼梯的理解

在很早之前就开始看算法题目, 在很想的网站和算法书籍上都有看过.
在实际的面试的时候甚至遇到过类似的题目,但是直径一知半解,完全不知道这类题目的解决方案.

很高兴能听到简单的讲解了改题目,同时能够让我很容易的理解了改题目.
然后我还尝试这给周围的人讲解了一下改题目,虽然讲解的不是太清楚,但是还是带来了一些帮助.

关于爬楼梯的这道题目,还可以这样理解.
如果是一个10级的台阶,一开始就是爬1级, 这样就剩下9级, 还可以爬2级,这样就剩下8级.
得到的结果与老师讲解的完全一样,其实就是f(10)=f(9)+f(8)

非常高兴能把这种题目理解的很好.

【028-week 01】总结

第一周

一、数组、链表、跳表的基本实现和特性

数组

优点：支持O(1)的随机访问

缺点：平均为O(n)的插入和删除

链表

优点：时间复杂度为O(1)的插入、删除操作

缺点：不支持随机访问

跳表

升维 空间换时间

时间复杂度：O(logn)

二、新api重写代码

Deque<String> deque = new LinkedList<String>();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);

String str = deque.peekFirst();
System.out.println(str);
System.out.println(deque);

while (deque.size() > 0) {
	System.out.println(deque.removeFirst()); 
}
System.out.println(deque);

三、分析Queue源码

Queue源码地址

1、add()和offer()区别:

add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断！

2、poll()和remove()区别:

remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，但是新的 poll() 方法在用空集合调用时只是返回 null。因此新的方法更适合容易出现异常条件的情况。

3、element() 和 peek() 区别:

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

四、分析Priority Queue 的源码

PriorityQueue源码地址

1、扩展自AbstractQueue

2、定义了默认容量大小DEFAULT_CAPACITY = 11

3、定义了一个Comparator<? super E> comparator;比较器

4、定义了一个E[] storage;

5、定义了6个构造方法

1、boolean offer() 添加元素的时间复杂度为O(n)，非线程安全

 177:   public boolean offer(E o)
 178:   {
 179:     if (o == null)
 180:       throw new NullPointerException();
 181: 
 182:     int slot = findSlot(-1); // 先操作扩容
 183: 
 184:     storage[slot] = o;
 185:     ++used;
 186:     bubbleUp(slot);
 187: 
 188:     return true;
 189:   }

2、E peek() 取元素的时间复杂为O(1)

 191:   public E peek()
 192:   {
 193:     return used == 0 ? null : storage[0];
 194:   }
 195: 

3、E poll() 移除的时间复杂度为O(n)

 196:  public E poll()
 197:   {
 198:     if (used == 0)
 199:       return null;
 200:     E result = storage[0];
 201:     remove(0); // 移除顶部元素
 202:     return result;
 203:   }

示例：【089-week1】关于二分查找的一些新的理解

标题格式：【学号后三位+week1】（如果是第二周就是week2，以此类推）+文章标题

正文部分，字数不限。

【423-Week 01】第一周总结

感想

这周内容相对基础,更多的是体会老师的思维方式以及解题思路,切记不能眼高手低,要可以练习,共勉

Note

Array

• Java, C++: int a[100];
• Python: list=[]
• JavaScript: let x = [1,2,3Â]

dsec

底层硬件实现,申请数组时计算机在内存中开辟一段连续的地址,每一个地址可直接通过内存管理器(Memory Controller)访问,随机访问任何一个元素时间复杂度都是一样的,增加或删除元素的时候需要让出位置保证内存的连续,需要移动元素 买最好情况 O(1), 最坏情况 O(n), 平均情况 O(n) 的时间复杂度,

advantage:

随机访问速度特别快

disadvantage:

增删操作时间复杂度为 O(n),大量的增删操作很消耗性能

Time Complexity

operation	Time Complexity
prepend	O(1) 如果实现的好可以达到O(1)
append	O(1)
lookup	O(1)
insert	O(n)
delete	O(n)

实现:

JAVA java.util.ArrayList src code
ensureCapacity() 动态扩容

Linked List

desc

弥补数组的缺点,在一些增删操作频繁的情况下,每一个节点 NODE 有包含元素的value和指向下一个元素的NEXT, 一般情况下 HEAD为头指针, NEXT指向null的为TAIL,我们称之为单链表, 如果定义 指向前一个元所有的 PREV 称之为 双向链表,如果TAIL 指针指向 HEAD 就称为 循环链表, 链表插入即 插入位置的 NODE 的NEXT 指向 新NODE, 新NODE指向之前的 NEXT,删除即添加的逆操作, 即 Target Node 的 PREV 的 NEXT 指向 Target Node,移动元素不会引起链表的群移的操作,所以删除添加元素的时间复杂度为O(1), 但也正是这样的结构访问任意位置需要的时间复杂度为O(n)

Time Complexity

operation	Time Complexity
prepend	O(1)
append	O(1)
lookup	O(n)
insert	O(1)
delete	O(1)

实现

Linked List的标准实现代码
Linked List实例代码
JAVA java>util.LinkedList src code
LRU Cache

Skip List

dsec

跳表是为了优化或补足链表的缺陷设计出来的,链表的缺陷是lookup时间复杂度为O(n),

优化**是升维, 空间换时间

添加头尾指针是最简单的优化,我们可以在头尾指针中间再加上一些指针进一步提高速度, 跳表称为索引,通过增加多级索引,可以为链表提速.

disadvantage

跳表添加和删除元素会导致一些索引不工整的情况(即有些位置很密集,有些位置跨度大),由于索引的持续更新,维护成本较高.空间复杂度为 O(n).

Time Complexity

operation	Time Complexity
prepend	O(1)
append	O(1)
lookup	O(log2N)
insert	O(1)
delete	O(1)

实现

Redis

Stack

FILO

Time Complexity

operation	Time Complexity
insertion	O(1)
deletion	O(1)
search	O(n)

Queue

FIFO

Time Complexity

operation	Time Complexity
insertion	O(1)
deletion	O(1)
search	O(n)

Deque(Double-Ended Queue)

实际使用中很少直接使用Stack和Queue, 而是直接使用Deque, 实际就是Stack和Queue的结合体,两端都可以进出的Queue

Time Complexity

operation	Time Complexity
insertion	O(1)
deletion	O(1)
search	O(n)

Priority Queue

取出顺序不再是FIFO, 按照优先级来取出,底层具体实现的数据结构较为多样和复杂: heap, bst, treap

Time Complexity

operation	Time Complexity
insertion	O(1)
deletion	O(1)
search	O(logN)

随堂作业

新api重写代码

Deque<String> deque = new LinkedList<>();

deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);

String str = deque.peekFirst();
System.out.println(str);
System.out.println(deque);

while (deque.size() > 0) {
	System.out.println(deque.removeFirst()); System.out.println(deque.pop());
}
System.out.println(deque);

Queue源码分析

add 添加元素到队列中,空间不足抛出异常
offer 元素加入队列
remove 移除头部元素如果队列为null, 返回null
poll 元素移除队列
element 检索head, 如果为null, 抛出异常
peek 检索头部,如果为null,返回null

PriorityQueue源码分析

• 底层使用 可变数组Object[] queue 存储元素
• 不严格先进先出
• 遍历没有顺序保证

源码实现了Queue的基本方法,利用二叉堆的特点(节点的左子树都小于等于其父节点，右子树都大于父节点),对Object[] queue 操作,实现优先特性

【138-Week 01】总结

第一周学习总结:
PartA: 本周学习内容总结

1. 学习数组、链表、队列、栈等数据结构，了解各种数据结构的优缺点。
2. 学习数组的操作方法：例如：循环遍历（多重遍历注意指针下标）、快慢指针、左右指针收敛。
3. 关于链表：快慢指针，递归。对于链表，必须通过理解背诵记忆。
   4.队列、栈：主要还是考虑在递归能够解决问题的时候能否通过栈或队列做优化。
   5.跳表：优化链表查询的时间，中心**是通过空间换时间，为每个节点创建索引，缺点是数据发生变化后需要触发索引或者缓存的重建，空间开销大。
   6.算法还是很考验记忆力的，但是记忆需要多理解，需要多动手，多思考。

PartB: PriorityQueue实现
1.PriorityQueue(JDK版本1.8)是一个基于优先级堆的无界优先队列。类图参考:PriorityQueue-uml.png。默认通过自然顺序进行排序，也可以通过构造方法指定排序比较器。
排队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间；为 remove(Object) 和 contains(Object) 方法提供线性时间；为获取方法（peek、element 和 size）提供固定时间。
此外该类是非线程安全的，如果是多线程推荐使用PriorityBlockingQueue.
构造方法： public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
优先级队列不允许插入null元素，同样不允许插入不可比较的对象。队列的头是按照比较顺序的最小元素。但是允许重复元素。内部使用数组Object[]存放元素。
示例代码： PriorityQueue queue = new PriorityQueue<>(8);
queue.add(7);
queue.add(6);
queue.add(1);
queue.add(1);
//queue.add(null);
System.out.println(queue);
输出： [1, 1, 6, 7]
2.主要的方法摘要:
1)boolean add(E e)
将元素插入到此优先队列,调用的是offer方法,重写父类的add方法,可能会抛出ClassCastException/NullPointerException
2)boolean offer(E e)
将元素插入到此优先队列,可能会抛出ClassCastException/NullPointerException
内部使用变量size存放元素个数，添加元素的时候，如果元素个数超过原数组长度则扩充数组。
具体调用方法：void grow(int minCapacity)，扩充的策略：原数组长度小于64，则长度加2；否则，长度扩充50%。
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
扩充数组后通过System.arraycopy方法完成数组的拷贝。
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
最后将元素插入到队列里，调用siftUpComparable/siftUpUsingComparator方法，完成比较后插入到对应的队列位置。
3)E peek()
获取但不移除此队列的头,队列为空，则返回null
由代码分析可知 return (size == 0) ? null : (E) queue[0];其实返回的就是内部数组的首个元素，也就是最小的元素。但是没有附加操作去修改数组长度,因此队列不变。
4)E poll()
获取并移除队列的头，队列空则返回null
该方法首先将内部数组的长度-1，记录数组的首元素。
5)boolean remove(Object o)
从此队列中移除指定元素的单个实例（如果此队列包含一个或多个满足 o.equals(e) 的元素 e，则移除一个这样的元素）。
具体实现方式先通过indexOf(遍历比较是否相等)方法定位下标，然后调用removeAt方法移除指定下标的元素。

3.应用场景:
优先队列以及DelayQueue实现
/**
* 从输入的n个数里获取top k
* @param args
* @param size
* @return
*/
public Object[] testPriorityQueue(int[] args, int size) {
PriorityQueue pq = new PriorityQueue<>(size);
if (args == null || args.length == 0)
return null;
for (int arg : args) {
if (pq.size() > size) {
if (pq.peek() < arg) {
pq.poll();
pq.add(arg);
}
}else {
pq.add(arg);
}
}

    return pq.toArray();
}

【493-week01】周总结

算法内容梳理，有三大块内容一维数据结构、二维数据结构和特殊数据结构，再结合算法的脑图，对算法的整体有个大致的认知。
进阶方法，五毒神掌练习法。
语言逻辑的写法只有if else for while 递归，所以解法只能是这几种方式的组合。计算器利用重复性解决复杂的问题
优化**，升维、空间换时间。
跳表，解决快速查询效率，redis种有使用，多级索引，空间复杂度O(n)，时间复杂度O(lgn）。
Priority Queue 插入O(1) 取出O(logn) 底层实现heap bst treap

【533-预习周】预习周总结

学习方法：
1. 切碎知识点
2. 刻意练习(对于知识的熟练掌握真的很重要)
3. 主动反馈(自己去找)与被动反馈(高手给的指点)，有助于完善知识体系、拓宽视野

切题四件套：
1. Clarification
2. Possible solutions
3. Coding
4. Test cases

五毒神掌
1. 刷题第一遍
5分钟(10到15分钟也可)：读题+思考，如果无思路-->直接看解法：注意！多解法，比较优劣。背诵、默写好的解法
2. 第二遍
马上自己写-->LeetCode提交，多种解法比较、体会-->优化！
3. 第三遍
一天之后 重做一遍
LeetCode国际站看most votes自己使用语言的前三回答。针对不同熟练程度的解法-->专项练习
4. 第四遍
过了一周：再回来练习一遍
LeetCode国际站看most votes自己使用语言的前三回答。针对不同熟练程度的解法-->专项练习
5. 第五遍
面试前一周恢复性训练

遵循严格的代码规范

养成良好的IDE使用习惯

自顶向下的编程方式，最关键的函数写在最上面，细节放在后面

【628-Week 预习周】预习周总结

预习周最大的感觉是 转变。

1、习惯的转变 ---- 对工具的认识，从eclipse尝试转换为idea，从svn转换为git，新事物的尝试和快捷键，编码风格习惯的转变在这一周是一个冰与火的熔铸。
2、思维的转变 ---- 刷题不一定必须自己去把题做出来，看了答案后理解了，学会了也可以。五毒神掌。
3、氛围的转变 ---- 从工作的氛围切换回学习的氛围，从自学的氛围切换为多人伴学的氛围。

【313-week 01】动手写，实践

动手写，实践

2年的工作经验干了5年的工作，这大概就是我的现状，希望通过训练营修炼一下内功。

通过视频和LeetCode做题，对数组、栈、队列有了一些新的认识。空间换时间，升维操作。

LeetCode做题总结

• 比较暴力的双层遍历，先解决问题，再想办法优化
• 快慢指针
• 指针对撞，一个指针指向第一个元素，一个指向最后一个元素，两个指针同时向中间遍历。
• 数组反转
• 接雨水的问题，没有想到用栈的方式去解决，动态规划不太熟悉还。

改写代码

由于对java不是特别熟悉，刚好LeetCode第641题是设计双端队列，就用go语言实现了一遍。
代码链接：https://github.com/varluffy/algorithm004-03/blob/master/Week%2001/id_313/LeetCode_641_313.go
关于队列的应用工作中用的比较多的是消息队列

PriorityQueue

优先队列不再像普通队列那样先进先出，它的作用是保证每次取出的元素都是队列中权值最小的，它是通过完全二叉树的结构实现的一个小顶堆。当有插入和删除操作时，都有可能会破坏小顶堆的性质，内部会进行调整。

【713-Week 01】周总结

NOTE

• 名词对应

英文	中文
array	数组
linked list	链表
skip list	跳表

复杂度分析

数组时间复杂度

操作	复杂度
prepend	O(1)
apppend	O(1)
lookup	O(1)
insert	O(n)
delete	O(n)

链表时间复杂度

方式	复杂度
prepend	O(1)
append	O(1)
lookup	O(n)
Insert	O(1)
delete	O(1)

跳表

• 解决链表的 随机访问 复杂度高的问题

优化**

• 空间换时间 (升级维度)

栈

• FILO 后进先出

• 什么样的问题可以用栈解决 -> 最近相关性

队列

• FIFO 先进先出
• 广度搜索

---

数组的常见算法

• 遍历左右边界

// 一维数组的坐标变换 i,j

// 遍历左右边界
int max = 0;
for (int i = 0; i < a.length - 1; i++) {
	for (int j = i + 1; j < a.length; i++) {
		// 可以自顶向下抽象: int area = getArea(i, j);
    int area = (j - i) * Math.min(a[i], a[j]);
		max = Math.max(area, max);
	}
}

• 左右双指针

// 双指针左右夹逼
// 第一件事是排序 O(NlogN)

int i = 0; j = a.length - 1;
while (i < j) {
  if (条件) {
    // 操作
    i++;
  } else {
    // 操作
    j--;
  }
}

链表的常见算法

• 双指针

// 初始化快慢指针
ListNode slow = head;
ListNode fast = head;
/**
 * 根据不同问题, 调整条件
 * 注意: 避免空指针
 */
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem

改写

//////////////////////改写前////////////////////////////////
Deque<String> deque = new LinkedList<>();

deque.push("a");
deque.push("b");
deque.push("c");

System.out.println(deque);

String str = deque.peek();
System.out.println(str);
System.out.println(deque);

while (deque.size > 0) {
  System.out.println(deque.pop());
}

System.out.println(deque);


//////////////////////改写后////////////////////////////////
Deque<String> deque = new LinkedList<>();

deque.addFirst("a"); // push(e) -> addFirst(e)
deque.addFirst("b");
deque.addFirst("c");

System.out.println(deque);

String str = deque.peekFirst(); // peek() -> peekFirst()
System.out.println(str);
System.out.println(deque);

while (deque.size > 0) {
  System.out.println(deque.removeFirst()); // pop() -> removeFirst()
}

System.out.println(deque);

---

源码分析

PriorityQueue

• 参考: https://www.cnblogs.com/linghu-java/p/9467805.html
• 概念
  • 区别于FIFO(先进先出)的队列, 每次出队都是优先级值高的元素
  • 元素比较方法需要实现Comparator
  • 底层数据结构是 二叉堆
    • 堆是完全数
    • 堆中某节点的值总是不大于或者不小于其父节点的值
    • 最大堆 (大顶堆, 大根堆)
      • 父节点的值 >= 任何一个子节点的值
    • 最小堆 (小顶堆, 小根堆)
      • 父节点的值 <= 任何一个子节点的值
    • 实现方式
      • 树
      • 数组
  • PriorityQueue底层是数组实现
    • 左子树位置 2 * n - 1
    • 右子树位置 2 * (n - 1) -> 2 * n - 2
    • 父亲节点位置 (n - 1) / 2

// 底层存储, 默认大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 数组实现
private transient Object[] queue;
// 初始容量值
private int size = 0;
// 比较器, 后面需要客户端传入或元素实现这个接口
private final Comparator<? super E> comparator;
// 模数, 修改的次数
private transient int modCount = 0;


// 默认构造方法, 比较器为空, 则需要传入的元素, 实现Comparator接口
public PriorityQueue() {
		this(DEFAULT_INITIAL_CAPACITY, null);
}

// 指定容量
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

// 指定容量, 和比较器
public PriorityQueue( int initialCapacity, Comparator<? super E> comparator) {
    // 初始大小不允许小于1
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    // 使用指定初始大小创建数组
    this.queue = new Object[initialCapacity];
    // 初始化比较器
    this.comparator = comparator;
}


// 数组扩容
private void grow(int minCapacity) {
    // 如果最小容量 < 0, 则超出int取值范围, 抛出异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 留存当前长度, 用于后面比较
    int oldCapacity = queue.length;
    // 如果当前队列长度小于64则扩容2倍, 否则扩容1.5倍
    int newCapacity = ((oldCapacity < 64)?
                       ((oldCapacity + 1) * 2):
                       ((oldCapacity / 2) * 3));
    // 如果扩容后的容量值 > int 取值范围, 则将newCapacity赋值为Integer.Max_VALUE
    if (newCapacity < 0) // overflow
        newCapacity = Integer. MAX_VALUE;
    // 如果扩容后, newCapacity小于最小需要的容量大小minCapacity, 则按找minCapacity长度进行扩容
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    // 数组copy, 进行扩容
    queue = Arrays.copyOf(queue, newCapacity);
}


// 入队
public boolean offer(E e) {
		// 校验: 入队元素空, 则抛空指针异常
		if (e == null)
		    throw new NullPointerException();
		// 修改模数(版本)+1
		modCount++;
		// 记录当前队列中元素的个数
		int i = size ;
		// 如果当前元素个数大于等于队列底层数组的长度, 则进行扩容
		if (i >= queue .length)
		    grow(i + 1);
		// 元素个数+1
		size = i + 1;
		// 如果队列中没有元素, 则将元素e直接添加至根（数组小标0的位置）
		if (i == 0)
		    queue[0] = e;
		else
        // 否则调用siftUp方法, 将元素添加到尾部, 进行上移判断
		    siftUp(i, e);
		return true;
}






// 上移, x表示新插入元素, k表示新插入元素在数组的位置
private void siftUp(int k, E x) {
    // 如果比较器comparator不为空, 则调用siftUpUsingComparator方法进行上移操作
    if (comparator != null)
        siftUpUsingComparator(k, x);
    // 如果比较器comparator为空, 则调用siftUpComparable方法进行上移操作
    else
        siftUpComparable(k, x);
}


private void siftUpComparable(int k, E x) {
    // 比较器comparator为空, 需要插入的元素实现Comparable接口, 用于比较大小
    Comparable<? super E> key = (Comparable<? super E>) x;
    // k>0表示判断k不是根的情况下, 也就是元素x有父节点
    while (k > 0) {
        // 计算元素x的父节点位置[(n-1)/2]
        int parent = (k - 1) >>> 1;
        // 取出x的父亲e
        Object e = queue[parent];
        // 如果新增的元素k比其父亲e大, 则不需要"上移", 跳出循环结束
        if (key.compareTo((E) e) >= 0)
            break;
        // x比父亲小, 则需要进行"上移"
        // 交换元素x和父亲e的位置
        queue[k] = e;
        // 将新插入元素的位置k指向父亲的位置, 进行下一层循环
        k = parent;
    }
    // 找到新增元素x的合适位置k之后进行赋值
    queue[k] = key;
}

// 同上, 区别在于 使用元素实现的Comparator接口, 还是构造传入Comparator接口的实现类
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator .compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}


// 删除并返回队头的元, , 如果队列为空则抛出NoSuchElementException异常（该方法在AbstractQueue中）
public E remove() {
  E x = poll();
  if (x != null)
    return x;
  else
    throw new NoSuchElementException();
}

// 删除并返回队头的, 素, 如果队列为空则返回null
public E poll() {
  // 队列为空, 返回null
  if (size == 0)
    return null;
  // 队列元素个数-1
  int s = --size ;
  // 修改版本+1
  modCount++;
  // 队头的元素
  E result = (E) queue[0];
  // 队尾的元素
  E x = (E) queue[s];
  // 先将队尾赋值为null
  queue[s] = null;
  // 如果队列中不止队尾一个元素, 则调用siftDown方法进行"下移"操作
  if (s != 0)
    siftDown(0, x);
  return result;
}

// 上移, x表示队尾的元素, k表示被删除元素在数组的位置
private void siftDown(int k, E x) {
  // 如果比较器comparator不为空, 则调用siftDownUsingComparator方法进行下移操作
  if (comparator != null)
    siftDownUsingComparator(k, x);
  // 比较器comparator为空, 则调用siftDownComparable方法进行下移操作
  else
    siftDownComparable(k, x);
}

private void siftDownComparable(int k, E x) {
  // 比较器comparator为空, 需要插入的元素实现Comparable接口, 用于比较大小
  Comparable<? super E> key = (Comparable<? super E>)x;
  // 通过size/2找到一个没有叶子节点的元素
  int half = size >>> 1;        // loop while a non-leaf
  // 比较位置k和half, 如果k小于half, 则k位置的元素就不是叶子节点
  while (k < half) {
    // 找到根元素的左孩子的位置[2n+1]
    int child = (k << 1) + 1; // assume left child is least
    // 左孩子的元素
    Object c = queue[child];
    // 找到根元素的右孩子的位置[2(n+1)]
    int right = child + 1;
    // 如果左孩子大于右孩子, 则将c复制为右孩子的值, 这里也就是找出左右孩子哪个最小
    if (right < size &&
        ((Comparable<? super E>) c).compareTo((E) queue [right]) > 0)
      c = queue[child = right];
    // 如果队尾元素比根元素孩子都要小, 则不需"下移", 结束
    if (key.compareTo((E) c) <= 0)
      break; 
    // 队尾元素比根元素孩子都大, 则需要"下移"
    // 交换跟元素和孩子c的位置
    queue[k] = c;
    // 将根元素位置k指向最小孩子的位置, 进入下层循环
    k = child;
  }
  // 找到队尾元素x的合适位置k之后进行赋值
  queue[k] = key;
}

// 同上, 区别在于 使用元素实现的Comparator接口, 还是构造传入Comparator接口的实现类
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue [right]) > 0)
            c = queue[child = right];
        if (comparator .compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

ArrayDeque

• 参考: https://www.cnblogs.com/tstd/p/5112177.html

// 存储方式为数组
private transient E[] elements;
// 头指针
private transient int head;
// 尾指针
private transient int tail;
// 最小的初始化容量大小，需要为2的n次幂
private static final int MIN_INITIAL_CAPACITY = 8;



// 默认构造, 初始容量是16
public ArrayDeque() {
  elements = (E[]) new Object[16];
}

// 指定初始容量的构造
public ArrayDeque( int numElements) {
  allocateElements(numElements);
}

// 传入一个集合, 分配空间并放置元素
public ArrayDeque(Collection<? extends E> c) {
  allocateElements(c.size());
  addAll(c);
}

// 分配合适容量大小的数组，确保初始容量是大于指定numElements的最小的2的n次幂
private void allocateElements(int numElements) {
  int initialCapacity = MIN_INITIAL_CAPACITY;
  // 找到大于指定容量的最小的2的n次幂
  // Find the best power of two to hold elements.
  // Tests "<=" because arrays aren't kept full.
  // 如果指定的容量小于初始容量8，则执行一下if中的逻辑操作
  if (numElements >= initialCapacity) {
    initialCapacity = numElements;
    initialCapacity |= (initialCapacity >>>  1);
    initialCapacity |= (initialCapacity >>>  2);
    initialCapacity |= (initialCapacity >>>  4);
    initialCapacity |= (initialCapacity >>>  8);
    initialCapacity |= (initialCapacity >>> 16);
    initialCapacity++;

    if (initialCapacity < 0)   // Too many elements, must back off
      initialCapacity >>>= 1; // Good luck allocating 2 ^ 30 elements
  }
  elements = (E[]) new Object[initialCapacity];
}



// 带异常处理的增加元素
public boolean add(E e) {
  // 调用addLast方法，将元素添加到队尾
  addLast(e);
  return true;
}


// 添加一个元素
public boolean offer(E e) {
  // 调用offerLast方法，将元素添加到队尾
  return offerLast(e);
}

// 在队尾添加一个元素
public boolean offerLast(E e) {
  // 调用addLast方法，将元素添加到队尾
  addLast(e);
  return true;
}

// 将元素添加到队尾
public void addLast(E e) {
  // 如果元素为null，咋抛出空指针异常
  if (e == null)
    throw new NullPointerException();
  // 将元素e放到数组的tail位置
  elements[tail ] = e;
  // 判断tail和head是否相等，如果相等则对数组进行扩容
  if ( (tail = (tail + 1) & ( elements.length - 1)) == head)
    // 进行两倍扩容
    doubleCapacity();
}


// 移除并返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
public E remove() {
  // 调用removeFirst方法，移除队头的元素
  return removeFirst();
}


public E removeFirst() {
  // 调用pollFirst方法，移除并返回队头的元素
  E x = pollFirst();
  // 如果队列为空，则抛出NoSuchElementException异常
  if (x == null)
    throw new NoSuchElementException();
  return x;
}

// 移除并返问队列头部的元素，如果队列为空，则返回null
public E poll() {
  // 调用pollFirst方法，移除并返回队头的元素
  return pollFirst();
}

public E pollFirst() {
  int h = head ;
  // 取出数组队头位置的元素
  E result = elements[h]; // Element is null if deque empty
  // 如果数组队头位置没有元素，则返回null值
  if (result == null)
    return null;
  // 将数组队头位置置空，也就是删除元素
  elements[h] = null;     // Must null out slot
  // 将head指针往前移动一个位置
  head = (h + 1) & (elements .length - 1);
  // 将队头元素返回
  return result;
}



// 返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
public E element() {
  // 调用getFirst方法，获取队头的元素
  return getFirst();
}

public E getFirst() {
  // 取得数组head位置的元素
  E x = elements[head ];
  // 如果数组head位置的元素为null，则抛出异常
  if (x == null)
    throw new NoSuchElementException();
  return x;
}

// 返回队列头部的元素，如果队列为空，则返回null
public E peek() {
  // 调用peekFirst方法，获取队头的元素
  return peekFirst();
}

public E peekFirst() {
  // 取得数组head位置的元素并返回
  return elements [head]; // elements[head] is null if deque empty
}

【218-Week 预习周】预习周总结

1：将算法打碎，细化了一次，不在畏惧，知道如何一一攻破了。
2：攻破的手段就是：五毒神掌法，不断的加深记忆和学习。
3：针对每一个算法：找到可执行的重复单元，进而将其攻破。同时要有全局观，即自顶向下发，然后，再完成细节和调优问题。
4：要仔细阅读题目或和面试官确认好算法前提环境后，再进行思考。

反复的练习，不断的深入学习，加油！

谢谢~

【303-Week 01】总结

基础：
Stack & Queue
1.Stack:先入后出；添加、删除皆为O(1);查询O(N)
2.Quene:先入先出；添加、删除皆为O(1);查询O(N)
特点：无序
Deque:Double-End Queue(双端队列)
想像为：一个队列，头和尾都可以进行push和pop
1.两端都可以进出的queue
2.插入、删除都是O(1)
Priority Queue(优先队列)
1.插入操作：O(1)
2.取出操作：O(logN) - 按照元素的优先级取
3.底层具体实现的数据结构较为多样和复杂：可以用heap(堆)、bst(二叉树)、treap

实战：
遇到不会的题目。彻底懵逼时：
1.暴力方法
2.最基本的情况
3.基于2泛化，最近重复的子问题

如何查看自己使用的语言的数据结构
Google 搜索 语言 + 结构名称

用正常的思维习惯去找出题目现实中对应的问题。

【593-Week 预习周】预习周总结

学习内容

1. 数据结构和算法总览
2. 编码环境
3. 时间复杂度分析
4. 学习方法

• check it up
• deliberate practicing
  -feedback

学习感想

1. 学习方法

• 预习很重要
• 刻意练习是唯一成长路径

2.做题方法

• 先审题
• 考虑所能想到的解法
• 五毒神掌

3.自顶向下编程方式
4.工具 tip

【308-Week 预习周】预习周的总结

作业：

数据结构脑图
算法脑图

解题笔记：

• 1137.第 N 个泰波那契数
  • 题解- JavaScript:执行用时击败100%的用户、内存消耗击败100%的用户
• 125. 验证回文串
  • 题解- Javascript:正则+数字reverse,应该铭记的好拍档

笔记：

数据结构与算法总览

如何系统的学习算法和数据结构

• 注重预习
• 课堂中一起思考、回答
• 按照切题方法完成作业

如何精通一个理论

• Chunk it up 切碎知识点
  • 庖丁解牛
  • 脉络相连
• Deliberate Practicing 刻意练习
• Feedback 反馈

数据结构

• 一维

  • 基础: 数组 array(String)、链表 linked list
  • 高级：栈 stack、队列 queue、双端队列 deque、 集合 Set、映射 map (hash or map),etc

• 二维

  • 基础： 树 tree、图 graph
  • 高级： 二叉搜索树 binary search tree(red-black tree)、堆 heap、 并查集 disjoint set、字典树 trie,etc

• 特殊

  • 位运算 Bitwise、布隆过滤器 BloomFilter
  • LRU Cache

算法

• if-else，switch -> branch
• for,while loop -> iteration
• 递归 Recursion（Divide & Conquer，Backtrace）
• 搜索 Seach: 深度有限搜索 Depth first search,广度优先算法 Breadth first search,A*,etc
• 动态规划 dynamic Programming
• 二分查找 Binary Search
• 贪心 Greedy
• 数学 Math，几何 Geometry

刻意练习

• 过遍数：（五毒神掌）
• 练习缺陷、弱点的地方

Feedback

• 即时反馈
• 主动型反馈
  • 高手代码(Github,LeetCode,.etc.)
  • 第一视角直播
• 被动型反馈
  • code review
  • 教练给反馈

切题四件套

• Clarification 保证理解清楚题目
• Possible solution 所有可能的解法
  • compare(time/space) 最优解法
  • optimal(加强)
• Coding(多写)
• Test cases 测试用例

五毒神掌

刷题第一遍

• 5分钟： 读题+思考
• 直接看解法： 多解法比较解法优劣
• 背诵、默写好的解法

刷题第二遍

• 马上默写 -> LeetCode提交
• 多种解法比较、体会->优化

刷题第三遍

• 隔天练习

刷题第四遍

• 隔周练习

刷题第五遍

• 面试前练习

时间复杂度和空间复杂度

时间复杂度

• O(1): Constant Complexity 常数复杂度
• O(log n): Logarithmic Complexity 对数复杂度
• O(n): Linear Complexity 线性时间复杂度
• O(n^2): N square Complexity 平方
• O(n^3): N cube Complexity 立方
• O(2^n): Exponential Growth 指数
• O(n!): Factorial 阶乘

Master Theorem

• 二分查找: T(n) = T(n/2) + O(1) -> log(n)

• 二叉树的遍历: T(n) = 2T(n/2) + O(1) -> O(n)

• 在排好序的二维矩阵二分查找: T(n) = 2T(n/2) + O(log n) -> O(n)

• 归并排序: T(n) = 2T(n/2) + O(n) -> O(n log n)

• 二叉树前序/中序/后序遍历的时间复杂度: O(n) -> n为总节点数

• 图的遍历时间复杂度：O(n) -> n为图的节点总数

• 搜索算法DFS/BFS的时间复杂度: O(n) -> n为搜索空间里的节点总数

• 二分查找时间复杂度是: O(log n)

[718预习周]算法总结

算法训练营（第4期）第一周作业

【153-Week 预习周】预习周的总结

目标

真正理解数据结构和算法，不追求速度，弄懂一道是一道。

输出

1. 学习总结
2. 时间复杂度、空间复杂度分析
3. Java和JavaScript代码各一份

方法

五遍刷题法

1. 第一遍
   • 5分钟：读题 + 思考
   • 直接看解法：比较不同解法的优劣，分析时间复杂度
   • 背诵、默写
2. 第二遍
   • 自己写，不参考任何资料，提交 LeetCode
   • 多种解法都写一遍，体会 -> 优化
3. 第三遍
   • 过了一天后，再重复做题
   • 不同解法的熟练程度 -> 专项练习
4. 第四遍
   • 过了一周，反复回来练习相同题目
5. 第五遍
   • 面试前一周恢复性训练

编程**

自顶向下编程

1. 先抽象，只写出需要用到的方法名，参数等
2. 利用编辑器自带的代码生成工具，生成函数
3. 再具体，补全各个方法中的具体细节

【578-week 01】总结

1）、数组随机访问时间复杂度为O(1)，插入、删除时间复杂度为O(n)
2）、链表插入、删除时间复杂度为O(1)，随机访问时间复杂度为O(n)
链表分为单链表、循环链表、双向链表、双向循环链表
LinkedList底层实现是一个双向链表
3）、跳表是链表加多级索引的结构，插入、删除、随机访问的时间复杂度均为O(logn)
4）、栈，先进后出，随机访问时间复杂度为O(n)，插入、删除时间复杂度为O(1)
Stack常用API：
public E push(E item)//将item压入栈并返回item

public synchronized E pop()//弹出并返回栈顶的item,如果栈为空会抛出EmptyStackException

public synchronized E peek()//返回栈顶的item,如果栈为空会抛出EmptyStackException

public boolean empty()//栈是否为空

5）、队列，先进先出，随机访问时间复杂度为O(n)，插入、删除时间复杂度为O(1)

PriorityQueuec常用API：

    //小顶堆(最小最优先)
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    //大顶堆
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(11, (x, y) -> (y - x));

public boolean offer(E e)//将指定元素插入到优先队列中
    
public E peek()//获取但不移除此队列的头,如果此队列为空则返回null
   
public E poll()//获取并移除此队列的头,如果此队列为空则返回null        

Java中的PriorityQueue是通过堆来实现的，扩容的时候如果旧容量小于64，则增加旧容量+2的大小
；如果旧容量大于等于64，则增加旧容量的一半大小，每次增加元素，都要进行堆化来保证堆序

【598-Week 01】第一周总结

本周收获

本周学习了数组，链表、跳表，栈和队列等内容，其中跳表和双端队列是第一次接触。 思路已有，代码未曾实现。

在接下来的课程中肯定还会出现我没有接触过的东西，毕业十年，前几年一直做.net(c#) ，基本就是ctrl+c ctrl+v, 最近几年一直做Java软件售后，写代码的机率大大减少，虽然是工科毕业，但依然没有接触过，好在这次训练营正好弥补缺憾,所以感谢训练营的各位老师

我觉得我本周最大的收获是这几个：

收获一：重复性(本周最大收获)

按老师的说明，计算机只是识别if else loop等一些关键字，最关键的就是重复性， 这一点从上阶梯的示例中得来：

• 走一级台阶：
  • 一步走上去，一种解法
• 走两级台阶：
  • 要么分两个一步上去，一种解法
  • 要么一步迈两个台阶上去，一种解决
• 走三级台阶：
  • 要么先走一步，再迈两步
  • 要么先迈两步，再迈一步
  • *** 这里的迈两步不就是走两级台阶的实现么，这个就是一个典型的重复 ***

收获二：自顶向下的编程方式

这种方式我很早就知道了，只是叫做列步骤，名称倒是无所谓，关键就是这种编程方式尚需要再次刻意练习，否则很容易陷入细节。

收获三：JDK源码的经典性

在看链表删除节点的代码时，发现它并没有手动将节点的next指针释放，当时就是认为是个bug，通过与各位朋友的讨论，外加看JDK源码，才知道是自己理解上的一个误区，GC会自动收集这些不可达的对象。这可以证明出一点：

• 再有类似问题直接看经典的类似的代码是怎么实现的

收获四：两大**

• 升维
• 空间换时间

改写Deque代码

改写后的代码如下

        Deque<String> deque = new LinkedList<>();
//        deque.addFirst("a");
//        deque.addFirst("b");
//        deque.addFirst("c");
        deque.addLast("c");
        deque.addLast("b");
        deque.addLast("a");
        System.out.println(deque);

        String str = deque.peekFirst();
        System.out.println(str);
        System.out.println(deque);

        while (deque.size()>0){
            System.out.println(deque.removeFirst());
        }
        System.out.println(deque);

分析Queue代码(jdk1.8)

Queue 为Java中的队列接口，各方法说明如下：

//向队列中添加元素，如添加失败抛出异常
boolean add(E e);
//阻塞式向队列中添加元素，如队列已满，则等待，直到能添加进去为止
boolean offer(E e);
//移除并返回队头的元素，如果队列为空，则抛出异常
E remove();
//移除并返回队头的元素，如果队列为空，则返回null
E poll();
//返回队头的元素，如果队列为空，则抛出异常
E element();
//返回队头的元素，如果队列为空，则返回null
E peek();

分析Priority Queue的源码(JDk1.8)

内部维护一个Queue 数组

 transient Object[] queue; 

优先队列本质上是对二叉堆的封装，目前对二叉堆的认识如下：

• 节点的左子树都小于等于其父节点，右子树都大于父节点
• 添加元素是通过上浮或者下沉的方式实现

关于时间复杂度 ： 主要考虑到维护其内部的二叉堆

• 要么添加元素的时间复杂度为O(1)， 取元素的时间复杂为O(logn)
• 要么添加元素的时间复杂度为O(logn)， 取元素的时间复杂为O(1)

【498-week 01】总结

感受

一定要找到最小重复单元

链表

以前不知道链表是怎样实现的，这一周把单链表、循环链表、双向链表、双向循环链表，实现了一遍。发现学习完链表，会对指针有更好的理解。

双指针

最近做题用的很多方法都使用的是双指针，即使是栈其实也储存的是指针，用空间换时间。
场景：遍历数组，两个指针指向不同的元素，从而协同完成任务。双指针可以从不同的方向向中间逼近。

栈

场景：拥有最近相关性，成对出现的题。要使用栈这种结构。

新知

还是练的太少，再练几遍

🌟🌟🌟Week 01 算法题作业链接集合

Hi各位同学，俗话说“三人行，必有我师”，因此我们鼓励大家在整个学习期间，多多 Review 同班同学的代码并进行点评。在这个过程中：

• 可能你会从其他同学的代码中学到一个更优的思路
• 可能你会因为其他同学给你的评论启发新的灵感
• 可能你的代码会得到大家纷纷的点赞
• 有时候也可能因为其他小伙伴的一句“学习了”而备受鼓舞

“让优秀的人一起学习”，大家可以在互相 Review 的过程中思考更多、获得更多。因此，请把你的算法题作业链接（你自己仓库的链接就好）回复在下面，这样大家就可以更方便的进行代码 review 啦！

跟帖格式：

学号后三位：
姓名（你在班里的姓名，便于同学可以跟你讨论）：
你的代码链接：

【363-Week 预习周】 预习周的总结

1.刻意练习：练习自己不会(欠缺)的地方，重复练习(leetcode上题目至少5遍)。
2.工欲善其事必先利其器
3.解题：
3.1 审题
3.2 想出所有的解决思路
不要想到一个思路后就马上写，要多想几个解题思路之间作对比，选择出时间复杂度最优的解决思路
3.3 code
3.4 testcase

【078-Week 01】周总结

1.方法总结：
1）“五毒神掌”的实操第一周，这周进行前三步，下周强化练习。
2）读题没有思路就找最小重复的单元，分析找到规律。
3）优化算法：升维**，空间换时间。
4）习题中多次用到的夹逼定理，双端指针的方法，以及作业中也有尝试到。
2.课后习题：
1）用 add first 或 add last 这套新的 API 改写 Deque 的代码：
Deque deque = new LinkedList();
deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);

    String str = deque.getFirst();
    System.out.println(str);
    System.out.println(deque);

    while (deque.size() > 0) {
        System.out.println(deque.removeFirst());
    }
    System.out.println(deque);

2）分析 Queue 和 Priority Queue 的源码（目前还没整理完成，在后面在comment中补充）

【738-week 预习周】训练前准备以及思考

 本周作为算法训练营的预习周，通过仔细学习了覃超老师的3个预习性视频，深有体会，主要有以下几点：

1. 数据结构和算法脑图，在没有查看老师给出的脑图之前，我自己画了自己知道数据结构和算法的脑图(脑图已经提交【 pull request】)，然后对比了老师给出的脑图，发现自己虽然数据结构掌握的比较全面，但是数据结构运用在算法上面还是很欠缺的。
2. 学习了刷题五步法：

• 第一步：用5-15分钟对题目进行思考，想出头绪
  • 如果5-15分钟还没想出头绪，那么直接看答案，理解答案并背诵
• 第二步：关闭答案，自己写程序，直到测试通过
• 第三步：第二天对前一天的程序进行重新写
• 第四步：一周后对程序进行重新写
• 第五步：面试准备前半周或者一周，对题目进行重新写

3. 切题四件套：

• 读懂题目，理解题目，和面试官做好足够的沟通，防止自己对题意误解
• 想出所有能想到的解法
  • 分析时间/空间复杂度
  • 选出最优解法
• 写程序
• 写测试样例进行测试

4. 老师提供了mac上面的很好的工具建议，通过视频我安装了iTerm2 + Oh My Zsh的终端，现在自己mac上的终端比系统提供的好用多了
5. 关于IDE，我之前一直使用IDEA，通过学习，我安装了Vscode，并在Vscode安装了leetcode的插件，并对插件功能进行简单的研究。现在可以在Vscode方便的刷题了。
6. 关于code style和IDE的top tip，对之前掌握的进行查漏补缺，工欲善其事必先利其器。
7. 老师讲解的自顶向下的编程方式，结合自己工作中的编程方法，的确，只有自顶向下的编程，才能让代码的BUG减少，并具有更高可阅读性和维护性。
8. 最后是时间复杂度的开篇介绍，通过开篇的预习热身，希望在后面每个专题里面，对算法的时间和空间复杂度做更加全面的掌握，并能在写算法题的时候，对每种不通解法寻求最优时间复杂度。

---

开学预习周，虽然说是预习，但是内容也是非常重要的。老师的3个视频，让我补充了之前没有接触过的方面的开发方面的东西。加油~！

【328-week01】第一周总结

第一周感觉使用了老师的五毒神掌，效果显著，从反馈阶段得到了很多的最佳时间以及注意事项，比如：使用数组的时候小心越界问题，涉及到数字计算的题要慎重选择变量类型，小心溢出。关于老师提供的自顶向下的编程方法，感觉使用起来直接就建立了我对编程的清晰的思路，同时也应用到了作业中，感觉这种方式编程的思路非常清晰，以后应该运用到工作中。之前我做算法题比较急功近利，之前有个体验就是：老是想直接做出最优解。其结果往往就是死磕几小时，甚至几天搞不定，弄出来的代码也是非常的烂。老师说要将所有思路考虑出来，其实这样反倒是效率高了，因为从最差解到最优解往往都是循序渐进的，心急吃不了热豆腐，一步步来，往往进步更快。

【108-Week 01】第一周总结

Note by dark fire 20191020

1.第一周知识点

-- https://mubu.com/doc/2Ri9O5sKMWM
二维码如下

2.算法题的思路

--升维**+空间换时间（跳表）
--如果一个问题具有最近相关性，可以用 栈 来解决（栈）
--左右夹逼：左右边界向中间收敛
--找最近重复子问题

3.源码分析(jdk1.7)

3.1 工程应用

队列和阻塞队列是在不同的包下，作用并不一样
[笔记：](https://shimo.im/sheet/Ld6c7wY0OgcQtLgy/RIDOC/ 《探底rt.jar》)

特别是阻塞队列更为常用，比如物联网项目的采集环节，如果平衡采集频度，线程池的大小，采集 阻塞处理都和队列能挂上关系，特别是线程池中几种队列的选择，另外常用的分布式任务调度框架（xxl-job，el-job）,底层源码都会有阻塞队列的应用。

3.2 PriorityQueue源码分析
--普通队列都是先进先出的，但是优先级队列是根据优先级进行确定的，优先级最高的先出队列；
--优先级队列类似于一棵完全二叉树，其内部实现使用的是数组；
--优先级队列在数组中其元素不一定是完全有序的，但是在出队列时，其元素是有序的；
--优先级队列插入和删除元素时，都需要对队列中的元素进行调整，其中remove()和add()方法的时间复杂度为O(log n),而remove(Obejct obj)和contaions()方法需要O(n)时间复杂度，取对头元素只需要O(1)时间；
--优先级队列是非同步的，队列中不允许使用null元素。
--不是线程安全，请使用线程安全的 PriorityBlockingQueue 类。
--初始化：在PriorityQueue中初始化定义了5个变量，可以看到它的底层存储逻辑是用数组实现的，默认的初始化容量是11.

3.3 Queue源码分析
--Queue也继承自Collection，说明它是集合家族的一员.
--Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Deque接口

4.改写代码

要求：用add first或add last这套新的API改写Deque的代码
Deque deque = new LinkedList();
//deque.push("a")
//deque.push("b")
//deque.push("c")

deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);

//String str = deque.peek();
String str = deque.peekFirst();
System.out.println(str);
System.out.println(deque);

while (deque.size() > 0) {
//System.out.println(deque.pop());
System.out.println(deque.removeFirst());
}
System.out.println(deque);

【063-week 01】Queue和PriorityQueue代码简单分析和周总结

第一周内容比较简单，课程中提到的LRU Cache和跳表以前没太接触过，通过视频学习也拓展了一些视野，首先按照作业要求，用JDK新的API改写的Deque代码如下

import java.util.Deque;
import java.util.LinkedList;

public class TestNewApi {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();

        deque.addFirst("a");
        deque.addFirst("b");
        deque.addFirst("c");

        String str = deque.getFirst();
        System.out.println(str);
        System.out.println(deque);

        while (deque.size() > 0) {
            System.out.println(deque.removeFirst());
        }

        System.out.println(deque);
    }
}

本人以前分析C++ STL库中的容器实现代码比较多，JDK中的容器实现代码阅读较少，借助这次机会对JDK中Queue和PriorityQueue的代码做下阅读和简单分析

Queue本身是一个泛型接口, 规范了队列这种容器的实现类需要实现的功能API
其中包含的主要API如下：
add 数据进行入队操作，在入队失败会返回false给调用端, 并且在空间不够用时候抛出IllegalStateException异常
offer 数据进行入队操作，入队失败以抛异常体现
remove 队头元素出队，出队元素返回给调用端，队列为空时向外抛NoSuchElementException异常
poll 队头元素出队，出队元素返回给调用端，队列为空时返回null给调用端
element 获取队头元素，但不进行出队操作，队列为空时候向外抛异常
peek 获取队头元素，但不进行出队操作, 队列为空时候返回null给调用端

根据使用场景和功能的不同， Queue接口有各种不同实现类， 相对起C++ STL中以模板类方式对queue容器进行实现要较为灵活，可以借多态机制通过统一的Queue接口调用不同实现类的具体实现，让调用方对Queue接口的使用和具体实现类解耦

各种实现类的关系可以参照下图

例如阻塞队列接口BlockingQueue继承自Queue， 不仅要求其实现类实现Queue接口中API的功能，同时拓展阻塞队列所具备的同步堵塞读写特性， 根据底层用链表或是数组或者是堆结构作为不同的存储结构，有LinkedBlockingQueue和ArrayBlockingQueue等不同的实现，在不同的场景下进行应用

并发库中对于Queue接口也有对应的支持多线程安全访问的实现类，例如ConcurrentLinkedQueue，底层利用了CAS技术实现了比单纯进行重型加锁较为高效的多线程并发同步

PriorityQueue提供一种数据能够根据预先定义比较规则进行有序出队的结构, 以前接触主要是在一些类似于A*的启发式搜索算法中作为中间状态转存的容器使用, 背后一般都使用堆结构进行实现

其内部用Object[] 类型的数组存储元素数值，因为Java泛型实现使用擦拭法进行，泛型类型并不真正体现在容器内部元素的实际类型上，这一点和C++中泛型的实现有所不同，泛型容器中一般保存元素都使用Object类型实例组成的数据结构, 本质上是用数组实现二叉堆结构，queue[0]是最小元素，queue[2n+1]和queue[2n+2]分别是queue[n]的两个儿子

PriorityQueue构造方法有多种重载方式, 提供不同的构造参数，可以选择用较少参数配置优先队列的初始容量，也可以用更多参数配置元素大小关系的比较方式，用于自定义元素的比较逻辑，如果不提供comparator参数，元素之间的比较操作就按照元素对应类实现的Comparable接口中的比较逻辑进行自然排序, PriorityQueue默认先出队的是最小的元素，是小顶堆实现，而C++ STL中的priority_queue容器默认是大顶堆

当优先队列中容量不够存储当前元素时候会进行容量拓展，老容量小于64就在老容量基础上加2，否则直接将容量 拓展为老容量两倍，具体可参见下面代码段

对优先队列的出队和入队操作都会导致二叉堆的形态发生变化，具体就体现在offer 和 remove的方法最终都会调用shiftXXX 函数调整二叉堆的状态， 具体调整二叉堆的方法就不再赘述，各种讲解数据结构的书籍和博客均有分析

比较有意思一个点是offer remove等操作都会将modCount成员进行递增，用于记录当前的优先队列对象被修改的次数，而PriorityQueue内部的迭代器的next 和 remove等操作都会在入口处检查预期的修改次数和实际的修改次数是否一致

这样做的目的是防止用同一个PriorityQueue对象的多个迭代器对优先队列进行修改时候导致访问错误，在检查到有这种情况出现时就向外抛出ConcurrentModificationException异常, 例如下面的代码多个迭代器误操作就会导致ConcurrentModificationException异常

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

public class TestOldApi {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();

        deque.push("a");
        deque.push("b");
        deque.push("c");

        Iterator<String> itr1 = deque.iterator();
        Iterator<String> itr2 = deque.iterator();
        itr1.next();
        itr2.next();
        itr1.remove();
        itr2.remove();
    }
}

时间和精力有限，代码大致分析到此结束，本人对Java语言不是很熟悉，如上分析如有错漏和谬误请大神指正，欢迎大家交流

【693-Week 01】周总结 + 课后习题

第一周算法总结+源码分析+改写Deque代码

[TOC]

一、学习总结

精华：

• 解题曲线：五毒神掌之少一掌
• 解题思路：重复点，重复规律
• 效率优化：升维，用空间换时间(典型的就有redis的跳表)
• 左右指针:左右边界向中间收敛
• 快慢指针：判断是否有环等
• 最新相关性问题：可以直接考虑用栈来解决

知识点：

​ 数组，链表、栈、队列、堆排

Leetcode：

​ 链接(欢迎指正错误):https://github.com/kyiln/algorithm004-03/tree/master/Week%2001/id_693

二、源码分析

1、Queue源码

继承关系

• 继承Collection、Iterable接口

函数说明

add(E e):boolean
	//添加元素
	//如果没有队列空间已满，抛出异常

offer(E e):boolean
	//添加元素
	//如果没有队列空间已满，进行扩容添加
	
remove():E
	//压出栈顶元素
	//如果队列为null，抛出异常
	
poll():E
	//压出栈顶元素
	//如果队列为null，返回null
	
element():E
	//检索栈顶元素
	//如果队列为null，抛出异常
	
peek():E
	//检索栈顶元素
	//如果队列为null，返回null

2、Priority Deque源码

继承关系

• 实现了Serializable、Queue、Collection、Iterable接口
• 实现了AbStractQueue、AbstractCollection抽象类

属性说明

//默认初始化大小
private static final intDEFAULT_INITIAL_CAPACITY = 11；
//用数组实现的二叉堆
private transient Object[] queue ;
//队列的元素数量
private int size = 0;
//比较器
private final Comparaotr<? super E> comparator;
//修改版本
private transient int modCount = 0;

常用函数

1、offer 添加元素

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        //如果队列size大于等于队列元素,则进行扩容
        //如果队列size小于64 则size * 2 + 2,否则扩容一半(size + size >> 1)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        //如果队列为null，直接添加元素
        queue[0] = e;
    else
        //函数插入尾部，并对其上浮判断
        siftUp(i, e);
    return true;
}
//上浮
private void siftUp(int k, E x) {
    //如果没有实现比较器则需要对插入的元素实现Comparaotr接口
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpComparable(int k, E x) {
    //比较器comparator为null，就需要对插入的元素实现Comparator接口，用于比较大小	
    Comparable<? super E> key = (Comparable<? super E>) x;
    //k判断是否是根，
    while (k > 0) {
        //计算元素x的父节点位置
        int parent = (k - 1) >>> 1;
        //取出x 的父节点
        Object e = queue[parent];
        //如果新增元素比父元素大或等于，则不用上浮，跳出循环
        if (key.compareTo((E) e) >= 0)
            break;
        //x比父亲小，需要进行上浮元素，和父元素进行交换，然后进入下一个循环，
        //直到k >= 父元素 或 为根节点
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

2、remove 删除元素

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i)
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        //从删除的元素位，开始下沉，原理类似上浮，
        //只是时会考虑左子节点和右子节点的大小，会把小的给左节点，挺有意思的
        siftDown(i, moved);
        //下沉后元素不变，就需要考虑元素的上浮。
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

三、改写Deque

LinkedList

Deque<String> deque = new LinkedList();
//deque.push("a")
//deque.push("b")
//deque.push("c")

deque.addFirst("a");
deque.addFirst("b");
deque.addFirst("c");
System.out.println(deque);

//String str = deque.peek();
String str = deque.peekFirst();
System.out.println(str);
System.out.println(deque);

while (deque.size() > 0) {
    //System.out.println(deque.pop());
    System.out.println(deque.removeFirst());
}
System.out.println(deque);