当前位置: 首页 > news >正文

刷题笔记26——图论二分图判定

世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言

  • visited数组是在如果有环的情况下,防止在图中一直绕圈设置的,类似于剪枝操作,走过了就没必要再走一遍

  • path是在探索过程中,记录此次的遍历路径,从而判断是否有环的

  • 如果是判断的话,visited是无法判断的,path是可以判断的

  • 二分图的题背会板子即可

785. 判断二分图:如果没访问就染色,访问过就判断染色是否匹配

class Solution {boolean[] visited;int[] color;boolean isB = true;public boolean isBipartite(int[][] graph) {int sz = graph.length;color = new int[sz];visited =new boolean[sz];for(int i=0;i<sz;i++){traverse(graph,i,1);}return isB;}void traverse(int[][] graph, int n, int col){if(visited[n]) return;visited[n] = true;color[n] = col;for(int node:graph[n]){if(visited[node]){if(color[node]!=(1-col)){isB = false;}}else{traverse(graph,node,1-col);}}}
}

886. 可能的二分法:有边的话就需要将两个节点分开,用二分图的思路

class Solution {// 遍历构图二分图boolean[] visited;int[] color;boolean isBi = true;public boolean possibleBipartition(int n, int[][] dislikes) {// 构造的是无向图visited = new boolean[n];color = new int[n];List<Integer>[] graph = generateGraph(n,dislikes);for(int i=0;i<n;i++){traverse(graph,i,1);}return isBi;}void traverse(List<Integer>[] graph,int n,int number){if(visited[n]) return;visited[n] = true;color[n] = number;for(int node:graph[n]){if(visited[node]){if(color[node]!=1-number){isBi = false;}}else{traverse(graph,node,1-number);}}}List<Integer>[] generateGraph(int n, int[][] dislikes){List<Integer>[] graph = new LinkedList[n];for(int i=0;i<n;i++){graph[i] = new LinkedList();}for(int i=0;i<dislikes.length;i++){graph[dislikes[i][0]-1].add(dislikes[i][1]-1);graph[dislikes[i][1]-1].add(dislikes[i][0]-1);}return graph;}
}

相关文章:

刷题笔记26——图论二分图判定

世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言 visited数组是在如果有环的情况下&#xff0c;防止在图中一直绕圈设置的&#xff0c;类似于剪枝操作&#xff0c;走…...

网站整站优化-网站整站优化工具

您是否曾为您的网站在搜索引擎中的排名而感到焦虑&#xff1f;是否苦苦思考如何提高流量、吸引更多用户&#xff1f; 什么是整站优化。简而言之&#xff0c;它是一项用于提升网站在搜索引擎中排名的策略和技巧。通过对网站的内容、结构、速度等方面进行优化&#xff0c;可以使…...

冲刺十五届蓝桥杯P0001阶乘求和

文章目录 题目描述思路分析代码解析 题目描述 思路分析 阶乘是蓝桥杯中常考的知识。 首先我们需要知道 int 和long的最大值是多少。 我们可以知道19的阶乘就已经超过了long的最大值&#xff0c;所以让我们直接计算202320232023&#xff01;的阶乘是不现实的。 所以我们需要…...

c++ 学习 之 运算符重载

前言 运算符重载的概念&#xff1a; 对已有的运算符重新进行定义&#xff0c;赋予其另外一种功能&#xff0c;以适应不同的数据类型 加号运算符重载 作用&#xff1a;定义两个自定义的数据类型相加的运算 正常情况下&#xff0c;如果想要实现类中两个int 类型的相加&#xf…...

各种数据库表名长度限制整理

因为工作原因&#xff0c;需要整理下系统支持的数据库的表名长度限制&#xff0c;现发出来&#xff0c;以节省大家的整理时间&#xff0c;如有不对的敬请斧正&#xff01; 数据库类型长度ORACLE 30GreenPlum40KINGBASEES63PostgreSql63Gbase63瀚高63OSCAR64MYSQL 64HBASE64Mar…...

Go 里的超时控制

前言 日常开发中我们大概率会遇到超时控制的场景&#xff0c;比如一个批量耗时任务、网络请求等&#xff1b;一个良好的超时控制可以有效的避免一些问题&#xff08;比如 goroutine 泄露、资源不释放等&#xff09;。 Timer 在 go 中实现超时控制的方法非常简单&#xff0c;…...

一文彻底搞清楚Spark Schema

前言 Spark Schema定义了DataFrame的结构,可以通过对DataFrame对象调用printSchema()方法来获得该结构。Spark SQL提供了StructType和StructField类以编程方式指定架构。 默认情况下,Spark从数据中推断schema,但有时我们可能需要定义自己的schema(列名和数据类型),尤其…...

Nginx多出口IP解决代理端口数量限制,CentOS安装Nginx并开启https2.0

