首页 > 猿辅导两道两道编程代码
头像
洛霞
编辑于 2020-10-24 20:38
+ 关注

猿辅导两道两道编程代码

我这边编程题一共两道,一道是数字组合被整除的最小数字,一道是拓扑排序类型的判断是否依赖循环,两道全部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) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