写一个广度搜索的算法
计算二叉树的层序遍历
层序遍历广度优先要借助队列这种数据结构才能实现，队列数据两部分一个存node节点另一个存在第几层。
当访问节点的层数等于返回的集合长度的时候，说明返回的集合中还没对应层数的集合，因为索引要小于集合的长度。[[]] ,索引为0此时集合的长度为1。
当把数据存入集合的时候，要把左右孩子的节点也要入队了。
import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
import javafx.util.Pair;
class Solution {
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List levelOrder(TreeNode root) {
ArrayList res = new ArrayList();
if(root == null)
return res;
// 我们使用LinkedList来做为我们的先入先出的队列
LinkedList queue = new LinkedList();
queue.addLast(new Pair(root, 0));
while(!queue.isEmpty()){
Pair front = queue.removeFirst();
TreeNode node = front.getKey();
int level = front.getValue();
if(level == res.size())
res.add(new ArrayList());
assert level < res.size();
res.get(level).add(node.val);
if(node.left != null)
queue.addLast(new Pair(node.left, level + 1));
if(node.right != null)
queue.addLast(new Pair(node.right, level + 1));
}
return res;
}
}图的广度优先与最短路径
使用队列把与某个相邻的节点一次都放入队列中，一层一层的遍历图中所有相邻的节点，ord数组记录第几层
import java.util.Vector;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
public class ShortestPath {
private Graph G; // 图的引用
private int s; // 起始点
private boolean[] visited; // 记录dfs的过程中节点是否被访问
private int[] from; // 记录路径, from[i]表示查找的路径上i的上一个节点
private int[] ord; // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public ShortestPath(Graph graph, int s){
// 算法初始化
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// 无向图最短路径算法, 从s开始广度优先遍历整张图
Queue q = new LinkedList();
q.add(s);
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.remove();
for( int i : G.adj(v) )
if( !visited[i] ){
q.add(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
// 查询从s点到w点是否有路径
public boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// 查询从s点到w点的路径, 存放在vec中
public Vector path(int w){
assert hasPath(w) ;
Stack s = new Stack();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector res = new Vector();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// 打印出从s点到w点的路径
public void showPath(int w){
assert hasPath(w) ;
Vector vec = path(w);
for( int i = 0 ; i < vec.size() ; i ++ ){
System.out.print(vec.elementAt(i));
if( i == vec.size() - 1 )
System.out.println();
else
System.out.print(" -> ");
}
}
// 查看从s点到w点的最短路径长度
// 若从s到w不可达，返回-1
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
}给定一个正整数n求用最少的完全平方数获得和为n
队列中存两个数据，第一个是还剩余的数字需要完全平方数构成，另一个是需要由几个完全平方数构成。
问题可以转换为求无向图的最短路径的问题，因为一次只能加入一个值到队列中，从4出发经过1的路径一共有4条路径到0，经过2的路径只有一条路径最先到达0，所以最短的路径是2*2。
因为现在的结构是一个图不是一个树，树一定有到头走不下去的情况，而图每一个节点有多个路径到达它，会重复推入值到队列中，为了处理冗余的情况提升效率需要判断节点之前是否访问过。
把终止的条件提前，如果a==0的时候，直接返回步数，不用再带入进去从队列中取出元素提升一定的性能。
import java.util.LinkedList;
import javafx.util.Pair;
public class Solution {
public int numSquares(int n) {
if(n == 0)
return 0;
LinkedList queue = new LinkedList();
queue.addLast(new Pair(n, 0));
boolean[] visited = new boolean[n+1];
visited[n] = true;
while(!queue.isEmpty()){
Pair front = queue.removeFirst();
int num = front.getKey();
int step = front.getValue();
if(num == 0)
return step;
for(int i = 1 ; num - i*i >= 0 ; i ++){
int a = num - i*i;
if(!visited[a]){
if(a == 0) return step + 1;
queue.addLast(new Pair(num - i * i, step + 1));
visited[num - i * i] = true;
}
}
}
throw new IllegalStateException("No Solution.");
}
public static void main(String[] args) {
System.out.println((new Solution3()).numSquares(12));
System.out.println((new Solution3()).numSquares(13));
}
}队列的其他应用
优先队列
java的优先队列默认是最小堆，可以自己重写比较器来实现自定义优先队列
比较个位数，谁小谁写在前面
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;
public class Main {
public static void main(String[] args) {
// 默认的PriorityQueue, 底层是最小堆
PriorityQueue pq = new PriorityQueue();
for(int i = 0 ; i < 10 ; i ++){
int num = (int)(Math.random() * 100);
pq.add(num);
System.out.println("insert " + num + " in priority queue.");
}
while (!pq.isEmpty())
System.out.print(pq.poll() + " ");
System.out.println();
System.out.println();
// 使用lambda表达式，创建底层是最大堆的PriorityQueue
PriorityQueue pq2 = new PriorityQueue(10, (a, b) -> b - a);
for(int i = 0 ; i < 10 ; i ++){
int num = (int)(Math.random() * 100);
pq2.add(num);
System.out.println("insert " + num + " in priority queue.");
}
while (!pq2.isEmpty())
System.out.print(pq2.poll() + " ");
System.out.println();
System.out.println();
// 使用自定义的Comparator，创建个性化的PriorityQueue
// 注意：也可以使用lambda表达式。在这里只是为了演示PriorityQueue的不同用法
// 同理，上一个例子也可以使用自定义的Comparator的方式完成
class myCmp implements Comparator{
@Override
public int compare(Integer a, Integer b){
if(a%10 != b%10)
return a%10 - b%10;
return a - b;
}
}
PriorityQueue pq3 = new PriorityQueue(10, new myCmp());
for(int i = 0 ; i < 10 ; i ++){
int num = (int)(Math.random() * 100);
pq3.add(num);
System.out.println("insert " + num + " in priority queue.");
}
while (!pq3.isEmpty())
System.out.print(pq3.poll() + " ");
System.out.println();
System.out.println();
}
}给出y一个非空的数组返回前k个出现频率最高的元素
[1，1，1，2，2，3] k=2 返回[1，2]
通过定义一个Map，k为值，value对应具体的频率，统计每一个数字出现的频率。
通过定义一个优先队列设置频率小的放在最前面如果频率相等的话值小的放在最前面，队列中存两个元素第一个为频率第二个为对应的值，如果Map中取出的频率为题目的指定的频率并且已经取出了k个元素，判断把频率较大的放入到优先队列中。
import java.util.*;
import java.util.HashMap;
import javafx.util.Pair;
class Solution {
private class PairComparator implements Comparator{
@Override
public int compare(Pair p1, Pair p2){
if(p1.getKey() != p2.getKey())
return p1.getKey() - p2.getKey();
return p1.getValue() - p2.getValue();
}
}
public List topKFrequent(int[] nums, int k) {
if(k freq.size())
throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");
// 扫描freq,维护当前出现频率最高的k个元素
// 在优先队列中,按照频率排序,所以数据对是 (频率,元素) 的形式
PriorityQueue pq = new PriorityQueue(new PairComparator());
for(Integer num: freq.keySet()){
int numFreq = freq.get(num);
if(pq.size() == k){
if(numFreq > pq.peek().getKey()){
pq.poll();
pq.add(new Pair(numFreq, num));
}
}
else
pq.add(new Pair(numFreq, num));
}
ArrayList res = new ArrayList();
while(!pq.isEmpty())
res.add(pq.poll().getValue());
return res;
}
private static void printList(List nums){
for(Integer num: nums)
System.out.print(num + " ");
System.out.println();
}
