⚠️⚠️⚠️ 注意!!! 本文还未完成,⚠️⚠️⚠️ 缓存一致性协议MESI_哔哩哔哩_bilibili 目前大多数PC的CUP都是多核 我们知道根据摩尔定律, CPU性能每隔18个月就会翻一倍(即使在10年后逐渐失效) 在经典的冯诺依曼体系中, 存储器和计算器的IO导致的性能低下已经越发的突出 由此,大多CPU都会存在缓存这一中间设备, 利用局部性原理, 将热点数据存储在缓存中 目前大多设备为三级缓存 其中L1, L2缓存为单个CPU私有(可能由于CPU架构而不同), L3缓存为共享, 但这并不是本节讨论的重点,接下来, 我们直接将缓存抽象为每个CPU核心所私有的 缓存的引入,极大的降低了IO效率, 提升了CPU整体的效率,但是多核架构下, 引入缓存会出现一致性问题 什么时一致性问题呢? 我们举个最简单的例子 CPU公有两个核心 P1 P2 现在内存中有一个全局变量 n = 1, 被两个核心共享 目前两个核心缓存都不存在这个全局变量(缓存引入后, CPU只直接操作缓存, 操作内存需要先读入缓存再写入缓存, 但是写入的时间并不确定) 假设 P1 P2的目的都是让全局变量 ...

