【蓝桥杯-刷题篇】基础数学思维与技巧

ゝ一世哀愁。 2024-04-20 07:51 84阅读 0赞

> ?系列专栏:[蓝桥杯][Link 1]
> 
> ?个人主页:[个人主页][Link 2]

**目录**

1.最大化股票交易的利润

2.乌托邦树

3.确定字符串是否是另一个的排列

4.压缩字符串

5.分发饼干

6.棋盘放麦子

7.等差数列

8.质因数个数

9.数数

--------------------

### 1.最大化股票交易的利润 ###

[最大化股票交易的利润 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

![99a49c7bc3df41bb8c538be368def9c9.png][]

**输入**

8
    2 5 6 1 4 3 1 3

**输出**

**方法1：暴力枚举，时间复杂度O(n的平方)**

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n=scanner.nextInt();
            int arr[]=new int[n];
            // 读入数组
            for (int i = 0; i < arr.length; i++) {
    			arr[i]=scanner.nextInt();
    		}
            int sum=Integer.MIN_VALUE;
            // 暴力枚举
            for (int i = 0; i < arr.length-1; i++) {
    			for (int j = i+1; j < arr.length; j++) {
    				sum=Math.max(sum, arr[j]-arr[i]);
    			}
    		}
            // 输出结果
            System.out.println(sum);
          
    
        }
    }

**方法2：存取当前出现过的最小值**

**时间复杂度O(n)**

public class Main {
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n=scanner.nextInt(); // 读取输入的整数个数
            int arr[]=new int[n]; // 创建一个长度为n的整数数组
            for (int i = 0; i < arr.length; i++) { // 循环读取n个整数
    			arr[i]=scanner.nextInt(); // 将读取的整数存入数组
    		}
            int ans=Integer.MIN_VALUE; // 初始化最大差值为整型最小值
            int min=arr[0]; // 初始化最小值为数组的第一个元素
            for (int i = 1; i < arr.length; i++) { // 循环计算最大差值和最小值
            	ans=Math.max(arr[i]-min, ans); // 更新最大差值
    			    min=Math.min(min, arr[i]); // 更新最小值
    		}
            
            System.out.println(ans); // 输出最大差值
            		
        }
    }

### 2.乌托邦树 ###

[乌托邦树 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 1]

![bbd43191a3c74b35a2caf4235d95dc9e.png][]

**输入**

**输出**

知识点：[【蓝桥杯-筑基篇】大整数][-]

import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int t=scanner.nextInt(); // 读取输入的整数t
    
            BigInteger  number=new BigInteger("1"); // 初始化一个大整数number为1
            
            if(t==0) { // 如果t为0，直接输出number并结束程序
            	System.out.println(number);
            	return ;
            }
    
            while(t>0) { // 当t大于0时，执行循环
                number=number.multiply(new BigInteger("2")); // number乘以2
                t--; // t减1
                if(t==0) { // 如果t为0，跳出循环
                    break;
                }
                number=number.add(new BigInteger("1")); // number加1
                t--; // t减1
            }
            System.out.println(number); // 输出number
            
        }
    }

### 3.确定字符串是否是另一个的排列 ###

[确定字符串是否是另一个的排列 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 2]

![878e813834444685aec19b262e53d948.png][]

**输入**

acb
    bac

**输出**

YES

**方法1：HashMap**

知识点：[【蓝桥杯-筑基篇】HashMap][-_HashMap]

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
        	// 创建两个HashMap，用于存储两个字符串中每个字符出现的次数
        	HashMap<Character,Integer> map1=new HashMap<>();
        	HashMap<Character,Integer> map2=new HashMap<>();
            Scanner scanner = new Scanner(System.in);
            // 读入两个字符串
            String s1=scanner.next();
            String s2=scanner.next();
            // 统计第一个字符串中每个字符出现的次数
            for (int i = 0; i < s1.length(); i++) {
            	char c=s1.charAt(i);
    			map1.put(c, map1.getOrDefault(c, 0)+1);
    		}
            // 统计第二个字符串中每个字符出现的次数
            for (int i = 0; i < s2.length(); i++) {
            	char c=s2.charAt(i);
    			map2.put(c, map2.getOrDefault(c, 0)+1);
    		}
            // 判断两个HashMap是否相等，输出结果
            System.out.println(map1.equals(map2)?"YES":"NO");
        }
    }

