字符串集合

偏执的太偏执、 2024-03-31 15:23 37阅读 0赞

## 前言 ##

学了一段时间的字符串书写，今天就浅浅发个集合吧。也算做个阶段性总结，方便以后复习。这一篇字符串集合也发到了蓝桥杯刷题笔记专栏里。接下来的几个月时间里，也会发一些专栏集合，和刷题总结啥的。冲刺蓝桥杯！那我们开始字符串旅程吧！

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

## 目录 ##

1. 门牌制作

2. 子串分值和

3. 用杂志拼接信封

4. 山

总结编辑

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

## 1. 门牌制作 ##

[门牌制作][Link 1]

> 小蓝要为一条街的住户制作门牌号。
> 
> 这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。
> 
> 小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、7，即需要 1 个字符 0，2 个字符 1，1 个字符 7。请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？

**分析**

先看一眼题目，即是统计每一个字符出现的次数，要知道从1到2020出现了几个字符2，这里列举出三种方法。

*  方法1：**暴力搜索。** 我们从1~2020进行遍历，每遍历一次，就判断改数字是否出现了数字2（对该数字取余看它是否等于2），对每一次遍历后的结果进行统计，最终得到2出现的次数。
 *  方法2：**字符串检索**。 首先我们可以将1~2020拼接成一个字符串长串，然后遍历该字符串，判断该索引下的字符是否为2；最后统计出现的次数。
 *  方法3：**字符串替换。** 也是先将数字拼接成一个字符串，然后用“null”替换掉不是2的数字，最终得到的字符串长度就是出现字符2的次数。

**代码如下：**

public class 门牌制作 {
        public static void main(String[] args) {
            int ans1 = 0; //统计个数（需要多少个字符2）
            int ans2 = 0; //统计个数（需要多少个字符2）
    
            /**
             * 方法1: 暴力搜索
             */
    
            for(int i=1; i<=2020; i++){
                ans1 += howmany2(i);
            }
            System.out.println(ans1);
    
      // ------------------------------------------------------------
    
            /**
             * 方法2：字符串检索
             */
            String a = ""; //初始化a字符串
            for(int i = 1; i <= 2020; i++) a += i; //这里将12345……2022无缝拼接成一个很长的字符串
            for(int i = 0; i < a.length(); i++){
                if(a.charAt(i) == '2') ans2++; //注意：这里是'2',而不是2,判断匹配的是2这个字符
            }
            System.out.println(ans2);
    
       // ------------------------------------------------------------
    
            /**
             * 方法3：字符串替换
             */
            String b = "";
            for(int i = 1; i <= 2020; i++) b += i; //字符串拼接
            //replaceAll(); 把第一个的值用第二个替换，返回的长度就是有几个2
            System.out.println(b.replaceAll("[0-1]|[3-9]","").length());
    
        }
    
        public static int howmany2(int n){
            int cnt = 0; //统计个数（需要多少个字符2）
            while (n>0){
                if(n%10 == 2) cnt++;
                n /= 10;
            }
            return cnt;
        }
    }

建议多去看看API，真的很有用。

## 2. 子串分值和 ##

> 对于一个字符串S，我们定义S的分值f(S)为S 中出现的不同的字符个数。例如f("aba") = 2, f("abc") = 3, f("aaa") = 1。现在给定一个字符串S\[0……n-1\] (长度为n)，请你计算所有S的非空字串S\[i...j\] (0 <= i <= j <n), f(S\[i...j\]) 的和是多少。

**分析**

这道题就是统计不同字母出现的个数。这里给出两种方法实现：

*  方法1：**字符数组。** 我们可以用一个含有26个字母的 int 数组来存放26个字母出现的次数，数组长度作为每个字母的索引，从a~z。如果原字符串里出现这个字母，我们就把该字母出现的次数增加一次。最终将 int 数组里值不为0的个数统计就是不同字母出现的次数。
 *  方法2：**哈希表。** 我们知道哈希表有去重的性质，那么我们就可以将字符串加入到哈希表里（不会哈希表可以去看我的哈希表集合）。最终返回哈希表的长度即可。

