[万字]面试题实录

21应届,2020.3三月以来一些没发出来的面经,回馈牛客。现在全部总结发出来。

有些记录的清晰就写的多,有些记录少就写得少,大概如下:

荔枝实习生面试

4道笔试题

1.tcp的三次握手

2.treemap和Hashmap的区别

3.单例设计模式手撕

4.1000个数据去重

面试:

1、数据库的索引(聚集索引)、引擎。

聚集索引通过B树/B+树定位数据记录的位置

非聚集索引其实是一个额外的空间,通过它去定位主键(聚集索引),再通过聚集索引定位表里的记录/位置

MyISAM->默认都是非聚集索引

2、两个队列实现一个栈。

import java.util.Stack;

public class MyStack {
    Stack<Integer> data = new Stack<Integer>(); //存放元素栈
    Stack<Integer> min = new Stack<Integer>(); //辅助栈,data栈中每次进入一个元素,min辅助栈就存放当前data栈中的最小元素

    //data栈和min栈进入元素
    public void push(int item){
        data.push(item);
        if(min.size() == 0 || item < min.peek()){
            min.push(item);
        }else{
            min.push(min.peek());
        }
    }

    //data栈和min栈弹出元素
    public void pop(){
        if(data.size() > 0 && min.size() > 0){
            data.pop();
            min.pop();
        }
    }

    //data栈的栈顶元素
    public int top(){
        if(data.size() > 0){
            return data.peek();
        }
        return 0;
    }
    //min栈的栈顶元素,栈顶元素为data栈中现有元素的最小元素
    public int min(){
        if(data.size() > 0 && min.size() > 0){
            return min.peek();
        }
        return 0;
    }

}

3、redis集群

4、arraylist和linklist区别 底层

5、如何正确地控制一个线程?

join方法:主线程调用/run方法里面调用

传统线程控制:object类的wait方法+notify/All:condition控制await/sign/all

同步计数器,countdownLatch,cyclicBarrier,线程等待至某个状态之后再全部同时执行,另外他可以重复使用,semaphore

6、让一个线程停止的方法(让线程平息地停止运行的方法)

  1. 使用退出标志,使线程正常退出,也就是当run方法完成后线程终止。

  2. 使用stop方法强行终止,但是不推荐这个方法,因为stop和suspend及resume一样都是过期作废的方法。

  3. 使用interrupt方法中断线程。

7、线程池

8、OOM能不能捕获?

只有在一种情况下,这样做是可行的:

在try语句中声明了很大的对象,导致OOM,并且可以确认OOM是由try语句中的对象声明导致的,那么在catch语句中,可以释放掉这些对象,解决OOM的问题,继续执行剩余语句。

但是这通常不是合适的做法。

Java中管理内存除了显式地catch OOM之外还有更多有效的方法:比如SoftReference, WeakReference, 硬盘缓存等。

唯品会第三面

大部分是结合项目问的,只记录部分,这个好像是三面的 1、java代码执行过程。

编译为class文件(编译器),然后

加载、连接、初始化

加载就是根据全限定类名,获取此类的二进制文件,把class文件载入内存的方法区Class文件

(补充加载时机: new、反射ClassLoader.getSystemClassLoader(不一定会。 Class.forName指定false的时候也不会)、初始化子父类、)

2、汉诺塔java

 public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int n = A.size();
        move(n, A, B, C);
    }

    private void move(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
        if (n == 1) {
            c.add(a.remove(a.size() - 1));
            return;
        }

        move(n - 1, a, c, b);
        c.add(a.remove(a.size() - 1));
        move(n - 1, b, a, c);
    }

3、部分Http状态码

200

当您的操作将在响应正文中返回数据时,出现此结果。

201

服务器依照客户端的请求创建了一个新资源时,发送此响应代码。

204、304

204->当您的操作成功,但不在响应正文中返回数据时,出现此结果。

304->响应实体主体都必须为空,重定向

301 状态码

永久性重定向,该状态码表示请求的资源已被分配到新的URI,这就代表你之前保存的书签已经没用了,需要换成新的URI。

302 状态码

临时性重定向,该状态码表示请求的资源已被分配了新的 URI, 希望用户(本次) 能使用新的 URI 访问,也就是说你不需要去更新保存的书签。只是临时性质。

4、RESTful调用和RPC调用有什么区别?

RESTful是一种软件架构风格,用于约束客户端和服务器交互, 满足这些约束条件和原则的应用程序或设计就是 RESTful。 比如HTTP协议使用同一个URL地址,通过GET,POST,PUT,DELETE等方式实现查询、提交、修改、删除数据。 put post

相同:都有更改的意思,

不同:但put会不重复提交,等幂安全,在uri对put有标识;

post支持重复提交

head 类似get,只获取报头

connect 建立tunnel隧道

option 查看性能

trace 回显请求

RPC是远程过程调用,实现分布式系统中的服务调用,双方约定接口,实现信息交互

同程艺龙第一面

只记录了第一面后面二面没记

1、栈帧:局部变量表、操作数栈、方法出入口、动态链接

2、String的replace、replaceAll、replaceof方法

3、votatile、sychornized

4、post、get区别

get有请求体 为空

5、包装类有啥优点

了方便对基本数据类型进行操作,包装类可以解决一些基本类型解决不了的问题:list等集合只能存放引用类型的数据、包装类的parse方法可以实现基本数据类型+string类型之间的相互转换

6、

线程安全的定义

7、

set、list:

set底层是哈希map嘛,他牺牲了有序,就是以链表+数组+红黑树方式存key,每次放入的key都去计算他的哈希,就可以辨别重复,value存的是一个空的object。

list有序,所以他没有办法辨别是不是重复

8、

设计模式:工厂模式

9、

mybatis:sqlmapconfig.xml文件,常用标签

10、

linux命令

11、

dos攻击

下面是年后春招的。先是面试准备,只拿到携程、顺丰和滴滴的面试机会,一些普遍的面试题。还有面试前记录的一些学习笔记。

携程面试准备

1、mysql分页偏移量_mysql limit分页(偏移量)过大时优化问题

利用主键优化

where id>=(select id from user_address order by id limit 10000,1)

或者写成子查询

2、缓存问题

1.查询缓存的利弊 MySQL 8.0 之前可以正常的使用查询缓存的功能,可通过“SHOW GLOBAL VARIABLES LIKE 'query_cache_type'”命令查询数据库是否开启了查询缓存的功能,它的结果值有以下三项:

