当前位置:网站首页>May brush question 27 - figure
May brush question 27 - figure
2022-07-06 09:38:00 【A Guang chasing dreams】
May brush questions 27—— chart
Today's brush topic content : chart
Preface
- An algorithm opens the way to brush the questions of waste materials , Update the problem solution content of the problem brush every day
- Focus on personal understanding , Look at the difficulty and update the number of questions
- The title comes from Li Kou
- Try to work out at least one question every day
- Language java、python、c\c++
One 、 Today's topic
I only did two questions , I didn't have much time to write solutions yesterday , Make up today , The next two questions will be brushed later when you are not so busy
- 1791. Find the central node of the star graph
- 797. All possible paths
- 851. Noise and wealth
- 959. Area by slash
Two 、 Their thinking
1. 1791. Find the central node of the star graph
edges[i]
Both are composed of two nodes , It is known that the central node will be connected to all other nodes- Select any point from a set of nodes , Compare with two points in another node set
- If it appears in another node set, it means that this point is the central node
- Otherwise, it is another node
class Solution {
public int findCenter(int[][] edges) {
int e = edges[0][0];
if (e == edges[1][0] || e == edges[1][1]){
return e;
}
return edges[0][1];
}
}
/* * Judge according to the edge , If it is the center point , It must appear in both sets */
2. 797. All possible paths
Depth first search again , Let's use recursion first , Next time use a loop to solve
- To find all the paths , That is, violent enumeration
graph[i]
Indication pointi
All point sets that can be reached- Define a stack
stack
, Initial deposit0
This node- The delivery process puts all points on the stack , If the end point is the last node , Then put
stack
Add the contents of to the list- In the process of returning
stack
Out of the stack
class Solution {
List<Integer> stack;
List<List<Integer>> ret;
public void dfs(int n, int[][]graph, int now){
if (now == n - 1){
ret.add(new ArrayList<>(stack)); // It can't be passed in directly stack, Only one object can be copied deeply
return;
}
for(int i = 0; i < graph[now].length; i++){
stack.add(graph[now][i]);
dfs(n, graph, graph[now][i]);
stack.remove(stack.size() - 1);
}
}
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
int n = graph.length; // Get the number of all points
stack = new ArrayList<>();
ret = new ArrayList<>();
stack.add(0);
dfs(n, graph, 0);
return ret;
}
}
/* * dfs( Number to find , Adjacency matrix , The current number ) */
3. 851. Noise and wealth
4. 959. Area by slash
边栏推荐
- Leetcode problem solving 2.1.1
- Appears when importing MySQL
- 【深度学习】语义分割:论文阅读(NeurIPS 2021)MaskFormer: per-pixel classification is not all you need
- QML control type: menu
- Global and Chinese market of electronic tubes 2022-2028: Research Report on technology, participants, trends, market size and share
- Global and Chinese market of airport kiosks 2022-2028: Research Report on technology, participants, trends, market size and share
- [Yu Yue education] reference materials of power electronics technology of Jiangxi University of science and technology
- Global and Chinese market of cup masks 2022-2028: Research Report on technology, participants, trends, market size and share
- CSP salary calculation
- [shell script] use menu commands to build scripts for creating folders in the cluster
猜你喜欢
随机推荐
解决小文件处过多
In order to get an offer, "I believe that hard work will make great achievements
Global and Chinese markets for modular storage area network (SAN) solutions 2022-2028: Research Report on technology, participants, trends, market size and share
What are the models of data modeling
O & M, let go of monitoring - let go of yourself
Kratos ares microservice framework (II)
[shell script] use menu commands to build scripts for creating folders in the cluster
Leetcode:608 树节点
Publish and subscribe to redis
有软件负载均衡,也有硬件负载均衡,选择哪个?
Kratos战神微服务框架(二)
Improved deep embedded clustering with local structure preservation (Idec)
Reids之缓存预热、雪崩、穿透
CSP salary calculation
五月刷题26——并查集
MapReduce工作机制
IDS' deletion policy
Design and implementation of online snack sales system based on b/s (attached: source code paper SQL file)
英雄联盟轮播图手动轮播
Vs All comments and uncomments