我这边编程题一共两道,一道是数字组合被整除的最小数字,一道是拓扑排序类型的判断是否依赖循环,两道全部ac,这边给出代码,语言用的是JS
第一道
第一道是给一系列数字,比如:[4, 1, 3, 0]
,求出组合当中能被K整除的最小数字,以0开头舍去0(比如134),都没有满足条件返回-1.
这道题是一个回溯问题,因为是最小数字,所以先给数组从小到大排序完再回溯会更优,找到符合条件的立刻退出回溯。
const [N, K] = readline().split(" ").map(i => parseInt(i)); const arr = readline().split(" ").sort((a, b) => b - a); const len = arr.length; // 记录对应所以处的数字是否使用过 const monitor = new Array(len).fill(0); let res = ''; const fn = (arr, len, K, cur) => { if (cur.length === len && parseInt(cur) % K === 0) { res = cur; return true; } for (let i = 0; i < len; i++) { if (monitor[i] === 1) continue; else if (monitor[i] === 0) { monitor[i] = 1; const newCur = cur + arr[i]; if (newCur[0] === '0') { monitor[i] = 0; continue; } const result = fn(arr, len, K, newCur); if (result === true) return result; monitor[i] = 0; } } } fn(arr, len, 7, "") print(res === "" ? -1 : res);
第二道
第二道是拓扑排序,有向无环图判断是否循环。
const isXunHuan = (N, match) => { if (match.length === 0) return 0; // 存储每个编号的入度 const edges = new Array(N).fill(0); // 存储有向图 const indeg = {}; for (let i = 0; i < match.length; i++) { const [dataIn, dataOut] = match[i]; edges[dataIn]++; indeg[dataOut] == undefined ? indeg[dataOut] = [dataIn] : indeg[dataOut].push(dataIn); } let index = edges.indexOf(0); while (edges.indexOf(0) > -1) { const index = edges.indexOf(0); const deduce = indeg[index]; edges[index]--; if (!deduce) { continue; } for (let i = 0; i < deduce.length; i++) { const shifang = deduce[i]; edges[shifang] > 0 ? edges[shifang]-- : null; } } return edges.every(i => i === -1) ? 0 : 1; } const T = parseInt(readline()); for (let k = 0; k < T; k++) { // 共有N项资源 const N = parseInt(readline()); const match = []; for (let i = 0; i < N; i++) { const line = readline().split(" ").map(i => parseInt(i)); for (let j = 0; j < N; j++) { if (line[j] === 1) match.push([i, j]); } } print(isXunHuan(N, match)); }
全部评论
(3) 回帖