0%

对两个有序数组进行排序:

将arr数组中,左右两个有序数组分别复制到两个数组中,逐个比较,再放到原数组中,这样原数组有序。(或者利用双指针遍历,复制到一个新的数组中)

Read more »

堆:
需满足两个条件:
1、是一个完全二叉树
2、parent > child (大顶堆)

完全二叉树,确保可以用数组来表示,并且从任意节点开始出发,可以轻松得到其父节点和两个子节点。
对于节点i,parent = (i - 1) / 2, c1 = i * 2 + 1, c2 = i * 2 + 2

heapify:
可以把一个完全平方树看成很多个子树,每个子树就3个元素,对这个子树按照parent>child的规则进行调整,调整后,再递归的对其子节点进行判断。这个过程称为heapify。

Read more »

Leetcode: https://leetcode-cn.com/problems/perfect-squares/submissions/

思路一:BFS + 贪心

BFS(广度优先搜索) 常用来解决最短路径问题。
第一次便利到目的节点时,所经过的路径是最短路径。

几个要点:

  • 只能用来求解无权图的最短路径问题
  • 队列:用来存储每一层便利得到的节点
  • 标记:对于遍历过的结点,应将其标记,以防重复访
Read more »

LRU,全称Least Recently Used,最近最少使用缓存。

LRU 算法实际就是设计一个数据结构,首先通过 capacity 参数控制缓存的容量,然后实现 get、put 两个方法。get 和 put 方法必须都是 O(1) 的时间复杂度。

LRU 缓存算法的核心数据结构就是哈希链表,双向链表和哈希表的结合体。

思想很简单,就是借助哈希表赋予了链表快速查找的特性嘛:可以快速查找某个 key 是否存在缓存(链表)中,同时可以快速删除、添加节点。

为啥需要双向链表,而不是单向链表?
因为需要保证链表中元素的访问有序性,即最近未使用的元素在链头,最近使用的在链尾。当缓存满时,从链头剔除一个元素,当插入新的元素时,追加到链尾。使用双向链表可以方便实现,并且时间复杂度为O(1)。

需要注意:

  • 当更新元素值时,也要将该 Node 重新放入链尾。
  • 处理链表节点的同时不要忘了更新哈希表中对节点的映射。

LeetCode: https://leetcode-cn.com/problems/lru-cache/

算法实现:哈希表 + 双向链表

Read more »

一、为什么要使用线程池

线程池复用线程有以下几点优点:

  • 减少资源创建 => 减少内存开销,创建线程占用内存。使用 new Thread 每次启动线程都需要进行对象和线程;
  • 降低系统开销 => 创建线程需要时间,会延迟处理的请求;
  • 提高稳定稳定性 => 避免无限创建线程引起的 OOM;
  • 功能更强大 => 提供了定期执行、线程中断、并发数控制等功能。

二、Executors 创建线程池的方式

根据返回的对象类型创建线程池可以分为三类:

Read more »

J.U.C 是 java.util.concurrent 的缩写,是 jdk 的并发包,包含了很多并发相关的类。下面介绍常用的类。

一、Atomic 原子操作类

1. 原子更新基本类型

使用原子的方式更新基本类型,Atomic 包提供了以下 3 个类:

  • AtomicBoolean
  • AtomicInteger
  • AtomicLong

以上类的基本使用方法都差不多,下面以 AtomicInteger 为例子说明。AtomicInteger 常用方法如下:

  • int addAndGet(int delta) : 以原子方式将输入值与实例中的值相加,并返回结果;
  • int getAndAdd(int delta)
  • int incrementAndGet()
  • boolean compareAndSet(int expect, int update) : 如果输入值等于预期值,则以原子的方式将该值设置为输入的值;
Read more »

一、线程安全

1. 线程安全

可以简单的理解为:一个方法或者一个实例可以在多线程环境中使用而不会出现问题。

2. 线程不安全的原因

多个线程使用了相同的资源,如同一内存区(变量、数组或对象)、系统(数据库、web服务等)或文件等。更准确的说,是多个线程对同一资源进行了写操作。多个线程只读取相同的资源,是没有线程安全问题的。

3. 如何保证线程安全

保证共享内存的原子性、可见性和有序性。

Read more »

一、 基本概念

并发:一个处理器处理多个任务,逻辑上的同时发生。

并行:多个处理器同时处理多个任务,物理上的同时发生。

并发与并行的区别
Read more »