数组切分 (蓝桥杯)爆搜,剪枝 JAVA

这篇具有很好参考价值的文章主要介绍了数组切分 (蓝桥杯)爆搜,剪枝 JAVA。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

已知一个长度为N的数组:A1, A2, A3,…, AN 恰好是1…N 的一个排列。
现在要求你将A数组切分成若干个(最少一个,最多N个) 连续的子数组, 并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
例如对于A={1,3,2,4}存在5种切分方法。
1、{1}{3}{2}{4}
2、{1}{3,2}{4}
3、{1}{3,2,4}
4、{1,3,2}{4}
5、{1,3,2,4}

输入格式:

第一行包含一个整数N。
第二行包含N个整数,代表A数组。
对于30% 评测用例,1≤N≤20。
对于100% 评测用例,1≤N≤10000。

输出格式:

输出一个整数表示答案。 由于答案可能很大,
所以输出其对1000000007取模后的值。

输入样例:

4
1 3 2 4

输出样例:

5


dfs 暴力破解 :

解题思路:

秉承“万物皆可爆搜”的信念,本题我们继续利用爆搜来混分。

1.首先对于题目给出的例子我们得有一个系统的解题方法(也就是咱得先会做,找到规律,再让电脑做。):

对题目给的例子进行分析如下:

数组切分 (蓝桥杯)爆搜,剪枝 JAVA
不难发现,这完全就是一颗递归树。其中每一层都对应每层递归内部的 for 循环,每一条路径都对应着一个符合题目要求的切分方法。
(还有一点就是我们可以看到,每一层 for 循环内的子数组都互不影响,所以这需要用到回溯。)

2.如判断某子数组内的整数,恰好可以组成一段连续自然数?

这里给出一个技巧:
子数组最大元素值 - 子数组最小元素值 = 子数组最大下标 - 子数组最小下标

即: max - min = j - i
若此等式成立,则子数组内整数恰好可以组成一段连续自然数。

数组切分 (蓝桥杯)爆搜,剪枝 JAVA

数组切分 (蓝桥杯)爆搜,剪枝 JAVA
由于数组内元素不能重复,所以上述等式是成立的。

3.解决完上述问题我们就需要贴合,dfs + 回溯 的模式,将答案爆搜出来。

理论成立代码如下:

dfs + 回溯(void类型):

import java.util.Scanner;

public class Main {
 
 public static int n = 0;
 public static int a[];//放在这里等会写函数就不用调用
 
 public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
     n = sc.nextInt();//注意别写成 int n
     a = new int[n];
  
     for(int i = 0; i < n; i ++) a[i] = sc.nextInt();
     
     dfs(0);//从第一个元素开始
     
     System.out.print(sum % 1000000007);//输出答案
 }
 public static int sum = 0;
 public static int max = Integer.MIN_VALUE;
 public static int min = Integer.MAX_VALUE;
 
 public static void updatave(int x, int y){//找到区间内最大值与最小值
       for(int i = x; i <= y; i ++) { 
        max = Math.max(max, a[i]);
        min = Math.min(min, a[i]);
       }
 }
 
 public static void default_state(){//将max,min 恢复默认状态
  max = Integer.MIN_VALUE;
  min = Integer.MAX_VALUE;
 }
 
 public static void dfs(int i) {
  if(i == n) sum ++;//重要的事情最先做,不能写 成n - 1,否者以j = n - 1结尾的情况不会被记录
  
  for(int j = i; j < n; j ++) {//本身也是一个最小连续子区间,所以从本身开始
   updatave(i, j);
   if(max - min == j - i) {//满足连续子区间
    default_state();//max,min要恢复默认状态,防止影响下面的递归操作
    dfs(j + 1);
    default_state();//运行完也要恢复默认状态,防止影响 j = i + 1的循环
   }
 }
 }
}

本代码在官方平台上能能拿到五成分数,感觉能混到这么多还是不错的,一直以为只能得三成分数。
数组切分 (蓝桥杯)爆搜,剪枝 JAVA

