房天下房官网_不定时更换域名请务必收藏_苏州关键词优化搜索排名_今天nba新闻最新消息

资源引用：

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 hereString[] 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);}
}