**方法2：API**

**知识点：**[【蓝桥杯-筑基篇】字符串基础][- 1]

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String s1=scanner.next(); // 读取第一个字符串
            String s2=scanner.next(); // 读取第二个字符串
            char[] arr1=s1.toCharArray(); // 将第一个字符串转换为字符数组
            char[] arr2=s2.toCharArray(); // 将第二个字符串转换为字符数组
            Arrays.sort(arr1); // 对第一个字符数组进行排序
            Arrays.sort(arr2); // 对第二个字符数组进行排序
            if(arr1.length!=arr2.length) { // 如果两个字符数组长度不相等
            	System.out.println("NO"); // 输出 NO
            	return ; // 结束程序
            }
            for (int i = 0; i < arr2.length; i++) { // 遍历第二个字符数组
    			if(arr1[i]!=arr2[i]) { // 如果两个字符数组在相同位置上的字符不相等
    				System.out.println("YES"); // 输出 YES
    				return ; // 结束程序
    			}
    		}
            System.out.println("YES"); // 如果两个字符数组完全相等，输出 YES
    
    
        }
    }

方法3：数组存

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    	
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String s1=scanner.next(); // 读取第一个字符串
            String s2=scanner.next(); // 读取第二个字符串
            int[] arr1=new int[26]; // 存储第一个字符串中每个小写字母出现的次数
            int[] arr2=new int[26]; // 存储第一个字符串中每个大写字母出现的次数
            int[] arr3=new int[26]; // 存储第二个字符串中每个小写字母出现的次数
            int[] arr4=new int[26]; // 存储第二个字符串中每个大写字母出现的次数
            for (int i = 0; i < s1.length(); i++) { // 遍历第一个字符串
            	char c=s1.charAt(i); // 获取当前字符
            	if(c>'Z') { // 如果是小写字母
            		arr1[c-'a']++; // 对应位置加1
            	}
            	else  arr2[c-'A']++; // 如果是大写字母，对应位置加1		
    		}
            for (int i = 0; i < s2.length(); i++) { // 遍历第二个字符串
            	char c=s2.charAt(i); // 获取当前字符
            	if(c>'Z') { // 如果是小写字母
            		arr3[c-'a']++; // 对应位置加1
            	}
            	else  arr4[c-'A']++; // 如果是大写字母，对应位置加1	
            		
    		}
            for (int i = 0; i < arr1.length; i++) { // 遍历数组
    			if(arr1[i]!=arr3[i]||arr2[i]!=arr4[i]) { // 如果对应位置的值不相等
    				System.out.println("NO"); // 输出 NO
    				return ; // 结束程序
    			}
    		}
            System.out.println("YES"); // 输出 YES

**方法4：**

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            // 创建Scanner对象
            Scanner scanner = new Scanner(System.in);
            // 读取两个字符串
            String s1 = scanner.next();
            String s2 = scanner.next();
            // 将字符串转换为字符数组
            char[] arr1 = s1.toCharArray();
            char[] arr2 = s2.toCharArray();
            // 对字符数组进行排序
            Arrays.sort(arr1);
            Arrays.sort(arr2);
            // 将字符数组转换为字符串
            String str1 = new String(arr1);
            String str2 = new String(arr2);
            // 判断两个字符串是否相等并输出结果
            System.out.println(str1.equals(str2) ? "YES" : "NO");
        }
    }

### 4.压缩字符串 ###

