dch'blog

####异常码的设计和使用 ​ 为了更快的确定异常原因，从而快速定位出错地点并解决异常。可以使用异常码，每个异常码都对应一个特定的错误。本项目参考阿里巴巴开发手册，将出错原因大体上分为3类：用户端出错，服务器端出错以及远端第三方组件出错，分别用大写英文字母A、B、C标识，每个类别下使用6位数字来表示出错原因，因而总共可以表示30万种错误。每个大类中根据内容详细程度不同，分为3个级别，级别越高内容越详细。 异常码设计 1234public Interface IErrorCode{ String code; String message;} 基础异常码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849/** * 基础错误码定义 */public enum BaseErrorCode implements IErrorCode { // ========== 一级宏观错误码 客户端错误 ========== ...

开发全局唯一ID生成器​ 保证id唯一的方法有很多种，本项目使用的是基于Redis的id生成器，其基本原理是借助于Redis自带的increment自增方法。 ​ 生成原理：以long类型作为生成id的类型，long类型具有64位，将这64位分为三部分，[63,63],[32,62],[0,31]。最高位是符号位，是一个固定值0，表示生成的id是非负数，后面63位需要决定生成id的唯一性。具体方法为，[0,31]位上填充由Redis的increment方法生成的值，[32,62]位填充当前时间距离某个基准时间的时间(一般以秒作为单位，69年后生成的值才会超过31位)。 实现代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344package com.hmdp.utils;import org.springframework.data.redis.core.StringRedisTemplate;import org.springframework.stereotype.Co ...

