题目:有 n 个网络节点,标记为 1 到 n。给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1 。示例 1:输入:times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2输出:2示例 2:输入:times = [[1,2,1]], n = 2, k = 1输出:1示例 3:输入:times = [[1,2,1]], n = 2, k = 2输出:-1来源:力扣(LeetCode)链接:https://leetcode.cn/problems/network-delay-time思路:信号的速度是固定的,需要的时间和距离是成正比的。需要多久就是需要多远。而本题从点A到点B,需要走过的距离就是点A到点B的最短距离。而本题答案就是从源点K到其他各个点的最短距离中的最大值。单源最短路径算法Dijkstr

题目有一个机器人,要穿越迷宫从起始点到终点,迷宫是由0和1组成的二维数组arr,0表示空地,1表示障碍物,给定出发点坐标(xStart,yStart)和终点坐标(xEnd,yEnd),机器人可以向上、下、左、右移动,机器人从起始点到终点的最短路径是多少?思路从起点出发,把起点的邻接点全部加到队列里。然后再把起点删掉。完成第一步,然后依次把队列里点的邻接点也加入到队列里,再把第一步里产生的邻接点全部从队列里删掉。完成第二步。不断重复这个过程,直到找到终点。代码int bfsMinPathStep(vector<vector<int>>& arr,int xStart,int yStart,int xEnd,int yEnd) { if (arr.size() == 0) { return 0; } int m = (int)arr.size(); int n = (int)arr[0].size(); deque<vector<int>> queue; vector&l

题目有一个机器人,要穿越迷宫从起始点到终点,迷宫是由0和1组成的二维数组arr,0表示空地,1表示障碍物,给定出发点坐标(xStart,yStart)和终点坐标(xEnd,yEnd),机器人可以向上、下、左、右移动,机器人从起始点到终点的最短路径是多少?思路机器人从起始点出发,正常情况下可以朝4个方向移动,移动到下个位置又可以朝4个方向移动,不断重复,当机器人的坐标和终点坐标相等时,即到达终点,此时有一个路径值,比较所有的路径值,得到最小值,即答案。代码vector<vector<int>> directions = {{0,1},{0,-1},{1,0},{-1,0}}; int minP = INT_MAX; vector<vector<int>> book; void dfsMinPath(vector<vector<int>>& arr,int xStart,int yStart,int xEnd,int yEnd, int step) { if (xStart == xEnd &&

题目:给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1:输入:nums = [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2:输入:nums = [0,1]输出:[[0,1],[1,0]]示例 3:输入:nums = [1]输出:[[1]] 提示:1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不相同本题来源leetcode:https://leetcode.cn/problems/permutations/思路:本题是dfs的入门问题。nums长度为n,想象n个位置,每次从nums中取一个数字放入其中一个位置,每个数字只能放入一次,对于第i个位置,每个数字都有可能被放入。所以用for循环来遍历nums尝试放入第i个位置,对于第i+1个位置的操作和第i个位置一样,所以直接调用。因为每个数字只能被放入一次,所以要记录是否已经被放入某个位置了。当没有空位置了,就是一个排列。

题目:小A认为如果在数组中有一个数出现了至少k次且这个数是该数组的众数,即出现次数最多的数之一那么这个数组被该数所支配显然当k比较大的时候,有些数组不被任何数所支配现在小A拥有一个长度为n的数组她想知道内部有多少个区间是被某个数支配的2 <= k <= n <= 1000001 <= 数组的值 <= n思路:遍历子数组,统计每个数出现的次数,只要有一个数出现至少k次,则认为当前子数组被某个数支配。这种连续的子数组遍历问题,可以用滑动窗口,因为滑动窗口遍历连续的子数组时间复杂度为O(n)。滑动窗口,当窗口内的数组被窗口内的最后一个数支配(之前位置的数都不支配该数组),那么之后的子数组都被某个数支配。此时移动窗口左边界,如果窗口右边界的数支配数组,则窗口内的数组,及窗口右侧的数组也都被某个数支配。即移动窗口,当窗口内的数组被某个数支配,则窗口右边的子数组都被支配。代码:int subArrayByMode(vector<int> & arr, int k) { int n = (int)arr.size(); int rig