模拟面经二（随机）

原创

后端码匠

修改于 2021-08-20 10:13:58

3850

文章被收录于专栏：后端码匠后端码匠

请描述避免多线程竞争时有哪些手段？

1) 不可变对象；

2) 互斥锁；

3) ThreadLocal 对象；

4) CAS；

六度人脉理论

1929年，匈牙利作家Frigyes Karinthy在短篇故事‘Chains’中首次提出的“六度人脉理论”，是指地球上所有的人都可以通过六层以内的熟人链和任何其他人联系起来。我们定义A的‘一度好友’为A直接相识的好友，A的‘二度好友’为A一度好友的好友且与A不是一度好友，A的‘三度好友’为A二度好友的好友且与A不是一度好友、二度好友，以此类推。

在美团点评，小美、小团、小卓、小越、小诚、小信的好友关系见下图。

以‘小点’为起始点，广度优先遍历，生成遍历树（无权图可以生成最小生成树），输出层数为6的结点。

数据结构使用邻接表，边表节点由一度好友组成。

java 中，邻接表可以用 linkedlist（边表）加 hashmap、ArrayList （顶点表）实现。

用邻接表及广度优先算法

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Graph {
    //边
    public class EdgeNode{
        int index;  //存储该顶点对应的下标
        int weight; //存储权重
    }

    ArrayList<String> pointList;    //顶点数组
    LinkedList<EdgeNode> edjList[]; //邻接表
    int pointNum;       //顶点数
    int edgeNum;        //边数


    public Graph(int n){
        pointList = new ArrayList<>(n);
        edjList = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            edjList[i] = new LinkedList<>();
        }
        pointNum = n;
    }

    //添加一条顶点
    public void addPoint(String name){
        if(pointList.size() >= pointNum){
            System.out.println("point array full");
            return ;
        }
        if(pointList.indexOf(name) != -1){
            System.out.println("已经存在"+name);
            return ;
        }
        pointList.add(name);
    }

    public String getName(int index){
        return pointList.get(index);
    }

    //添加一条边
    public void addEdge(String name1, String name2, int weight){

        int i = pointList.indexOf(name1);
        if(i == -1){
            System.out.println("not find nam1="+name1);
            return ;
        }
        int j = pointList.indexOf(name2);
        if(j == -1){
            System.out.println("not find name2="+name2);
            return ;
        }

        EdgeNode edge = new EdgeNode();
        edge.index = j;
        edge.weight = weight;
        edjList[i].add(edge);
        edgeNum++;

        //加入另一个边 （无向边 两边都加）
        edge = new EdgeNode();
        edge.index = i;
        edge.weight = weight;
        edjList[j].add(edge);
        edgeNum++;
    }

    public void printAll(){
        for (String s : pointList) {

        }
        for (int i=0;i<pointList.size();i++) {
            System.out.print("节点"+pointList.get(i) +"边为:");
            for (EdgeNode edgeNode : edjList[i]) {
                System.out.print(pointList.get(edgeNode.index)+" ");
            }
            System.out.println("");
        }
    }

    /**
     * 广度遍历
     * @param name
     */
    public void BSTTraverse(String name){
        LinkedList<Integer> queue = new LinkedList();

        //找到name
        int i = pointList.indexOf(name);
        if(i == -1){
            System.out.println("not find name="+name);
            return ;
        }
        int[] a = new int[pointNum];
        for (int j = 0; j < pointNum; j++) {
            a[j] = 0;
        }

        a[i] = 1;
        LinkedList<EdgeNode> list = edjList[i];
        for (EdgeNode edgeNode : list) {
            queue.addLast(edgeNode.index);
            a[edgeNode.index] = 1;
        }
        while(queue.size() != 0){
            //从queue中拿出一个节点
            i = queue.removeFirst();
            System.out.println("遍历 " + pointList.get(i));

            list = edjList[i];
            for (EdgeNode edgeNode : list) {
                if(a[edgeNode.index] != 1){
                    queue.addLast(edgeNode.index);
                    a[edgeNode.index] = 1;
                }
            }
        }
    }


    public class Node{
        int index;
        int deep;
    }

    /**
     * 根据深度获取好友队列
     * @param name
     * @param deep 获取1度好友 则深度为2
     * @return
     * 采用广度优先算法
     */
    public LinkedList<Node> getQueueByDeep(String name, int deep){
        LinkedList<Node> queue = new LinkedList();
        //找到name
        int i = pointList.indexOf(name);
        if(i == -1){
            System.out.println("not find name="+name);
            return null;
        }
        int[] a = new int[pointNum];
        for (int j = 0; j < pointNum; j++) {
            a[j] = 0;
        }
        Node node = new Node();
        node.index = i;
        node.deep = 1;
        queue.addLast(node);
        a[i] = 1;

        while(queue.size() != 0){
            //从queue中拿出一个节点
            node = queue.getFirst();
            if(node.deep == deep){
                return queue;
            }
            queue.removeFirst();
            //System.out.println("遍历 " + pointList.get(node.index).data);

            List<EdgeNode> list = edjList[node.index];
            for (EdgeNode edgeNode : list) {
                if(a[edgeNode.index] != 1){
                    Node temp = new Node();
                    temp.index = edgeNode.index;
                    temp.deep = node.deep+1;
                    queue.addLast(temp);
                    a[edgeNode.index] = 1;
                    System.out.println("deep="+temp.deep + pointList.get(edgeNode.index));
                }
            }
        }
        return null;
    }

    public static void main(String[] args) throws Exception{

        Graph g = new Graph(7);
        g.addPoint("小团");
        g.addPoint("小美");
        g.addPoint("小诚");
        g.addPoint("小信");
        g.addPoint("小卓");
        g.addPoint("小越");

        g.addPoint("小孩");

        g.addEdge("小团", "小美", 1);
        g.addEdge("小卓", "小美", 1);
        g.addEdge("小诚", "小美", 1);
        g.addEdge("小团", "小卓", 1);
        g.addEdge("小诚", "小信", 1);
        g.addEdge("小信", "小越", 1);
        g.addEdge("小卓", "小越", 1);

        g.addEdge("小信", "小孩", 1);

        g.printAll();

        g.BSTTraverse("小美");

        int deep = 4;
        LinkedList<Node> queue = g.getQueueByDeep("小美", 4);
        if(queue == null){
            System.out.println("没有"+(deep-1)+"度好友");
        }else{
            for (Node node : queue) {
                System.out.println(node.deep+"度好友为 "+ g.getName(node.index));
            }
        }
    }
}