OFF,关闭了查询缓存功能; ON,开启了查询缓存功能; DEMAND,在 sql 语句中指定 sql_cache 关键字才会有查询缓存,也就是说必须使用 sql_cache 才可以把该 select 语句的查询结果缓存起来,比如“select sql_cache name from token where tid=1010”语句。 开启和关闭查询缓存可以通过修改 MySQL 的配置文件 my.cnf 进行修改,它的配置项如下:

query_cache_type = ON

3、sql查及格率

SELECT [班级], [课程], avg([分数]) as [平均分], SUM(CASE WHEN [分数]>=60 THEN 1 ELSE 0 END)/COUNT(*) AS [及格率] FROM [成绩] GROUP BY [班级],[课程]

4、thrift与protobuffer的区别

不同:

hrift由facebook出品,protobuffer由google出品;

1)Thrift: 支持的语言更广泛一些c++, java, python,ruby, csharp, haskell, ocmal, erlang, cocoa, php

protobuf 目前还是只支持c++, java, python

2)Thrift提供的功能更丰富一些: Thrift提供了简单的RPC构架(其实不简单了, block, nonblock的都有了…..)

protobuf好像一心一意做好自己的事情,只提供了序列化和反序列化的功能。

3)Thrift支持多种协议格式. Thrift的代码实现,有专门的TProtocol和TTransport抽象,相互配合,可以实现多种协议,方便集成各种传输方式。至少目前Thrift就能使用json作为序列化协议。

protobuf只安心一种协议,并下决心把这个格式做好。输入输出也是标准的stream.

4)thrift目前不支持Windows平台

protobuf没有这个问题,提供了visual studio的项目文件,可以很顺利的在windows平台下编译。

5)thrift侧重点是构建夸语言的可伸缩的服务,特点就是支持的语言多,同时提供了完整的rpc service framework,可以很方便的直接构建服务,不需要做太多其他的工作。

相同点:

数据类型相对固定的情况下,不论是thrift还是protobuf都会比直接处理xml要方便很多。

顺丰面试准备

面经:

https://www.nowcoder.com/discuss/576490?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack&subType=2

https://www.nowcoder.com/discuss/577816?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack&subType=2

https://www.nowcoder.com/discuss/577819?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack&subType=2

https://www.nowcoder.com/discuss/591965?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack&subType=2

https://www.nowcoder.com/discuss/611009?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack

https://www.nowcoder.com/discuss/611733?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack

总体概括spring的启动过程:

1.首先,对于一个web应用,其部署在web容器中,web容器提供其一个全局的上下文环境,这个上下文就是ServletContext,其为后面的spring IoC容器提供宿主环境;

2.其 次,在web.xml中会提供有contextLoaderListener。在web容器启动时,会触发容器初始化事件,此时 contextLoaderListener会监听到这个事件,其contextInitialized方***被调用,在这个方法中,spring会初始 化一个启动上下文,这个上下文被称为根上下文,即WebApplicationContext,这是一个接口类,确切的说,其实际的实现类是 XmlWebApplicationContext。这个就是spring的IoC容器,其对应的Bean定义的配置由web.xml中的 context-param标签指定。在这个IoC容器初始化完毕后,spring以WebApplicationContext.ROOTWEBAPPLICATIONCONTEXTATTRIBUTE为属性Key,将其存储到ServletContext中,便于获取;

3.再 次,contextLoaderListener监听器初始化完毕后,开始初始化web.xml中配置的Servlet,这里是DispatcherServlet,这个servlet实际上是一个标准的前端控制器,用以转发、匹配、处理每个servlet请 求。DispatcherServlet上下文在初始化的时候会建立自己的IoC上下文,用以持有spring mvc相关的bean。在建立DispatcherServlet自己的IoC上下文时,会利用WebApplicationContext.ROOTWEBAPPLICATIONCONTEXTATTRIBUTE 先从ServletContext中获取之前的根上下文(即WebApplicationContext)作为自己上下文的parent上下文。有了这个 parent上下文之后,再初始化自己持有的上下文。这个DispatcherServlet初始化自己上下文的工作在其initStrategies方 法中可以看到,大概的工作就是初始化处理器映射、视图解析等。这个servlet自己持有的上下文默认实现类也是 mlWebApplicationContext。初始化完毕后,spring以与servlet的名字相关(此处不是简单的以servlet名为 Key,而是通过一些转换,具体可自行查看源码)的属性为属性Key,也将其存到ServletContext中,以便后续使用。这样每个servlet 就持有自己的上下文,即拥有自己独立的bean空间,同时各个servlet共享相同的bean,即根上下文(第2步中初始化的上下文)定义的那些 bean。

滴滴面试准备

1、tomcat的线程池模型

主从reactor模型

2、tomcat如何保证应用的隔离

https://blog.csdn.net/Wangdiankun/article/details/105819963

Tomcat通过自定义的类加载器WebAppClassLoader打破了双亲委托机制

Tomcat 自定义一个类加载器WebAppClassLoader, 并且给每个 Web 应用创建一个类加载器实例。

而我们知道双亲委派机制中尽管类名相同,但只要是不同个加载器加载的类就不是同一个类。从而实现隔离。

原理是,不同的加载器实例加载的类被认为是不同的类,即使它们的类名相同。这就相当于在 Java 虚拟机内部创建了一个个相互隔离的 Java 类空间,每一个 Web 应用都有自己的类空间,Web 应用之间通过各自的类加载器互相隔离。

补充:通用的会放在上级里。如,自定义的WebAppClassLoader的父类sharedclassloader。

为什么要双亲委派?安全,每个人都写一个object,就乱了。

jdk——>安全

tomcat->不同应用环境隔离,又可以共用某些类库,所以自定义了tomcat的加载器

3、SpringBoot自动装配源码

springboot的自动装配原理 Springboot的自动装配是因为在启动类上贴有@SpringbootApplication注解,这个注解表明该类为一个spring的配置类。 项目启动时,会将贴有该注解的类的所在包名下的所有组件扫描加载到spring容器。 @SpringBootApplication注解内部是@SpringBootApplication = (默认属性)@SpringbootBootConfiguration+ @EnableAutoConfiguration + @ComponentScan的三大注解的集成

