求阙厅

春有百花秋有月，夏有凉风冬有雪。若无闲事挂心头，便是人间好时节。

算法 系列 双指针

基础数据结构...

快慢指针 快慢指针⼀般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决⼀些链表中的问题。 判定链表中是否含有环 单链表的特点是每个节点只知道下⼀个节点，所以⼀个指针的话⽆法判断链表中是否含有环的。 经典解法就是⽤两个指针，⼀个跑得快，⼀个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终...

Posted by lichao modified on June 17, 2020

算法 系列 单链表反转

基础数据结构...

递归反转整个链表 实现代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 单链表节点的结构 public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } ListNode reverse(ListNode head) { if (head.next ...

Posted by lichao modified on June 17, 2020

算法 系列 栈

基础数据结构...

单调队列 就是⼀个「队列」，只是使⽤了⼀点巧妙的⽅法，使得队列中的元素单调递增（或递减）。这个数据结构有什么⽤？可以解决滑动窗⼝的⼀系列问题。 每个窗⼝前进的时候，要添加⼀个数同时减少⼀个数，所以想在 O(1) 的时间得出新的最值，就需要「单调队列」这种特殊的数据结构来辅助了。 ⼀个「单调队列」的操作： 1 2 3 4 5 6 7 8 class MonotonicQueue { ...

Posted by lichao modified on June 16, 2020

算法 系列 单调栈

基础数据结构...

栈（stack）是很简单的⼀种数据结构，先进后出的逻辑顺序，符合某些问题的特点，⽐如说函数调⽤栈。 单调栈实际上就是栈，只是利⽤了⼀些巧妙的逻辑，使得每次新元素⼊栈后，栈内的元素都保持有序（单调递增或单调递减）。 单调栈⽤途不太⼴泛，只处理⼀种典型的问题，叫做 Next Greater Element。Next Greater Number 的原始问题：给定⼀个数组，返回⼀个等⻓的...

Posted by lichao modified on June 16, 2020

算法 系列 二叉搜索树

基础数据结构...

⼆叉树算法的设计的总路线：明确⼀个节点要做的事情，然后剩下的事抛给框架。 ⼆叉搜索树（Binary Search Tree，简称 BST）是⼀种很常⽤的的⼆叉树。它的定义是：⼀个⼆叉树中，任意节点的值要⼤于左⼦树所有节点的值，且要⼩于右边⼦树的所有节点的值。 二叉搜索树的中序遍历是一个升序的排序 查找效率最好O(logn)，最坏O(n)，插入效率和查找效率相同（只插入...

Posted by lichao modified on June 16, 2020

算法 系列 二分搜索

基础数据结构...

在有序数组中搜索给定的某个⽬标值的索引。再推⼴⼀点，如果⽬标值存在重复，修改版的⼆分查找可以返回⽬标值的左侧边界索引或者右侧边界索引。 寻找一个数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int binarySearch(int[] nums, int target) { int left = 0; int right = nums.le...

Posted by lichao modified on June 16, 2020

算法 系列 概述

基础数据结构...

算法 - Algorithms 排序算法：快速排序、归并排序、计数排序 搜索算法：回溯、递归、剪枝技巧 图论：最短路、最⼩⽣成树、⽹络流建模 动态规划：背包问题、最⻓⼦序列、计数问题 基础技巧：分治、倍增、⼆分、贪⼼、双指针 数据结构 - Data Structures 数组与链表：单 / 双向链表、跳舞链 栈与队列 树与图：最近公共祖先、并查集 ...

Posted by lichao modified on June 15, 2020

算法 系列 回溯算法

基础数据结构...

「回溯算法」实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯...

Posted by lichao modified on June 15, 2020

算法 系列 LRU

基础数据结构...

LRU 是⼀种缓存淘汰策略。LRU 的全称是 Least Recently Used，也就是说认为最近使⽤过的数据应该是是「有⽤的」，很久都没⽤过的数据应该是⽆⽤的，内存满了就优先删那些很久没⽤过的数据。 实现 LRU 算法实际上是设计数据结构：⾸先要接收⼀个 capacity 参数作为 缓存的最⼤容量，然后实现两个 API，⼀个是 put(key, val) ⽅法存⼊键值 对，另⼀个是...

Posted by lichao modified on June 15, 2020

Redis 系列 持久化

开启 redis 探索新篇章

Redis 数据全部在内存里，如果突然宕机，数据就会全部丢失，因此必须有一种机制来保证 Redis 数据不会因为故障而丢失，这种机制就是 Redis 的持久化机制。 Redis 持久化机制 Redis 4.0 之前有两种，第一种是快照，第二种是 AOF 日志。快照是一次全量备份，AOF 日志是连续的增量备份。快照是内存数据的二进制序列化形式，在存储上非常紧凑，而 AOF 日志记录的是内...

Posted by lichao modified on June 10, 2020

FEATURED TAGS
redis go mysql algorithm distribute jvm network spring java kafka mongo mq concurrent index design_pattern io rocket_mq store netty os concurrency nosql mesh etcd graph hbase kitex lang zookeeper
ABOUT ME

Pleasure derived from simplicity is the true happiness in life.
人间有味是清欢

FRIENDS