纯 dfs (int类型):

import java.util.Scanner;

public class Main {
	
    public static int mod = 1000000007;
    public static int n = 0;
    public static int a[];
    public static int memo[];
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new  int[n];
		for(int i = 0; i < n; i ++) {
			a[i] = sc.nextInt();
		}
		System.out.print(dfs(0)); 
	}
	public static int dfs(int index) {
		 if(index == n) return 1;//到达末端返还1
		 int sum = 0;
		 int max = Integer.MIN_VALUE;
		 int min = Integer.MAX_VALUE;
		 for(int i = index; i < n; i ++) {
			 max = Math.max(max, a[i]);
			 min = Math.min(min, a[i]);
			 if(max - min == i - index) {
				 sum = (sum + dfs(i + 1)) % mod;//将符条件的加起来
			 }
		 }
		 return sum;
	}
}

数组切分 (蓝桥杯)爆搜,剪枝 JAVA

纯 dfs (void类型):

import java.util.*;

public class Main {
    public static int n;
    public static int a[];
	public static void main(String[] args) {
		 Scanner sc = new Scanner(System.in);
		 n = sc.nextInt();
		 a = new int[n];
		 for(int i = 0; i < n; i ++) a[i] = sc.nextInt();
		 dfs(0);
		 System.out.print(sum);
	}
    public static int sum = 0;
    public static void dfs(int index) {
    	if(index == n) sum ++;
    	int max = Integer.MIN_VALUE;
    	int min = Integer.MAX_VALUE;
        for(int j = index; j < n; j ++) {
        	max = Math.max(max, a[j]);
        	min = Math.min(min, a[j]);
        	if(max - min == j - index) dfs(j + 1);
        }
    }
}

数组切分 (蓝桥杯)爆搜,剪枝 JAVA


dfs + 备忘录(满分):

解题:

创作灵感来源于一个低调的大佬,今天一位大佬跟我分享了他的 dfs + 备忘录代码,焯 !只能说写的太优雅了!😍

由于我用暴力用的太久了,默认暴力只能拿一部分分数,今天大佬的代码给我狠狠的打醒了,即可以对 dfs 生成的递归树,通过这种使用备忘录的方法,达到剪枝的效果。

由于我有幸之前懵懂时期在力扣中学过备忘录,再加上大哥的代码足够简洁,我侥幸的能在这么短的时间明白其中原理,只能说相见恨晚,上正题:

以 A= {1,2, 3, 4} 为例

按题目要求生成的递归树如下:
数组切分 (蓝桥杯)爆搜,剪枝 JAVA
数组切分 (蓝桥杯)爆搜,剪枝 JAVA
上图递归树,每层都是一个新的递归内容,本层内每个枝节都对应着整个 for 循环的每种情况:

对上述递归树简要观察不难发现:
数组切分 (蓝桥杯)爆搜,剪枝 JAVA
如上图所示,蓝色矩形区域,和红色圆圈区域都有重复,正是这些重复部分消耗了额外的无效时间,导致超时,引入备忘录的作用就是记录这些值,以便在下次遇见,就不必再次计算,也就是空间换时间。如下:
数组切分 (蓝桥杯)爆搜,剪枝 JAVA
如上,将第一次出现的蓝色矩形和红色圆圈部分记录下来,下方再次出现直接调用memo备忘录即可:

数组切分 (蓝桥杯)爆搜,剪枝 JAVA
如上图就是剪枝后的递归树

明白上述样例,代码就很清晰了
由于我一直用的void类型大哥给的int类型。
所以以下给出两种类型的dfs方法可按喜好选择:

int类型实现:

import java.util.*;

public class Main {
	
    public static int mod = 1000000007;
    public static int n = 0;
    public static int a[];
    public static int memo[];
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new  int[n];
		memo = new int[n + 1];
		for(int i = 0; i < n; i ++) {
			a[i] = sc.nextInt();
			memo[i] = -1;//初始化
		}//记忆数组 焯! 太妙了。
		