@ComponentScan:开启组件扫描 2.@SpringbootBootConfiguration:作用等同于@Configuration注解,用于表明这是一个spring的配置类 3.@EnableAutoConfiguration:通过@import注解内部导入AutoConfigurationImportSelector(自动配置导入选择器),该类中有个getCandidateConfigurations方法加载jar包中META-INF/spring.factories文件中配置的配置对象,自动配置定义的功能

4、删除单链表中的重复节点

  • 删除单链表中的重复节点,空间O(1)

    /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode() {}  *     ListNode(int val) { this.val = val; }  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  * }  */ class Solution {  public ListNode deleteDuplicates(ListNode head) {  if (head == null) {  return head;  }   ListNode cur = head;  while (cur.next != null) {  if (cur.val == cur.next.val) {  cur.next = cur.next.next;  } else {  cur = cur.next;  }  }   return head;  } }
    /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */ class Solution {  public ListNode deleteNode(ListNode head, int val) {  if(head.val == val) return head.next;  ListNode pre = head, cur = head.next;  while(cur != null && cur.val != val) {  pre = cur;  cur = cur.next;  }  if(cur != null) pre.next = cur.next;  return head;  } } 

5、drop、truncate和delete的用法区别

drop (删除表):删除内容和定义,释放空间。简单来说就是把整个表去掉.以后要新增数据是不可能的,除非新增一个表。

truncate (清空表中的数据):删除内容、释放空间但不删除定义(保留表的数据结构)。与drop不同的是,只是清空表数据而已。

delete (删除表中的数据):delete 语句用于删除表中的行。delete语句执行删除的过程是每次从表中删除一行,并且同时将该行的删除操作作为事务记录在日志中保存

滴滴一面

一面就凉了,问的问题挺难的,只记录不会的,一直锤源码。。。

longadder

mysql的幻读处理

arraylist和linkedlist的并发修改异常,迭代器触发,底层怎么样的

快速失败

无算法

顺丰两轮

顺丰一面

自我介绍

sting 有哪些方法、为什么设计为final

哈希map说一下

设计模式,熟悉啥 ?代理模式说一下

用的什么框架? ssm。spring你用过他的那些特性?ioc、aop?

aop有什么使用场景吗?

linux,你用过什么命令?

数据库用的mysql,如何保证可重复读,我说的mvcc机制。

算法:

leetcode第一题。。。两数之和,就算多了要对相同数字做处理

顺丰二面

1、自我介绍

2、Java基础部分

线程安全的集合

红黑树了解吗?说一下有哪写性质

jvm:内存模型,回收算法

3、mysql

有哪些索引?

为什么用B+树?

b+树最多可以有多少层?

我说六,层数太多,数据量特别大,几千万行了都。

面试官说,其实是4,四层就极限了

百度了一下:1-3层约 2 千万行数据

索引优化(explain)

分表分库,三台机器,我如何设计id?说了redis、步长、uuid、雪花

雪花的原理知道吗?

3、redis

五种设计结构使用场景。

数据持久化方式

架构有哪写?(不用解释,你就说有几种,我再问就行)

哨兵有什么缺点?(没回答好)其实两个点,第一是扩容比较复杂,第二是哨兵本身没有实现高可用,哨兵如果宕机,则直接影响用户使用

集群分了集群分片多少槽位?16384=2^14个卡槽

最少分多少个?3个(其实是3对一主一从,6个)

如果没有3个主节点,就会报错:

Redis Cluster requires at least 3 master nodes

redis穿透,如何解决?

布隆过滤器?什么原理?

4、场景题目

给几千万个数据,四台机器各自需要开定时任务处理,如何保证一致。

我说了redis set nx ex?

还有吗?

面试官见时间差不多了 也没有追问下去。

30min左右问了这么多,为什么我的二面和他们不一样,他们两个问题就拜拜了。。。

携程三轮

拿我刷kpi,备胎面试,浪费我好多时间,祝生意兴隆(微笑) 1.测评 就是做行测题 2.笔试,技术笔试 3.一轮技术面 4.二轮技术面 5.换部门加一面 6.hr面 (电话联系) 7.语没有过六级/四级500分 需要做测评。

8.问hr反馈 不通过

携程一面

1、自我介绍

2、哈希map

说一下,介绍一下

链表数组红黑树,什么条件下变红黑树。

哈希map的hash方法与hashCode()有什么关系?

(h & (length - 1) 和 h % length,它俩是等价不等效的,明显位运算效率非常高)

我new HashMap(10),实际大小是多少?16,为什么是16?因为是2的n次方,扩容时候方便,0.75负载因子巴拉巴拉。

面试官:纠错,其实是resize方法,跟2的n次方有关,底层2进制,运算起来很快。你自己了解下。

5、jvm

堆和栈有什么区别 ,里面分别有什么东西?

垃圾回收算法?

6、spring

事务隔离级别?

事务的开启方式?注解和xml

@Transactional 可以与private连用吗?(不可以)为什么?(答不上来)

可以打在私有方法上,但是没有意义,报红的原因应该是idea设置的校验问题

transactional标签用于将对应包装的bean设置成一个新的代理bean对象供外部使用,就是说外部调用这个proxy bean的公共方法时先会调用开启事务等的切面工作,若设置成私有方法只能类内用this指针调用,这样被调用的bean是其本身,不是proxy对象,因此没有transactional切面的意义

ioc与aop介绍

7、设计模式

单例模式几种

工厂模式介绍,3种

8、redis

几种结构

分布式锁 setnx setex,如何实现 如何保证原子

9、线程池

几个参数

工作流程

10、object类有几个方法

我说了wait、notify、notifyall、emm还有equels、hashcode方法,还有很多我说不全。

equels算出来一样、hashcode方法一样吗?(反过来就不一定)

wait方法和sleep方法的区别?说不上来,后面补充了。

还有两个很简单的问题答的不好

11、接口与抽象类的区别

说的不好,面试官说你可以冲共同点和不同说,再说说里面的关键字。

12、new string("hello");几个对象

13、算法

没用手撕,说一下快排思想

没用问项目

反问:

公司技术怎么样?

自己研发SOA、rpc自己封装,dubbo等也有。 但dao层,我们没用hibernate,后面可能会做。

携程二面

1、自我介绍

2、线程池了解?里面有什么组成部分?执行是怎么样的?

3、tomcat了解?如果线程请求到服务器tomcat,我要怎么设计 参数?

还有阻塞队列呢?阻塞队列怎么设计?

这个比较抽象,就回答