**上代码：**

public class 子串分值和 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String s = sc.next();
            int ans = num1(s);
            System.out.println(ans);
    
        }
        //用字符数组
        private static int num1(String s){
            int[] sum = new int[26]; //里面装的是26个字母出现的次数
            for(int i=0; i < s.length(); i++){
                sum[s.charAt(i)-'a']++; 
            }
            int d = 0; //存储出现的次数
            for(int i = 0; i < 26; i++){
                if(sum[i] != 0) d++;
            }
            return d;
        }
        //用哈希表
        private static int num2(String s){
            Set<Character> set = new HashSet<>();
            for(int i = 0; i < s.length(); i++){
                set.add(s.charAt(i));
            }
            return set.size();
        }
        //用哈希表查看每个字符添加到哈希表的过程
        private static int num3(String s){
            int sum = 0;
            for(int i = 0; i < s.length(); i++){
                Set<Character> set = new HashSet<>();
                String m = "";
                for(int j = i; j < s.length(); j++){
                    set.add(s.charAt(j));
                    m = m + s.charAt(j);
                    sum  = sum + set.size(); //哈希表是去重的
                    System.out.println(m + " " + set.size());
                }
            }
            return sum;
        }
    }

## **3. 用杂志拼接信封** ##

> 实现一个算法确定能否由杂志构成信件。介绍如下：
> 
> 影视剧中信件大多是从报纸或杂志上的字符剪下来拼接而成的。
> 
> 杂志和信件均由字符串构成，对于给定的杂志和信件，确定信件是否可以由杂志上的字符构成。
> 
> 例如杂志为 `ab`，信件为 `aa`，则不能构成。杂志为 `aab`，信件为 `aa`，则可以构成。

**分析**

既然是字符串集合，这里就将字符拆分做法吧。（代码里面也附上了哈希表做法）

*  跟上一道题一样，这一道题也是可以用数组来统计每个字母出现的次数，如果杂志里字幕出现的次数小于信件里的，就不能构成。没有出现的字母次数是0；出现了1次就是1；以次类推。

**上代码：**

public class 杂志2 {
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            String s = sc.next(); //杂志
            String l = sc.next(); //信件
            int[] ms = new int[26],ml = new int[26];
            for(int i = 0; i < s.length(); i++)
            {
                char c = s.charAt(i); //将字符串s放入字符数组c中，c中存放的是字母
                //ms里存放的是字母，'a'-'a'=0,得到m[0]就是a的位置，然后a位置的数值+1；'b'-'a'=1,得到m[1]就是b的位置，然后b位置的数值+1；
                //如果有两个字母一样的话，那么该字母的位置上的数值就再+1，最终得到该26个字母在相应位置出现的次数
                ms[c-'a']++;
            }
            for(int i = 0; i < l.length(); i++)
            {
                char c = l.charAt(i);
                ml[c-'a']++;
            }
            //判断杂志上的字符是否可以构成信件
            for(int i = 0; i < 26; i++)
            {
                //这里也就是在比较字母出现次数的大小了
                if(ms[i] < ml[i])
                {
                    System.out.println("NO");
                    return;
                }
            }
            System.out.println("YES");
        }
    }