回溯算法模板回溯算法和DFS很像, 本质都是是一种暴力枚举算法, 不过回溯算法是遍历树枝, DFS是在遍历结点 回溯问题需要思考如下三个问题 路径: 做出的选择 选择列表: 当前可以做的选择 结束条件: 到达决策底层无需或者无法进一步选择 伪代码模板(python) result = []def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 本质上就是对一棵递归树进行选择和撤回,在合适的位置(前序和后续)进行选择和记录 以下是全排列代码 class Solution { List<List<Integer>> res = new LinkedList<>(); List<List<Integer>> permute(int[] nums) { ...

双指针27. 移除元素给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。for (int i = 0; i < len; i++) { print(nums[i]);} 示例 1： 输入：nums = [3,2,2,3], val = 3输出：2, nums = [2,2]解释：函数应该返回新的长度 2, 并且 nums ...

:closed_book::blue_book:红蓝二分法 解题​ :mag:红蓝二分法讲解：特此声明：本文模板非原创，核心内容均转自B站 五点七边 ，本人主要进行简要介绍，相应题目代码展示，持续更新中…… 关于红蓝二分法，五点七边以给出很不错的讲解： 二分查找为什么总是写错？_哔哩哔哩_bilibili leetcode 大佬讲解红蓝二分法 蓝红二分法单模板秒杀二分查找 :star2:二分的本质：​ 如果我们能够通过某种方式将一个区间划分成两个区间，左边区间满足某种特性；右边区间不满足某种特性。​ 那么我们就能够通过二分法来寻找左区间的右边端点或者右区间的左边端点 ​ 有单调性一定可以二分，但是二分不一定要有单调性 ​ 通常二分法的思路是通过二分不断缩小结果范围直到确认结果或者区间不存在 ​ 而红蓝二分法则是逆向思路，通过不断扩大非结果区间的范围直到直到确认结果或者区间不存在 ​ ​ 通常二分法的思路对应的各种左闭右闭或者左闭右开往往面临繁琐的边界问题，虽然通过大量练习也能熟能 生巧，但红蓝二分提供的简易思路可以摒弃复杂的边界问题，更加贴近二分的本质——循环不变量 ...

背包问题🚧🚧🚧 暂待施工🚧🚧🚧 01背包 public int maxValue(int[] weight, int[] value, int bagSize) { int goods = weight.length; int[][] dp = new int[goods + 1][bagSize + 1]; for (int i = 1; i <= goods; i++) { for (int j = 1; j <= bagSize; j++) { if (j < weight[i - 1]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max( dp[i - 1][j], dp[i - 1][j - weight[i ...

红黑树🚧🚧🚧 暂待施工🚧🚧🚧 Sedgewick的红黑树 - SteveWang - 博客园 (cnblogs.com) 主要性质 叶根黑 红黑 黑高 有则黑 自平衡方式 左旋 右旋 变色 插入 157 -> 12 父节点是黑结点, 直接插入, 不会破坏(-> 200) 父节点是红色, 需要自平衡 父和叔结点为红, 父结点, 叔结点和爷结点颜色反转 (->250) 父为红, 叔为黑 孙父爷在一条直线上, 父和爷颜色反转, 父爷旋转(->260) 孙父爷不在一条直线上, 父和孙 先旋转成一条直线 再执行上一条(->220[复习上一条] -> 210)

设计原则与思想: 面向对象我们在讨论面向对象的时候,我们到底在谈论什么?什么是面向对象编程和面向对象编程语言? 面向对象编程是一种编程范式或编程风格, 它以类或对象作为组织代码的基本单元, 并将封装, 抽象, 继承, 多态四个特性,作为代码设计和实现的基石 面向对象编程语言是支持类或对象的语法机制, 并由现成的语法机制,能方便地实现面向对象编程四大特性(封装, 抽象, 继承, 多态)的编程语言 面向对象语言和面向对象编程语言之间地关系 面向过程语言也可以实现面向对象编程 面向对象语言也会写出面向过程编程 如何判定一个编程语言是否面向对象编程语言并没有严格地定义,面向对象语言要求宽泛,并不一定要求具有所有的四大特性, 只要某种编程语言支持类, 对象语法机制,那几本上就可以说这种编程语言是面向对象编程语言了 什么是面向对象分析和面向对象设计?OOA, OOD, OOP 软件开发流程 面向对象分析就是搞清楚做什么, 面向对象设计就是搞清楚怎么做,. 两个阶段地产出就是类的设计,包括程序被拆解为哪些类, 每个类有哪些属性方法,类与类之间如何交互等等 封装, 抽象, 继承,多态可以解决哪 ...

ArrayList源码分析Hey 大家好，我是 Shio👋。今天我们将深入探讨 Java 的ArrayList源码, ArrayList 是Java提供的动态数组容器, 和Java中数组相比， 它能够动态增加长度。 其继承了AbstractList, 并且实现了List, RandomAccess, Cloneable, Serializable接口 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ } 这些接口代表的含义如下： List代表他是一个列表， 支持添加，删除， 查找操作， 可存放重复元素 RandomAccess 是一个标记接口， 代表实现类支持随机访问（根据元素序号快速获取元素对象） Cloneable是一个标记接口， 代表实现类具有拷贝能力（可以调用Object.clone()方法进行拷贝） Serializa ...

为什么要学习设计模式?越早学习设计模式越好,有些东西早点知道,才能在日后一直发挥作用 在计算机五大件(计组, 计网, 操作系统, 编译原理, 设计模式)中 数据结构和算法研究如何高效实现 设计模式研究如何保证代码的可维护性 总结 应对面试中的设计模式相关问题 告别被别人吐槽的烂代码(talk is cheap, show me your code) 提高复杂代码的设计和开发能力 让读源码,学框架事半功倍 为职场发展做铺垫 ​ 在日常开发中用过哪些设计模式? 使用代理模式进行共性话处理,比如AOP思想,将非业务功能和业务功能解耦 事务的处理 @Translation 系统间上下文的传递ThreadLocal+ restTemplate#intercept等等 使用工厂 + 策略 不同优惠种类的计算 定制化功能的解耦 观察者模式 : 这个模式的思想在很多中间件(mq, zookeeper, netty等等)可以看到银子 通过领域事件解耦业务 理解eventloop, epoll等等 通过watch实现动态配置, HA等等 职责链模式: pipeline思想 fi ...