首先、去线上服务器看看,参考他是几核几G的。还可以结合用top、free啊等一些命令看一看

其次、看看业务场景,他是查询频繁,那就给大一点核心数。

最后面试官还问阻塞队列,我就说不能用默认的LinkedBlockingQueue,那个无限长,造成线程堆积,最好是自己根据场景设计一下,比如需要即时响应,那就single那个单例的阻塞队列。

4、双亲委派机制

5、对象头里都有什么

6、算法

求0-n几个数字不包含4、7,遍历判断

代码

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        for (int i = 1;i<n+1;i++) {
            int temp = i;
            boolean ishash =false;
            while(temp>0){
                if(temp %10 == 4 || temp%10 == 7){
                    ishash  = true;
                    break;
                }
                temp = temp/10;
            }
            if(!ishash){
                count ++;
            }
        }
        System.out.println (count);

    }

我把7写成8,面试官让我仔细看看题目,给力.

反问:

英语测评,不清楚应该是要的

面试评价,还可以

携程三面

相比这次面试难一点,hr告诉我原本部门 没有hc了,愿不愿意去其他部门

1、多线程了解?Java的锁,说了synchronized 和 ReentrantLock。

数据库的锁呢?说了数据库乐观锁和悲观锁

2、举个用锁场景把 为什么用锁,我说了项目中的redis锁。

3、两个队列,一个1234,一个abcd,交替打印。

4、搞个算法把

给个文章,你找里面的回文串数量

import java.io.*;
import java.util.*;


class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String word = in.next();
        int len = word.length();
        int left = 0;
        int right = len-1;

        int count  = 0;
        
        //eg:levelabc,扫描到索引0和4,

//索引0和7首位都不一样,肯定不是回文 继续走

//如果索引0和索引4一样,就继续判断 索引1 和 索引2 是不是也一样
       for(int left=0;left<len;left++){
           for(int right = len-1;right>len;right--){
            int leftTemp = left;
            int rightTemp = right;
            for(int i = 0;i<(rightTemp- leftTemp+1)/2&&leftTemp<rightTemp;i++){
                if(word.charAt(leftTemp) == word.charAt(rightTemp){
                    leftTemp++;
                    rightTemp--;
                }else{
                    break;
                }
                count++;
            }
           }
       }
         
        }
        System.out.println(count);
    }
}

解释大半天,幸好说了我思路没问题。

5、spring,遇到过什么问题。

循环依赖?

反问:部门?

英语测评准备

maimai这环节其实就是走个形式,要你的话你挂几次就给你发几次测评 测到你过。

准备的要死,还背了英语作文,命中了很开心,以为没问题了,结果挂了。

英语测评:

10个左右自己读,10左右无文字跟读,一个30秒思考45秒说,描述洪水或者去过哪玩,10个左右语法选择,10个左右近义词反义词选择

临时百度的英语作文:

英语描述去过一个地方:

Last summer vacation,my friend and I went to Guangzhou Shamian Park by train.

上个暑假,我和我的朋友坐火车去了广州沙面公园.

It was a sunny day, the sky was blue and the flowers were beautiful.We see a lot of historic buildings.

那一天阳光很明媚,天空很蓝,鲜花也很美

我们看到很多有历史的建筑

There we bought many interesting souvenirs,I was planing to send them to my family .

我们在这里买了好多有趣的纪念品,我打算送给我的家人.

We ate many delicious food there,such as noodle,dumpling,and so on.

我们在这里吃到了美食东西,比如面条、饺子

Then we lived in a clean and tidy hotel,and the price was not so expensive.

我们住在一个干净整洁的旅馆里,而且价格不是很昂贵.

that is a fine day.

那是一段美好的日子。

I like here very much,and if I got a chance,I hope to come here again。

我很喜欢这里,如果有机会我还希望可以再次去。

Last summer vacation,my friend and I went to Guangzhou Shamian Park by train. It was a sunny day, the sky was blue and the flowers were beautiful.We see a lot of historic (heyi story)buildings. we we bought many interesting souvenirs,I was planing to send them to my family . We ate many delicious food there,such as noodle,dumpling,and so on. Then we lived in a clean and tidy(泰迪) hotel,and the price was not so expensive. that is a fine day. I like here very much,and if I got a chance,I hope to come here again.

度假村:

Last summer vacation,my friend and I went to Resort.

that is a fine day.

It was a sunny day, the sky was blue and the flowers were beautiful.

We see a lot of historic (heyi story)buildings.

Then we lived in a clean and tidy(泰迪) hotel,and the price was not so expensive.

The place is famous for its hot spring.

It makes us comfortable.

I like here very much,and if I got a chance,I hope to come here again.

洪水:

Flood is a kind of natural disaster, which may affect traffic,agriculture and even destroy villages.

洪水是一种自然灾害,他可能是会影响交替、农业,甚至可能毁坏村庄。

Floods are often accompanied by rainstorms. I remember another year, rainstorms lasted for three days.

洪水常常伴有暴雨,我记得又一年,暴雨持续了三天。

Many fields and villages were flooded, houses were washed away by floods, villagers were in danger, many people were struggling in the water, crying for help.

许多田地村庄被淹没,房子被洪水冲走,村民处于危险中,许多人在水中挣扎,呼喊着求救。

At that time, the army came by boat, and they tried their best to help the villagers and move them to a safe place.

正在那时,军队乘舟赶来,他们尽力救助村民,将村民转移到安全的地方。

The government is very concerned about the villagers and provides them with materials(me ti lui er) immediately.

政府非常关心村民,为他们马上提供物资。

Without the aid of the our country, many people will lose their lives or starve to death in the flood.

如果没有国家的援助,许多人将会在洪水中失去生命或者饿死。

Flood is a kind of natural disaster, which may affect traffic,agriculture and even destroy villages.

Floods are often accompanied by rainstorms. I remember another year, rainstorms lasted for three days.

Many fields and villages were flooded, houses were washed away by floods, villagers were in danger, many people were struggling(死抓零) in the water, crying for help.

At that time, the army came by boat, and they tried their best to help the villagers and move them to a safe place.

The government is very concerned about the villagers and provides them with materials(me ti lui er) immediately.

Without the aid of the our country, many people will lose their lives or starve(si da ve) to death in the flood.

机场:

上周,我和我朋友订机票去旅游。

我们先在网络上预定机票,然后再去机场。

刚刚进入机场,看到的是整洁的大厅。

机场人很多,每个人都背着行李。