Nginx多出口IP解决代理端口数量限制,CentOS安装Nginx并开启https2.0。 配置文件如下: http {...upstream test {server www.test.com;}server {listen 80 default_server;server_name _;location / {proxy_pass http://test;proxy_bind $split_ip...

SpringBoot项目(百度AI整合)——如何在Springboot中使用语音文件识别 ffmpeg的安装和使用

前言 前言&#xff1a;在实际使用中&#xff0c;经常要参考官方的案例&#xff0c;但有时候因为工具的不一样&#xff0c;比如idea 和 eclipse&#xff0c;普通项目和spring项目等的差别&#xff1b;还有时候因为水平有限&#xff0c;难以在散布于官方的各个文档读懂&#xff…...

探索古彝文AI识别技术:助力中国传统文化的传承与发扬

目录 ⭐️ 写在前面 ⭐️ 一、什么是古彝文 1.1 古彝文介绍 1.2 古彝文与其他古文字示例 1.3 古彝文的重要性 ⭐️二、AI识别技术的挑战与前景 2.1 挑战 2.2 前景 ⭐️三、合合信息AI识别技术 3.1 智能文字识别技术&#x1f44d;&#x1f44d; 3.2 古文识别应用 ⭐…...

mysql面试题2:说一说MySQL的架构设计?一条 MySQL 语句执行的步骤?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:说一说MySQL的架构设计? MySQL的架构设计主要包括以下几个组件: 连接器(Connector):负责与客户端建立连接,并进行身份验证和授权。 查询缓存…...

UPnP协议和SSDP协议

1、两种协议 UPnP协议&#xff1a;Universal Plug and Play&#xff0c;广义的即插即用。UPnP协议的目的&#xff1a;当有新设备连接上网络&#xff0c;网络上的其他设备能够马上知道有新设备加入&#xff0c;然后这些设备能互相宣传和发现彼此&#xff0c;以便能使用和控制彼…...

notepad++配置python2环境

&#xff08;1&#xff09;python2版本下载&#xff1a;Index of /ftp/python/2.7.8/https://www.python.org/ftp/python/2.7.8/ &#xff08;2&#xff09; 配置notepad环境 1.打开Notepad&#xff0c;点击“插件”-“插件管理器”&#xff0c;在“可用”选项卡中&#xff0c…...

在ThinkAdmin中弹出层关闭后回调

在thinkadmin里面&#xff0c;窗口的的一些方法全部都集成在admin.js里面&#xff0c;在之前的文章中也有出现过类似的问题&#xff0c;就是对动态加载的数据进行统计&#xff0c;那时候写也是想记录下&#xff0c;现在自己都不记得是哪个站用的了&#xff0c;所以在这里也把这…...

vue3 和vue2 的比较

文章目录 生命周期多根节点Composition API组合式APIOptions API与composition API对比优化逻辑组织优化逻辑复用 异步组件(Suspense)Suspense组件 响应式原理性能体积优化编译优化diff算法优化静态提升数据劫持&#xff08;响应式系统&#xff09;优化 生命周期 vue3在组合AP…...

算法通过村第八关-树(深度优先)黄金笔记|寻找祖先

文章目录 前言最近公共祖先问题总结 前言 提示&#xff1a;生活就是一场有很多规则&#xff0c;却没有裁判的比赛。 --约瑟夫布罗茨基《悲伤与理智》 最近公共祖先问题 参考题目地址&#xff1a;236. 二叉树的最近公共祖先 - 力扣&#xff08;LeetCode&#xff09; 如果将搜索…...

postgresql|数据库|数据库测试工具pgbench之使用

前言&#xff1a; 数据库是项目中的重要组件&#xff0c;也是一个基础的重要组件&#xff0c;其地位说是第一我想应该是没有什么太多问题的。 那么&#xff0c;数据库的设计这些方面是不用多说的&#xff0c;关键的第一步&#xff0c;主要是涉及数据库的部署方式&#xff0c;…...

代码随想录Day51 | 309.最佳买卖股票时机含冷冻期

309. 买卖股票的最佳时机含冷冻期 class Solution { public:int maxProfit(vector<int>& prices) {int n prices.size();if (n 0) return 0;vector<vector<int>> dp(n, vector<int>(4, 0));dp[0][0] - prices[0]; // 持股票for (int i 1; i &l…...

libopenssl 实现私钥加密公钥解密

在需要验证可信来源时&#xff0c;需要用到签名验签。因此&#xff0c;需要使用私钥加密&#xff0c;公钥解密&#xff0c;取得被加密的信息。这就会使用到私钥加密&#xff0c;公钥解密的场景了。 参考&#xff1a; https://github.com/openssl/openssl/issues/20493 https:/…...

代码随想录 Day - 51|#309 最佳买卖股票时机含冷冻期|#714 买卖股票的最佳时机含手续费

清单 ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费 LeetCode #309 最佳买卖股票时机含冷冻期 1. 题目 给定一个整数数组&#xff0c;其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下&#xff0c;你可…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...