	   //注意下标从0开始
		memo[n] = 1;//n越界,说明得到一个方式,返回1。
		
		System.out.print(dfs(0));
		//上下等效。
//		dfs(0);
//      System.out.print(memo[0]);
	}
    public static int dfs(int starIndex) {
    	if(memo[starIndex] != - 1) return memo[starIndex];
    	int sum = 0;
    	int max = Integer.MIN_VALUE;
    	int min = Integer.MAX_VALUE;
    	for(int j = starIndex; j < n; j ++) {
    		max = Math.max(max, a[j]);
    		min = Math.min(min, a[j]);
    		if(max - min == j - starIndex) {
    			sum = (sum + dfs(j + 1)) % mod;
    		}
    	}
    	memo[starIndex] = sum;//存
    	return sum;//返还本层递归的结果
    }
}

void类型实现:

import java.util.Scanner;

public class Main {
	
    public static int mod = 1000000007;
    public static int n = 0;
    public static int a[];
    public static int memo[];
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new  int[n];
		memo = new int[n + 1];
		for(int i = 0; i < n; i ++) {
			a[i] = sc.nextInt();
			memo[i] = -1; 
		} 
		memo[n] = 1; 
        dfs(0);
        System.out.print(memo[0]);
	}
    public static void dfs(int starIndex) {
    	int sum = 0;
    	int max = Integer.MIN_VALUE;
    	int min = Integer.MAX_VALUE;
    	for(int j = starIndex; j < n; j ++) {
    		max = Math.max(max, a[j]);
    		min = Math.min(min, a[j]);
    		if(max - min == j - starIndex) {
    			if(memo[j + 1] == -1)//查看备忘录
    			dfs(j + 1);
    			sum = (sum + memo[j + 1]) % mod;
    		}
    	}
    	memo[starIndex] = sum;//存
    }
}

数组切分 (蓝桥杯)爆搜,剪枝 JAVA

思考dfs + 回溯与 纯 dfs(int类型)的区别 :

dfs + 回溯:

将一条路走到尾,在终点计数,再回溯,找其他可行路径。

纯dfs (int 类型):

从递归末端,将可行路径数量,传递到上一层递归,再由上层递归传输至上上层递归,类似大树按次序用所有的根吸收水分,传递到树干的过程。


小结:

如果问我为什么不用动态规划写正解呢,还是基于实际情况考虑。
1,是我动态规划,只学了背包九讲,只是初步了解,让我不看解析去做这道题,我是真打死不会。
2,是动态规划,也是基于爆搜的前提下去,剪切掉多余的重复部分而逐渐得到的最优解法,如果爆搜都并不会的话,想直接写出动态规划,就好似孩子走路都没学会,就让他跑一样牵强。

这里给出大佬,对递归和动态规划区别的看法:
动态规划是递推,从小问题扩展到大问题。而dfs解决这种问题的方式是递归,先是将大问题抛出,然后不断的将问题变小,最后来解决的大问题。

3,是我目前编程水平比较一般,最擅长的还是爆搜,赛场上用爆搜混到目前这些分数已经是超长发挥了,可以磕头烧香了。当然后期用动态规划如何剪枝这道题我也会去学习的,但前提得先把爆搜学好,毕竟用爆搜解这道题我都想了半天更何况动态规划,而且蓝桥杯快到了。。。。

最后,水平高的大佬可以看看别人的dp解法,如果这个爆搜方法还有可以优化的地方也欢迎大佬们指点。
数组切分 (蓝桥杯)爆搜,剪枝 JAVA文章来源地址https://www.toymoban.com/news/detail-406295.html