然后我们去往柜台,工作人员态度很好。

第一次坐飞机,我们都感到紧张和新鲜,这真是难忘的旅程。

Last week, my friend and I made a reservation to travel.

We book tickets on the Internet before we go to the airport.

Just entering the airport, I saw a tidy hall(he o).

There are a lot of people at the airport. Everyone is carrying luggage.

Because the airport was very big, we lost our way. But with the help of the staff, we went to the counter. The staff had a good attitude.
The first time we took a plane, we all felt nervous and fresh. It was an unforgettable journey.

补充某扣上的顺丰和携程企业题库

大家都说穷学生,血本开了两个月,分享给大家,先是携程的。
代码
package didi.sf.xiec;

import tree.TreeNode;

import java.util.*;

public class Main {

    public int[] bfs(TreeNode root){

        if (root == null) return null;

        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        for (TreeNode tmp = root; !queue.isEmpty(); ){
            // 此处注意循环中 queue.size() 在变,应事先记录 size--
            for (int size = queue.size(); size > 0; size--){
                tmp = queue.poll();
                if (tmp.left != null) queue.offer(tmp.left);
                if (tmp.right != null) queue.offer(tmp.right);
            }
            // 添加每层最右元素
            list.add(tmp.val);
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();

    //重建二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < preorder.length; i++) {
            dic.put(inorder[i], i);

        }
        return recur(0, 0, inorder.length - 1);
    }

    /**
     * @param root  先序遍历的索引
     * @param left  中序遍历的索引
     * @param right 中序遍历的索引
     */
    private TreeNode recur(int root, int left, int right) {
        if (left > right) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[root]);
        int i = dic.get(preorder[root]);
        //左子树的根节点就是 左子树的(前序遍历)第一个,就是+1,左边边界就是left,右边边界是中间区分的idx-1
        treeNode.left = recur(root + 1, left, i - 1);
        treeNode.right = recur(root + i - left + 1, i + 1, right);
        return treeNode;
    }

    public static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.println(pop.val);
            if (pop.left != null) {
                stack.add(pop.left);
            }
            if (root.right != null) {
                stack.add(pop.right);
            }
        }
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    //路径总和
    public int pathSum2(TreeNode root, int sum) {
        int depth = depth(root);
        int[] path = new int[depth];
        findSum(root, sum, path, 0);
        return count;
    }

    int count = 0;

    private void findSum(TreeNode node, int sum, int[] path, int level) {
        if (node == null) {
            return;
        }
        // 当前结点插入路径
        path[level] = node.val;
        // 查找以此为重点且总和为sum的路径
        int t = 0;
        for (int i = level; i >= 0; i--) {
            t += path[i];
            if (t == sum) {
                count++;
            }
        }
        // 查找此结点之下的结点
        findSum(node.left, sum, path, level + 1);
        findSum(node.right, sum, path, level + 1);

        // 从路径中移除当前结点
        path[level] = Integer.MIN_VALUE;
    }

    //查找二叉树最大深度
    private int depth(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + Math.max(depth(node.left), depth(node.right));
        }
    }


    //路径总和
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }

    void recur(TreeNode root, int tar) {

        if (root == null) return;
        path.add(root.val);
        tar -= root.val;
        if (tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }

    //判断是不是搜索二叉树
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isBST(root, root.left.val, root.right.val);
    }

    private boolean isBST(TreeNode root, int left, int right) {

        if (left <= root.val || right <= root.val) {
            return false;
        }
        return (root.left == null ? true : isBST(root.left, root.left.val, root.right.val)) && (root.right == null ? true : isBST(root.right, root.right.val, root.right.val));
    }

    //二叉树中的最大路径和
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时,才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }


    //二叉树的所有路径
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }

    public void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            } else {
                pathSB.append("->");  // 当前节点不是叶子节点,继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }


    //二叉树的所有路径
    public List<String> binaryTreePaths2(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();

        nodeQueue.offer(root);
        pathQueue.offer(Integer.toString(root.val));

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            String path = pathQueue.poll();

            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                }

                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return paths;
    }

    //1、两数之和

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //2、两数字相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    //最长回文子串
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    dp[i][j] = true;
                } else if (l == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && l + 1 > ans.length()) {
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        return ans;
    }


    public String longestPalindrome2(String s) {
        // 特判
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;

        // dp[i][j] 表示 s[i, j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        char[] charArray = s.toCharArray();

        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][j] == true 成立,就表示子串 s[i..j] 是回文,此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    //206反转链表
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    //92 反转2
    public ListNode reverseBetween(ListNode head, int left, int right) {
        /// 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
        ListNode dumnyNode = new ListNode(-1);
        dumnyNode.next = head;

        ListNode pre = dumnyNode;
        // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
        // 建议写在 for 循环里,语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
        ListNode rightNode = pre;

        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }
        // 第 3 步:切断出一个子链表(截取链表)
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        //4、切断连接。
        pre.next = null;
        rightNode.next = null;

        //5\fanzhuan
        reverseLinkedList(leftNode);

        pre.next = rightNode;
        leftNode.next = curr;
        return dumnyNode.next;

    }

    private void reverseLinkedList(ListNode head) {
        // 也可以使用递归反转一个链表
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }


    //46 全排列
    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        int[] visited = new int[nums.length];
        backtrack(res, nums, new ArrayList<Integer>(), visited);
        return res;

    }

    private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {
        if (tmp.size() == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 1) continue;
            visited[i] = 1;
            tmp.add(nums[i]);
            backtrack(res, nums, tmp, visited);
            visited[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }

    //47 全排列 排列
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            //当前值用过了 或
            //当前值等于前一个值: 两种情况:
            //1 nums[i-1] 没用过 说明回溯到了同一层 此时接着用num[i] 则会与 同层用num[i-1] 重复,这个在下一个循环排除
            //2 nums[i-1] 用过了 说明此时在num[i-1]的下一层 相等不会重复,这个在本次排除
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }

    //7 整数反转
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }

    //23合并k个有序链表
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node : lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }

    //22 合并两个有序链表
    public ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //将偶数和奇数的情况合并,如果是奇数,会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        //两个有一个用到,大部分试试是k/2
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

    //70爬楼梯
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    //53 最长子序列

    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }

    //9 回文数
    public boolean isPalindrome(int x) {
        // 特殊情况:
        // 如上所述,当 x < 0 时,x 不是回文数。
        // 同样地,如果数字的最后一位是 0,为了使该数字为回文,
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
        // 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }


    //415 字符串相加

    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        return ans.toString();
    }

    //25、k个一组反转
    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }

    //56 区间合并
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals.length == 0 || intervals == null) return res.toArray(new int[0][]);
        // 对起点终点进行排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int i = 0;
        while (i < intervals.length) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            // 如果有重叠,循环判断哪个起点满足条件
            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            // 将现在的区间放进res里面
            res.add(new int[]{left, right});
            // 接着判断下一个区间
            i++;
        }
        return res.toArray(new int[0][]);
    }

    //19、删除倒数第k个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    //22括号生成
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> ans = new ArrayList<String>();
            backtrack(ans, new StringBuilder(), 0, 0, n);
            return ans;
        }

        public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
            if (cur.length() == max * 2) {
                ans.add(cur.toString());
                return;
            }
            if (open < max) {
                cur.append('(');
                backtrack(ans, cur, open + 1, close, max);
                cur.deleteCharAt(cur.length() - 1);
            }
            if (close < open) {
                cur.append(')');
                backtrack(ans, cur, open, close + 1, max);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }

    //offer22  链表倒数第k

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head, latter = head;
        for (int i = 0; i < k; i++) {
            if (former == null) return null;
            former = former.next;
        }
        while (former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }

    //链表成环141
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    //349、重合
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>(), set2 = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for (int i : nums1) {
            list.add(i);
        }
        for (int i : nums2) {
            set2.add(i);
        }
        list.retainAll(set2);
        set1.addAll(list);
        return set1.stream().mapToInt(i -> i).toArray();
    }
    //118、杨辉三角

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }

    //48. 旋转图像
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

    //72 编辑距离
