Posts

冒泡排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 // 冒泡排序：超时 public int[] sortArray(int[] nums) { int len = nums.length; for (int i = len - 1; i >= 0; i--) { // 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较， // 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组 boolean sorted = true; for (int j = 0; j < i; j++) { if (nums[j] > nums[j + 1]) { swap(nums, j, j + 1); sorted = false; } } if (sorted) { break; } } return nums; } private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } 时间复杂度：$O(N^2)$，这里 N 是数组的长度； 空间复杂度：$O(1)$，使用到常数个临时变量。 选择排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 // 选择排序：每一轮选择最小元素交换到未排定部分的开头 public int[] sortArray(int[] nums) { int len = nums....

本篇概要 二叉树是大厂面试的常考题之一。面试者除了日常刷题以外，还需要思考二叉树的定义、生成和输出，以便于在面试官提出不同要求时应对自如。每个二叉树的题目基本上都有递归和迭代两种方式，对于简单题来说，建议面试者两种方法都掌握，对于其他难度的题目，建议面试者量力而行。 二叉树的遍历 提升：在本地编译器跑起来，并思考如何将返回值改为void。 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 剑指 Offer 33. 二叉搜索树的后序遍历序列：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。 剑指 Offer 32 - I. 从上到下打印二叉树：自上而下，自左而右，不分层输出 剑指 Offer 32 - II. 从上到下打印二叉树 II和 102. 二叉树的层序遍历：自上而下，自左而右，分层输出 二叉树的层次遍历 II：自下而上，自左而右，分层输出 剑指 Offer 32 - III. 从上到下打印二叉树 III和 103. 二叉树的锯齿形层次遍历：先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。 构造二叉树 相同点：输入都不是TreeNode，输出都是TreeNode 从前序与中序遍历序列构造二叉树和 剑指 Offer 07. 重建二叉树 从中序与后序遍历序列构造二叉树 根据前序和后序遍历构造二叉树 将有序数组转换为二叉搜索树和 面试题 04....

https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190

缓存穿透 缓存穿透是指，缓存和数据库都没有的数据，被大量请求，比如订单号不可能为-1，但是用户请求了大量订单号为-1的数据，由于数据不存在，缓存就也不会存在该数据，所有的请求都会直接穿透到数据库。 注意：穿透的意思是，都没有，直接一路打到数据库。 那对于这种情况，我们该如何解决呢？ 接口增加业务层级的Filter，进行合法校验，这可以有效拦截大部分不合法的请求。 布隆过滤器 缓存无效数据 缓存击穿 缓存击穿是指数据库原本有得数据，但是缓存中没有，一般是缓存突然失效了，这时候如果有大量用户请求该数据，缓存没有则会去数据库请求，会引发数据库压力增大，可能会瞬间打垮。 针对这类问题，一般有以下做法： 如果是热点数据，可以设置永远不过期。 如果数据一定会过期，那么就需要在数据为空的时候，设置一个互斥的锁，只让一个请求通过，只有一个请求去数据库拉取数据，取完数据，不管如何都需要释放锁，异常的时候也需要释放锁，要不其他线程会一直拿不到锁。 缓存雪崩 缓存雪崩是指缓存中有大量的数据，在同一个时间点，或者较短的时间段内，全部过期了，这个时候请求过来，缓存没有数据，都会请求数据库，则数据库的压力就会突增，扛不住就会宕机。 针对这种情况，一般我们都是使用以下方案： 如果是热点数据，那么可以考虑设置永远不过期。 缓存的过期时间除非比较严格，要不考虑设置一个波动随机值 分布式。 也可以考虑双缓存的方式，A设置过期时间，B不设置过期时间