在java中创建一个线程有3种方法。 一.直接new一个Thread对象 123456789public void testForCreateThread1(){ Thread thread1 = new Thread("t1") { public void run() { System.out.println("t1 is doing"); } }; thread1.start(); } 二.通过Runnable接口辅助创建线程 1234567891011public void testForCreateThread2(){ Runnable runnable = new Runnable() { @Override public void run() { System.out.println(" ...

单调栈题集​ 单调栈是一种特殊的栈，因为栈中的元素大小是单调的而得名单调栈。经过预处理(预处理的时间复杂度为O(n))，可以在O(1)的时间复杂度求出数组中每个元素右边(左边)第一个大于(小于)该元素的值的下标。是一种非常常用且好用的数据结构 LeetCode84 ​ 这道题我一开始的想的暴力做法是枚举两个自由度，第一个自由度表示该矩形的起始位置(start)，另一个自由度表示该矩形的结束位置(end)，在枚举的过程中维护一个最小高度(minH)并更新答案 12345678910int res = 0;for(int i = 0; i < n; i ++){ int minH = heights[i]; res = Math.max(res,minH); for(int j = i + 1; j < n; j ++){ minH = Math.min(minH,heights[j]); res = Math.max(res,(j - i + 1) * minH); }} ​ 这似乎也是一种暴力 ...

缓存工具类​ 在解决缓存技术中存在的问题时，其解决方案基本上是有固定套路的 ​ 针对缓存穿透问题(指查询数据既不存在于缓存中，也不存在于数据库中，如果有用户恶意刷该请求，会给数据库造成巨大压力，影响系统性能)，有以下两种解决方案： 当数据库查询不到数据时，给缓存返回空值。这个方案也是有问题的，比如此后不久数据库中插入了该数据，那么直到缓存中的空值过期，否则用户一直无法取到对应数据，并且会消耗额外的内存。 采用布隆过滤器技术：这是一种利用二进制来判断缓存中是否有对应数据的技术，作用于用户请求和Redis之间，能够过滤掉缓存和数据库中都不存在数据的请求。但是实现复杂，并且存在误判可能(类似于哈希冲突) ​ 针对缓存雪崩问题(指某一段时间，缓存中的大量数据失效在项目初始化时，有大量数据同时加入缓存，又称为数据预热或者缓存服务挂了，导致大量请求涌入数据库，给数据库造成巨大压力，影响系统性能)，有以下解决方案 给缓存中的每条数据设置随机的过期时间。该方案只能解决前一种情况 针对第二种情况，可以采用缓存集群以及设置多级缓存的方式加以解决。 ​ 针对缓存击穿问题(通常是针对某些热点key，比 ...

O(n)时间复杂度常数空间求解最小未出现正整数LeetCode41 ​ 这道题的难点在于，既要求时间复杂度控制在O(n)，有要求常数级空间复杂度。 ​ 假设抛开时间复杂度复杂度这一要求，我们可以使用快排或者二分来实现，都能满足常数时间复杂度的要求。 ​ 如果抛开空间复杂度这一要求，我们可以额外创建一个哈希表来记录数组中的数，能够满足O(n)时间复杂度的要求。 ​ 如果想要满足这两个要求，这是一种思维上的挑战。这里的想法是，其实题目中有一个隐含条件，那就是[1,2,…n]这个数组，我们只要保证让n以内的数在nums中有序，再通过对比这个数组就能找出最小未出现正整数，这也是排序做法的思路。做法就是让这些数回到它们本应该在的位置，比如2应该在nums下标为1的位置，同理，n应该在nums下标为n-1的位置，遍历nums每个数，将n以内的数交换至对应的位置，这样就能实现nums数组的部分有序性，这样就既符合时间复杂度O(n)(交换的次数非常少),常数级空间复杂度。 ​ 实现代码 123456789101112131415161718192021222324class Solution  ...

字典树Tire题集LeetCode3045 ​ 讲一下这道题使用字典树的做法，首先介绍一下什么是字典树。字典树是一种处理字符串的数据结构，通常用于快速统计某些字符串出现的次数，比如：给定一个字符串数组[a,a,c,abc,ab],以下就是该字符串数组形成的字典树。 ​ 这棵树可以表示以字符串a出现了2次，ab出现了1次，abc出现了1次，c出现了1次 ​ 这道题的特别之处在于，不仅要求我们匹配前缀还要匹配后缀。比如ab虽然是abc的前缀但不是它的后缀，因此不符合题意。这里灵神提供的一种思路是将前缀和后缀综合考虑，比如字符串abcde、abcdesabcde，将它们的前后缀综合考虑变为{(a,e),(b,d),(c,c),(d,b),(e,a)},{(a,e),(b,d),(c,c),(d,b),(e,a),(s,s),…},可以发现经过这样转化后，只需判断前者是否是后者的前缀即可判定，某个字符串是否既是另一个字符串的前缀，又是另一个字符串的后缀，而这样就可以直接使用字典树解决。为了进一步简化，我们可以将这个键值对映射为一个数字。 实现代码： 12345678910111213141 ...

栈题集 栈是一种特殊的数据结构，具有先进后出的特点。可以把栈想象成一个桶，当从桶中取出物品时，先放入的物品会后取出，并且只有将上面的物品取出后，处于桶下面的物品才能取出。 在java中也提供了这种数据结构，位于java.util包下，名称为Stack。以下是有关Stack的一些常用操作 //初始化 Stack<Integer>stack = new Stack<>(); //向栈中存放数据 stack.push(1); //取出栈顶元素 int x = stack.pop(); //查看栈顶元素 int top = stack.peek(); //移除栈中对应的元素 stack.remove(1); //查看栈是否为空 stack.isEmpty(); //返回栈的大小 stack.size(); //翻转栈 Collections.reverse(stack); 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535 ...

深度优先遍历(dfs)回溯LeetCode22 ​ 本题要求生成给定数量的”()”，问有多少种生成方案。比如：要求生成3对括号，那么生成结果可以是”()()()”、”((()))”、”(()())”。 ​ 解决本题的关键在于需要保证在生成”)”时，在此之前至少有一个未被配对的”(“。因此我dfs的主要参数有已使用的”(“数量，未被配对的”(“数量。接下来在生成”(“时只需保证”(“的数量还未使用完；生成”)”时只需保证在此之前至少有一个未被配对的”(“。 ​ 实现代码： 1234567891011121314151617181920212223242526272829class Solution { private List<String>res = new ArrayList<>(); private int leftNum; public List<String> generateParenthesis(int n) { char s[] = new char[2 * n]; le ...

二叉树题集Leetcode105 这道题要求我们根据二叉树的前序遍历和中序遍历还原这棵二叉树。这是一个定理：只要给定一棵树的前序遍历和中序遍历或者后序遍历和中序遍历，我们就能够唯一构造出这棵树。需要注意的是如果只给定前序遍历和后续遍历，虽然也能构造出一棵树，但不唯一。 其原理为：由于前序遍历的特点为先遍历根节点，再遍历左儿子，最后遍历右儿子。因此通过前序遍历/后序遍历可以知道根节点(整棵树的根节点以及子树的根节点)，再通过中序遍历可以知道根节点的左子树和右子树。这样我们就能够唯一确定这棵树。比如给定某棵树的前序遍历集合为[3,4,5,7,9,10],再给定其中序遍历集合为[4,5,3,7,10,9]. 首先，通过前序遍历集合可以知道3是根节点，再定位到中序遍历集合中，4、5是它的左子树；7、10、9是它的右子树。因为前序遍历集合中4在5前，因此4才是3的左儿子；7在10和9前，因此它是3的右儿子。这样不断重复操作，最终还原这棵二叉树 实现代码 12345678910111213141516171819202122232425262728293031323334353637 ...

动态规划题集LeetCode2369 ​ 本题的状态定义为dp[i + 1]表示下标0-i的子数组是否可以是有效划分，状态转移方案为 1. nums[i] == nums[i - 1],问题就转化为查看0-(i-2)的子数组是否是有效划分，根据状态定义就是dp[i - 1] 2. nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2],问题就转化为查看0-(i - 3)的子数组是否是有效划分，根据状态定义就是dp[i - 2] 3. nums[i] == nums[i - 1] + 1 && nums[i - 1] == nums[i - 2] + 1,问题就转化为查看0-(i - 3)的子数组是否是有效划分，根据状态定义就是dp[i - 2] 实现代码 123456789101112131415161718class Solution { public boolean validPartition(int[] nums) { ...

缓存击穿问题：什么是缓存击穿？如何解决该问题？ 实现互斥锁及其设计细节 实现逻辑过期