//    dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
//
//    所以,
//
//    当 word1[i] == word2[j],dp[i][j] = dp[i-1][j-1];
//
//    当 word1[i] != word2[j],dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
//
//    其中,dp[i-1][j-1] 表示替换操作,dp[i-1][j] 表示删除操作,dp[i][j-1] 表示插入操作。
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 第一行
        for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
        // 第一列
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
        return dp[n1][n2];
    }

//
//    作者:powcai
//    链接:https://leetcode-cn.com/problems/edit-distance/solution/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai-3/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    //43 字符串相乘
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        String ans = "0";
        int m = num1.length(), n = num2.length();
        for (int i = n - 1; i >= 0; i--) {
            StringBuffer curr = new StringBuffer();
            int add = 0;
            for (int j = n - 1; j > i; j--) {
                curr.append(0);
            }
            int y = num2.charAt(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.charAt(j) - '0';
                int product = x * y + add;
                curr.append(product % 10);
                add = product / 10;
            }
            if (add != 0) {
                curr.append(add % 10);
            }
            ans = addStrings2(ans, curr.reverse().toString());
        }
        return ans;
    }

    public String addStrings2(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }

    //38 外观数组
    private StringBuilder getNext(StringBuilder res) {
        StringBuilder s = new StringBuilder();
        int start = 0, n = res.length();
        for (int i = 1; i < n; i++)
            if (res.charAt(i) != res.charAt(start)) {
                s.append(i - start).append(res.charAt(start));
                start = i;
            }
        return s.append(res.length() - start).append(res.charAt(start));
    }

    public String countAndSay(int n) {
        StringBuilder res = new StringBuilder();
        res.append(1);
        for (int i = 1; i < n; i++) res = getNext(res);
        return res.toString();
    }
    //86 分隔链表

    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }


    //123 动态规划 股票买入
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-iii-by-wrnt/
//    来源:力扣(LeetCode)

    //107 层次遍历2

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }

    //236  二叉树的最近公共祖先
    private TreeNode ans = null;


    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }
//
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    //139. 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    //165 比较版本号:https://leetcode-cn.com/problems/compare-version-numbers/solution/bi-jiao-ban-ben-hao-by-leetcode/
    public int compareVersion(String version1, String version2) {
        String[] nums1 = version1.split("\\.");
        String[] nums2 = version2.split("\\.");
        int n1 = nums1.length, n2 = nums2.length;

        // compare versions
        int i1, i2;
        for (int i = 0; i < Math.max(n1, n2); ++i) {
            i1 = i < n1 ? Integer.parseInt(nums1[i]) : 0;
            i2 = i < n2 ? Integer.parseInt(nums2[i]) : 0;
            if (i1 != i2) {
                return i1 > i2 ? 1 : -1;
            }
        }
        // the versions are equal
        return 0;
    }

    //1029 两地最小费用
    public int twoCitySchedCost(int[][] costs) {
        // Sort by a gain which company has
        // by sending a person to city A and not to city B
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o1[1] - (o2[0] - o2[1]);
            }
        });

        int total = 0;
        int n = costs.length / 2;
        // To optimize the company expenses,
        // send the first n persons to the city A
        // and the others to the city B
        for (int i = 0; i < n; ++i) total += costs[i][0] + costs[i + n][1];
        return total;
    }
//
//    作者:LeetCode
//    链接:https://leetcode-cn.com/problems/two-city-scheduling/solution/er-cha-shu-de-chui-xu-bian-li-by-leetcode/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
//
//
//   622、设计循环队列
class MyCircularQueue {
//    queue:一个固定大小的数组,用于保存循环队列的元素。
//
//    headIndex:一个整数,保存队首 head 的索引。
//
//    count:循环队列当前的长度

    //capacity:循环队列的容量
    //tailIndex=(headIndex+count−1)modcapacity
    private int[] queue;
    private int headIndex;
    private int count;
    private int capacity;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        this.capacity = k;
        this.queue = new int[k];
        this.headIndex = 0;
        this.count = 0;
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (this.count == this.capacity)
            return false;
        this.queue[(this.headIndex + this.count) % this.capacity] = value;
        this.count += 1;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (this.count == 0)
            return false;
        this.headIndex = (this.headIndex + 1) % this.capacity;
        this.count -= 1;
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if (this.count == 0)
            return -1;
        System.out.println();
        return this.queue[this.headIndex];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if (this.count == 0)
            return -1;
        int tailIndex = (this.headIndex + this.count - 1) % this.capacity;
        return this.queue[tailIndex];
    }

    /** Checks whether the circular queue is empty&nbs***bsp;not. */
    public boolean isEmpty() {
        return (this.count == 0);
    }

    /** Checks whether the circular queue is full&nbs***bsp;not. */
    public boolean isFull() {
        return (this.count == this.capacity);
    }
}
//
//    作者:LeetCode
//    链接:https://leetcode-cn.com/problems/design-circular-queue/solution/she-ji-xun-huan-dui-lie-by-leetcode/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


}