Bean 生命周期 https://www.pdai.tech/md/spring/spring-x-framework-ioc-source-3.html#spring-bean%E7%94%9F%E5%91%BD%E5%91%A8%E6%9C%9F%E6%B5%81%E7%A8%8B MVC流程 前端控制器 DispatcherServlet：接收请求、响应结果，相当于转发器，有了DispatcherServlet 就减少了其它组件之间的耦合度。 处理器映射器 HandlerMapping：根据请求的URL来查找Handler 处理器适配器 HandlerAdapter：负责执行Handler 处理器 Handler：处理器，需要程序员开发 视图解析器 ViewResolver：进行视图的解析，根据视图逻辑名将ModelAndView解析成真正的视图（view） 视图View：View是一个接口， 它的实现类支持不同的视图类型，如jsp，freemarker，pdf等等 （1）用户发送请求至前端控制器DispatcherServlet； （2）DispatcherServlet收到请求后，调用HandlerMapping处理器映射器，请求获取Handler； （3）处理器映射器根据请求url找到具体的处理器Handler，生成处理器对象及处理器拦截器(如果有则生成)，一并返回给DispatcherServlet； （4）DispatcherServlet 调用 HandlerAdapter处理器适配器，请求执行Handler； （5）HandlerAdapter 经过适配调用 具体处理器进行处理业务逻辑； （6）Handler执行完成返回ModelAndView； （7）HandlerAdapter将Handler执行结果ModelAndView返回给DispatcherServlet； （8）DispatcherServlet将ModelAndView传给ViewResolver视图解析器进行解析； （9）ViewResolver解析后返回具体View； （10）DispatcherServlet对View进行渲染视图（即将模型数据填充至视图中） （11）DispatcherServlet响应用户。 https://www.jianshu.com/p/73d6f1a03005 向上转型 父子对象之间的转换分为了向上转型和向下转型,它们区别如下: 向上转型 : 通过子类对象(小范围)实例化父类对象(大范围),这种属于自动转换 向下转型 : 通过父类对象(大范围)实例化子类对象(小范围),这种属于强制转换

https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/ 阅读提示：内容比较多，核心思想帮大家归纳一下。如果没有时间看，建议把后面的问题做一下。 题解核心内容：所有模板都一样，不可以套模板，而应该 仔细看题（解题的关键在认真读题），分析清楚题目要找的答案需要满足什么性质。采用两边夹的方式，每一轮把待搜索区间分成两个部分，排除掉一定不是答案的区间，最后左右指针重合的地方就是我们要找的元素。 说明：我所有的关于「二分查找」法的题解，都会明确地标注「下一轮搜索区间是什么」，进而设置左边界 left 和 右边界 right。在我写的「二分查找」题解里，while(left < right) 不表示 循环不变量的区间定义是 [left..right)，也就是说，如果我分析出，下一轮搜索区间是 [mid..10]，我会设置 right = 10，而不会设置 right = 11。 如果你看我写的「二分查找」题解，请忘记掉「左闭右开」这件事情，它会对你有所干扰。 二分查找只有一个思想，那就是：逐步缩小搜索区间。 本题解向大家介绍的，使用 left 和 right 向中间靠拢的方法，有一个非常强的语义，那就是：当 left与right 重合的时候，我们就找到了问题的答案，使用这种写法有一个巨大的好处，那就是返回值不需要考虑返回 left 还是 right，因为退出循环以后，它们是重合的。 在做题的过程中，会遇到两个难点：1、取 mid 的时候，有些时候需要 +1，这是因为需要避免死循环；2、只把区间分成两个部分，这是因为：只有这样，退出循环的时候才有 left 与 right 重合，我们才敢说，找到了问题的答案。（这两个难点，在练习的过程中，会逐渐清晰，不用着急一下子搞懂，事实上并不难理解）。 第一部分：本题题解 这一部分一定要分析清楚： 题目要找的元素是：第一个大于等于 target 的元素的下标； 数组的长度 len 也有可能是问题的答案，「参考代码 2」设置 right = len 不是因为设置区间是「左闭右开」，而是因为 len 本来就有可能是问题的答案。 上面 2 个小点，都需要仔细分析题意和几个示例得到，任何模板都不能回答这样的问题。...

https://leetcode-cn.com/circle/discuss/6Ghjnw/ 本篇主要列举一些输入是一维数组或者二维数组的题目，其中包括了一些可以用二分法和摩尔投票法的题目。 考虑边界？ 二分 - 查找元素或者索引 开闭 -> 搜索区间 计算 mid 时需要防止溢出 运算优先级 ！！！部分解释错误 慎看 二分查找细节 https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/ while(left < right) 不表示 循环不变量的区间定义是 [left..right)，也就是说，如果我分析出，下一轮搜索区间是 [mid..10]，我会设置 right = 10，而不会设置 right = 11。 作者：liweiwei1419 链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/ 二分查找：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 剑指 Offer 53 - I. 在排序数组中查找数字 I:统计一个数字在排序数组中出现的次数。...