public class 用杂志拼接信封
    {
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            String s = sc.next(); //杂志
            String l = sc.next(); //信件
            HashMap<Character,Integer> ms = new HashMap<>();
            HashMap<Character,Integer> ml = new HashMap<>();
            for(int i = 0; i < s.length(); i++)
            {
                char c = s.charAt(i); //将字符串s放入字符数组c中
                ms.put(c,ms.getOrDefault(c,0)+1); //这里对应的下标值+1，防止空指针
            }
            for(int i = 0; i < l.length(); i++)
            {
                char c = l.charAt(i); //将字符串s放入字符数组c中
                ml.put(c,ms.getOrDefault(c,0)+1);
            }
            //判断杂志上的字符是否可以构成信件
            for(char i = 'a'; i <= 'z'; i++) //这里for循环遍历字母A~Z
            {
                //如果某个字母在哈希表中存在，就返回该字母在哈希表中的下标，不存在就返回0
                //若杂志的长度小于信件的长度，则代表不能构成（这里每次是判断一个字符，依次判断每一个字符）
                //因为哈希表不能存相同的值（若相同，则会被后面的相同值覆盖），所以返回相同值最大的下标
                if(ms.getOrDefault(i,0) < ml.getOrDefault(i,0))
                {
                    System.out.println("NO");
                    return;
                }
            }
            System.out.println("YES");
        }
    }

## 4. 山 ##

[第十三届蓝桥杯真题][Link 2]

> 这天小明正在学数数。
> 
> 他突然发现有些止整数的形状像一挫 “山”, 比如 123565321 、 145541123565321、145541, 它 们左右对称 (回文) 且数位上的数字**先单调不减, 后单调不增。**
> 
> 小朋数了衣久也没有数完, 他惒让你告诉他在区间 2022, 2022222022 中有 多少个数的形状像一座 “山”。

**分析**

我们首先想到的方法肯定是暴力，我们从 `2022` 到 `2022222022` 遍历，对于每一个数，我们判断是否是回文串，并且是否满足是递增再递减的序列，最后统计答案 ， 时间复杂度大概是 10^10 级别的，大概在本地要跑 90-100s 左右 。已经超时了，所以我们不能用这种做法。

*  由本题题意可知我们最多能形成`长度为 10`的回文串，于是我们暴力枚举前五个不下降序列，偶数长度和奇数长度的不下降子序列分开维护，最后判断形成的回文串是否在 20,2022222022 区间即可。

import java.util.Collections;
    import java.util.Scanner;
    
    public class Main {
        static int ans = 0 ; //符合条件的数
        static int o[] = new int[20] ; //偶数长度的序列
        static int e[] = new int[20] ; //奇数长度的序列
    
        static long get(int[] s , int n) {//n为序列长度，s是一个暂存数组
            long res = 0 ;
            for(int i = 1 ; i <= n ; i ++)
                res = (res * 10 + s[i]) ;//这里就是返回序列数，res即原数
            while(res > 0 && res % 10 == 0) res /= 10 ; //因为我们前后添加了0，这里在做去0处理
            return res ;
        }
    
        static void dfs(int u , int last) {//u代表位数，last代表最后一位的值
            if(u == 6) {
                //判断序列是否在范围之间
                if(get(o , 10) >= 2022 && get(o , 10) <= 2022222022) ans ++ ;
                if(get(e , 9) >= 2022 && get(e , 9) <= 2022222022) ans ++ ;
                return ;
            }
            for(int i = last ; i <= 9 ; i ++) {
                //构造回文串，即对称数字
                o[u] = o[10 - u + 1] = i ;//第i位等于对称位
                e[u] = e[9 - u + 1] = i ;
                dfs(u + 1 , i) ;//循环，第十位，0~9
            }
        }
        public static void main(String[] args) {
            dfs(1 , 0) ;
            System.out.println(ans) ;
        }
    
    }

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

## **总结**![7565c6f92442454ba212b728572adcfd.png][] ##

用题目来简单对字符串的运用做了一个集合，对于字符串的运用要熟练运用还是要通过多做题目，另外，API里也有很多String，Char，Arrays里面很多方法，多运用库函数更能简化我们做题的步骤。今天的分享就到这里啦！

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

[Link 1]: https://www.lanqiao.cn/courses/11011/learning/?id=579745
[Link 2]: https://www.lanqiao.cn/courses/11011/learning/?id=580011
[7565c6f92442454ba212b728572adcfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/76cb09930dcb45e5bc357403c07841d7.png