顺丰的


顺丰的代码
package didi.sf;

import day1119.TreeNode;

import java.util.*;

public class Main {

    //3. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }
        return max;

    }

    //16. 最接近的三数之和
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10000000;

        // 枚举 a
        for (int i = 0; i < n; ++i) {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                // 根据差值的绝对值来更新答案
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    // 如果和大于 target,移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target,移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }


//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

//32. 最长有效括号

    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }

    public int longestValidParentheses2(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
//
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //33. 搜索旋转排序数组
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
//
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


    //39. 组合总和
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param begin      搜索起点
     * @param len        冗余变量,是 candidates 里的属性,可以不传
     * @param target     每减去一个元素,目标值变小
     * @param path       从根结点到叶子结点的路径,是一个栈
     * @param res        结果集列表
     */
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意:由于每一个元素可以重复使用,下一轮搜索的起点依然是 i,这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }

    //    作者:liweiwei1419
//    链接:https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //40. 组合总和2
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 关键步骤
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs2(candidates, len, 0, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param len        冗余变量
     * @param begin      从候选数组的 begin 位置开始搜索
     * @param target     表示剩余,这个值一开始等于 target,基于题目中说明的"所有数字(包括目标数)都是正整数"这个条件
     * @param path       从根结点到叶子结点的路径
     * @param res
     */
    private void dfs2(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            // 大剪枝:减去 candidates[i] 小于 0,减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0,因此用 break
            if (target - candidates[i] < 0) {
                break;
            }

            // 小剪枝:同一层相同数值的结点,从第 2 个开始,候选数更少,结果一定发生重复,因此跳过,用 continue
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.addLast(candidates[i]);
            // 调试语句 ①
            // System.out.println("递归之前 => " + path + ",剩余 = " + (target - candidates[i]));

            // 因为元素不可以重复使用,这里递归传递下去的是 i + 1 而不是 i
            dfs2(candidates, len, i + 1, target - candidates[i], path, res);

            path.removeLast();
            // 调试语句 ②
            // System.out.println("递归之后 => " + path + ",剩余 = " + (target - candidates[i]));
        }
    }

    //
//    作者:liweiwei1419
//    链接:https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //    41. 缺失的第一个正数
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }


    //42. 接雨水
    //使用栈来存储条形块的索引下标。
    //遍历数组:
    //当栈非空且 \text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]
    //意味着栈中元素可以被弹出。弹出栈顶元素 \text{top}top。
    //计算当前元素和栈顶元素的距离,准备进行填充操作
    //\text{distance} = \text{current} - \text{st.top}() - 1distance=current−st.top()−1
    //找出界定高度
    //\text{bounded\_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]
    //往答案中累加积水量\text{ans} \mathrel{+}= \text{distance} \times \text{bounded\_height}ans+=distance×bounded_height
    //将当前索引下标入栈
    //将 \text{current}current 移动到下个位置
    public int trap(int[] height) {
        int ans = 0, current = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty())
                    break;
                int distance = current - stack.peek() - 1;
                int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
                ans += distance * bounded_height;
            }
            stack.push(current++);
        }
        return ans;
    }

    //43、字符串相乘
    //43 字符串相乘
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        String ans = "0";
        int m = num1.length(), n = num2.length();
        for (int i = n - 1; i >= 0; i--) {
            StringBuffer curr = new StringBuffer();
            int add = 0;
            for (int j = n - 1; j > i; j--) {
                curr.append(0);
            }
            int y = num2.charAt(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.charAt(j) - '0';
                int product = x * y + add;
                curr.append(product % 10);
                add = product / 10;
            }
            if (add != 0) {
                curr.append(add % 10);
            }
            ans = addStrings2(ans, curr.reverse().toString());
        }
        return ans;
    }

    public String addStrings2(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }

    //作者:LeetCode
    //链接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
    //来源:力扣(LeetCode)
    //著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
//    68. 文本左右对齐 https://leetcode-cn.com/problems/text-justification/solution/cjian-dan-dai-ma-jian-dan-si-lu-di-gui-s-oa9j/

    //93. 复原 IP 地址
    static final int SEG_COUNT = 4;
    List<String> ans = new ArrayList<String>();
    int[] segments = new int[SEG_COUNT];

    public List<String> restoreIpAddresses(String s) {
        segments = new int[SEG_COUNT];
        dfs(s, 0, 0);
        return ans;
    }

    public void dfs(String s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
        if (segId == SEG_COUNT) {
            if (segStart == s.length()) {
                StringBuffer ipAddr = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr.append(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr.append('.');
                    }
                }
                ans.add(ipAddr.toString());
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
        if (segStart == s.length()) {
            return;
        }

        // 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
        if (s.charAt(segStart) == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
        }

        // 一般情况,枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }

    //
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/restore-ip-addresses/solution/fu-yuan-ip***-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    //110\110. 平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //109. 有序链表转换二叉搜索树 fenzhi
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

//
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //149. 直线上最多的点数
//    作者:LeetCode
//    链接:https://leetcode-cn.com/problems/max-points-on-a-line/solution/zhi-xian-shang-zui-duo-de-dian-shu-by-leetcode/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //152. 乘积最大子数组
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] maxF = new int[length];
        int[] minF = new int[length];
        System.arraycopy(nums, 0, maxF, 0, length);
        System.arraycopy(nums, 0, minF, 0, length);
        for (int i = 1; i < length; ++i) {
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
        }
        int ans = maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }
//
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //169. 多数元素
    // Arrays.sort(nums);
    //        return nums[nums.length / 2];
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            } else {
                counts.put(num, counts.get(num) + 1);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }

    //
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
//198. 打家劫舍
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    //213. 打家劫舍 II
    public int rob2(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    private int myRob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for (int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }

    //    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/house-robber-iii/solution/da-jia-jie-she-iii-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
//    作者:jyd
//    链接:https://leetcode-cn.com/problems/house-robber-ii/solution/213-da-jia-jie-she-iidong-tai-gui-hua-jie-gou-hua-/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    //240. 搜索二维矩阵 II
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        return false;
    }

//    作者:LeetCode
//    链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }

    //    public class Solution {
