资源引用：

7.创意标题匹配问题（易）

14.数组元素之和最小化（中）

12.最大UCC字串计算（难）

久违小碎碎念：

假期开始，继续更新！感谢wj同学的拷打敦促！

稀土掘金-7.创意标题匹配问题（7.创意标题匹配问题）

题目分析：

给定一个含有成对的'{}'作为通配符的字符串，每个通配符内可以包含0或多个字符，含有通配符的字符串叫做“创意”，对应字符串template_。此时又给出存储在字符串数组titles中的n个标题，需要依次判断这些标题是否是从template_生成的。

解题思路：

将模板中由通配符隔开的部分提取出，然后逐个在标题中找到其匹配以判断是否符合模板。

需要注意：

• 模板结尾是否为通配符
• 匹配过程中，除最后一部分用最末尾匹配lastIndexOf，其余用最先匹配的indexOf

原因：

strs中的各个部分依次与标题s2进行最先匹配，使用indexOf查找该部分在当前s2中首次出现的位置，若查找成功则接着对下一部分进行匹配，并更新s2为未检查部分（即indexOf查找的位置加上该部分的长度所得到的位置往后的字符串）。

到最后一部分时，若模板以通配符结尾，则只需检查s2中是否存在该部分即可；若模板不以通配符结尾，则该部分必须是s2的结尾部分，故使用lastIndexOf来查找该字符串的最末尾匹配。

总结反思：

这是一道字符串匹配题目，通过引入可任意匹配的通配符，给解题增加了一定难度，需要注意两方面：

1. 字符串方法indexOf和lastIndexOf的实现
2. 分类讨论模板文件是否以通配符结尾

import java.util.ArrayList;
import java.util.List;

public class Main {

    // 查找子字符串最后一次出现的位置
    private static int findLastSubstring(String target, String sub) {
        int pos = target.lastIndexOf(sub);
        return pos != -1 ? pos : -1;
    }

    // 判断标题是否可以从模板生成
    private static boolean test(String s1, String s2) {
        List<String> strs = new ArrayList<>();
        int l = 0;
        boolean a = false;// 判断模板是否以通配符结尾
        
        //将创意模板中由通配符分隔开的部分依次添入strs中
        while (l < s1.length()) {
            if (s1.charAt(l) != '{') {
                StringBuilder s = new StringBuilder();
                while (l < s1.length() && s1.charAt(l) != '{') {
                    s.append(s1.charAt(l++));
                }
                strs.add(s.toString());
            } else {
                while (l < s1.length() && s1.charAt(l) != '}') {
                    l++;
                }
                l++;
                if (l == s1.length()) a = true;
            }
        }

        for (int i = 0; i < strs.size(); i++) {
            if (i != strs.size() - 1) {
                int index = s2.indexOf(strs.get(i));
                if (index == -1) return false;
                s2 = s2.substring(index + strs.get(i).length());
            } else {
                int pos = findLastSubstring(s2, strs.get(i));
                if (pos != -1 && a) return true;
                if (pos + strs.get(i).length() != s2.length() || pos == -1) return false;
            }
        }
        return true;
    }

    public static String solution(int n, String template_, String[] titles) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < titles.length; i++) {
            if (test(template_, titles[i])) {
                result.append("True");
            } else {
                result.append("False");
            }
            if (i != titles.length - 1) {
                result.append(",");
            }
        }
        System.out.println(result);
        return result.toString();
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        String[] testTitles1 = {"adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"};
        String[] testTitles2 = {"CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"};
        String[] testTitles3 = {"abcdefg", "abefg", "efg"};

        System.out.println(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1).equals("True,False,False,True"));
        System.out.println(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2).equals("False,False,False,False,False,True"));
        System.out.println(solution(3, "a{bdc}efg", testTitles3).equals("True,True,False"));
    }
}

稀土掘金-14.数组元素之和最小化（14.数组元素之和最小化）

题目分析：

给定数组的元素个数n，最大公约数k，构造这样的一个无重复元素的数组并使其元素之和尽可能小，输出该数组元素之和的最小值。

解题思路：

符合要求的数组一定包含元素k才能使元素之和最小，由此可以得到数组的第一个元素即为k。

又因为数组中的元素的最大公约数为k，则数组中的元素均为k的整数倍。又因为数组中的元素不可重复，欲使元素之和最小，数组中的元素若按升序排列，则分别为该元素的1~n倍数。

总结反思：

需要注意静态变量与临时变量的关系

若使用sum += (i * k);则参数k本身没有被改动

若使用k *= i; sum += k;则参数k本身被改动，k *= i并不能得到最初的参数k的i倍数。