> **题目描述**
> 
> 实现一个算法来压缩一个字符串。压缩的要求如下：
> 
> 1.  需要判断压缩能不能节省空间，仅在压缩后字符串比原字符串长度更短时进行压缩。
> 2.  压缩的格式是将连续相同字符替换为字符 + 数字形式，例如 "AAABCCDDDD" 变为 "A3BC2D4"。
> 
> **输入描述**
> 
> 输入一行字符串，长度不超过 500.
> 
> **输出描述**
> 
> 输出一行。若输入的字符串可压缩，则输出压缩后的字符串，否则输出 `NO`。
> 
> **输入**
> 
>     AAABCCDDDD
> 
> **输出**
> 
>     A3BC2D4

**知识点：双指针**

import java.util.Scanner;
    
    public class Main {
    	public static void main(String[] args) {
    
    		Scanner scanner = new Scanner(System.in);
    		char[] s = scanner.next().toCharArray();
    		boolean flag=false;
    		for (int i = 0; i < s.length-1; i++) {
    			if(s[i]==s[i+1]) flag=true; // 如果有相邻的字符相同，flag设为true
    		}
    		
    		if(flag==false) { // 如果flag为false，输出NO并结束程序
    			System.out.println("NO");
    			return;
    		}
    		
    		StringBuilder sb=new StringBuilder();
    		for (int i = 0,j=0; i < s.length;) {
    			
    			while(j+1<s.length&&s[i]==s[j+1])j++; // 找到连续相同字符的最后一个位置
    			int len=j-i+1; // 计算连续相同字符的长度
    			sb.append(s[i]); // 将当前字符加入StringBuilder
    			if(len>1) sb.append(len); // 如果连续相同字符的长度大于1，将长度加入StringBuilder
    			i=j+1; // 更新i的值，开始下一轮查找
    		
    		}
    		System.out.println(sb); // 输出结果
    
    	}
    }

### 5.分发饼干 ###

[分发饼干 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 3]

![c3c8ef7cb9e14afa9b91b10d466c77f4.png][]

**输入**

3 2
    1 2 3
    1 1

**输出**

知识点：[【蓝桥杯-筑基篇】贪心][- 2]

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		int n = scanner.nextInt(); // 输入第一个数组的长度
    		int m = scanner.nextInt(); // 输入第二个数组的长度
    		int arr1[]=new int[n]; // 定义第一个数组
    		int arr2[]=new int[m]; // 定义第二个数组
    		for (int i = 0; i < arr1.length; i++) { // 循环输入第一个数组的元素
    			arr1[i]=scanner.nextInt();
    		}
    		for (int i = 0; i < arr2.length; i++) { // 循环输入第二个数组的元素
    			arr2[i]=scanner.nextInt();
    		}
    
    		Arrays.sort(arr1); // 对第一个数组进行排序
    		Arrays.sort(arr2); // 对第二个数组进行排序
    		int cnt=0; // 定义计数器
    		int i=arr1.length-1; // 定义第一个数组的指针
    		int j=arr2.length-1; // 定义第二个数组的指针
    		while(j>=0&&i>=0) { // 循环比较两个数组的元素
    			if(arr2[j]>=arr1[i]) { // 如果第二个数组的元素大于等于第一个数组的元素
    				i--; // 第一个数组的指针向前移动
    				j--; // 第二个数组的指针向前移动
    				cnt++; // 计数器加1
    			}
    			else { // 如果第二个数组的元素小于第一个数组的元素
    				i--; // 第一个数组的指针向前移动
    			}
    		}
    		System.out.println(cnt); // 输出计数器的值
    	}
    }

### 6.棋盘放麦子 ###

[棋盘放麦子 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 4]

> 你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，问他要什么报酬，大臣说：请在第 11 个棋盘格放 11 粒麦子，在第 22 个棋盘格放 22 粒麦子，在第 33 个棋盘格放 44 粒麦子，在第 44 个棋盘格放 88 粒麦子，......后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有 6464 格）。
> 
> 国王以为他只是想要一袋麦子而已，哈哈大笑。
> 
> 当时的条件下无法准确计算，但估算结果令人吃惊：即使全世界都铺满麦子也不够用！
> 
> 请你借助计算机准确地计算，到底需要多少粒麦子。

