字节青训营 | 数字分组求偶数和
数字分组求偶数和
问题描述
小M面对一组从 1 到 9 的数字,这些数字被分成多个小组,并从每个小组中选择一个数字组成一个新的数。目标是使得这个新数的各位数字之和为偶数。任务是计算出有多少种不同的分组和选择方法可以达到这一目标。
numbers
: 一个由多个整数字符串组成的列表,每个字符串可以视为一个数字组。小M需要从每个数字组中选择一个数字。
例如对于[123, 456, 789]
,14个符合条件的数为:147 149 158 167 169 248 257 259 268 347 349 358 367 369
。
测试样例
样例1:
输入:
numbers = [123, 456, 789]
输出:14
样例2:
输入:
numbers = [123456789]
输出:4
样例3:
输入:
numbers = [14329, 7568]
输出:10
JavaScript代码
(含注释&要点)
// 目标: 分组内的任选一个数,各组各数之和 得偶数。有几种分法。
// 思路:
// ① 将每个数字组拆成单个数字
// ② 记录每个数字的奇偶性
// ③ 递归/回溯 从每个数字组中选择一个数字,并检查各数之和是否为偶数
// ④ 计算结果:递归的终止条件中,检查当前组合的各数之和是否为偶数。
function solution(numbers) {
// ① 将每个数字拆成单个数字(法一):第二个map, ★(.map(Number))将其转为数字类型
// let digits = numbers.map(numStr => (numStr + '').split('').map(Number))
// console.log(digits)
// ① 将每个数字拆成单个数字(法二):
let n = numbers.length;
let str = [];
let result = 0;
for (let i = 0; i < n; i++) {
let t = [];
t = (numbers[i] + '').split('');
str.push(t.map(Number));
}
console.log(str)
// ② 记录每组数字的奇偶性.数组1为奇数,0为偶数
let parity = str.map(group => group.map(x => x % 2))
// ③ 组合计算
// 问题:如何表示第一个数组中的某个数与其他的数组相加
// 解决:★递归/回溯!!
// ③ 使用回溯法或组合生成法,从每个数字组中选择一个数字,并检查其各位之和是否为偶数
function backtrack(index, currentSum) {
// 终止条件:若已选择了所有数字组,检查当前组合的各位之和是否为偶数(做判断 是在终止条件内)
if (index === str.length) {
return currentSum % 2 === 0 ? 1 : 0;
}
let count = 0;
// 选择当前的数字组内的元素
for (let num of str[index]) {
// 递归调用,选择下一个数字组中的数字
count += backtrack(index + 1, currentSum + num);
}
return count;
}
// ④ 统计符合条件的组合资源
return backtrack(0, 0)
}
function main() {
console.log(solution([123, 456, 789]));
console.log(solution([123, 456, 789]) === 14);
console.log(solution([123456789]) === 4);
console.log(solution([14329, 7568]) === 10);
}
main();
Java代码
import java.util.ArrayList;
import java.util.List;
public class Main {
public static int solution(int[] numbers) {
// 思路:
// ① 将每组数字拆成单个数字
// ② 记录每个数字的奇偶性
// ③ 递归/回溯,从每个数字组中选择一个数字,并检查各数之和是否为偶数
// ④ 计算结果:递归的终止条件中,检查当前组合的各数之和是否为偶数
int n = numbers.length;
List<List<Integer>> digits = new ArrayList<>();
for(int i = 0;i < n;i++){
List<Integer> group = new ArrayList<>();
char[] charArr = Integer.toString(numbers[i]).toCharArray(); //将数字转为字符数组
for(int j = 0;j < charArr.length;j++){
group.add(charArr[j]-'0');
}
digits.add(group);
}
return backtrack(digits, 0, 0);
}
// 组合选择,用递归、回溯的方法,从数字组中选择一个数字,并检查各位之和是否为偶数
private static int backtrack(List<List<Integer>> digits, int index, int currentSum){
// 终止条件:若已选择了所有数字组
if(index == digits.size()) {
return currentSum % 2 == 0 ? 1 : 0;
}
int count = 0;
for(int num : digits.get(index)){ // 增强for循环;List特有方法get、set、add、remove
// 递归调用,选择下一个数字组中的数字
count += backtrack(digits, index+1, currentSum + num);
}
return count;
}
public static void main(String[] args) {
System.out.println(solution(new int[]{123, 456, 789}) == 14);
System.out.println(solution(new int[]{123456789}) == 4);
System.out.println(solution(new int[]{14329, 7568}) == 10);
}
}
创意标题匹配问题
问题描述
在广告平台中,为了给广告主一定的自由性和效率,允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候,会根据用户的搜索词触发的 bidword 对创意中的通配符(通配符是用成对 {} 括起来的字符串,可以包含 0 个或者多个字符)进行替换,用来提升广告投放体验。例如:“{末日血战} 上线送 SSR 英雄,三天集齐无敌阵容!”,会被替换成“帝国时代游戏下载上线送 SSR 英雄,三天集齐无敌阵容!”。给定一个含有通配符的创意和n个标题,判断这句标题是否从该创意替换生成的。
测试样例
样例1:
输入:
n = 4, template = "ad{xyz}cdc{y}f{x}e", titles = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
输出:"True,False,False,True"
样例2:
输入:
n = 3, template = "a{bdc}efg", titles = ["abcdefg", "abefg", "efg"]
输出:"True,True,False"
样例3:
输入:
n = 5, template = "{abc}xyz{def}", titles = ["xyzdef", "abcdef", "abxyzdef", "xyz", "abxyz"]
输出:"True,False,True,True,True"
Java代码
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Pattern;
public class Main {
public static String solution(int n, String template, String[] titles) {
// n个测试样例,template 通配符,titles模板
// 思路:① 记录通配符,② 匹配
// 将模板转换为正则表达式,并确保匹配整个字符串
String regex = template.replaceAll("\\{[^}]*}",".*");
regex = "^" + regex + "$";
// 创建一个 StringBuilder 来存储结果
StringBuilder result = new StringBuilder();
// 遍历每个标题。若匹配成功,添加true;失败则添加false
for(String title: titles) {
result.append( Pattern.matches(regex,title) ? "True" : "False").append(",");
}
// 删除最后一个逗号
if(result.length() > 0) {
result.deleteCharAt(result.length()-1);
}
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"));
}
}
参考:青训营链接【✍️ 入营考核】AI 加码,青训营 X 豆包MarsCode 技术训练营👏 欢迎各位同学报名“AI 加码,青训营 X - 掘金 (juejin.cn)
AI刷题-掘金 (juejin.cn)
字节掘金青训营题解(持续更新)-CSDN博客
202410 青训营(5题)-CSDN博客
字节青训营 数字分组求偶数和 组合数-CSDN博客
数字分组求偶数和_2024字节跳动青训营中数字分组求偶数和的答案-CSDN博客
java for 循环遍历list java for循环遍历集合_轩辕的技术博客_51CTO博客
java list的get java list的get方法_coolfengsy的技术博客_51CTO博客