public class Main {
    public static int solution(int n, int k) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += (i * k);
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(solution(3, 1) == 6);
        System.out.println(solution(2, 2) == 6);
        System.out.println(solution(4, 3) == 30);
    }
}

稀土掘金-12.最大UCC字串计算（12.最大UCC字串计算）

题目分析：

已有一个由U和C组成的字符串s，通过不超过m次“编辑操作”得到尽可能多的“UCC”子串，并输出最多的的子串数。

编辑操作定义：插入、删除或替换单个字符为一次操作。

解题思路：

定义有效操作：

定义单次有效操作：一次能使“UCC”子串数增多1个的编辑操作。

• 插入有效操作：

• • 对“UC”子串插入“C”；
  • 对“CC”子串插入“U”

• 删除有效操作：

• • 对“UCUC”子串删除第二个“U”

• 替换有效操作：

• • 对“UUC”子串替换第二个“U”为“C”
  • 对“UCU”子串替换第二个“U”为“C”
  • 对“CCC”子串替换第一个“C”为“U”

对比观察：

思路一：

观察三类有效操作可以发现：

• 删除有效操作需要4个操作数
• 替换有效操作需要3个操作数
• 插入有效操作需要2个操作数

可知：

插入操作是最高效的选择，则所有操作均为插入操作时，获取UCC子串的效率最高。

思路二：

观察三类有效操作可以发现：

• 删除操作：

仅在“UCUC”子串下能够有效，然而这无疑是低效的。

因为通过两次插入可以得到两次有效操作，删除却使得可利用的“U”丢失，因而不考虑删除操作。

• 修改操作：

由“删除操作”得到启发，保留较多的字符以便利用，那么修改操作能否由增加字符的插入操作替代呢？探究如下：

1. 对UUC，m=3：

1. 1. 修改UUC为UCC，只剩2个操作，则至多增加2个字符，共5个字符，无法得到更多UCC
   2. 插入3个字符，得到6个字符，显然可以得到2个UCC

1. 对UCU，m=3，与上述同理
2. 对CCC，m=3，仍然与上述同理

综上可知：

所有操作均应采取插入操作，以获取尽可能多的有效操作。

此外，对于UCC子串，显然不应进行任何操作，在进行每一步操作前，应标记已为UCC子串组成部分的字符为“已使用”，每一步操作和新增UCC子串时不可牵涉“已使用”的字符串。

补充：无需对字符串本身进行改动，只需标记是否使用过即可。

解题步骤：

1. 检查初始字符串s，得到UCC子串个数并标记已使用字符
2. 遍历字符串，对符合插入有效操作的子串进行操作，更新UCC子串数、字符使用情况和剩余操作次数。
3. 对剩余字符，由于插入有效操作的操作数为2，则剩余字符必然为孤立的单个字符U或C，且夹在已使用字符之间。因此，每个剩余的孤立字符均消耗2次操作以增加1个UCC子串数。
4. 若仍有剩余操作次数，而原字符串已经没有未使用字符，则每3次操作可增加1个UCC子串，最终得到结果。

总结反思：

1. 通过合理的分析并选择操作方式，以符合要求的同时简化过程。
2. 注意对res、cnt和m的更新
3. 对于操作步骤，按照效率高低，显然优先进行1次插入即可获得UCC子串的操作，然后再对剩余未使用的孤立字符进行2次操作获取UCC子串，最终若有剩余操作次数，则每3次操作可增加1个UCC子串

public class Main {
    public static int solution(int m, String s) {
        int res = 0;
        int cnt = 0;
        int n = s.length();
        boolean[] use = new boolean[n];
        // 检查初始字符串
        for (int i = 2; i < n; i++) {
            String t = s.substring(i-2, i+1);
            if (t.equals("UCC")) {
                use[i] = 
                use[i-1] =
                use[i-2] = true;
                cnt += 3;
                res++;
                i += 2;// 跳过已遍历字符，无需重复检查
            }
        }
        // 遍历字符串做插入有效操作
        for (int i = 1; i < n; i++) {
            if (!use[i-1] && !use[i] && m > 0) {
                String t = s.substring(i-1, i+1);
                if (t.equals("UC") || t.equals("CC")) {
                    use[i] = 
                    use[i-1] = true;
                    cnt += 2;
                    res++;
                    m--;//
                    i++;// 跳过已遍历字符，无需重复检查
                }
            }
        }
        // 对每个孤立字符做2次插入操作
        res += Math.min(m/2, n-cnt);
        m -= Math.min(m/2, n-cnt)*2;
        // 充分使用剩余操作数
        res += m/3;
        return res;
    }

    public static void main(String[] args) {
        System.out.println(solution(3, "UCUUCCCCC") == 3);
        System.out.println(solution(6, "U") == 2);
        System.out.println(solution(2, "UCCUUU") == 2);
    }
}