请简述HTTP的5个常用Method及其含义，以及5个常用Status Code及其含义？HTTP与HTTPS的区别是什么，简述一下HTTPS的实现原理。

get 从服务器端获取资源

put 提交资源

post 更新资源

delete 删除资源

connect 建立tunnel隧道

100 请求已收到，正等待后续资源

200 ok 成功

206 partial content 部分资源

301 永久重定向

400 bad request 客户端请求语法错误

500 Not Implement 服务器内部错误

502 Bad Getaway 网关错误

HTTP与HTTPS区别：

HTTPS是HTTP经由加入SSL层来提高数据传输的安全性。其中SSL依靠证书来验证服务器的身份，并对浏览器与服务器之间的通信进行数据加密。HTTP不适合传输敏感信息。

HTTPs实现原理：

发起请求：客户端通过TCP和服务器建立连接后，发出一个请求证书的消息给到服务器。

证书返回：服务器端在收到请求后回应客户端并且返回证书。

给出一个布尔表达式的字符串，比如：true or false and false，表达式只包含true，false，and和or，现在要对这个表达式进行布尔求值，计算结果为真时输出true、为假时输出false，不合法的表达时输出error（比如：true true）。表达式求值是注意and 的优先级比 or 要高，比如：true or false and false，等价于 true or (false and false)，计算结果是 true。

将字符串分割后分别压栈，若遇到顶层为and时候进行弹出对比，最后保证栈中只有true、false、or字符串，再对栈中符号进行判断

public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String[] ss=scanner.nextLine().split(" ");
        Stack<String> stack=new Stack<>();
        for(int i=0;i<ss.length;i++){
            String curr=ss[i];
            //当前值为true或false时
            if(curr.equals("true")||curr.equals("false")){
                if(stack.isEmpty()){
                    stack.push(curr);
                }else{
                    String top=stack.peek();
                    if(top.equals("true")||top.equals("false")){
                        System.out.println("error");
                        return;
                    }else{
                        if(top.equals("or")) stack.push(curr);
                        else{
                            stack.pop();
                            String pre=stack.pop();
                            if(curr.equals("false")||pre.equals("false")) stack.push("false");
                            else stack.push("true");
                        }
                    }
                }
            }
            //当前值为and或or时
            else{
                if(stack.isEmpty()){
                    System.out.println("error");
                    return;
                }else{
                    String top=stack.peek();
                    if(top.equals("and")||top.equals("or")){
                        System.out.println("error");
                        return;
                    }
                    stack.push(curr);
                }
            }
        }
        if(!stack.isEmpty()&&(stack.peek().equals("or")||stack.peek().equals("and"))){
            System.out.println("error");
            return;
        }
        while(!stack.isEmpty()){
            String curr=stack.pop();
            if(curr.equals("true")){
                System.out.println("true");
                break;
            }
            if(stack.isEmpty()) System.out.println("false");
        }
    }

给出两个字符串，分别是模式串P和目标串T，判断模式串和目标串是否匹配，匹配输出 1，不匹配输出 0。模式串中‘？’可以匹配目标串中的任何字符，模式串中的 ’*’可以匹配目标串中的任何长度的串，模式串的其它字符必须和目标串的字符匹配。例如P=a?b，T=acb，则P 和 T 匹配。

力扣44原题

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String p = sc.next();
        String s = sc.next();
        // System.out.println(s + " - " + p);
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int i = 1; i <= n; i++) dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*';
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if(p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        System.out.println((dp[m][n] ? 1 : 0));
    }
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

登录后参与评论

0 条评论

热度