美团内推+校招笔试题+知识点总结

package cn.edu.ujn.practice;
import java.util.Scanner;
import java.util.regex.Pattern;
import java.util.ArrayList;
// 死在了多行输入上
public class meituan1 {
static ArrayList<Integer> list = new ArrayList<Integer>();
public static void main(String [] args){
Scanner in = new Scanner(System.in);
int lines = in.nextInt();
Pattern pattern = Pattern.compile("[,]+");
int [] arr = null;
// 用于接收换行符
in.nextLine();
for(int i = 0; i < lines; i++){
String [] str = pattern.split(in.nextLine());
arr = new int[str.length];
for(int j = 0; j < str.length; j++){
//System.out.print(str[j]+" ");
arr[j] = Integer.parseInt(str[j]);
}
// 调用方法
solution(arr);
//System.out.println();
}
for(int k = 0; k < arr.length; k++){
//System.out.println(arr[k]);
}
for(Integer a : list){
System.out.print(a + "");
}
}
private static void solution(int [] arr){
System.out.println(arr.length);
list.add(1);
}
}

package cn.edu.ujn.demo;

public class Prime {

	public static void main(String[] args) {
		int num = 1024;
		System.out.println(sumOfZero(num));
	}
	
	// 结算阶乘中包含0的个数
	private static int sumOfZero(int num){
		int cnt = 0;
		int a = 5;
		while(num > 0){
			cnt += num / a;
			num /= a;
		}
		return cnt;
	}
}

package cn.edu.ujn.graph;
import java.util.ArrayList;
import java.util.LinkedList;
/**
 * @description 邻接矩阵模型类
 * @author SHQ
 * @time 2016.09.12
 */
public class DFS_BFS {
    private ArrayList<Object> vertexList;// 存储点的链表
    private int[][] edges;	 // 邻接矩阵，用来存储边
    private int numOfEdges;	 // 边的数目
    boolean[] isVisited;	 // 遍历标志位
 
    public DFS_BFS(int n) {
        //初始化矩阵，一维数组，和边的数目
        edges = new int[n][n];
        vertexList = new ArrayList<Object>(n);
        numOfEdges = 0;
        // 将所有节点访问标志位均置为未访问
        isVisited = new boolean[n];
        for(int i = 0; i < n; i++){
        	isVisited[i] = false;
        }
    }
 
    //得到结点的个数
    public int getNumOfVertex() {
        return vertexList.size();
    }
 
    //得到边的数目
    public int getNumOfEdges() {
        return numOfEdges;
    }
 
    //返回结点i的数据
    public Object getValueByIndex(int i) {
        return vertexList.get(i);
    }
 
    //返回v1,v2的权值
    public int getWeight(int v1,int v2) {
        return edges[v1][v2];
    }
 
    //插入结点
    public void insertVertex(Object vertex) {
        vertexList.add(vertexList.size(),vertex);
    }
 
    //插入结点
    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2]=weight;
        numOfEdges++;
    }
 
    //删除结点
    public void deleteEdge(int v1,int v2) {
        edges[v1][v2] = 0;
        numOfEdges--;
    }
 
    //得到第一个邻接结点的下标
    public int getFirstNeighbor(int index) {
        for(int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }
 
    //根据前一个邻接结点的下标来取得下一个邻接结点
    public int getNextNeighbor(int v1, int v2) {
        for (int j = v2+1; j < vertexList.size(); j++) {
            if (edges[v1][j]>0) {
                return j;
            }
        }
        return -1;
    }
    
    //私有函数，深度优先遍历
    private void depthFirstSearch(boolean[] isVisited,int  i) {
        //首先访问该结点，在控制台打印出来
        System.out.print(getValueByIndex(i) + "  ");
        //置该结点为已访问
        isVisited[i] = true;
        
        int w = getFirstNeighbor(i);
        while (w != -1) {
            if (!isVisited[w]) {
                depthFirstSearch(isVisited,w);
            }
            w = getNextNeighbor(i, w);
        }
    }
    
    //对外公开函数，深度优先遍历，与其同名私有函数属于方法重载
    public void depthFirstSearch() {
        for(int i = 0; i < getNumOfVertex(); i++) {
            //因为对于非连通图来说，并不是通过一个结点就一定可以遍历所有结点的。
            if (!isVisited[i]) {
                depthFirstSearch(isVisited,i);
            }
        }
    }
    
    /**
     * 私有函数，广度优先遍历
     * 遍历步骤:
     * 访问初始结点v并标记结点v为已访问。
     * 结点v入队列
     * 当队列非空时，继续执行，否则算法结束。
     * 出队列，取得队头结点u。
     * 查找结点u的第一个邻接结点w。
     * 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
     * 1)若结点w尚未被访问，则访问结点w并标记为已访问。
     * 2)结点w入队列
     * 3)查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
     * @param isVisited
     * @param i
     */
    private void broadFirstSearch(boolean[] isVisited, int i) {
        int u, w;
        // 借助辅助队列，记录访问顺序
        LinkedList<Object> queue = new LinkedList<Object>();
        // 访问结点i
        System.out.print(getValueByIndex(i) + "  ");
        isVisited[i] = true;
        // 结点入队列
        queue.addLast(i);
        while (!queue.isEmpty()) {
            u = ((Integer)queue.removeFirst()).intValue();
            w = getFirstNeighbor(u);
            while(w != -1) {
                if(!isVisited[w]) {
                        //访问该结点
                        System.out.print(getValueByIndex(w)+"  ");
                        //标记已被访问
                        isVisited[w] = true;
                        //入队列
                        queue.addLast(w);
                }
                //寻找下一个邻接结点
                w = getNextNeighbor(u, w);
            }
        }
    }
    
    //对外公开函数，广度优先遍历
    public void broadFirstSearch() {
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                broadFirstSearch(isVisited, i);
            }
        }
    }
}

package cn.edu.ujn.graph;
 
public class Main {
    public static void main(String args[]) {
        int n = 8, e = 9; // 分别代表结点个数和边的数目
        String labels[]={"1","2","3","4","5","6","7","8"};	//结点的标识
        DFS_BFS graph = new DFS_BFS(n);
        for(String label : labels) {
            graph.insertVertex(label);	// 插入结点
        }
        //插入九条边
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);
        graph.insertEdge(1, 0, 1);
        graph.insertEdge(2, 0, 1);
        graph.insertEdge(3, 1, 1);
        graph.insertEdge(4, 1, 1);
        graph.insertEdge(7, 3, 1);
        graph.insertEdge(7, 4, 1);
        graph.insertEdge(6, 2, 1);
        graph.insertEdge(5, 2, 1);
        graph.insertEdge(6, 5, 1);
        
/*        System.out.println("深度优先搜索序列为：");
        graph.depthFirstSearch();
        System.out.println();*/
        System.out.println("广度优先搜索序列为：");
        graph.broadFirstSearch();
    }
}