到了这里,关于数组切分 (蓝桥杯)爆搜,剪枝 JAVA的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十三届蓝桥杯国赛 C++ C 组 Java A 组 C 组 Python C 组 E 题——斐波那契数组(三语言代码AC)

    如果数组 A = ( a 0 , a 1 , ⋯ . a n − 1 ) A=(a_0,a_1,⋯.a_{n-1}) A = ( a 0 ​ , a 1 ​ , ⋯ . a n − 1 ​ ) 满足以下条件, 就说它是一个斐波那契数组: n ≥ 2 ; n≥2; n ≥ 2 ; a 0 = a 1 a_0=a_1 a 0 ​ = a 1 ​ 对于所有的 i ( i ≥ 2 ) , i(i≥2), i ( i ≥ 2 ) , 都满足 a i = a i − 1 + a i − 2 。 a_i=a_{i-1}+a_{i-2

    2024年01月18日
    浏览(44)
  • 蓝桥杯-动态规划-子数组问题

    目录 一、乘积最大数组 二、乘积为正数的最长子数组长度 三、等差数列划分 四、最长湍流子数组 心得: 最重要的还是状态表示,我们需要根据题的意思,来分析出不同的题,不同的情况,来分析需要多少个状态 乘积最大数组 1.状态表示 dp[i]:到达i位置的最大乘积子数组。

    2024年02月05日
    浏览(36)
  • 组合(力扣)dfs + 回溯 + 剪枝 JAVA

    给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例 2: 输入:n = 1, k = 1 输出:[[1]] 提示: 1 = n = 20 1 = k = n 解题思路: 1.每个元素有选与不选两种情况,

    2024年02月16日
    浏览(52)
  • leetcode814. 二叉树剪枝(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/binary-tree-pruning 给你二叉树的根结点 root ,此外树的每个结点的值要么是 0 ,要么是 1 。 返回移除了所有不包含 1 的子树的原二叉树。 节点 node 的子树为 node 本身加上所有 node 的后代。 示例1: 输入:root = [1,null,0,0,1] 输出:

    2024年02月10日
    浏览(39)
  • 第九届蓝桥杯省赛——3字母阵列(二维数组)

    仔细寻找,会发现:在下面的8x8的方阵中,隐藏着字母序列:“LANQIAO”。 SLANQIAO ZOEXCCGB MOAYWKHI BCCIPLJQ SLANQIAO RSFWFNYA XIFZVWAL COAIQNAL 我们约定: 序列可以水平,垂直,或者是斜向; 并且走向不限(实际上就是有一共8种方向)。 上图中一共有4个满足要求的串。 下面有一个更大的

    2024年02月15日
    浏览(46)
  • (leetcode1761一个图中连通三元组的最小度数,暴力+剪枝)-------------------Java实现

    题目表述 给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] = [ui, vi] ,表示 ui 和 vi 之间有一条无向边。 一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。 连通三元组的度数 是所有满足此条件的边的数目:一个顶点

    2024年02月10日
    浏览(38)
  • Python 训练集、测试集以及验证集切分方法:sklearn及手动切分

    目录 方法一 方法二 需求目的:针对模型训练输入,按照6:2:2的比例进行训练集、测试集和验证集的划分。当前数据量约10万条。如果针对的是记录条数达上百万的数据集,可按照98:1:1的比例进行切分。 方法一:切分训练集和测试集,采用机器学习包sklearn中的train_test_split()函

    2024年02月04日
    浏览(37)
  • Python Pandas:DataFrame 一列切分成多列、分隔符切分选字段

    创建一个复杂又简单的数据集 split expand:这个参数直接将分列后的结果转换成 DataFrame drop axis 是指处哪一个轴 columns 是指某一列或者多列 inplaces 是否替换原来的 dataframe

    2024年02月12日
    浏览(67)
  • 【蓝桥杯算法模板题--蓝桥题库Java】

    PDF下载地址:点击即可 题目描述 给定一个长度为 N 的数组 A ,请你先从小到大输出它的每个元素,再从大到小输出它的每个元素。 输入描述 第一行包含一个整数 N 。 第二行包含 N 个整数 a1,…,an ,表示数组 A 的元素。 1≤N≤5×10 5,−10 9≤ai≤10^9。 输出描述 输出共两行,

    2023年04月09日
    浏览(105)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包