XiaoYi Blog

Problem: 853. 车队 思路: 采用单调递减栈，单调栈中存放所有可能的车队到达终点需要的时间。（注意，只保存位置最大的那个车辆，也就是车队中速度最慢的车辆）。我们需要对数组按照postion升序排列，然后从左到右遍历。 如果当前车辆到达时间大于等于栈顶车辆的时间，说明栈顶车辆能追上当前车辆，将栈顶车辆弹出，当前车辆入栈，将它两合并成一个车队。如果当前车辆到达时间小于栈顶车辆达到时间，说明栈顶车辆追不上当前车辆，那么将当前车辆入栈。循环结束后，单调栈的大小就是车队的数量。 复杂度 时间复杂度: O(nlog(n))，瓶颈在排序的复杂度上。当然，也可以采用空间换时间的方法，利用target大小的数组来保存数据。 空间复杂度: O(n) Code 1234567891011121314151617181920class Solution { public int carFleet(int target, int[] position, int[] speed) { int n = position.length; int ...

Problem: 37. 解数独 思路: 利用row[i][val]表示第i行有没有val出现。 利用col[j][val]表示第j列有没有val出现。 利用block[i / 3][j / 3][val]表示第（i/3,j/3）个九宫格有没有val出现。 利用empCells存储尚未被填充的点。 首先取出empCells中的第一个点，digital从0~9填充，如果digital不在行，列，其所在九宫格中存在，则遍历下一个未被填充的点。直到填充结束。 注意点: 1、在digital遍历的时候，需要加上 !valid 条件。也就是(int digital = 0; digital < 9 && !valid; digital ++)。为什么？ 因为如果不加这个条件，假设找到数独的解时，整个dfs还未完成。就要进行回溯，回溯的时候会将先前已经遍历过的digital设置为false。这样的话，当回溯到某个点时，该点的digital从k~9遍历（k是未被遍历过的第一个数字），而恰好在之前回溯过程中，k被设置为fals ...

Problem: 1971. 寻找图中是否存在路径 1234567891011121314class Solution { int[] pa; public boolean validPath(int n, int[][] edges, int source, int destination) { pa = new int[n]; Arrays.setAll(pa, i -> i); for (int[] e : edges) { pa[find(e[0])] = find(e[1]); } return find(source) == find(destination); } private int find(int a) { return (pa[a] == a) ? a : (pa[a] = find(pa[a])); }} 37解数独 Problem: 37. ...

Problem: 3025. 人员站位的方案数 I 思路: 想了好久，发现最后挺简单的。如图。当以1作为左端点时，如果右端点大于左端点的值，说明不满足A 在 B 的左上角条件，直接跳过此次循环。如果右端点的值小于等于左端点，判断右端点是否大于记录的最大值，如果大于，例如点3，说明左、右端点构成的矩形中没有其他点，更新最大值，ans++。 难点：当满足A 在 B 的左上角时才更新最大值。这样就能确保最大值永远在左端点高度之下（或者平齐），换句话说，该最大值是以左端点为左上角的矩形范围内的最大值，后面每次右端点进入的时候，只需要比较右端点和最大值即可。 复杂度 时间复杂度: O(n^2) 空间复杂度: O(1) Code 12345678910111213141516171819202122class Solution { public int numberOfPairs(int[][] points) { int n = points.length; Arrays.sort(points, (a, b) -> a[0 ...

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