//        public int lengthOfLIS(int[] nums) {
//            int len = nums.length;
//            if (len <= 1) {
//                return len;
//            }
//
//            // tail 数组的定义:长度为 i + 1 的上升子序列的末尾最小是几
//            int[] tail = new int[len];
//            // 遍历第 1 个数,直接放在有序数组 tail 的开头
//            tail[0] = nums[0];
//            // end 表示有序数组 tail 的最后一个已经赋值元素的索引
//            int end = 0;
//
//            for (int i = 1; i < len; i++) {
//                // 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大
//                if (nums[i] > tail[end]) {
//                    // 直接添加在那个元素的后面,所以 end 先加 1
//                    end++;
//                    tail[end] = nums[i];
//                } else {
//                    // 使用二分查找法,在有序数组 tail 中
//                    // 找到第 1 个大于等于 nums[i] 的元素,尝试让那个元素更小
//                    int left = 0;
//                    int right = end;
//                    while (left < right) {
//                        // 选左中位数不是偶然,而是有原因的,原因请见 LeetCode 第 35 题题解
//                        // int mid = left + (right - left) / 2;
//                        int mid = left + ((right - left) >>> 1);
//                        if (tail[mid] < nums[i]) {
//                            // 中位数肯定不是要找的数,把它写在分支的前面
//                            left = mid + 1;
//                        } else {
//                            right = mid;
//                        }
//                    }
//                    // 走到这里是因为 【逻辑 1】 的反面,因此一定能找到第 1 个大于等于 nums[i] 的元素
//                    // 因此,无需再单独判断
//                    tail[left] = nums[i];
//                }
//                // 调试方法
//                // printArray(nums[i], tail);
//            }
//            // 此时 end 是有序数组 tail 最后一个元素的索引
//            // 题目要求返回的是长度,因此 +1 后返回
//            end++;
//            return end;
//        }
//
//        // 调试方法,以观察是否运行正确
//        private void printArray(int num, int[] tail) {
//            System.out.print("当前数字:" + num);
//            System.out.print("\t当前 tail 数组:");
//            int len = tail.length;
//            for (int i = 0; i < len; i++) {
//                if (tail[i] == 0) {
//                    break;
//                }
//                System.out.print(tail[i] + ", ");
//            }
//            System.out.println();
//        }
//
//        public static void main(String[] args) {
//            int[] nums = new int[]{3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12};
//            Solution solution = new Solution8();
//            int lengthOfLIS = solution8.lengthOfLIS(nums);
//            System.out.println("最长上升子序列的长度:" + lengthOfLIS);
//        }
//    }
//
//    作者:liweiwei1419
//    链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
//337. 打家劫舍 III
    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }


    //365. 水壶问题


    public boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z) {
            return false;
        }
        if (x == 0 || y == 0) {
            return z == 0 || x + y == z;
        }
        return z % gcd(x, y) == 0;
    }

    public int gcd(int x, int y) {
        int remainder = x % y;
        while (remainder != 0) {
            x = y;
            y = remainder;
            remainder = x % y;
        }
        return y;
    }

//
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/water-and-jug-problem/solution/shui-hu-wen-ti-by-leetcode-solution/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //547. 省份数量
    public int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        int[] parent = new int[provinces];
        for (int i = 0; i < provinces; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < provinces; i++) {
            for (int j = i + 1; j < provinces; j++) {
                if (isConnected[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (parent[i] == i) {
                circles++;
            }
        }
        return circles;
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }

    //674. 最长连续递增序列
    class Solution {
        public int findLengthOfLCIS(int[] nums) {
            int ans = 0;
            int n = nums.length;
            int start = 0;
            for (int i = 0; i < n; i++) {
                if (i > 0 && nums[i] <= nums[i - 1]) {
                    start = i;
                }
                ans = Math.max(ans, i - start + 1);
            }
            return ans;
        }
    }
//
//    作者:LeetCode-Solution
//    链接:https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/solution/zui-chang-lian-xu-di-zeng-xu-lie-by-leet-dmb8/
//    来源:力扣(LeetCode)
//    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    //1266. 访问所有点的最小时间
    public int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        int[] prev = points[0];
        int[] cur;
        for (int i = 1; i < points.length; ++i) {
            cur = points[i];
            ans += Math.max(
                    Math.abs(cur[0] - prev[0]),
                    Math.abs(cur[1] - prev[1])
            );
            prev = cur;
        }
        return ans;
    }

    //二进制1的个数
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
    //剑指 Offer 40. 最小的k个数

    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();
        }
        return vec;
    }

//https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/

    //115. 不同的子序列

    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }
        for (int i = m - 1; i >= 0; i--) {
            char sChar = s.charAt(i);
            for (int j = n - 1; j >= 0; j--) {
                char tChar = t.charAt(j);
                if (sChar == tChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
//        kmp

        int kmp = KMP("adbcabda", "ab");

        System.out.println(kmp);
    }

    //https://www.cnblogs.com/yjiyjige/p/3263858.html
    public static int KMP(String ts, String ps) {

        char[] t = ts.toCharArray();

        char[] p = ps.toCharArray();

        int i = 0; // 主串的位置

        int j = 0; // 模式串的位置

        int[] next = getNext(ps);

        while (i < t.length && j < p.length) {

            if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,当然j也要归0

                i++;

                j++;

            } else {

                // i不需要回溯了

                // i = i - j + 1;

                j = next[j]; // j回到指定位置

            }

        }

        if (j == p.length) {

            return i - j;

        } else {

            return -1;

        }

    }

    public static int[] getNext(String ps) {

        char[] p = ps.toCharArray();

        int[] next = new int[p.length];

        next[0] = -1;

        int j = 0;

        int k = -1;

        while (j < p.length - 1) {

            if (k == -1 || p[j] == p[k]) {

                next[++j] = ++k;

            } else {

                k = next[k];

            }

        }

        return next;

    }
}


#实习##面经##荔枝##捷程##唯品会##同程旅行##滴滴#
全部评论
给帆宝点个赞
点赞 回复
分享
发布于 2021-04-01 23:19
太厉害了,你有询问携程为什么挂你吗
点赞 回复
分享
发布于 2021-04-11 09:26
阿里巴巴
校招火热招聘中
官网直投
楼主你好,请问你是实习、校招还是社招
点赞 回复
分享
发布于 2021-04-21 20:31

相关推荐

12 64 评论
分享
牛客网
牛客企业服务