知识点：[【蓝桥杯-筑基篇】大整数][-]

import java.math.BigInteger;
    
    public class Main {
    	public static void main(String[] args) {
    
    		BigInteger num=new BigInteger("1"); // 初始化num为1
    		BigInteger sum=new BigInteger("1"); // 初始化sum为1
    		for (int i = 1; i < 64; i++) { // 循环64次
    			num=num.multiply(new BigInteger("2")); // num乘2
    			sum=sum.add(num); // sum加上num
    		}
    		System.out.println(sum); // 输出sum
    	
    	}
    }

###  ###

### 7.等差数列 ###

[等差数列 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 5]

![f94530f6edad4698b53b6fdb50e6b6fa.png][]

**输入**

5
    2 6 4 10 20

**输出**

样例说明：

包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    	public static void main(String[] args) {
    		// 创建Scanner对象
    		Scanner scan = new Scanner(System.in);
    		// 读取输入的整数n
    		int n=scan.nextInt();
    		// 创建长度为n的整型数组arr
    		int arr[]=new int[n];
    		// 循环读取n个整数并存入数组arr中
    		for (int i = 0; i < arr.length; i++) {
    			arr[i]=scan.nextInt();
    		}
    		// 对数组arr进行排序
    		Arrays.sort(arr);
    		
    //		System.out.println(Arrays.toString(arr));
    		// 初始化min为整型最大值
    		int min=Integer.MAX_VALUE;
    		// 循环遍历数组arr，计算相邻两个元素之间的差的最小值
    		for (int i = 0; i < arr.length-1; i++) {
    			min=Math.min(min, arr[i+1]-arr[i]);
    		}
    		
    		// 如果min为0，说明数组中所有元素都相等，直接输出n并结束程序
    		if(min==0) {
    			System.out.println(arr.length);
    			return;
    		}
    		
    		// 初始化cnt为1，sum为数组arr的第一个元素
    		int cnt=1;
    		int sum=arr[0];
    		// 循环计算数组arr中每个元素与第一个元素之间的差，如果差等于min，则cnt加1，sum加上min
    		while(sum!=arr[arr.length-1]) {
    			cnt++;
    			sum+=min;
    		}
    		
    		// 输出cnt
    		System.out.println(cnt);
    	}
    }

### 8.质因数个数 ###

[质因数个数 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 6]

![3eb54c0b7af74d248cfde23dd38851c4.png][]

**因为n<10的16次方，故此暴力法 不能完成全部的测试用例**

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
        	
        	//不需要遍历到n，任何一个数，它的质因子大于根号n的要么没有，要么只有一个
            //对于正整数 N 来说，它的任意一个因数 T 都是它质因数的乘积
            //但是要注意一个问题，比如说 求6得质因子个数，当i*i<=6时结束循环，此时i一定是小于3的，按照我们的分析 6应该包含2个质因子(2和3)，
            //所以当循环完毕时，要判断一下 n此时的值，若为1 说明已经把质因数找完，若不为1，那么剩下的一定是个质数
            Scanner sc = new Scanner(System.in);
            long n = sc.nextLong(); // 读入一个长整数n
            int ans = 0; // 记录n的因子个数
    
            for (int i = 2; i <= Math.sqrt(n); i++) { // 从2到n的平方根遍历
                if(n%i == 0) { // 如果i是n的因子
                    ans++; // 因子个数加1
                }
                while(n%i==0) { // 如果i是n的因子
                    n = n/i; // 将n除以i，更新n的值
                }
            }
            if (n > 1) ans++; // 如果n大于1，说明n本身也是一个因子，因子个数加1
            System.out.println(ans); // 输出因子个数
        }
    }

### 9.数数 ###

[数数 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn 7]