京东 1、调用反射的有几种方法？ 1 2 3 4 TargetObject.class; Class.forName("cn.javaguide.TargetObject"); instance.getClass() ClassLoader.loadClass("cn.javaguide.TargetObject"); 2、线程池的参数、线程池的执行流程、拒绝策略等 1 2 3 4 5 6 7 8 //通过ThreadPoolExecutor构造函数自定义参数创建 ThreadPoolExecutor executor = new ThreadPoolExecutor( CORE_POOL_SIZE, MAX_POOL_SIZE, KEEP_ALIVE_TIME, TimeUnit.SECONDS, new ArrayBlockingQueue<>(QUEUE_CAPACITY), new ThreadPoolExecutor.CallerRunsPolicy()); 拒绝策略 ThreadPoolExecutor.AbortPolicy： 抛出 RejectedExecutionException来拒绝新任务的处理。 ThreadPoolExecutor.CallerRunsPolicy： 调用执行自己的线程运行任务，也就是直接在调用execute方法的线程中运行(run)被拒绝的任务，如果执行程序已关闭，则会丢弃该任务。因此这种策略会降低对于新任务提交速度，影响程序的整体性能。如果您的应用程序可以承受此延迟并且你要求任何一个任务请求都要被执行的话，你可以选择这个策略。 ThreadPoolExecutor.DiscardPolicy： 不处理新任务，直接丢弃掉。 ThreadPoolExecutor.DiscardOldestPolicy： 此策略将丢弃最早的未处理的任务请求。 3、抽象类与接口的区别？ 共同点 ： 都不能被实例化。 都可以包含抽象方法。 都可以有默认实现的方法（Java 8 可以用 default 关键在接口中定义默认方法）。 参数 抽象类 接口 成员变量 默认 default。可以变量，也可以常量 只可以常量 成员方法 可以抽象，也可以非抽象。抽象类中可以没有抽象方法，但有抽象方法的一定是抽象类 只可以抽象 方法实现 可以有默认的方法实现 接口完全是抽象的（Java 8 可以用 default） 构造器 抽象类可以有构造器 接口不能有构造器 与正常Java类的区别 除了你不能实例化抽象类之外，它和普通Java类没有任何区别 接口是完全不同的类型 访问修饰符 抽象方法可以有public、protected和default这些修饰符 接口方法默认修饰符是public。default。 main方法 抽象方法可以有main方法并且我们可以运行它 接口没有main方法，因此我们不能运行它。 多继承 抽象方法可以继承一个类和实现多个接口 接口只可以继承一个或多个其它接口 添加新方法 如果你往抽象类中添加新的方法，你可以给它提供默认的实现。因此你不需要改变你现在的代码。 如果你往接口中添加方法，那么你必须改变实现该接口的类。 设计理念 被继承体现的是：”is a”的关系。抽象类中定义的是该继承体系的共性功能 被实现体现的是：”like a”的关系。接口中定义的是该继承体系的扩展功能。 4、重载与重写的区别 重载Overload...

