当前位置: 首页> 文旅> 旅游 > 淄博百度电话_四川九江龙钢结构网架公司_球队积分排名_阿里云建网站

淄博百度电话_四川九江龙钢结构网架公司_球队积分排名_阿里云建网站

时间:2025/7/11 14:28:52来源:https://blog.csdn.net/cjejwe/article/details/146164031 浏览次数:2次
淄博百度电话_四川九江龙钢结构网架公司_球队积分排名_阿里云建网站

目录

前言

第一题 1482. 制作 m 束花所需的最少天数 - 力扣(LeetCode)

第二题  962. 最大宽度坡 - 力扣(LeetCode)

第三题 3.星际旅行 - 蓝桥云课

结尾  


前言

本博客是记录和分享笔者写过的一些算法题,在帮助自己梳理思路的同时分享给愿意看的人,这些题目笔者认为值得一写,让我们一起进步,提高代码能力!

如标题所示, 这一期分享一些笔者写过的 关于单调栈,简单DFS,BFS和二分的题目,题目来源主要是蓝桥云的题库和力扣.

笔者并非是大牛,部分题解参考和模仿了大佬的写法,感谢那些愿意分享题解和思路的大佬!!!

第一题 1482. 制作 m 束花所需的最少天数 - 力扣(LeetCode)

涉及的知识点:二分查找答案减少时间复杂度

这道题需要我们去求等待的最少天数,很明显是需要我们枚举出一些可能的天数,看看是否符合题意,这样的话,我们可以使用二分算法去枚举可能的天数,然后根据题意模拟一遍,知道找到最小的而且符合的天数.

关于左右边界的确定,不需要直接套模板,因为根据题意,左边界肯定是bloomDay数组的最小值,右边界同理,最大值,这样就减少了二分查找的次数,而根据示例二,我们可以提前判断是否可以制作出足够数量的花束.

以下是笔者的代码:


class Solution {public int minDays(int[] bloomDay, int m, int k) {if (m > bloomDay.length / k) {return -1;}int low = Integer.MAX_VALUE, high = 0;int length = bloomDay.length;for (int i = 0; i < length; i++) {low = Math.min(low, bloomDay[i]);    // 左边边界high = Math.max(high, bloomDay[i]);  // 右边边界}while (low < high) {int days = (high - low) / 2 + low;if (canMake(bloomDay, days, m, k)) {high = days;} else {low = days + 1;}}return low;}public boolean canMake(int[] bloomDay, int days, int m, int k) {int num = 0; // 要求的花的数量int flowers = 0;  // 能连续的花的数量int length = bloomDay.length;for (int i = 0; i < length && num < m; i++) {if(bloomDay[i]<=days){flowers++;if(flowers==k){num++;flowers=0;}}else{flowers = 0;}}return num >= m;}
}

其中这一段代码的思路是这样的:

 public boolean canMake(int[] bloomDay, int days, int m, int k) {int num = 0; // 要求的花的数量int flowers = 0;  // 能连续的花的数量int length = bloomDay.length;for (int i = 0; i < length && num < m; i++) {if(bloomDay[i]<=days){flowers++;if(flowers==k){num++;flowers=0;}}else{flowers = 0;}}return num >= m;}

因为题目要求的是连续的花朵,遍历数组,如果符合条件就让 flowers 增加,如果等于了要求的数量,num增加,flowers重新归零,但是,因为要求是连续的,假设在flowers的大小没有到达K之前,就已经出现了天数不够的情况,flowers要立刻归零,这样才能体现出要求连续的花朵.

本题强化了笔者对于二分算法的理解和使用

第二题  962. 最大宽度坡 - 力扣(LeetCode)

考察了使用单调栈解题.

首先,这一题当然可以使用暴力算法,直接 外层 for循环,内存for循环,然后维护最大值. 这样的的确确可以写出来,但是时间复杂度是 O(n^2) 所以,笔者介绍另一种思路

1.首先,我们构建一个单调递减的栈,

它的核心作用是:

 在数组 A 中,找到当前元素 A[j] 在它左侧最小的元素 A[i],并保证索引 i<j

但是!它不是简单的存储最小值,它实际上存储的是:

 数组中"最有可能形成最大坡宽"的起点索引 i,因为我们要保证宽距 j-i尽可能的大!

所以:

  • 我们在遍历数组时,必须优先保留最小值,同时保证索引靠前
  • 这就导致了:
    • 如果当前元素 A[i]≥A[stack.peek()] ,说明当前元素不会成为坡起点,直接跳过

自己想想很简单,我比你小,还比你靠左,为什么要选你不选我?肯定是选我呀.

代码如下:

class Solution {public static int maxWidthRamp(int[] A) {int n = A.length;Stack<Integer> stack = new Stack<>(); // 维护一个单调递减栈,存索引int maxWidth = 0;// **1. 先构造单调递减栈,存储可能的 i**for (int i = 0; i < n; i++) {if (stack.isEmpty() || A[stack.peek()] > A[i]) {stack.push(i);}}// **2. 从后往前遍历 j,找到最大 j - i**for (int j = n - 1; j >= 0; j--) {while (!stack.isEmpty() && A[stack.peek()] <= A[j]) {int i = stack.pop();maxWidth = Math.max(maxWidth, j - i);}}return maxWidth;}
}

第三题 3.星际旅行 - 蓝桥云课

考察了图的存储和简单BFS.

 首先,根据题意,使用邻接表方式建图是比较合适的,然后通过BFS算法,去查找 y消耗之前,我们可以去多少星球, 邻接表的数据结构和 哈希的散列表类似,都是一个"链表数组"

"链表数组",即 数组的每个元素都是链表的数组.

代码如下:

import java.util.*;
import java.math.*;public class Demo31
{static int n, m, Q;static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 邻接表方式建图static double ans = 0;public static int bfs(int start,int maxstep){Queue<int []> queue = new LinkedList<>();boolean[] visited = new boolean[n + 1];queue.offer(new int[]{start,0}); // 把起点加入队列,起点还未移动过,因此步数为0  // 这个新初始化的数组表示什么? start 表示点,0表示用了多少步数int count = 1;visited[start] = true;//start 这个点已经走过了while(!queue.isEmpty()){int [] cur = queue.poll();int node = cur[0];//点的位置int step = cur[1];//步数if(step<maxstep)  // 步数小于最大步数{for(int nei : graph.get(node)) // 遍历以node为头结点的链表,也就是node 的相邻节点{if(visited[nei]==false){visited[nei] =true;count++;queue.offer(new int[]{nei,step+1});}}}}return count;}public static void main(String[] args) {Scanner scanner =new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();Q = scanner.nextInt();graph.clear();for(int i = 0;i<=n;i++){graph.add(new ArrayList<>());// 创建好 邻接表}for(int i =1;i<=m;i++){int ai = scanner.nextInt();int bi = scanner.nextInt();graph.get(ai).add(bi);graph.get(bi).add(ai);}for(int i = 1;i<=Q;i++){int x = scanner.nextInt();int y = scanner.nextInt();// x 表示起始点,y表示最大步数ans +=bfs(x,y);}System.out.printf("%.2f\n", ans / Q);}
}

笔者的队列中放的是一个数组,这样的话,0下标可以表示位置,1下标可以表示步数,使用起来也相对简单 

结尾  

博客到此结束,希望对看到这里的人有用,这不是题解,更像是笔者的推荐题.

关键字:淄博百度电话_四川九江龙钢结构网架公司_球队积分排名_阿里云建网站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: