yhw-miracle

数据结构与算法(翻译)

痛点就是起点 writed in

Data Structures And Algorithms

The level of questions asked on Data Structures And Algorithms totally depends on the company for which you are applying.

  • Array
  • LinkedList
  • A LinkedList, just like a tree and unlike an array, consists of a group of nodes which together represent a sequence. Each node contains data and a pointer. The data in a node can be anything, but the pointer is a reference to the next item in the LinkedList. A LinkedList contains both a head and a tail. The Head is the first item in the LinkedList, and the Tail is the last item. A LinkedList is not a circular data structure, so the tail does not have its pointer pointing at the Head, the pointer is just null. The run time complexity for each of the base methods are as follows:
Algorithm Average WorstCase
Space O(n) O(n)
Search O(n) O(n)
Insert O(1) O(1)
Delete O(1) O(1)
  • DoublyLinkedList
  • Stack
  • A Stack is a basic data structure with a “Last-in-First-out” methodology. Which means that the last item that was added to the stack, is the first item that comes out of the stack. A Stack is like a stack of books. In order to get to the first book that was added in the stack (the bottom book), all of the books that were added after need to be removed first. Adding to a Stack is called a Push, removing from a stack is called a Pop, and getting the last item inserted into the stack without removing it is called Top. The most common way to implement a stack is by using a LinkedList, but there are also StackArray (implemented with an array) which does not replace null entries, and there is also a Vector implementation that does replace null entries.
Algorithm Average Worst Case Image representation
Space O(n) O(n)  
Search O(n) O(n)  
Insert(Push) O(1) O(1)  
Delete(Pop) O(1) O(1)  
Top O(1) O(1)  
  • Queue
  • PriorityQueue
  • Dynamic Programming
  • String Manipulation
  • Binary Tree
  • Binary Search Tree
  • Sorting Algorithms
  • Hash Table or Hash Map
  • Breadth First Search
  • Depth First Search
  • Greedy Algorithm

翻译如下:

数据结构和算法

数据结构和算法的问题层面完全取决于你所应聘公司的要求。

  • 数组
  • 链表
  • 就像树形结构,而不像数组那样的链表结构是由一起表示一个序列数据的一组结点组成的。每个结点包含数据域和指针域。结点中的数据域可以是任何一种数据结构,但是指针域是链表中对后一个元素的引用。一个链表可以包含一个头指针和一个尾指针,头指针是指向链表的的第一个元素,即头部,而尾指针是指向最后一个元素的,即尾部。链表不是一个循环的数据结构,因此尾指针所指向的尾部没有指向头部的指针,尾部的指针域为 null。链表具有增删改查等基本操作,下表是链表中每个基本操作运行的时间复杂度。
操作 平均时间复杂度 最差时间复杂度
修改 O(n) O(n)
查询 O(n) O(n)
插入 O(1) O(1)
删除 O(1) O(1)
  • 双向链表
  • 栈是一个具有“后进先出”操作的基本数据结构。这就说明被添加到栈的最后一个元素将是第一个出栈元素。栈结构就像一堆书,如果你为了获得在这堆书中的第一本书(就是最底部的书),你需要书堆里的所有书都需要先移除,这样你才能获得书堆里的第一本书。在栈里面,添加一个元素到栈里的操作被称为入栈,即 Push,从栈了删除一个元素的操作被称为出栈,即 Pop,而在不移除栈的情况下获取栈里最后一个元素的操作叫做获取栈顶部元素,即 Top。栈的内部实现的最常用方法是使用链表;但是也有用堆栈数组(用数组实现)的,这会保留一些空条目;还有是用 Vector 实现的,这不会保留空条目。
操作 平均时间复杂度 最差时间复杂度 图像表示
修改 O(n) O(n)  
查询 O(n) O(n)  
插入(Push) O(1) O(1)  
删除(Pop) O(1) O(1)  
取栈顶元素(Top) O(1) O(1)  
data structures algorithms
技术翻译

欢迎关注,我们一起进行认知迭代!


痛点就是起点

© 2016 - 2020 基于 jekyll | Github Pags | iconfont By yhw-miracle