京东 1、进程与线程的区别？ 一个进程至少拥有一个线程，进程可以根据需要创建其他进程，也可以创建若干个线程。而线程虽然可以创建其他线程，但是不能创建进程。 进程是个拥有资源的独立单位，而线程本身基本不拥有资源（只含有必不可少的资源，比如TCB和栈）。 在通信方面进程中所有的线程共享该进程的所有资源在通信方面进程中所有的线程共享该进程的所有资源，并驻留在同一地址空间，访问相同的数据。但是进程只能通过同步，互斥来实现对共享资源的访问 从调度的角度，在引入线程的操作系统中，线程是调度和分派的基本单位，进程是资源分配的基本单位。在同一个进程中，线程的切换不会引起进程的切换，只有在进程中一个线程切换到另一个进程的线程中的时候，才会引起进程的切换。 从系统开销来说。在创建和撤销进程的时候，操作系统所付出的时间和空间开销将远远大于重建或者撤销线程的开销 2、HTTP和HTTPS的区别？ HTTPS 协议（Hyper Text Transfer Protocol Secure），HTTPS 是基于 HTTP 的，用 TCP 作为底层协议，并使用 SSL/TLS 协议用作加密和安全认证。 SSL/TLS 的核心要素是非对称加密。非对称加密采用两个密钥——一个公钥，一个私钥。在通信时，私钥仅由解密者保存，公钥由任何一个想与解密者通信的发送者（加密者）所知。可以设想一个场景， 数字签名，是 CA 在给服务器颁发证书时，使用散列+加密的组合技术，在证书上盖个章，以此来提供验伪的功能。 3、了解TCP吗？谈谈三次握手的流程？ https://blog.csdn.net/qzcsu/article/details/72861891 测试双方 收发功能是否可用 TCP服务器进程先创建传输控制块TCB，时刻准备接受客户进程的连接请求，此时服务器就进入了LISTEN（监听）状态； TCP客户进程也是先创建传输控制块TCB，然后向服务器发出连接请求报文，这是报文首部中的同部位SYN=1，同时选择一个初始序列号 seq=x ，此时，TCP客户端进程进入了 SYN-SENT（同步已发送状态）状态。TCP规定，SYN报文段（SYN=1的报文段）不能携带数据，但需要消耗掉一个序号。 TCP服务器收到请求报文后，如果同意连接，则发出确认报文。确认报文中应该 ACK=1，SYN=1，确认号是ack=x+1，同时也要为自己初始化一个序列号 seq=y，此时，TCP服务器进程进入了SYN-RCVD（同步收到）状态。这个报文也不能携带数据，但是同样要消耗一个序号。 TCP客户进程收到确认后，还要向服务器给出确认。确认报文的ACK=1，ack=y+1，自己的序列号seq=x+1，此时，TCP连接建立，客户端进入ESTABLISHED（已建立连接）状态。TCP规定，ACK报文段可以携带数据，但是如果不携带数据则不消耗序号。 当服务器收到客户端的确认后也进入ESTABLISHED状态，此后双方就可以开始通信了。 4、了解操作系统吗？进程调度的方式？ 先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。 短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。 时间片轮转调度算法 : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。 多级反馈队列调度算法 ：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。 对于同一个队列中的各个进程，按照FCFS分配时间片调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列末尾，直至完成。 优先级调度 ： 为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。 5、了解哪些IO模型？ UNIX 系统下， IO 模型一共有 5 种： 同步阻塞 I/O、同步非阻塞 I/O、I/O 多路复用、信号驱动 I/O 和异步 I/O。...

京东 1. 数据库的事务 事务是逻辑上的一组操作，要么都执行，要么都不执行。 何为 ACID 特性呢？ 原子性（Atomicity） 一致性（Consistency） 隔离性（Isolation） 持久性（Durability） InnoDB 引擎使用 redo log(重做日志) 保证事务的持久性，使用 undo log(回滚日志) 来保证事务的原子性,通过 锁机制、MVCC 等手段来保证事务的隔离性（ 默认支持的隔离级别是 REPEATABLE-READ ）。 2. 建索引的注意事项 选择合适的字段创建索引： 不为 NULL 的字段 ：对于数据为 NULL 的字段，数据库较难优化 被频繁查询的字段 被作为条件查询的字段 频繁需要排序的字段 被经常频繁用于连接的字段 被频繁更新的字段应该慎重建立索引。 尽可能的考虑建立联合索引而不是单列索引: 磁盘空间 注意避免冗余索引 。 考虑在字符串类型的字段上使用前缀索引代替普通索引。 3. MySQL中的隔离级别 READ-UNCOMMITTED (读取未提交)： 最低的隔离级别，允许读取尚未提交的数据变更 READ-COMMITTED (读取已提交)： 允许读取并发事务已经提交的数据 REPEATABLE-READ (可重复读)： 对同一字段的多次读取结果都是一致的，除非数据是被本身事务自己所修改 SERIALIZABLE (可串行化)： 完全服从 ACID，所有的事务依次逐个执行 隔离级别 脏读 不可重复读 幻读 READ-UNCOMMITTED √ √ √ READ-COMMITTED × √ √ REPEATABLE-READ × × √ SERIALIZABLE × × × 不可重复读和幻读区别：...