Rayce. Blogs

KMPKMP 的思想kmp的思想就是当出现字符串不匹配的情况时，可以知道一部分之前已经匹配的文本内容，利用这些信息避免从头再去匹配 怎么记录之前已经匹配的内容 ？ 一般使用前缀表来做记录 前缀表 ： 记录了模式串 和 文本串 不匹配的时候， 模式串应该从哪里开始重新匹配的信息 案例 （下文所有都会拿这两个举例）： 文本串 : 【 a a b a a b a a f a】 模式串 ： 【 a a b a a f】 有关前缀表什么是前缀 ?​ 字符串中前缀是指 不包含最后一个字符的所有以第一个字符开头的连续子字符串 以模式串为例 【a a b a a f】 它的前缀有 [ a ] [ a a ] [ a a b ] [ a a b a] [ a a b a a] 什么是后缀 ?​ 字符串中后缀是指 不包含第一个字符的所有以最后一个字符结尾的连续子字符串 以模式串为例 【a a b a a f】 它的后缀有 [ f ] [ a f ] [ a a f ] [ b a a f ] [ a b a a f ] 最长相等前后缀以模式串为例 【a a b a a f】 那么这 ...

分割等和子串 题目链接(opens new window) 题目难易：中等 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集. 提示： 1 <= nums.length <= 200 1 <= nums[i] <= 100 思路对于这种类型的题 我们一上来首先想到的肯定不是动归 ，而使回溯，回溯解决切割问题。但是这道题相对于也是可以使用dp去解决的 这道题 他求解的是是否可以分割成两个相等的子集 ，既然想要相同， 那么想要相同，那sum肯定不能是基数 ，如果是奇数 那么就不可能平分 ，所以我们可以先进行判断 ，排除一些不可能的结果。 动归五部曲 确定dp数组 含义 ...

秒杀接口 基础下单实现controller层实现 12345678910111213141516/** * 秒杀下单业务 */@RestController@RequestMapping("/voucher-order")public class VoucherOrderController { @Resource private IVoucherOrderService voucherOrderService; @PostMapping("seckill/{id}") public Result seckillVoucher(@PathVariable("id") Long voucherId) { return voucherOrderService.seckillVoucher(voucherId); }} service层实现下单【未涉及下单模块】 1234567891011121314151617181920 ...

参考 : 代码随想录 理论知识动态规划问题，将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！ 确定dp数组（dp table）以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 发出这样的问题之前，其实可以自己先思考这三个问题： 这道题目我举例推导状态转移公式了么？ 我打印dp数组的日志了么？ 打印出来了dp数组和我想的一样么？ 如果这灵魂三问自己都做到了，基本上这道题目也就解决了 01背包问题详解： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384/** * 0 1背包问题 *有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。 * 每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 */p ...

setset之所以没有放到和Collection接口一块学习是因为set接口底层实现的还是Map接口。他只是相当于在map接口上做了一次封装。 set接口常用的方法 12345678910111213141516171819202122//源码中的public interface Set<E> extends Collection<E> { int size(); boolean isEmpty(); boolean contains(Object o); Iterator<E> iterator(); Object[] toArray(); <T> T[] toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); bo ...

​ 对于java语言来说，如果需要实现栈队列的数据结构，我们已经不需要自己手动实现了，java内部已经帮我们实现好了栈和队列，而且在其基础上又有了优化 ​ 当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；既然Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了(次选是LinkedList) 队列（先进先出）对于栈来说，java内部封装Stack方法，但是没有封装Queue的方法。只有实现了接口 Queue接口Queue接口继承自Collection接口，除了最基本的Collection的方法之外，它还支持额外的insertion, extraction和inspection操作。这里有两组格式，共6个方法，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。 Deque—-继承Queue的接口双向队列，也就是既可以实现队首插入、删除、查看。也可以实现队尾插入、删除、查看的操作。通过这些操作能够更加高效的实现我们所需的操作 由于Deque是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是 ...

CollectionArrayList源码剖析添加元素分析 ArrayList数组源码剖析 三个构造器1234567891011121314151617181920212223242526272829303132333435363738public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapac ...

回溯的适用范围回溯法，一般可以解决如下几种问题： 组合问题：N个数里面按一定规则找出k个数的集合 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个N个数的集合里有多少符合条件的子集 排列问题：N个数按一定规则全排列，有几种排列方式 棋盘问题：N皇后，解数独等等 三大关键点回溯法解决的问题都可以抽象为树形结构 **集合的大小就构成了树的宽度，递归的深度，都构成的树的深度**。 递归就要有终止条件，所以必然是一棵高度有限的树（N叉树） 回溯模板就是递归三部曲遇到题目的解法首先，一定要分类是哪类题。组合、分割、子集还是棋盘… 组合最经典的题目 给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。 示例:输入: n = 4, k = 2输出:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],] 在没有学习回溯之前我们可能就是只会n层for循环来解决这种题 在学习了回溯之后，我们就可以先进行画图分析【图片来自代码随想录: 连接代码随想录 (programmercarl.com)】 思路很显然就是递归三部曲 ...

题40.组合总和三 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。 示例 1: 123456789输入: candidates = [10,1,2,7,6,1,5], target = 8,输出:[[1,1,6],[1,2,5],[1,7],[2,6]] 示例 2: 123456输入: candidates = [2,5,2,1,2], target = 5,输出:[[1,2,2],[5]] 思路首先根据我们之前的总结，可以确定这道题我们需要到回溯 【回溯可以解决的问题 : 组合问题：N个数里面按一定规则找出k个数的集合 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个N个数的集合里有多少符合条件的子集 排列问题：N个数按一定规则全排列，有几种排列方式 棋盘问题：N皇后，解数独等等 】 如果按照我们之前的思路，那么这道题就是经典的递归回溯三部曲,[参考上面的图 ...

题目：151. 反转字符串中的单词难度中等758收藏分享切换为英文接收动态反馈 给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 示例 1： 12输入：s = "the sky is blue"输出："blue is sky the" 示例 2： 123输入：s = " hello world "输出："world hello"解释：反转后的字符串中不能存在前导空格和尾随空格。 思路本题如果我们按照之前固有的思路来解的话那就是用split来分割， 然后再进行反转就可以了，但是这样题目就失去了本身的意义。所以我们这里不借助String的本身的工具，而是自定义实现删除空格 操作虽然只有三步，但是每一步需要思 ...