搜索到
354
篇与
的结果
-
麒麟软件面试题整理 1.“equal”、“==” 和 “hashCode” 的区别和使用场景三者都是用于判断对象之间是否相等的，判断的方式不一样。==对于基本类型，==是比较其值是不是相等，对于引用类型，==比较两个对象是否相同。equals方法equals 方法是用于比较两个独立对象的内容是否相同：如果一个类没有重写 equals(Object obj)方法，则等价于通过 == 比较两个对象，即比较的是对象在内存中的空间地址是否相等。如果重写了equals(Object ibj)方法，则根据重写的方法内容去比较相等，返回 true 则相等，false 则不相等。hashcode()hashCode 是用来在散列存储结构中确定对象的存储地址的。hashCode 的存在主要用于查找的快捷性，如 Hashtable, HashMap 等，如果两个对象相同，就是适用于 euqals(java.lang.Object) 方法，那么这两个对象的 hashCode一定相同。如果对象的euqals 方法被重写，那么对象的 hashCode 也尽量重写，并且产生 hashCode 使用的对象，一定要和 equals 方法中使用的一致。两个对象的 hashCode 相同，并不一定表示这两个对象就相同，也就是不一定适用于equals() 方法，只能够说明这两个对象在散列存储结构中，如 Hashtable.,他们存在同一个篮子里。使用场景：equals 方法是用于比较两个独立对象的内容是否相同。hashCode方法存在的主要目的就是提高判断效率，如用来在散列存储结构中确定对象的存储地址的。因为 hashCode 并不是完全可靠，有时候不同的对象他们生成的 hashcode 也会一样（hash冲突），所以 hashCode只能说是大部分时候可靠，并不是绝对可靠，所以可以得出：equals 相等的两个对象他们的 hashCode 肯定相等，也就是用 equals 对比是绝对可靠的hashCode 相等的两个对象他们的 equals 不一定相等，也就是 hashCode 不是绝对可靠的。对于需要大量并且快速的对比的话如果都用 equals 去做显然效率太低，解决方式是，每当需要对比的时候，首先用 hashCode 去对比，如果 hashCode 不一样，则表示这两个对象肯定不相等（也就是不必再用 equals 去再对比了）,如果 hashCode 相同，此时再对比他们的 equals，如果 equals 也相同，则表示这两个对象是真的相同了2.DNS域名解析过程简略版浏览器缓存——》系统hosts文件——》本地DNS解析器缓存——》本地域名服务器（本地配置区域资源、本地域名服务器缓存)——》根域名服务器——》主域名服务器——》下一级域名域名服务器 客户端——》本地域名服务器（递归查询) 本地域名服务器—》DNS服务器的交互查询是迭代查询详细解释当我们在浏览器地址栏中输入某个Web服务器的域名时。用户主机首先用户主机会首先在自己的DNS高速缓存中查找该域名所应的IP地址。如果没有找到，则会向网络中的某台DNS服务器查询，DNS服务器中有域名和IP地映射关系的数据库。当DNS服务器收到DNS查询报文后，在其数据库中查询，之后将查询结果发送给用户主机。现在，用户主机中的浏览器可以通过Web服务器的IP地址对其进行访问了。如果上级的DNS没有该域名的DNS缓存，则会继续向更上级查询，包含两种查询方式，分别是递归查询和迭代查询。递归查询如果主机所询问的本地域名服务器不知道被查询域名的 IP 地址，那么本地域名服务器就以 DNS 客户端的身份，向其他根域名服务器继续发出查询请求报文，即替主机继续查询，而不是让主机自己进行下一步查询。我们以一个例子来了解DNS递归查询的工作原理，假设图中的主机 (IP地址为m.xyz.com) 想知道域名y.abc.com的IP地址。1、主机首先向其本地域名服务器进行递归查询。2、本地域名服务器收到递归查询的委托后，也采用递归查询的方式向某个根域名服务器查询。3、根域名服务器收到递归查询的委托后，也采用递归查询的方式向某个顶级域名服务器查询。4、顶级域名服务器收到递归查询的委托后，也采用递归查询的方式向某个权限域名服务器查询。过程如图所示：迭代查询当根域名服务器收到本地域名服务器发出的迭代查询请求报文时，要么给出所要查询的IP 地址，要么告诉本地服务器下一步应该找哪个域名服务器进行查询，然后让本地服务器进行后续的查询。迭代查询过程如下：1、主机首先向其本地域名服务器进行递归查询。2、本地域名服务器采用迭代查询，它先向某个根域名服务器查询。3、根域名服务器告诉本地域名服务器，下一次应查询的顶级域名服务器的IP地址。4、本地域名服务器向顶级域名服务器进行迭代查询。5、顶级域名服务器告诉本地域名服务器，下一次应查询的权限域名服务器的IP地址。6、本地域名服务器向权限域名服务器进行迭代查询。7、权限域名服务器告诉本地域名服务器所查询的域名的IP地址。8、本地域名服务器最后把查询的结果告诉主机。过程如图所示：由于递归查询对于被查询的域名服务器负担太大，通常采用以下模式：从请求主机到本地域名服务器的查询是递归查询，而其余的查询是迭代查询。3.synchronized关键字及加到方法和对象上的区别Synchronized是Java提供的同步关键字，在多线程场景下，对共享资源代码段进行读写操作（必须包含写操作，光读不会有线程安全问题，因为读操作天然具备线程安全特性），可能会出现线程安全问题，我们可以使用Synchronized锁定共享资源代码段，达到互斥（mutualexclusion）效果，保证线程安全。synchronized 既可以加在一段代码上，也可以加在方法上。加到对象上(加到代码块上)使用synchronized(object) { 代码块.... } 能对代码块进行加锁，不允许其他线程访问，其的作用原理是：在object内有一个变量，当有线程进入时，判断是否为0，如果为0，表示可进入执行该段代码，同时将该变量设置为1，这时其他线程就不能进入；当执行完这段代码时，再将变量设置为0。加到方法上synchronized加在方法上本质上还是等价于加在对象上的。如果synchronized加在一个类的普通方法上，那么相当于synchronized（this）。如果synchronized加载一个类的静态方法上，那么相当于synchronized（Class.this）。4.HTTP/HTTPS区别HTTP协议传输的数据都是未加密的，也就是明文的，因此使用HTTP协议传输隐私信息非常不安全，为了保证这些隐私数据能加密传输，于是网景公司设计了SSL（Secure Sockets Layer）协议用于对HTTP协议传输的数据进行加密，从而就诞生了HTTPS。为了数据传输的安全，HTTPS在HTTP的基础上加入了SSL/TLS协议，SSL/TLS依靠证书来验证服务器的身份，并为浏览器和服务器之间的通信加密。HTTPS和HTTP的区别主要如下：1、https协议需要到ca申请证书，一般免费证书较少，因而需要一定费用。2、http的信息是明文传输，https则是具有安全性的ssl加密传输协议。3、http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。4、http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。5.MySQL删除数据的方式都有哪些？/delete/drop/truncate区别、谁的速度更快以及原因可以这么理解，一本书，delete是把目录撕了，truncate是把书的内容撕下来烧了，drop是把书烧了常用的三种删除方式：通过 delete、truncate、drop 关键字进行删除；这三种都可以用来删除数据，但场景不同。执行速度drop > truncate >> DELETE区别详解delete1、DELETE属于数据库DML操作语言，只删除数据不删除表的结构，会走事务，执行时会触发trigger；2、在 InnoDB 中，DELETE其实并不会真的把数据删除，mysql 实际上只是给删除的数据打了个标记为已删除，因此 delete 删除表中的数据时，表文件在磁盘上所占空间不会变小，存储空间不会被释放，只是把删除的数据行设置为不可见。虽然未释放磁盘空间，但是下次插入数据的时候，仍然可以重用这部分空间（重用 → 覆盖）。3、DELETE执行时，会先将所删除数据缓存到rollback segement中，事务commit之后生效;4、delete from table_name删除表的全部数据,对于MyISAM 会立刻释放磁盘空间，InnoDB 不会释放磁盘空间;5、对于delete from table_name where xxx 带条件的删除, 不管是InnoDB还是MyISAM都不会释放磁盘空间;6、delete操作以后使用optimize table table_name会立刻释放磁盘空间。不管是InnoDB还是MyISAM 。所以要想达到释放磁盘空间的目的，delete以后执行optimize table 操作。7、delete 操作是一行一行执行删除的，并且同时将该行的的删除操作日志记录在redo和undo表空间中以便进行回滚（rollback）和重做操作，生成的大量日志也会占用磁盘空间。truncate1、truncate：属于数据库DDL定义语言，不走事务，原数据不放到 rollback segment 中，操作不触发 trigger。执行后立即生效，无法找回 执行后立即生效，无法找回 执行后立即生效，无法找回2、truncate table table_name立刻释放磁盘空间 ，不管是 InnoDB和MyISAM。truncate table其实有点类似于drop table 然后creat,只不过这个create table 的过程做了优化，比如表结构文件之前已经有了等等。所以速度上应该是接近drop table的速度;3、truncate能够快速清空一个表。并且重置auto_increment的值。小心使用 truncate，尤其没有备份的时候，如果误删除线上的表，记得及时联系中国民航，订票电话：400-806-9553Drop1、drop：属于数据库DDL定义语言，同Truncate；2、drop table table_name 立刻释放磁盘空间 ，不管是 InnoDB 和 MyISAM;drop 语句将删除表的结构被依赖的约束(constrain)、触发器(trigger)、索引(index); 依赖于该表的存储过程/函数将保留,但是变为 invalid 状态。小心使用 drop ，要删表跑路的兄弟，请在订票成功后在执行操作！订票电话：400-806-95536.Linux根目录下有哪些基本目录/bin：里边包含了一般程序工具，用户、管理员、系统都可以调用。比如常用的ls、cp、cat、mv等等。 /sbin：系统和系统管理员用到的程序工具。 /lib、/lib64：库文件，包含了所有系统和用户需要的程序文件，64表示64位，但实际上除特殊的库，大部分还是链接到了lib目录下。 /home：一般用户目录，一般一个用户对应一个目录，保存用户的数据。 /root：root用户的家目录。 /etc：包含了大部分重要的系统配置文件，这里文件的作用类似windows中的控制面板。 /boot：系统启动文件和内核，在有些发行版中还包括grub，grub是一种通用的启动引导程序。 /dev：系统设备文件目录，除cpu外的所有的硬件设备都会抽象成特殊的文件放在这里，虚拟设备也放在这里。 /media：磁盘设备自动挂载的位置。按照用户分类，每一个用户目录下有其磁盘目录。 /cdrom：专门用来挂载光盘的目录，有些发行版将该目录放在media或mnt目录下。 /mnt：标准挂载点，可以挂载外设磁盘。 /opt：一般存放第三方软件。 /tmp：系统使用的临时空间，重启后会清空。 /var：包含一些用户可变的或临时的文件，比如log文件、邮件队列、网络下载的临时文件等等。 /sys：与proc类似的虚拟文件系统，都是内核提供给用户的接口，可读可写。 /proc：包含系统资源信息的虚拟文件系统，提供了一个接触内核数据的接口，大部分是只读的，有些允许改变。系统运行时才有文件。7.Java类加载过程Java类加载过程主要可以分为三个步骤：加载、连接、初始化。加载：是Java将字节码数据从不同的数据源读取到JVM中，映射为JVM认可的数据结构。连接：是把原始的类定义信息平滑地转入JVM运行的过程中。这一阶段可以细分为验证、准备、解析三步。验证：1.格式检查 --> 魔数验证、版本检查、长度检查2.语义检查 --> 是否继承final、是否有父类、是否实现抽象方法3.直接验证 --> 跳转指令是否只想正确的位置，操作数类型是否合理4.符号引用验证 --> 符号引用的直接引用是否存在准备：为类中的所有静态变量分配内存空间，并为其设置一个初始值（由于还没有产生对象，实例变量不在此操作范围内）被final修饰的静态变量， 会直接赋予原值；类字段的字段属性表中存在ConstantValue属性，则在准备阶段，其值就是ConstantValue的值解析：将常量池中的符号引用转为直接引用（得到类或者字段、方法在内存中的指针或者偏移量，以便直接调用该方法），这个可以在初始化之后 再执行。可以认为是一些静态绑定的会被解析，动态绑定则只会在运行是进行解析；静态绑定包括一些final方法(不可以重写),static方法(只 会属于当前类)，构造器(不会被重写)初始化：是执行类初始化的代码逻辑，包括静态字段赋值的动作，以及执行类定义中的静态初始化块内的逻辑。8.堆和栈的区别堆和栈的区别主要有五大点，分别是：1、申请方式的不同。栈由系统自动分配，而堆是人为申请开辟;2、申请大小的不同。栈获得的空间较小，而堆获得的空间较大;3、申请效率的不同。栈由系统自动分配，速度较快，而堆一般速度比较慢;4、存储内容的不同。栈内存存储的是局部变量而堆内存存储的是实体； 栈在函数调用时，函数调用语句的下一条可执行语句的地址第一个进栈，然后函数的各个参数进栈，其中静态变量是不入栈的。而堆一般是在头部用一个字节存放堆的大小，堆中的具体内容是人为安排;5、底层不同。栈是连续的空间，而堆是不连续的空间。6、栈内存存放的变量生命周期一旦结束就会被释放，而堆内存存放的实体会被垃圾回收机制不定时的回收。9.生产者消费者模型概念生产者消费者模式就是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯，而通过阻塞队列来进行通讯，所以生产者生产完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据，而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。这个阻塞队列就是用来给生产者和消费者解耦的。321原则三种角色：生产者、消费者、仓库两种关系：生产者与生产者之间是互斥关系，消费者与消费者之间是互斥关系，生产者与消费者之间是同步与互斥关系。一个交易场所：仓库优点解耦–生产者。消费者之间不直接通信，降低了耦合度。支持并发支持忙闲不均PV原语描述s1初始值为缓冲区大小、s2初始值为0 生产者: 生产一个产品; P(s1); 送产品到缓冲区; V(s2); 消费者: P(s2); 从缓冲区取出产品; V(s1); 消费水平;代码实现synchronized + wait() + notify() 方式package ProducerAndConsumer; import java.util.ArrayList; import java.util.List; class Produce extends Thread { List<Object> productBuffer; // 产品缓冲区 int bufferCapacity; // 缓冲区容量 public Produce(int bufferCapacity,List<Object> productBuffer){ this.productBuffer = productBuffer; this.bufferCapacity = bufferCapacity; } @Override public void run() { while (true){ // 生产行为 synchronized (productBuffer){ // 如果某一个生产者能执行进来，说明此线程具有productBuffer对象的控制权,其它线程（生产者&消费者）都必须等待 if(productBuffer.size()==bufferCapacity){ // 缓冲区满了 try { productBuffer.wait(1); // 释放控制权并等待 } catch (InterruptedException e) { e.printStackTrace(); } }else { // 缓冲区没满可以继续生产 productBuffer.add(new Object()); System.out.println("生产者生产了1件物品，当前缓冲区里还有" + productBuffer.size() + "件物品"); productBuffer.notifyAll(); // 唤醒等待队列中所有线程 } } // 模拟生产缓冲时间 try { Thread.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } } } } class Consumer extends Thread{ List<Object> productBuffer; // 产品缓冲区 int bufferCapacity; // 缓冲区容量 public Consumer(int bufferCapacity,List<Object> productBuffer){ this.productBuffer = productBuffer; this.bufferCapacity = bufferCapacity; } @Override public void run(){ while (true){//消费行为 synchronized (productBuffer){ if(productBuffer.isEmpty()){ //产品缓冲区为空,不能消费，只能等待 try { productBuffer.wait(1); } catch (InterruptedException e) { e.printStackTrace(); } }else { // 缓冲区没空可以继续消费 productBuffer.remove(0); System.out.println("消费者消费了1个物品，当前缓冲区里还有" + productBuffer.size() + "件物品"); productBuffer.notifyAll(); } } // 模拟消费缓冲时间 try { Thread.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } } } } public class ProducerAndConsumer { public static void main(String[] args) { List<Object> productBuffer = new ArrayList<>(); // 产品缓冲区 int bufferCapacity = 3; // 缓冲区容量 for (int i = 0; i < 3; i++) { new Produce(bufferCapacity,productBuffer).start(); } for (int i = 0; i < 3; i++) { new Consumer(bufferCapacity,productBuffer).start(); } } }10.servlet是线程安全的吗Servlet不是线程安全的。当Tomcat接收到Client的HTTP请求时，Tomcat从线程池中取出一个线程，之后找到该请求对应的Servlet对象并进行初始化，之后调用service()方法。要注意的是每一个Servlet对象再Tomcat容器中只有一个实例对象，即是单例模式。如果多个HTTP请求请求的是同一个Servlet，那么着两个HTTP请求对应的线程将并发调用Servlet的service()方法。11.http请求头和响应头信息请求头信息Accept:浏览器能够处理的内容类型Accept-Charset:浏览器能够显示的字符集Accept-Encoding：浏览器能够处理的压缩编码Accept-Language：浏览器当前设置的语言Connection：浏览器与服务器之间连接的类型Cookie：当前页面设置的任何CookieHost：发出请求的页面所在的域Referer：发出请求的页面的URLUser-Agent：浏览器的用户代理字符串响应头信息Date：表示消息发送的时间，时间的描述格式由rfc822定义server:服务器名字。Connection：浏览器与服务器之间连接的类型content-type:表示后面的文档属于什么MIME类型Cache-Control：控制HTTP缓存参考资料“equal”、“==” 和 “hashCode” 的区别和使用场景？Java 基础 | hashCode 和 equals 在实体类的应用场景 Java的synchronized加在方法上或者对象上有什么区别？13张图，深入理解Synchronized全网最全JAVA面试八股文，终于整理完了面试官灵魂一问：MySQL 的 delete、truncate、drop 有什么区别？Linux根目录下各个目录的介绍HTTP与HTTPS的区别多张图带你彻底搞懂DNS域名解析过程java 类加载过程（步骤）详解堆和栈的区别有哪些？PV操作-生产者/消费者关系Java 学习笔记 使用synchronized实现生产者消费者模式 经典面试题 -- 手写生产者消费者模式Java面试题：Servlet是线程安全的吗？http的请求头都有那些信息 -
生产者消费者模型原理及java实现 1.概念生产者消费者模式就是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯，而通过阻塞队列来进行通讯，所以生产者生产完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据，而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。这个阻塞队列就是用来给生产者和消费者解耦的。2.321原则三种角色：生产者、消费者、仓库两种关系：生产者与生产者之间是互斥关系，消费者与消费者之间是互斥关系，生产者与消费者之间是同步与互斥关系。一个交易场所：仓库3.优点解耦–生产者。消费者之间不直接通信，降低了耦合度。支持并发支持忙闲不均4.PV原语描述s1初始值为缓冲区大小、s2初始值为0 生产者: 生产一个产品; P(s1); 送产品到缓冲区; V(s2); 消费者: P(s2); 从缓冲区取出产品; V(s2); 消费水平;5.代码实现5.1 synchronized + wait() + notify() 方式package ProducerAndConsumer; import java.util.ArrayList; import java.util.List; class Produce extends Thread { List<Object> productBuffer; // 产品缓冲区 int bufferCapacity; // 缓冲区容量 public Produce(int bufferCapacity,List<Object> productBuffer){ this.productBuffer = productBuffer; this.bufferCapacity = bufferCapacity; } @Override public void run() { while (true){ // 生产行为 synchronized (productBuffer){ // 如果某一个生产者能执行进来，说明此线程具有productBuffer对象的控制权,其它线程（生产者&消费者）都必须等待 if(productBuffer.size()==bufferCapacity){ // 缓冲区满了 try { productBuffer.wait(1); // 释放控制权并等待 } catch (InterruptedException e) { e.printStackTrace(); } }else { // 缓冲区没满可以继续生产 productBuffer.add(new Object()); System.out.println("生产者生产了1件物品，当前缓冲区里还有" + productBuffer.size() + "件物品"); productBuffer.notifyAll(); // 唤醒等待队列中所有线程 } } // 模拟生产缓冲时间 try { Thread.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } } } } class Consumer extends Thread{ List<Object> productBuffer; // 产品缓冲区 int bufferCapacity; // 缓冲区容量 public Consumer(int bufferCapacity,List<Object> productBuffer){ this.productBuffer = productBuffer; this.bufferCapacity = bufferCapacity; } @Override public void run(){ while (true){//消费行为 synchronized (productBuffer){ if(productBuffer.isEmpty()){ //产品缓冲区为空,不能消费，只能等待 try { productBuffer.wait(1); } catch (InterruptedException e) { e.printStackTrace(); } }else { // 缓冲区没空可以继续消费 productBuffer.remove(0); System.out.println("消费者消费了1个物品，当前缓冲区里还有" + productBuffer.size() + "件物品"); productBuffer.notifyAll(); } } // 模拟消费缓冲时间 try { Thread.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } } } } public class ProducerAndConsumer { public static void main(String[] args) { List<Object> productBuffer = new ArrayList<>(); // 产品缓冲区 int bufferCapacity = 3; // 缓冲区容量 for (int i = 0; i < 3; i++) { new Produce(bufferCapacity,productBuffer).start(); } for (int i = 0; i < 3; i++) { new Consumer(bufferCapacity,productBuffer).start(); } } }5.2 可重入锁ReentrantLock （配合Condition）方式package ProducerAndConsumer; import java.util.ArrayList; import java.util.List; import java.util.concurrent.locks.Condition; import java.util.concurrent.locks.ReentrantLock; class Produce extends Thread { List<Object> productBuffer; // 产品缓冲区 int bufferCapacity; // 缓冲区容量 ReentrantLock lock; // 可重入锁 Condition producerCondition; // 生产者condition Condition consumerCondition; // 消费者condition public Produce(int bufferCapacity,List<Object> productBuffer,ReentrantLock lock,Condition producerCondition,Condition consumerCondition){ this.productBuffer = productBuffer; this.bufferCapacity = bufferCapacity; this.lock = lock; this.producerCondition = producerCondition; this.consumerCondition = consumerCondition; } @Override public void run() { while (true) { // 生产行为 lock.lock(); //加锁 if (productBuffer.size() == bufferCapacity) { // 缓冲区满了 try { producerCondition.await(); // 释放控制权并等待 } catch (InterruptedException e) { e.printStackTrace(); } } else { // 缓冲区没满可以继续生产 productBuffer.add(new Object()); System.out.println("生产者生产了1件物品，当前缓冲区里还有" + productBuffer.size() + "件物品"); consumerCondition.signal(); // 唤醒消费者线程 } lock.unlock(); //解锁 // 模拟生产缓冲时间 try { Thread.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } } } } class Consumer extends Thread{ List<Object> productBuffer; // 产品缓冲区 int bufferCapacity; // 缓冲区容量 ReentrantLock lock; // 可重入锁 Condition producerCondition; // 生产者condition Condition consumerCondition; // 消费者condition public Consumer(int bufferCapacity,List<Object> productBuffer,ReentrantLock lock,Condition producerCondition,Condition consumerCondition){ this.productBuffer = productBuffer; this.bufferCapacity = bufferCapacity; this.lock = lock; this.producerCondition = producerCondition; this.consumerCondition = consumerCondition; } @Override public void run(){ while (true){//消费行为 lock.lock();//加锁 if(productBuffer.isEmpty()){ //产品缓冲区为空,不能消费，只能等待 try { consumerCondition.await(); } catch (InterruptedException e) { e.printStackTrace(); } }else { // 缓冲区没空可以继续消费 productBuffer.remove(0); System.out.println("消费者消费了1个物品，当前缓冲区里还有" + productBuffer.size() + "件物品"); producerCondition.signal(); // 唤醒生产者线程继续生产 } lock.unlock(); //解锁 // 模拟消费缓冲时间 try { Thread.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } } } } public class ProducerAndConsumer { public static void main(String[] args) { List<Object> productBuffer = new ArrayList<>(); // 产品缓冲区 int bufferCapacity = 3; // 缓冲区容量 ReentrantLock lock = new ReentrantLock(); // 可重入锁 Condition producerCondition = lock.newCondition(); // 生产者condition Condition consumerCondition = lock.newCondition(); // 消费者condition for (int i = 0; i < 3; i++) { new Produce(bufferCapacity,productBuffer,lock,producerCondition,consumerCondition).start(); } for (int i = 0; i < 3; i++) { new Consumer(bufferCapacity,productBuffer,lock,producerCondition,consumerCondition).start(); } } }参考资料PV操作-生产者/消费者关系Java 学习笔记 使用synchronized实现生产者消费者模式 经典面试题 -- 手写生产者消费者模式
-
Python字符串处理：过滤字符串中的英文与符号，保留汉字 使用Python 的re模块，re模块提供了re.sub用于替换字符串中的匹配项。1 re.sub(pattern, repl, string, count=0) 参数说明：pattern：正则重的模式字符串repl：被拿来替换的字符串string：要被用于替换的原始字符串count：模式匹配后替换的最大次数，省略则默认为0，表示替换所有的匹配例如import re str = "hello,world!!%[545]你好234世界。。。" str = re.sub("[A-Za-z0-9\!\%\[\]\,\。]", "", str) print(str) 输出结果：你好世界
-
python读写csv文件 逗号分隔值（Comma-Separated Values，CSV，有时也称为字符分隔值，因为分隔字符也可以不是逗号），其文件以纯文本形式存储表格数据（数字和文本）1.读csv文件# coding:utf-8 import csv data_list = csv.reader(open('data.csv','r',encoding="utf8")) for data_item in data_list: print(data_item) 代码结果： ['测试1', '软件测试工程师'] ['测试2', '软件测试工程师'] ['测试3', '软件测试工程师'] ['测试4', '软件测试工程师'] ['测试5', '软件测试工程师']2.写入CSV文件# coding:utf-8 import csv data_list = [ ("测试1",'软件测试工程师'), ("测试2",'软件测试工程师'), ("测试3",'软件测试工程师'), ("测试4",'软件测试工程师'), ("测试5",'软件测试工程师'), ] f = open('data.csv','w',encoding="utf8") csv_writer = csv.writer(f) for data_item in data_list: csv_writer.writerow(data_item) f.close()参考资料python读写csv文件
-
mAP计算工具使用|快速计算mAP 计算mAP的工具：https://github.com/Cartucho/mAP1.使用步骤clone代码git clone https://github.com/Cartucho/mAPCreate the ground-truth files(将标签文件转为对应的格式,，工具参考2.1)format<class_name> <left> <top> <right> <bottom> [<difficult>]E.g. "image_1.txt"tvmonitor 2 10 173 238 book 439 157 556 241 book 437 246 518 351 difficult pottedplant 272 190 316 259Copy the ground-truth files into the folder input/ground-truth/Create the detection-results filesformat<class_name> <confidence> <left> <top> <right> <bottom>E.g. "image_1.txt"tvmonitor 0.471781 0 13 174 244 cup 0.414941 274 226 301 265 book 0.460851 429 219 528 247 chair 0.292345 0 199 88 436 book 0.269833 433 260 506 336Copy the detection-results files into the folder input/detection-results/Run the codepython main.py2.工具补充2.1 VOC_2_gt.py设置好xml_dir并执行即可得到对应的gt_txt文件import os import xmltodict import shutil from tqdm import tqdm # TODO：需要修改的内容 xml_dir = "/data/jupiter/project/dataset/帯広空港_per_frame/xml/" gt_dir = "./input/ground-truth/" shutil.rmtree(gt_dir) os.mkdir(gt_dir) """ 将voc xml 的数据转为对应的gt_str """ def voc_2_gt_str(xml_dict): objects = xml_dict["annotation"]["object"] obj_list = [] if isinstance(objects,list): # xml文件中包含多个object for obj in objects: obj_list.append(obj) else: # xml文件中包含1个object obj_list.append(objects) # 获取gt格式的数据信息 gt_str = "" for obj in obj_list: left = int(obj['bndbox']['xmin']) top = int(obj['bndbox']['ymin']) right = int(obj['bndbox']['xmax']) bottom = int(obj['bndbox']['ymax']) obj_name = obj['name'] gt_str += "%s %s %s %s %s\n" % (obj_name, left, top, right, bottom) return gt_str xml_list = os.listdir(xml_dir) pbar = tqdm(total=len(xml_list)) # 加入进度条支持 pbar.set_description("VOC2GT") # 设置前缀 for tmp_file in xml_list: xml_path = os.path.join(xml_dir,tmp_file) gt_txt_path = os.path.join(gt_dir,tmp_file.replace(".xml", ".txt")) # 读取xml文件+转为字典 with open(xml_path,'r',encoding="utf8") as f: xml_str = f.read() xml_dict = xmltodict.parse(xml_str) # 提取对应的数据 gt_str = voc_2_gt_str(xml_dict) # 写入对应的gt_txt文件 with open(gt_txt_path, "w") as f: f.write(gt_str) pbar.update(1) pbar.close()VOC2GT: 27%|██████████████████████████████████████████████████████████████▌ | 24013/89029 [03:25<09:54, 109.31it/s]2.2 YOLOv5_2_dr.py# YOLOv5_2_dr import os import xmltodict import shutil from tqdm import tqdm # TODO：需要修改的内容 yolov5_detect_txt_dir = "/data/jupiter/project/目标检测对比实验/yolov5/runs/detect/exp3/labels" cls_list = ['conveyor', 'refueller', 'aircraft', 'lounge', 'dining car', 'front of baggage car', 'tractor'] img_width = 1632 img_height = 1080 def txt_convert(txt_src,img_width,img_height,cls_list): txt_dst = "" for line in txt_src.split("\n"): if(len(line)==0):continue cls_id,dx,dy,dw,dh,conf = line.split(" ") cls_name = cls_list[int(cls_id)].replace(" ","") x_center = int(float(dx)*img_width) y_center = int(float(dy)*img_height) w = int(float(dw)*img_width) h = int(float(dh)*img_height) x1 = x_center - int(w/2) y1 = y_center - int(h/2) x2 = x1 + w y2 = y1 + h txt_dst += "{} {} {} {} {} {}\n".format(cls_name,conf,x1,y1,x2,y2) return txt_dst dr_dir = "./input/detection-results/" txt_list = os.listdir(yolov5_detect_txt_dir) pbar = tqdm(total=len(txt_list)) # 加入进度条支持 pbar.set_description("YOLOv5_2_dr") # 设置前缀 for file in txt_list: txt_path_src = os.path.join(yolov5_detect_txt_dir,file) txt_path_dst = os.path.join(dr_dir,"{:>05d}.txt".format(int(file.split("_")[1][:-4]))) # 读取原文件 with open(txt_path_src) as f: txt_src = f.read() # 转为目标格式 txt_dst = txt_convert(txt_src,img_width,img_height,cls_list) # 写入对应的dr_txt文件 with open(txt_path_dst,"w") as f: f.write(txt_dst) pbar.update(1) pbar.close()参考资料https://github.com/Cartucho/mAP.git目标检测中的mAP及代码实现
-
leetcode|中等:15. 三数之和 1.题目给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。示例 1：输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]示例 2：输入：nums = [] 输出：[]示例 3：输入：nums = [0] 输出：[]提示：$0 <= nums.length <= 3000$$-10^5 <= nums[i] <= 10^5$2. 题解2.1 思路分析首先对数组进行排序，排序后固定一个数 nums[i] 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环 否则使用左右指针指向nums[i]后面的两端，数字分别为 nums[L]和 nums[R]计算三个数的和 sum 判断是否满足等于0 等于0则添加进结果集 小于0则L++(L<R) 大于0则R--(L<R) 关于去重: 如果 nums[i]== nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过 当 sum == 0 时，nums[L] == nums[L+1]则会导致结果重复，应该跳过，L++ 当 sum == 0 时，nums[R] == nums[R-1] 则会导致结果重复，应该跳过，R--2.2 代码实现import java.util.*; public class Solution { public List<List<Integer>> threeSum(int[] nums) { // 数组排序 Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); if(nums.length>=3) { for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) break; if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i + 1; // 左指针 int R = nums.length - 1; // 右指针 while (L < R) { while (L < R && nums[L] == nums[L + 1]) L++; // 去重 while (L < R && nums[R] == nums[R - 1]) R--; // 去重 int sum = nums[i] + nums[L] + nums[R]; if (sum == 0) { res.add(Arrays.asList(nums[i], nums[L], nums[R])); L++; R--; } else if (sum < 0) { L++; } else { R--; } } } } return res; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4})); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过19 ms45.6 MBJava2022/03/24 20:29添加备注参考资料https://leetcode-cn.com/problems/3sum/https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
-
leetcode|中等:12. 整数转罗马数字 1.题目罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。给你一个整数，将其转为罗马数字。示例 1:输入: num = 3 输出: "III"示例 2:输入: num = 4 输出: "IV"示例 3:输入: num = 9 输出: "IX"示例 4:输入: num = 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3.示例 5:输入: num = 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.提示：1 <= num <= 39992. 题解2.1 思路分析思路1：贪心 首先我们构造出所有可能会出现的元素 vals = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; keys = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"}; 然后我们每次尽量使用最大的数来表示。 比如对于 1994 这个数，如果我们每次尽量用最大的数来表示，依次选 1000，900，90，4，会得到正确结果 MCMXCIV。2.2 代码实现public class Solution { public String intToRoman(int num) { int[] vals = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; String[] keys = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"}; StringBuilder sb = new StringBuilder(); while (num>0){ // 先确定是要减哪一个 int targetIndex = vals.length-1; while (vals[targetIndex]>num){targetIndex--;}; sb.append(keys[targetIndex]); num -= vals[targetIndex]; } return sb.toString(); } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.intToRoman(1994)); } } 2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过3 ms40.7 MBJava2022/03/24 13:07添加备注参考资料https://leetcode-cn.com/problems/integer-to-roman/
-
leetcode|中等:11. 盛最多水的容器 1.题目给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。示例 1：输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1] 输出：1提示：n == height.length2 <= n <= 1050 <= height[i] <= 1042. 题解2.1 思路分析思路1：双指针 设两指针 i,j ，指向的水槽板高度分别为 h[i], h[j] ，此状态下水槽面积为 S(i,j)。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ： S(i, j) = min(h[i], h[j]) × (j - i) 在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1 变短： 若向内移动短板，水槽的短板 min(h[i],h[j])可能变大，因此下个水槽的面积可能增大 若向内移动长板，水槽的短板 min(h[i],h[j])不变或变小，因此下个水槽的面积一定变小 因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。2.2 代码实现public class Solution { public int maxArea(int[] height) { int max = 0; int left = 0,right = height.length-1; // 双指针 while (left<right){ int area = Math.min(height[left],height[right])*(right-left); max = Math.max(area,max); if(height[left]>height[right]){ right--; }else { left++; } } return max; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.maxArea(new int[]{1,8,6,2,5,4,8,3,7})); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过4 ms51.6 MBJava2022/03/24 12:32添加备注参考资料https://leetcode-cn.com/problems/container-with-most-water/https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
-
leetcode|中等:5. 最长回文子串 1.题目给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2：输入：s = "cbbd" 输出："bb"提示：1 <= s.length <= 1000s 仅由数字和英文字母组成2. 题解2.1 思路分析思路1：暴力求解 从每个字符开始向右延伸探索可能构成的最长回文子串并记录最长子串的开始位置和长度2.2 代码实现public class Solution { //判断子串是否构成回文 public boolean isPalindrome(char[] sChars,int indexStart,int indexEnd){ int len = indexEnd-indexStart; if(len==1)return true; for (int i = 0; i < len/2; i++) { if(sChars[indexStart+i]!=sChars[indexEnd-1-i]){ return false; } } return true; } public String longestPalindrome(String s) { char[] sChars = s.toCharArray(); //转为字符数组 int sLen = s.length(); // 字符串长度 int indexStart = 0; //记录最长子串的开始位置 int maxLen = 1; //记录最大子串长度 for (int i = 0; i < sLen-maxLen; i++) { // 子串开始下标 for (int j = maxLen; j <= sLen-i; j++) { // 子串长度 if(isPalindrome(sChars,i,i+j)){ indexStart = i; maxLen = j; } } } return s.substring(indexStart,indexStart+maxLen); } public static void main(String[] args) { Solution solution = new Solution(); String in = "babad"; String res = solution.longestPalindrome(in); System.out.println(res); } } 2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过265 ms41.2 MBJava2022/03/23 17:11添加备注参考资料https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/
-
VOC2VID:将VOC格式的数据集转为视频进行查看|可视化视频标注结果 通常用于查看针对连续视频标注的结果，因博主有视频目标检测的需求所以写了该小工具# 可视化视频标注结果 import numpy as np import cv2 import xmltodict import os from tqdm import tqdm # 基本信息填充 xml_dir="./data_handle/xml/"# VOC xml文件所在文件夹 img_dir="./data_handle/img/"# VOC img文件所在文件夹 class_list = ['conveyor', 'refueller', 'aircraft', 'lounge', 'dining car', 'front of baggage car', 'tractor'] # class_list """ 将voc xml 的数据转为对应的bbox_list """ def voc_2_yolo_bbox_list(xml_dict): objects = xml_dict["annotation"]["object"] obj_list = [] if isinstance(objects,list): # xml文件中包含多个object for obj in objects: obj_list.append(obj) else: # xml文件中包含1个object obj_list.append(objects) bbox_list = [] for obj in obj_list: # 获取voc格式的数据信息 x1 = int(obj['bndbox']['xmin']) y1 = int(obj['bndbox']['ymin']) x2 = int(obj['bndbox']['xmax']) y2 = int(obj['bndbox']['ymax']) score = 1 cls_id = class_list.index(obj['name']) bbox_list.append([x1,y1,x2,y2,score,cls_id]) return bbox_list """ 生成color_list """ def random_color(color_num): color_list = [] for j in range(color_num): color_single = (int(np.random.randint(0,255)),int(np.random.randint(0,255)),int(np.random.randint(0,255))) color_list.append(tuple(color_single)) return color_list color_list = random_color(len(class_list)) """ 目标检测预测结果可视化函数 + img:进行目标检测的图片 + bbox_list:处理过的预测结果 + class_name_list:用于将cls_is转为cls_name + color_list:绘制不同的类别使用不同的颜色 + thresh:阈值 """ def vis_detections(img, bbox_list,class_name_list=class_list,color_list=color_list,thresh=0.5): for bbox in bbox_list: # 参数解析 x1,y1,x2,y2,score,cls_id = bbox[0],bbox[1],bbox[2], bbox[3],bbox[4],int(bbox[5]) cls_name = class_name_list[cls_id] color = color_list[cls_id] # 跳过低于阈值的框 if score<thresh:continue # 画框 cv2.rectangle(img, (int(x1),int(y1)), (int(x2),int(y2)),color_list[cls_id],2) # 画label label_text = '{:s} {:.3f}'.format(cls_name, score) cv2.putText(img, label_text, (x1-5, y1-5),cv2.FONT_HERSHEY_SIMPLEX, 0.8, color_list[cls_id], 2) return img img_list = os.listdir(img_dir) frame_rate = 30 # 帧率 frame_shape = cv2.imread(os.path.join(img_dir,img_list[0])).shape[:-1] # 图片大小/帧shape frame_shape = (frame_shape[1],frame_shape[0]) # 交换w和h videoWriter = cv2.VideoWriter('result.mp4', cv2.VideoWriter_fourcc(*'MJPG'), frame_rate, frame_shape) # 初始化视频帧writer # 加入进度条支持 pbar = tqdm(total=len(img_list)) pbar.set_description("VOC2VID") # 开始逐帧写入视频帧 frame_id = 1 for file in img_list: img_path = os.path.join(img_dir,file) # img地址 img = cv2.imread(img_path) # 读取img xml_path = os.path.join(xml_dir,file[:-3]+"xml") # xml地址 # 读取xml文件+转为字典+ 转为bbox_list with open(xml_path,'r',encoding="utf8") as f: xml_str = f.read() xml_dict = xmltodict.parse(xml_str) bbox_list = voc_2_yolo_bbox_list(xml_dict) # 绘制xml标注结果 img = vis_detections(img,bbox_list) frame_id += 1 # if frame_id%120 == 0: # break videoWriter.write(img) pbar.update(1) pbar.close() videoWriter.release()
-
目标检测结果可视化 1.核心函数# 目标检测效果可视化 import numpy as np import cv2 # class_list class_list = ['Plane', 'BridgeVehicle', 'Person', 'LuggageVehicle', 'RefuelVehicle', 'FoodVehicle', 'LuggageVehicleHead', 'TractorVehicle', 'RubbishVehicle', 'FollowMe'] """ 生成color_list """ # 生成number个color def random_color(color_num): color_list = [] for j in range(color_num): color_single = (int(np.random.randint(0,255)),int(np.random.randint(0,255)),int(np.random.randint(0,255))) color_list.append(tuple(color_single)) return color_list color_list = random_color(len(class_list)) """ 目标检测预测结果可视化函数 + img:进行目标检测的图片 + bbox_list:处理过的预测结果 + class_name_list:用于将cls_is转为cls_name + color_list:绘制不同的类别使用不同的颜色 + thresh:阈值 """ def vis_detections(img, bbox_list,class_name_list=class_list,color_list=color_list,thresh=0.5): for bbox in bbox_list: # 参数解析 x1,y1,x2,y2,score,cls_id = bbox[0],bbox[1],bbox[2], bbox[3],bbox[4],int(bbox[5]) cls_name = class_name_list[cls_id] color = color_list[cls_id] # 跳过低于阈值的框 if score<thresh:continue # 画框 cv2.rectangle(img, (int(x1),int(y1)), (int(x2),int(y2)),color_list[cls_id],2) # 画label label_text = '{:s} {:.3f}'.format(cls_name, score) cv2.putText(img, label_text, (x1-5, y1-5),cv2.FONT_HERSHEY_SIMPLEX, 0.8, color_list[cls_id], 2) return img2.调用测试img = cv2.imread("./data_handle/img/00001.jpg.") bbox_list = [ [882,549,1365,631,1,1] ] img = vis_detections(img,bbox_list) img_show = cv2.cvtColor(img,cv2.COLOR_BGR2RGB) import matplotlib.pyplot as plt plt.figure(dpi=200) plt.xticks([]) plt.yticks([]) plt.imshow(img_show) plt.show()
-
蓝桥杯|历届真题:作物杂交 1.题目【问题描述】作物杂交是作物栽培中重要的一步。已知有$N$种作物（编号$1$至$N$），第$i$种作物从播种到成熟的时间为$T_i$。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物$A$种植时间为5天，作物$B$种植时间为7天，则$AB$杂交花费的时间为7天。作物杂交会产生固定的作物，新产生的作物仍然属于N种作物中的一种。初始时，拥有其中$M$种作物的种子（数量无限，可以支持多次杂交）。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。如存在4种作物$ABCD$，各自的成熟时间为5天、7天、3天、8天。初始拥有AB两种作物的种子，目标种子为$D$，已知杂交情况为$A \times B→C，A \times C→D$。则最短的杂交过程为：第1天到第7天（作物B的时间），$A \times B→C$。第8天到第12天（作物A的时间），$A \ times C→D$。花费12天得到作物D的种子。【输入格式】输入的第1行包含4个整数$N，M，K，T，N$表示作物种类总数（编号1至$N$），$M$表示初始拥有的作物种子类型数量，$K$表示可以杂交的方案数，$T$表示目标种子的编号。第2行包含$N$个整数，其中第i个整数表示第i种作物的种植时间T；（$1 \leq T_i \leq 100$）第3行包含$M$个整数，分别表示已拥有的种子类型$K_j( 1 \leq K_j \leq M)$，$K_j$两两不同。第4至$K+3$行，每行包含3个整数$A，B，C$，表示第$A$类作物和第$B$类作物杂交可以获得第$C$类作物的种子。【输出格式】输出一个整数，表示得到目标种子的最短杂交时间。【样例输入】6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6【样例输出】16【样例说明】第1天至第5天，将编号1与编号2的作物杂交，得到编号3的作物种第6天至第10天，将编号1与编号3的作物杂交，得到编号4的作物种第6天至第9天，将编号2与编号3的作物杂交，得到编号5的作物种第11天至第16天，将编号4与编号5的作物杂交，得到编号6的作物种总共花费16天【评测用例规模与约定】对于所有评测用例，$1 \leq N \leq 2000,2 \leq M \leq N，1 \leq K \leq 100000,1 \leq T \leq N$，保证目标种子一定可以通过杂交得到。2. 题解2.1 思路分析思路1：暴力求解 设置一个数字minGetTime用于保存每类种子的最小获取时间 循环遍历杂交方案： minGetTime[C] = min(minGetTime[C],maxAB获取时间+maxAB成熟数据) 直至数组minGetTime收敛(不再有任何位置发生变化)2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); // 判断minGetTime数组是否收敛|是否存在某位发生修改 无则返回true public static boolean isNoChange(boolean[] changeFlag){ boolean res = true; for (int i = 0; i < changeFlag.length; i++) { res = res&changeFlag[i]; } return res; } public static void main(String[] args) { int N = scanner.nextInt(); // 作物种类数 int M = scanner.nextInt(); // 初始时候拥有的种子数量 int K = scanner.nextInt(); // 可以杂交的方案数量 int T = scanner.nextInt(); // 目的种子编号 int[] timeSpendArr = new int[N];// 作物成熟时间 for (int i = 0; i < N; i++) { timeSpendArr[i] = scanner.nextInt(); } int[] startSeedArr = new int[M]; //初始拥有的种子 for (int i = 0; i < M; i++) { startSeedArr[i] = scanner.nextInt(); } int[][] methodArr = new int[K][3]; //杂交方案数 for (int i = 0; i < K; i++) { for (int j = 0; j < 3; j++) { methodArr[i][j] = scanner.nextInt(); } } int[] minGetTime = new int[N];//最小获取时间 // 初始化最小获取时间 for (int i = 0; i < N; i++) { minGetTime[i] = Integer.MAX_VALUE; } for (int i = 0; i < M; i++) { minGetTime[startSeedArr[i]-1] = 0; } boolean[] changeFlag = new boolean[K];//用于判断本轮处理杂交方案是否导致了最小时间发生修改|判断收敛 Arrays.fill(changeFlag,false); while (!isNoChange(changeFlag)){//知道未发生修改位置 Arrays.fill(changeFlag,true); for (int i = 0; i < K; i++) { int seedA = methodArr[i][0]-1; int seedB = methodArr[i][1]-1; if(minGetTime[seedA]==Integer.MAX_VALUE||minGetTime[seedB]==Integer.MAX_VALUE)continue; int newSeed = methodArr[i][2]-1;//新品种 int minGetTimeOfNewSeed = Math.min(minGetTime[newSeed],Math.max(minGetTime[seedA],minGetTime[seedB])+Math.max(timeSpendArr[seedA],timeSpendArr[seedB])); if(minGetTimeOfNewSeed!=minGetTime[newSeed]){ changeFlag[i] = false; minGetTime[newSeed] = minGetTimeOfNewSeed; } } } System.out.println(minGetTime[T-1]); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms25.54MB输入 输出2正确10.00109ms25.46MBVIP特权3正确10.00468ms75.14MBVIP特权4正确10.00406ms68.42MBVIP特权5正确10.00390ms77.67MBVIP特权6正确10.00296ms54.73MBVIP特权7正确10.00500ms99.37MBVIP特权8正确10.00453ms98.50MBVIP特权9正确10.00578ms97.82MBVIP特权10正确10.00500ms98.80MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2859
-
蓝桥杯|历届真题:修改数组 1.题目【问题描述】给定一个长度为N的数组$A=[A_1,A_2,\dots,A_N]$，数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改$A_2,A_3,\dots,A_N$当修改$A_i$；时，小明会检查$A_i$是否在$A_1 \rightarrow A_{i-1}$中出现过。如果出现过，则小明会给$A_i$加上$1$；如果新的$A_i$仍在之前出现过，小明会持续给$A_i$加上1直到$A_i$没有在$A_1 \rightarrow A_{i-1}$中出现过。当$A_n$也经过上述修改之后，显然A数组中就没有重复的整数了。现在给定初始的A数组，请你计算出最终的A数组。【输入格式】第一行包含一个整数$N$。第二行包含N个整数$A_1,A_2,\dots,A_N$【输出格式】输出N个整数，依次是最终的$A_1,A_2,\dots,A_N$【样例输入】5 2 1 1 3 4【样例输出】2 1 3 4 5【评测用例规模与约定】对于80%的评测用例，$1 \leq N \leq 10000$。对于所有评测用例，$1 \leq N \leq 100000,1 \leq A_i \leq 1000000$。2. 题解2.1 思路分析思路1：暴力求解(80分) 用一个set保存已遍历过的数字，当遍历到新的位置时，如果再set里则一直++，再将其加入回set 思路2：并查集 维护并查集并通过查操作直接找到A_i2.2 代码实现思路1：暴力求解// 暴力求解 80分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); } Set<Integer> set = new HashSet<>(); for (int i = 0; i < N; i++) { while (set.contains(arr[i])){ arr[i]++; } set.add(arr[i]); } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }思路2：并查集// 并查集 80分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] find = new int[1000001]; // 查操作 找到x的真正祖先 public static int findRoot(int x){ return x==find[x]?x:findRoot(find[x]); } public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; // 初始化find数组(用于查找祖先) for (int i = 0; i < find.length; i++) { find[i] = i; } for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); int root = findRoot(arr[i]); //找到目标A_{i-1} arr[i] = root; find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系 } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }// 并查集+路径压缩 100分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] find = new int[1000100]; // 查操作 找到x的真正祖先 增加路径压缩降低耗时 public static int findRoot(int x){ if(x==find[x]){ return x; }else { find[x] = findRoot(find[x]); return find[x]; } } public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; // 初始化find数组(用于查找祖先) for (int i = 0; i < find.length; i++) { find[i] = i; } for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); int root = findRoot(arr[i]); //找到目标A_{i-1} arr[i] = root; find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系 } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }2.3 提交结果思路1：暴力求解评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms22.51MB输入 输出2正确10.0093ms22.47MBVIP特权3正确10.0093ms22.62MBVIP特权4正确10.00125ms31.51MBVIP特权5正确10.00656ms158.1MBVIP特权6正确10.00484ms149.7MBVIP特权7正确10.00765ms242.9MBVIP特权8正确10.00531ms156.5MBVIP特权9运行超时0.00运行超时287.7MBVIP特权10运行超时0.00运行超时287.8MBVIP特权思路2：并查集评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms26.23MB输入 输出2正确10.00125ms26.23MBVIP特权3正确10.0078ms26.39MBVIP特权4正确10.00156ms30.05MBVIP特权5正确10.00296ms40.35MBVIP特权6正确10.00296ms42.53MBVIP特权7正确10.00328ms40.65MBVIP特权8正确10.00281ms40.58MBVIP特权9正确10.00609ms96.44MBVIP特权10正确10.00484ms97.01MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2856图论——并查集(详细版)蓝桥杯 -2019年第十届真题 修改数组 暴力|并查集
-
蓝桥杯|历届真题:回文日期 1.题目【问题描述】2020年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按"yyyymmdd”的格式写成一个8位数是20200202，恰好是一个回文数。我们称这样的日期是回文日期。有人表示20200202是“千年一遇”的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202即2021年12月2日。也有人表示20200202并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121年12月12日。算不上“千年一遇”，顶多算“千年两遇”。给定一个8位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。【输入格式】输入包含一个八位整数N，表示日期。【输出格式】输出两行，每行1个八位数。第一行表示下一个回文日期，第二行表示下一个ABABBABA型的回文日期。【样例输入】20200202【样例输出】20211202 21211212【评测用例规模与约定】对于所有评测用例，$10000101 \leq N \leq 89991231$，保证N是一个合法日期的8位数表示。2. 题解2.1 思路分析本题需要求解下一个ABCDDCBA型的日期和下一个ABABBABA型的日期 只需先完成nextABCDDCBADate的求解并再此基础上增加ABCD-->ABAB的限制条件即可 nextABCDDCBADate(date)的求解包含内容： 1.date年月日拆解 2.4位数字反转 ABCD-->DCBA 为了降低时间复杂度，只对年进行遍历，月日根据ABCD-->DCBA生成 3.有效日期判断(年月日分别进行判断) 包含闰年判断 4.判断新的日期是否再当前日期之后2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] maxDayOfMonthList = {31,28,31,30,31,30,31,31,30,31,30,31}; // 判断闰年 public static boolean isUniqueYear(int year){ return (year%4==0&&year%100!=0)||year%400==0; } // 判断day是否有效 public static boolean isValidDay(int year,int month,int day){ // 求该月最大天数 int maxDayOfMonth = maxDayOfMonthList[month-1]; if(isUniqueYear(year)&&month==2){ maxDayOfMonth = 29; } return !(day==0||day>maxDayOfMonth); } // 判断month是否有效 public static boolean isValidMonth(int month){ return month>0&&month<13; } // 4位数字反转 ABCD-->DCBA public static int reverse4BitInt(int num){ // 从低位到高位进行分解 int bit1 = num%10; int bit2 = (num%100)/10; int bit3 = (num/100)%10; int bit4 = num/1000; return bit1*1000+bit2*100+bit3*10+bit4; } // 寻找下一个回文/ABCDDCBA日期 public static int nextABCDDCBADate(int date){ int year = date / 10000; int ABCDDCBADate = date; for (int i = year; i < 10000; i++) { int tmp_year = i; int tmp_year_reverse = reverse4BitInt(tmp_year); int tmp_day = tmp_year_reverse%100; int tmp_month = tmp_year_reverse/100; int tmp_date = tmp_year*10000+tmp_month*100+tmp_day; if (isValidMonth(tmp_month) && isValidDay(tmp_year, tmp_month, tmp_day)&&tmp_date>date){//有效日期+日期更后 ABCDDCBADate = tmp_date; break; } } return ABCDDCBADate; } // 寻找下一个符合ABABBABA的日期 public static int nextABABBABADate(int date) { int ABABBABA = nextABCDDCBADate(date); int month = (ABABBABA % 10000) / 100; int day = ABABBABA % 100; while (month!=day){ ABABBABA = nextABCDDCBADate(ABABBABA); month = (ABABBABA % 10000) / 100; day = ABABBABA % 100; } return ABABBABA; } public static void main(String[] args) { int date= scanner.nextInt(); System.out.println(nextABCDDCBADate(date)); System.out.println(nextABABBABADate(date)); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms22.52MB输入 输出2正确10.0078ms22.48MBVIP特权3正确10.00109ms22.49MBVIP特权4正确10.0062ms22.44MBVIP特权5正确10.00109ms22.44MBVIP特权6正确10.0093ms22.47MBVIP特权7正确10.0046ms22.50MBVIP特权8正确10.0093ms22.48MBVIP特权9正确10.0078ms22.51MBVIP特权10正确10.0078ms22.48MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2856
-
蓝桥杯|历届真题:子串分值和 1.题目【问题描述】对于一个字符串$S$，我们定义S的分值$f(S)$为$S$中恰好出现一次的字符个数。例如$f(aba)=1，f(abc)=3，f(aaa) = 0$。现在给定一个字符串$S[0..n-1]$（长度为n），请你计算对于所有S的非空子串$S[i..j]（0 \leq i \leq j \lt n）$，$f(S[i..j])$的和是多少。【输入格式】输入一行包含一个由小写字母组成的字符串S。【输出格式】输出一个整数表示答案。【样例输入】ababc【样例输出】21【样例说明】子串,f值 a,1 ab,2 aba,1 abab,0 ababc,1 b,1 ba,2 bab,1 babc,2 a,1 ab,2 abc,3 b,1 bc,2 c,1【评测用例规模与约定】对于20%的评测用例， $1 \leq n \leq 10$；对于40%的评测用例， $1 \leq n \leq 100$；对于50%的评测用例， $1 \leq n \leq 1000$；对于60%的评测用例， $1 \leq n \leq 10000$；对于所有评测用例， $1 \leq n \leq 100000$；2. 题解2.1 思路分析思路1：暴力求解(50分) 首先需要写一个计算子串得分的函数 1.统计各个字符出现的次数 2.得到只出现一次的字符数 然后遍历所有的子串并对其得分进行求和 思路2：动态规划(50分) 考虑子串之间的关系,即新增一个字符对子串得分的影响,从避免重复统计字符出现次数导致耗时 思路3:考虑每个位置的字符只出现一次的子串总数(100分) 用 pre[i] 记录第 i 位置上的字母上一次出现的位置，用 next[i] 记录第 i 位置上的字母下一次出现的位置； 那么往左最多能延伸到 pre[i] + 1，其到第 i 个字母一共有 i - pre[i] 个字母； 同理往右最多能延伸到 next[i] - 1，其到第 i 个字母一共有 next[i] - i 个字母； 二者相乘，就是该 i 位置上的字符只出现一次的子串总数 具体可以结合上述输入输出例子思考。2.2 代码实现思路1：暴力求解import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static int getScore(String str){ int score = 0; char[] strChars = str.toCharArray(); int[] charCounter = new int[26]; for (int i = 0; i < 26; i++)charCounter[i]=0; for (int i = 0; i < strChars.length; i++) { charCounter[(int)(strChars[i]-'a')]++; } for (int i = 0; i <26 ; i++) { if(charCounter[i]==1)score++; } return score; } public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int scoreSum = 0; for (int i = 0; i < strChars.length; i++) { StringBuilder sb = new StringBuilder(); for (int j = i; j < strChars.length; j++) { sb.append(strChars[j]); scoreSum+=getScore(sb.toString()); } } System.out.println(scoreSum); } }// 简化子串得分求解 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); int len = str.length(); char[] strChars = str.toCharArray(); int scoreSum = 0; for (int i = 0; i < strChars.length; i++) { Set<Character> set1 = new HashSet<>(); //统计所有字符串 Set<Character> set2 = new HashSet<>();//统计不止出现一次的字符串 for (int j = i; j < strChars.length; j++) { if(set1.contains(strChars[j])){ set2.add(strChars[j]); } set1.add(strChars[j]); scoreSum+= set1.size()-set2.size(); } } System.out.println(scoreSum); } }思路2：动态规划// 40分 会爆内存 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int[][] dp = new int[str.length()][str.length()]; int scoreSum = 0; for (int i = 0; i < str.length(); i++) { for (int j = 0; j < str.length();j++) { if(j<i){ dp[i][j] = 0; }else if(j==i){ dp[i][j] = 1; }else { int startIndex = str.substring(i,j).indexOf(strChars[j]); if(startIndex!=-1){//旧的子包含待加入字符 int endIndex = str.substring(i,j).lastIndexOf(strChars[j]); if(startIndex==endIndex){//旧的子串只包含1个待加入字符 dp[i][j]=dp[i][j-1]-1; }else {//旧的子串包含多个个待加入字符，之前已进行了-1操作，无需再减 dp[i][j]=dp[i][j-1]; } }else {//旧的子不包含待加入字符 dp[i][j]=dp[i][j-1]+1; } } scoreSum += dp[i][j]; } } System.out.println(scoreSum); } }// dp优化 避免爆内存 还是50分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); int len = str.length(); char[] strChars = str.toCharArray(); int lastDpstate = 0; int scoreSum = 0; for (int i = 0; i < len; i++) { for (int j = 0; j < len;j++) { if(j<i){ lastDpstate=0; }else if(j==i){ lastDpstate = 1; }else { int startIndex = str.substring(i,j).indexOf(strChars[j]); if(startIndex!=-1){//旧的子串包含待加入字符 int endIndex = str.substring(i,j).lastIndexOf(strChars[j]); if(startIndex==endIndex){//旧的子串只包含1个待加入字符 lastDpstate=lastDpstate-1; } }else { lastDpstate=lastDpstate+1; } } scoreSum += lastDpstate; } } System.out.println(scoreSum); } }思路3：考虑每个位置的字符只出现一次的子串总数// 60分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int scoreSum = 0; for (int i = 0; i < strChars.length; i++) { int nextIndex = str.substring(i+1).indexOf(strChars[i]); //下一个strChars[i]字符的位置 nextIndex = nextIndex==-1? strChars.length : nextIndex+i+1; int preIndex = str.substring(0,i).lastIndexOf(strChars[i]);////前一个strChars[i]字符的位置 scoreSum += (nextIndex-i)*(i-preIndex); } System.out.println(scoreSum); } }// 优化 100分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int len = strChars.length; int scoreSum = 0; int[] pre = new int[len]; int[] next = new int[len]; Arrays.fill(pre,-1); Arrays.fill(next,len); // 求解next[i] for (int i = 0; i < len; i++) { for (int j = i+1; j < len; j++) { if(strChars[i]==strChars[j]){ next[i]=j; break; } } } // 求解pre[i] for (int i = 0; i < len; i++) { for (int j = i-1; j>=0; j--) { if(strChars[i]==strChars[j]){ pre[i]=j; break; } } } // 计算得分和 for (int i = 0; i < len; i++) { scoreSum += (next[i]-i)*(i-pre[i]); } System.out.println(scoreSum); } }2.3 提交结果思路1：暴力求解评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.0078ms22.17MB输入 输出2正确10.00109ms22.19MBVIP特权3正确10.00109ms22.19MBVIP特权4正确10.0093ms24.36MBVIP特权5正确10.00359ms233.1MBVIP特权6运行超时0.00运行超时281.0MBVIP特权7运行超时0.00运行超时283.3MBVIP特权8运行超时0.00运行超时435.0MBVIP特权9运行超时0.00运行超时282.5MBVIP特权10运行超时0.00运行超时282.6MBVIP特权思路2：动态规划评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.0078ms22.17MB输入 输出2正确10.00109ms22.19MBVIP特权3正确10.00109ms22.19MBVIP特权4正确10.0093ms24.36MBVIP特权5正确10.00359ms233.1MBVIP特权6运行超时0.00运行超时281.0MBVIP特权7运行超时0.00运行超时283.3MBVIP特权8运行超时0.00运行超时435.0MBVIP特权9运行超时0.00运行超时282.5MBVIP特权10运行超时0.00运行超时282.6MBVIP特权思路3：考虑每个位置的字符只出现一次的子串总数评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00109ms22.40MB输入 输出2正确10.0046ms22.40MBVIP特权3正确10.0078ms22.41MBVIP特权4正确10.0093ms22.39MBVIP特权5正确10.0078ms22.44MBVIP特权6正确10.00125ms23.34MBVIP特权7正确10.00125ms26.62MBVIP特权8正确10.00140ms26.70MBVIP特权9正确10.00109ms26.51MBVIP特权10正确10.00171ms26.66MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2858蓝桥杯试题 历届试题 子串分值和
