抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

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

  1. 不可变对象;
  2. 互斥锁;
  3. ThreadLocal 对象;
  4. CAS;

六度人脉理论

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

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

以‘小点’为起始点,广度优先遍历,生成遍历树(无权图可以生成最小生成树),输出层数为6的结点。
数据结构使用邻接表,边表节点由 一度好友 组成。
java 中,邻接表可以用 linkedlist(边表) 加 hashmap、ArrayList (顶点表)实现。

用邻接表及广度优先算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
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字符串,再对栈中符号进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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));
}
}

用户交流区

温馨提示: 遵纪守法, 友善评论!





津ICP备19009605号

WordCount24k