当前位置:网站首页>729. My schedule I / offer II 106 Bipartite graph
729. My schedule I / offer II 106 Bipartite graph
2022-07-06 02:14:00 【PI Qiliang】
729. My schedule I【 Medium question 】【 A daily topic 】
Ideas :【TreeMap】
Study TreeMap Use , Two ways .
See code Notes for details .
Code 1:
class MyCalendar {
TreeMap<Integer,Integer> treeMap;
public MyCalendar() {
treeMap = new TreeMap<>();
}
public boolean book(int start, int end) {
// The first is greater than or equal to start The range of
Map.Entry<Integer,Integer> ceilingEntry = treeMap.ceilingEntry(start);
// The first is less than or equal to start The range of
Map.Entry<Integer,Integer> floorEntry = treeMap.floorEntry(start);
// If floorEntry by null perhaps floorEntry Corresponding value ( Indicates the right end of the interval ) Less than or equal to start
// And meanwhile ceilingEntry by null perhaps ceilingEntry The corresponding key ( Represents the left end point of the interval ) Greater than or equal to end
// Then explain the current schedule range It can be inserted into treeMap Indicates that in the calendar , And will not result in duplicate bookings
if((floorEntry == null || floorEntry.getValue() <= start)
&& (ceilingEntry == null || end <= ceilingEntry.getKey())){
treeMap.put(start,end);
return true;
}
// If the above conditions are not met Then you can't add daily to your calendar , return false
return false;
}
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */
Code 2:
class MyCalendar {
TreeMap<Integer,Integer> map;
public MyCalendar() {
// initialization TreeMap,map in key Is the left end point of the interval ( contain ),value Is the right end of the interval ( It doesn't contain )
map = new TreeMap<>();
// stay map Add the big boundary of the whole interval
// Leftmost -1
map.put(-1,-1);
// On the far right is 1000000001
map.put(1000000001,1000000001);
}
public boolean book(int start, int end) {
// seek map in To insert the left endpoint of the interval start Left and right values , Set as left and right,left Representation ratio start The left end of the small interval right Representation ratio start The left end of the large interval
Integer left = map.floorKey(start),right = map.ceilingKey(start);
// If right Less than end Representation ratio start The ratio of the left end point of the large interval end Small Now insert [start,end) It will definitely cause interval overlap , return false
// If left The value ratio of the right end point of the corresponding interval start Big It will also cause interval overlap return false
if (right < end || map.get(left) > start){
return false;
}
// Exclude the above Intervals do not overlap , Then the schedule is successfully inserted
map.put(start,end);
return true;
}
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */
The finger of the sword Offer II 106. Bipartite graph 【 Medium question 】
Ideas :【DFS】
It's important to understand the topic , The definition of bipartite graph in the title is :
Divide all nodes of a graph into two independent subsets A and B, And make one of the two nodes of each edge in the graph come from the set A, One comes from the set B.
Then we can use the concept of coloring to try bisection of undirected graphs , Initially, all nodes in the graph are colorless , Starting from any node , Traverse all the nodes in the graph , If the node is not stained , Then dye it red ,
Then traverse all adjacent points of this node , If the adjacency point is not stained , Dye it green , And search all the adjacency points of this adjacency point , If it is not dyed, it will be dyed red ; If the adjacency point has been dyed , And the color is the same as the current node , Then the dyeing fails , The function returns false.
See the notes for the detailed process . Ideas and codes refer to the official solutions .
Code :
class Solution {
// Definition color Array , Used to mark the color of each node in the undirected graph
static int[] color;
// Define flag bit valid, Used to indicate whether the current status is valid
static boolean valid;
// Define static variables to mark node colors
static final int UNCOLORED = 0;
static final int RED = 1;
static final int GREEN = 2;
public boolean isBipartite(int[][] graph) {
int n = graph.length;
// initialization valid by true, Indicates that the starting state is valid
valid = true;
// Initialize the color array color
color = new int[n];
//color The initial value of the assignment is colourless UNCOLORED
Arrays.fill(color,UNCOLORED);
// Traverse every valid node in the undirected graph
for (int i = 0; i < n && valid; i++) {
// If the current node is not colored , Call dfs The function colors it red
if (color[i] == UNCOLORED){
dfs(i,RED,graph);
}
}
// Returns the effective state of the node after the undirected graph traversal
return valid;
}
public void dfs(int node,int c,int[][] graph){
// Set the current node node Dye to the specified color c
color[node] = c;
// Record the target color of the adjacent node of the current node cNei, If c In red , be cNei It's green , If c It's green , be cNei In red
int cNei = c == RED ? GREEN : RED;
// Traverse each adjacent node of the current node neighbor
for (int neighbor : graph[node]) {
// If the adjacent contact is colorless , Then dye the adjacent contact , That is, the node is red , Then dye the adjacent nodes green , Node is green , Then dye the adjacent dots red
if (color[neighbor] == UNCOLORED){
// Dye the adjacent dots as cNei Color
dfs(neighbor,cNei,graph);
// If after dyeing , Find out valid by false, Then the coloring function directly returns , Don't continue to dye the next adjacent point
if (!valid){
return;
}
}else if (color[neighbor] != cNei){
// If the color of the adjacent contact has been dyed , And its color is not the color to be dyed ( It is the same color as the current node )
// It will be valid Marked as false, Indicates dyeing failure . The coloring function returns
valid = false;
return;
}
}
}
}
边栏推荐
- 2 power view
- 【社区人物志】专访马龙伟:轮子不好用,那就自己造!
- Campus second-hand transaction based on wechat applet
- Using SA token to solve websocket handshake authentication
- Redis-列表
- How to improve the level of pinduoduo store? Dianyingtong came to tell you
- 使用npm发布自己开发的工具包笔记
- Unreal browser plug-in
- Ali test open-ended questions
- Social networking website for college students based on computer graduation design PHP
猜你喜欢
【社区人物志】专访马龙伟:轮子不好用,那就自己造!
PHP campus financial management system for computer graduation design
Kubernetes stateless application expansion and contraction capacity
[depth first search] Ji Suan Ke: Betsy's trip
Open source | Ctrip ticket BDD UI testing framework flybirds
NiO related knowledge (II)
Computer graduation design PHP part-time recruitment management system for College Students
同一个 SqlSession 中执行两条一模一样的SQL语句查询得到的 total 数量不一样
NumPy 数组索引 切片
[solution] add multiple directories in different parts of the same word document
随机推荐
Selenium waiting mode
[coppeliasim] 6-DOF path planning
RDD conversion operator of spark
Reasonable and sensible
同一个 SqlSession 中执行两条一模一样的SQL语句查询得到的 total 数量不一样
Compact lidar global and Chinese markets 2022-2028: technology, participants, trends, market size and share Research Report
Virtual machine network, networking settings, interconnection with host computer, network configuration
在线怎么生成富文本
[solution] every time idea starts, it will build project
NLP fourth paradigm: overview of prompt [pre train, prompt, predict] [Liu Pengfei]
Use image components to slide through photo albums and mobile phone photo album pages
[width first search] Ji Suan Ke: Suan tou Jun goes home (BFS with conditions)
I like Takeshi Kitano's words very much: although it's hard, I will still choose that kind of hot life
Know MySQL database
Publish your own toolkit notes using NPM
[ssrf-01] principle and utilization examples of server-side Request Forgery vulnerability
Using SA token to solve websocket handshake authentication
Accelerating spark data access with alluxio in kubernetes
Redis daemon cannot stop the solution
Text editing VIM operation, file upload