XiaoYi Blog

Problem: 76. 最小覆盖子串 思路 利用滑动窗口思想。right表示子串的最后一个位置，right不断右移，直到覆盖t中所有字符。此时left不断左移，移动过程中更新最小子串的值，直到不再满足条件，left停止移动。然后right向右移动，重复以上的步骤，直到right==n。其中left，right初始化为0。 怎么判断覆盖了t中所有字符呢？有两种方法。 利用map存储t中字符和对应的个数。每次更新right之后，更新map，循环调用isContainAll函数判断mp中是否所有键对应的值都小于等于0。如果是，说明已经覆盖了t中所有字符，可以更新结果。但利用map的话，每次循环调用isContainAll函数，时间复杂度会增加，最小是O(52∗m+n)O(52*m+n)O(52∗m+n)。 利用两个变量。required表示t中字符的种类数。matched表示已经包含的字符种类数。每次更新right时，根据条件更新matched，然后循环判断mathed是否等于required，不断更新结果。这样做，时间复杂度是O(m+n)O(m+n)O(m+n) ...

Problem: 3439. 重新安排会议得到最多空余时间 I 思路 这道题的核心思路是：一定是安排连续的k个会议才能求出最大空闲时间。 为什么？如图，k=2，安排两个会议。 不难发现，重新安排连续的2和3能得到最大值5。如果安排不连续的2和4，那么安排4得到的空间时间对2并没有帮助，因为中间有3相隔，得到的空闲时间无法拼凑一起得到连续的空闲时间。 因此，必定是安排连续k个会议，才能得到最大空闲时间。就转化成了定长滑动窗口问题。 复杂度 时间复杂度: O(n) 空间复杂度: O(1) Code 1234567891011121314151617181920212223242526272829class Solution { public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) { int n = startTime.length; int freeTime = 0; int s = 0; ...

Problem: 3459. 最长 V 形对角线段的长度 思路 本题的实质就是有限制条件的图的DFS，以及利用记忆化搜索减少重复计算。 在设计dfs的时候，每次遍历到一个点，都先判断能不能直行，如果能直行，则直行走到尽头，每直行一步，更新一下最大线段的长度。直行到尽头之后，退回一步，尝试向右转，直到右转到达尽头，右转过程中也更新线段的最大长度。右转到尽头后，再往回退一步，重复以上步骤，每一步都更新线段的长度，直到回到出发点。这时就求出最大的线段长度了。 设线段最大长度为l。例如下图中，从1出发，直行，直行到2，直到尽头3，更新l=3。接着回溯到2，这时该向右转了，到达4，到达5，更新l=4。接着再回溯到1，向右转到达6，l没有更新。因此，执行一次dfs就能求出从该点出发可达的最大线段长度。 这时我们回到题目，将题目场景带入以上的dfs。出发点是grid[i][j]为1的位置，而往哪个方向走，什么时候能直行，什么时候能右转呢？这个就是dfs的限制条件，我们需要在设计dfs的时候传入参数。 我们设dfs函数为dfs(i,j,k,isTurn,target,grid,m ...

Problem: 3660. 跳跃游戏 9 思路 从题意知，从i位置向右跳转只能跳转到比nums[i]小的位置，从i位置向左跳转只能跳转到nums[i]大的位置。 那么，如果i位置右边的所有值都比i位置左边的所有值都要大，那么从i位置跳转，无法向右边跳转，只能向左边跳转。 因此，从i位置处跳转能到达的最大值在i位置左边数组里面，能到达的最大值就是i位置左边所有值中的最大值。 那么什么时候i位置右边的所有值都比i位置左边的所有值要大呢？i位置左边的最大值都要比i位置右边的最小值要小的时候。 我们设f[i]为0i位置中最大的值，g[i]表示i+1n位置中最小的值。假设我们从n-1向0遍历。 如果f[i]<=g[i+1]，那么ans[i]=f[i]。 如果f[i]>g[i+1]，这个时候最大值就不是f[i]了。 此时最大值可能分布在i左边或者i右边的位置。i位置左边的最大值已经找出来了，就是f[i]，所以不妨先从i位置跳转到f[i]所在的那个位置处。 又因为f[i]>g[i+1]，所以又能从f[i]所在的位置跳转到g[i+1]所在的位置。 而 ...

为什么输出的num一直不正确？1234567891011121314151617181920212223class Solution { private int num; private boolean[] vis; public boolean canVisitAllRooms(List<List<Integer>> rooms) { int n = rooms.size(), num = 0; vis = new boolean[n]; dfs(rooms, 0); return num == n; } private void dfs(List<List<Integer>> rooms, int i) { vis[i] = true; System.out.println(i); num ++; System.out.println("num为 ...

现在是9月1号开学前夕，晚上的19点13分，坐在空荡荡的屋子中写下这篇文章。其实7月初就想写下对大学四年的总结，可是一直没下笔。也许是对本科生活的不舍，一直不敢回忆大学的各种美好、各种快乐、各种悲伤。这算是一种逃避心理吧。直到今天的一个契机。研究生宿舍分配结果出来了。出来之后，心里五味杂陈。我被分配到了一个还不错的宿舍，距离工位也很近。但是好像怎么也开心不起来。是的，因为又回到了原来的学校，熟悉的场景，熟悉的工位，熟悉的麓山南路，熟悉的后湖。可是朋友们都不在了，本科时的好心情也没有了，随之而来的是陌生的研究生生活，不太熟悉的实验室。想到这很难受。😭😭😭好了，先回归文章的主要内容：大学四年回忆录。 遥想大一刚入学的时候，是一个学长替我搬了行李，帮我运到公寓内，然后里面的志愿者帮忙送上楼。当时的我，哈哈，也不怕大家笑话，普通话还不是很流利，说着蹩脚的普通话，和杨学长打电话，对接新生公寓接送行李工作。现在，我还觉得那个学长很热情，是我来到湖大遇到的第一份温暖，十分感激。因为高三的暑假期间，甚至追溯到高中时，我就会担心，到了大学怎么办呢，怎么和同学相处，怎么和室友相处，怎么和老师相处？ ...

学习自：【黑马程序员Redis入门到实战教程，深度透析redis底层原理+redis分布式锁+企业解决方案+黑马点评实战项目】https://www.bilibili.com/video/BV1cr4y1671t?p=67&vd_source=9fed3cefc266aa5b3895aaab6e6214f5 本文是基于上述视频教程和视频配套文档的文字总结，包含了以下几方面内容： 基于Redis实现验证码登录 Redis缓存、缓存更新策略、缓存穿透、雪崩、击穿问题 典型的秒杀场景、超卖问题及解决方案 Redis分布式锁、误删问题、原子性问题、lua脚本 Redisson分布式锁，包含其可重入、可重试、自动续期以及MutiLock的原理以及源码的分析 基于Redis实现验证码登录基于session实现登录过去我们使用基于session的验证码登录。缺点是session在集群环境下不能使用，因为多台tomcat服务器并不能共享session数据。由此产生了基于redis的登录流程。为了读者理解，先简单介绍一下基于session的登录。 登录的流程 发送验证码 用户输入手机号发起 ...

先来看一个例子。 1234567@Mapperpublic interface LoginMapper { @Select("select * from tb_user where phone=#{phone} and password=#{password}") User getByPhoneAndPassword(String phone, String password);} 在这段代码证，我们通过#{phone}，#{password}占位符来获取形参phone和password。咋一看没错，但运行会发现报错： 说是找到不到phone参数。我们明明将形参名和#{}占位符里面的保持一致了，为什么还是找不到phone参数呢？ 这是因为，在java8以前的版本中，编译器在编译的时候会将形参String phone编译为String arg0，并不会保留形参原来的名字。这个时候必须手动设置@Param参数完成映射。 12@Select("select * from tb_user ...

学习自：【黑马程序员Java项目实战《苍穹外卖》，最适合新手的SpringBoot+SSM的企业级Java项目实战】https://www.bilibili.com/video/BV1TP411v7v6?vd_source=9fed3cefc266aa5b3895aaab6e6214f5 本文是基于上述视频教程和视频配套文档的文字总结。 本篇文章是苍穹外卖前端的学习笔记。 前提条件：后端项目启动完成，后端服务地址为http://localhost:8080。 前端环境搭建技术选型 node.js > 14.17.0 (typescript 要求 node.js版本大于 14.17.0 以上) vue 2.6.10 Element UI 2.12.0 axios 0.19.0 vuex 3.1.1 vue-router 3.1.2 typescript 5.x具体不记得了 启动项目注意到导入的初始工程里面并没有前端项目运行所以来的js包，需要执行npm install 命令来安装。生成的依赖包在node_moudles目录。如下图示。 然后运行npm run serve启动 ...