> **问题描述**
> 
> 任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2×2×728=2×2×7 被分解为了三个质数相乘。请问在区间 \[2333333, 23333333\] 中有多少个正整数 可以被分解为 12 个质数相乘?
> 
> **答案提交**
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

public class Main {
     public static void main(String[] args) {
          int count = 0;
          for (long i = 2333333; i <= 23333333; i++) {
              if (chack(i)){
                  count++;
              }
          }
          System.out.println(count);
    //     System.out.println(25606);
    
     }
    
     private static boolean chack(long n) {
    
         int ans=0;
         //只需要到sqrt(n)即可，因为如果有一个因数大于等于sqrt(n)
         // 那么必定有一个因数小于等于sqrt(n)
         for (int i = 2; i <= Math.sqrt(n) ; i++) {
             //快速找到所有的质因子
             while (n % i == 0){
                 n/=i;
                 //更新数据
                 ans++;
             }
         }
         /*
             比如最后的n为5的时候,n%i!=0
             但是5也是这里面的一个质数
             所以这个质因子5不能漏掉
              */
         if(n>1)ans++;
         return ans == 12 ;
     }

[Link 1]: https://blog.csdn.net/javascript_tsj/category_12167433.html
[Link 2]: https://blog.csdn.net/Javascript_tsj?type=blog
[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/307/learning/?page=1&first_category_id=1&sort=students_count&name=%E4%BA%A4%E6%98%93
[99a49c7bc3df41bb8c538be368def9c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3225b74fc7fe482d90e5b40ff8f8a7d2.png
[- _ _lanqiao.cn 1]: https://www.lanqiao.cn/problems/324/learning/?page=1&first_category_id=1&sort=students_count&name=%E4%B9%8C
[bbd43191a3c74b35a2caf4235d95dc9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ef8f00a8b997440e93712c5226aba938.png
[-]: https://blog.csdn.net/Javascript_tsj/article/details/129441006?spm=1001.2014.3001.5501
[- _ _lanqiao.cn 2]: https://www.lanqiao.cn/problems/203/learning/?page=1&first_category_id=1&sort=students_count&name=%E7%A1%AE%E5%AE%9A
[878e813834444685aec19b262e53d948.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2360c6db30e04d97b4466b15ac4d0694.png
[-_HashMap]: https://blog.csdn.net/Javascript_tsj/article/details/129877751?spm=1001.2014.3001.5502
[- 1]: https://blog.csdn.net/Javascript_tsj/article/details/129469090?spm=1001.2014.3001.5502
[- _ _lanqiao.cn 3]: https://www.lanqiao.cn/problems/321/learning/?page=1&first_category_id=1&sort=students_count&name=%E5%88%86%E5%8F%91
[c3c8ef7cb9e14afa9b91b10d466c77f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/21c3a9979623430997aa80a8ad008e3a.png
[- 2]: https://blog.csdn.net/Javascript_tsj/article/details/129753152?spm=1001.2014.3001.5502
[- _ _lanqiao.cn 4]: https://www.lanqiao.cn/problems/739/learning/?page=1&first_category_id=1&sort=students_count&name=%E6%A3%8B%E7%9B%98
[- _ _lanqiao.cn 5]: https://www.lanqiao.cn/problems/192/learning/?page=1&first_category_id=1&sort=students_count&name=%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97
[f94530f6edad4698b53b6fdb50e6b6fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/db011a9e7b2749d38104a604d7b86a60.png
[- _ _lanqiao.cn 6]: https://www.lanqiao.cn/problems/2155/learning/?page=1&first_category_id=1&sort=students_count&name=%E8%B4%A8%E5%9B%A0%E6%95%B0%E4%B8%AA%E6%95%B0
[3eb54c0b7af74d248cfde23dd38851c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3f3a1fd8ec4d427ab19222d6a3b3d5d2.png
[- _ _lanqiao.cn 7]: https://www.lanqiao.cn/problems/2218/learning/?page=1&first_category_id=1&sort=students_count&name=%E6%95%B0%E6%95%B0