开一个n的区间, 指针指向开头; 不够的时候, 再开一个2n的区间, 把指针挪过来.
FIFO队列包含两个基本操作：插入(put)一个新的项，删除(get)一个最早插入的项。
循环数组实现方式：
对于每一个队列数据结构，我们保留一个数组S,其最多存放的Nmax个元素，定义两个位置front和rear分别指向队列的头尾两端，此外我们用N来记录队列中实际存在的元素 的个数。
对于一个元素item入队，我们让N和rear增1，然后置s[rear]=item;
对于一个元素item入队，我们让N减1，让front增1.
注意：这种实现有一个潜在的问题。假设数组的Nmax=10,经过10次入队后，队列似乎已经满了，因为此时rear=9.然而，队列中可能只存在小于9个的元素，因为 之前入队的操作可能伴随着出队的操作。例如我们将1,2,3,4,5,6,7,8,9,10一次入队，然后又进行2次出队操作，此时front指向数组元素S[2]处的位置，此时队列中只 有8个元素，这时rear仍然指向数组的最后一个元素S[Nmax-1]的位置，此时我们有没有办法继续进行入队操作呢？
简单的解决方法是：只要front和rear到达数组的末尾，它就又绕回到开头，这种实现方式就是循环数组的实现。这样队列的操作就局限在所定义的数组这块存储空间内。
push, pop, top
push, pop,front,back
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
将“内存”中结构化的数据变成“字符串”的过程
序列化:object to string
反序列化:string to object
Example
An example of testdata: Binary tree {3,9,20,#,#,15,7}, denote the following structure:
3
/ 9 20
/ 15 7
class Solution {
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
public String serialize(TreeNode root) {
if (root == null) {
return "{}";
}
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
queue.add(root);
for (int i = 0; i < queue.size(); i++) {
TreeNode node = queue.get(i);
if (node == null) {
continue;
}
queue.add(node.left);
queue.add(node.right);
}
while (queue.get(queue.size() - 1) == null) {
queue.remove(queue.size() - 1);
}
StringBuilder sb = new StringBuilder();
sb.append("{");
sb.append(queue.get(0).val);
for (int i = 1; i < queue.size(); i++) {
if (queue.get(i) == null) {
sb.append(",#");
} else {
sb.append(",");
sb.append(queue.get(i).val);
}
}
sb.append("}");
return sb.toString();
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it‘s given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
public TreeNode deserialize(String data) {
if (data.equals("{}")) {
return null;
}
String[] vals = data.substring(1, data.length() - 1).split(",");
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
queue.add(root);
int index = 0;
boolean isLeftChild = true;
for (int i = 1; i < vals.length; i++) {
if (!vals[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
if (isLeftChild) {
queue.get(index).left = node;
} else {
queue.get(index).right = node;
}
queue.add(node);
}
if (!isLeftChild) {
index++;
}
isLeftChild = !isLeftChild;
}
return root;
}
}
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
一个graph是不是tree的决定条件有两个：
public class Solution {
/**
* @param n an integer
* @param edges a list of undirected edges
* @return true if it‘s a valid tree, or false
*/
public boolean validTree(int n, int[][] edges) {
if (n == 0) {
return false;
}
if (edges.length != n - 1) {
return false;
}
Map<Integer, Set<Integer>> graph = initializeGraph(n, edges);
// bfs
Queue<Integer> queue = new LinkedList<>();
Set<Integer> hash = new HashSet<>();
queue.offer(0);
hash.add(0);
while (!queue.isEmpty()) {
int node = queue.poll();
for (Integer neighbor : graph.get(node)) {
if (hash.contains(neighbor)) {
continue;
}
hash.add(neighbor);
queue.offer(neighbor);
}
}
return (hash.size() == n);
}
private Map<Integer, Set<Integer>> initializeGraph(int n, int[][] edges) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.put(i, new HashSet<Integer>());
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
graph.get(u).add(v);
graph.get(v).add(u);
}
return graph;
}
}
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
How we serialize an undirected graph:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
0. Connect node 0 to both nodes 1 and 2.1. Connect node 1 to node 2.2. Connect node 2 to node 2 (itself), thus forming a self-cycle.Visually, the graph looks like the following:
1
/ / 0 --- 2
/ \_/
public class Solution {
/**
* @param node: A undirected graph node
* @return: A undirected graph node
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return node;
}
// use bfs algorithm to traverse the graph and get all nodes.
ArrayList<UndirectedGraphNode> nodes = getNodes(node);
// copy nodes, store the old->new mapping information in a hash map
HashMap<UndirectedGraphNode, UndirectedGraphNode> mapping = new HashMap<>();
for (UndirectedGraphNode n : nodes) {
mapping.put(n, new UndirectedGraphNode(n.label));
}
// copy neighbors(edges)
for (UndirectedGraphNode n : nodes) {
UndirectedGraphNode newNode = mapping.get(n);
for (UndirectedGraphNode neighbor : n.neighbors) {
UndirectedGraphNode newNeighbor = mapping.get(neighbor);
newNode.neighbors.add(newNeighbor);
}
}
return mapping.get(node);
}
private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
HashSet<UndirectedGraphNode> set = new HashSet<>();
queue.offer(node);
set.add(node);
while (!queue.isEmpty()) {
UndirectedGraphNode head = queue.poll();
for (UndirectedGraphNode neighbor : head.neighbors) {
if(!set.contains(neighbor)){
set.add(neighbor);
queue.offer(neighbor);
}
}
}
return new ArrayList<UndirectedGraphNode>(set);
}
}
三步走：
劝分不劝合， 编程能分开的尽量分开写。
能用BFS， 一定不用DFS， 因为dfs有recursion， 容易stack over flow
由点及面
不用做分层遍历
Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can’t find.
There is a mapping store the nodes’ values in the given parameters.
It’s guaranteed there is only one available solution
2------3 5
\ | |
\ | |
\ | |
\ | |
1 --4
Give a node 1, target is 50
there a hash named values which is [3,4,10,50,50], represent:
Value of node 1 is 3
Value of node 2 is 4
Value of node 3 is 10
Value of node 4 is 50
Value of node 5 is 50
Return node 4
public class Solution {
/**
* @param graph a list of Undirected graph node
* @param values a hash mapping, <UndirectedGraphNode, (int)value>
* @param node an Undirected graph node
* @param target an integer
* @return the a node
*/
public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
Map<UndirectedGraphNode, Integer> values,
UndirectedGraphNode node,
int target) {
// Write your code here
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
Set<UndirectedGraphNode> hash = new HashSet<UndirectedGraphNode>();
queue.offer(node);
hash.add(node);
while (!queue.isEmpty()) {
UndirectedGraphNode head = queue.poll();
if (values.get(head) == target) {
return head;
}
for (UndirectedGraphNode nei : head.neighbors) {
if (!hash.contains(nei)){
queue.offer(nei);
hash.add(nei);
}
}
}
return null;
}
}
-可以用DFS？
可以，但是不推荐
-应用场景
选课
编译：编译的时候用link的东西，所以要看看有没有循环依赖。
-关心能否进行拓扑排序， 即是关心有没有环
-入度： 指向一个节点的边的个数
Given an directed graph, a topological order of the graph nodes is defined as follow:
A -> B in graph, A must before B in the order list.Find any topological order for the given graph.
For graph as follow:
The topological order can be:
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
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 the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Given n = 2, prerequisites = [[1,0]]
Return true
Given n = 2, prerequisites = [[1,0],[0,1]]
Return false
九章算法笔记 4.宽度优先搜索 Breadth First Search
原文：https://www.cnblogs.com/jiuzhangsuanfa/p/9895654.html