优化算法以接受不喜欢的字符串和[Prereq，next_class]子数组的数组，输出在它之前可以接受的类数。

Question

我们想要避免的课程肯定在课程和先决条件列表的某个地方。不会有不可接受的课程。可能有多个没有先决条件的课程。提示符是创建一个用于避免的过程的函数，以及一个课程和先决条件的列表。返回在我们想要避免的课程之前可以选择多少课程。不喜欢的课程应该列在课程和先决条件的清单上，保证。函数返回在我们想要避免的课程之前可以选择多少课程。

我用手写了这个算法，没有任何效率。我希望有人能帮助我优化它，或者指导我使用现代javascript算法的最佳实践，因为我花了比平常更长的时间来形成一个解决方案。此外，如果有人能帮助我计算我所拥有的大O时间复杂性，解释为什么另一个解决方案更好，这将是非常感激的。

var disliked = "Linear Algebra";

var prereqs = [
  ["Calculus 1", "Calculus 2"],
  ["Calculus 2", "Linear Algebra"],
  ["Linear Algebra", "Discrete Math"],
  ["Discrete Math", "Analysis of Algorithms"],
  ["Algorithms", "Analysis of Algorithms"],
  ["Data Structures", "Algorithms"],
  ["Algorithms", "AI"],
  ["Calculus 1", "AI"],
  ["AI", "Computer Vision"],
  ["Algorithms", "Networks"],
  ["Algorithms", "Operating Systems"],
  ["Analysis of Algorithms", "Theory of CS"],
];

function countCourses(disliked, prereqs) {

  // [x] 1) Choose dislike: ie, alg
  //  for each array {
  //    if current array indice 0 === "alg" (ie, dislike)
  //      push its indice value 1 to new array, delete current array
  //  ex, uniques[] = [analysis, AI, NET, OS]
  //  new array:  [calc1, calc2], [calc2, lin alg],[lin alg, d math], [d math, analysis], [d. struct, alg]
  //              [calc1, AI], [AI, comp], [analysis, theory]
  //
  // O(N)
  let next_classes = [];
  for (let i = 0; i < prereqs.length; i++) {
    if (prereqs[i][0] === disliked) {
      next_classes.push(prereqs[i][1]);
      prereqs.splice(i, 1);
      i = i - 1;
    }
  }
  console.table(next_classes);
  console.table(prereqs);
  
  // For each next class requirement in the sequence (after disliked class)
  // Remove, add to impossible_classes as we cannot take them
    // impossible_courses[]:  [analysis, AI, net, OS]
  for(let i = 0; i < prereqs.length; i++) {
    for(let j = 0; j < next_classes.length; j++) {
      if (prereqs[i][0] === next_classes[j]) {
        next_classes.push(prereqs[i][1]);
        //prereqs.splice(i, 1);
        //j = i - 1;
      }
    }
    }
  console.table(next_classes);
  
  // 2) for each array {
  //    if current array indice 0 === [a unique value] (ie, value from [analysis, AI, net, OS])
  //      delete current array
  //      Effectively deletes classes after unique [analysis, AI, net, OS] in the sequence,
  //      which cannot also be taken
  //      ie, theory, comp
  for (let i = 0; i < prereqs.length; i++) {
    for (let j = 0; j < next_classes.length; j++) {
      if (prereqs[i][0] === next_classes[j]) {
        prereqs.splice(i, 1);
        i = 0;
      }
    }
  }

  // if nothing inside impossible_courses --> that means,
  // the course you dislike is a "final course", nothing comes after it
  // it contains only pre-requisites.
  if (next_classes.length === 0) {
    for (let i = 0; i < prereqs.length; i++) {
      // find the disliked final course
      if (prereqs[i][1] === disliked) {
        // delete disliked course array from prereqs
        prereqs.splice(i, 1);
        // return the size of prereqs -
        console.table(prereqs);
        return prereqs.length;
      }
    }
  } else {
    

    console.table(prereqs);
    



    // use concat() to merge all prereqs into one
    const flattenedPrereqs = [].concat(...prereqs);

    const distinctCourses = [...new Set(flattenedPrereqs)];
    // remove all occurences of 'disliked' course and impossible courses
    // from the flattened array
    for(let i = 0; i < distinctCourses.length; i++) {
      if(distinctCourses[i] === disliked) {
        distinctCourses.splice(i, 1);
      }
      for (let j = 0; j < next_classes.length; j++) {
        if (distinctCourses[i] === next_classes[j]) {
          distinctCourses.splice(i, 1);
          i = i - 1;
        }
      }
    }

    console.table(distinctCourses);
    return distinctCourses.length;
  }
  // NOTE: You may use print statements for debugging purposes, but you may
  //       need to remove them for the tests to pass.
}

console.log(countCourses(disliked, prereqs));

这是一个使用“线性代数”作为不喜欢的过程的输出示例：

$ node disliked_courses.js 
┌─────────┬─────────────────┐
│ (index) │     Values      │
├─────────┼─────────────────┤
│    0    │ 'Discrete Math' │
└─────────┴─────────────────┘
┌─────────┬──────────────────────────┬──────────────────────────┐
│ (index) │            0             │            1             │
├─────────┼──────────────────────────┼──────────────────────────┤
│    0    │       'Calculus 1'       │       'Calculus 2'       │
│    1    │       'Calculus 2'       │     'Linear Algebra'     │
│    2    │     'Discrete Math'      │ 'Analysis of Algorithms' │
│    3    │       'Algorithms'       │ 'Analysis of Algorithms' │
│    4    │    'Data Structures'     │       'Algorithms'       │
│    5    │       'Algorithms'       │           'AI'           │
│    6    │       'Calculus 1'       │           'AI'           │
│    7    │           'AI'           │    'Computer Vision'     │
│    8    │       'Algorithms'       │        'Networks'        │
│    9    │       'Algorithms'       │   'Operating Systems'    │
│   10    │ 'Analysis of Algorithms' │      'Theory of CS'      │
└─────────┴──────────────────────────┴──────────────────────────┘
┌─────────┬──────────────────────────┐
│ (index) │          Values          │
├─────────┼──────────────────────────┤
│    0    │     'Discrete Math'      │
│    1    │ 'Analysis of Algorithms' │
│    2    │      'Theory of CS'      │
└─────────┴──────────────────────────┘
┌─────────┬───────────────────┬──────────────────────────┐
│ (index) │         0         │            1             │
├─────────┼───────────────────┼──────────────────────────┤
│    0    │   'Calculus 1'    │       'Calculus 2'       │
│    1    │   'Calculus 2'    │     'Linear Algebra'     │
│    2    │   'Algorithms'    │ 'Analysis of Algorithms' │
│    3    │ 'Data Structures' │       'Algorithms'       │
│    4    │   'Algorithms'    │           'AI'           │
│    5    │   'Calculus 1'    │           'AI'           │
│    6    │       'AI'        │    'Computer Vision'     │
│    7    │   'Algorithms'    │        'Networks'        │
│    8    │   'Algorithms'    │   'Operating Systems'    │
└─────────┴───────────────────┴──────────────────────────┘
┌─────────┬─────────────────────┐
│ (index) │       Values        │
├─────────┼─────────────────────┤
│    0    │    'Calculus 1'     │
│    1    │    'Calculus 2'     │
│    2    │    'Algorithms'     │
│    3    │  'Data Structures'  │
│    4    │        'AI'         │
│    5    │  'Computer Vision'  │
│    6    │     'Networks'      │
│    7    │ 'Operating Systems' │
└─────────┴─────────────────────┘
8

Answer 1

我猜这是一门课的作业。这很好，尽管在将来，请注意这个问题。

你有一个可行的解决方案，所以值得称赞！干得好。你要求帮助分析它的算法复杂性。恐怕我的脑子现在还没准备好。但是您也要求改进，我可以提供一个非常简单的实现。

但是，如果您还没有研究递归，那么您可能想跳过这个答案，因为它使用递归，虽然它实际上并不是一个复杂的主题，但是您可能希望等到它被引入到您的研究中。

但是，如果您对递归有一定的经验，下面是我的实现：

​

const countCourses = (disliked, prereqs) => {
  const courses = unique (prereqs .flat())
  const ineligible = allDependencies (prereqs) (disliked)
  const eligible = courses .filter (c => ! ineligible .includes (c))
  return eligible .length
}

const unique = (xs) => [... new Set (xs)]

const allDependencies = (prereqs) => (disliked) => unique ([
  disliked, 
  ...prereqs .filter (([p]) => p == disliked) 
             .map (([_, c]) => c) 
             .flatMap (allDependencies (prereqs))
])


const prereqs = [['Calculus 1', 'Calculus 2'], ['Calculus 2', 'Linear Algebra'], ['Linear Algebra', 'Discrete Math'], ['Discrete Math', 'Analysis of Algorithms'], ['Algorithms', 'Analysis of Algorithms'], ['Data Structures', 'Algorithms'], ['Algorithms', 'AI'], ['Calculus 1', 'AI'], ['AI', 'Computer Vision'], ['Algorithms', 'Networks'], ['Algorithms', 'Operating Systems'], ['Analysis of Algorithms', 'Theory of CS']]
const disliked = 'Linear Algebra'

console .log (countCourses (disliked, prereqs))

​

我们的主要功能相对简单。我们从先决条件列表中提取所有课程的列表。你在你的代码里这么做。我认为这个单线比较简单，但它是一种类似的技术。它使用帮助器unique，它只是将一个数组通过一个Set移动回一个数组，以便删除重复的数组。这是足够简单的，我可能经常内联，但我再次使用它在下面，所以它值得拔出。

然后，我调用一个助手函数来收集所有阻塞的课程。接下来我们将讨论这个助手函数。在此之后，我们将所有课程的列表过滤到那些不在阻止列表中的课程中。与您的版本相比，使用filter调用执行此操作要简单得多，而且在算法上可能也是如此。如果没有其他的话，它可以避免splice调用；我认为这是一个非常罕见的情况，splice是个好主意。

最后，我们返回该数组的长度。

但是现在我们需要讨论助手allDependencies。又一次，看起来是这样的：

const allDependencies = (prereqs) => (disliked) => unique ([
  disliked, 
  ...prereqs .filter (([p]) => p == disliked) 
             .map (([_, c]) => c) 
             .flatMap (allDependencies (prereqs))
])

我们首先看到的是unique包装器。在我们完成剩下的工作之后，我们将使用它来删除重复的内容。(这就是我提取助手函数而不是在主函数中插入它的原因；我们在这里再次使用它。)理由很简单。虽然我们的主要功能会很好，如果我们不费心删除重复，这似乎是一个真正有用的功能本身，所以它应该足够好，以自己站起来。这意味着，如果课程B和C依赖于A，而D依赖于B和C，那么我们的结果不应该包括D两次。这个unique调用确保了这一点。

该函数的主体将给定的不喜欢的过程和执行三个步骤的结果收集到数组中：

• 过滤先决条件数组，查找第一个元素是不喜欢的元素的所有项，
• 接受每个先决条件中的第二个元素，直接依赖于不喜欢的课程，
• ，并收集现在不喜欢的每一个课程的allDependencies调用结果。

这最后一步是递归步骤，也是最有可能具有挑战性的步骤。我们调用.flatMap (allDependencies (prereqs)) .flatMap是一个数组方法，它对其每个元素调用提供的函数，并将结果数组组合成一个数组。我们传递给它函数allDependencies (prereqs)注意，这是一个函数，因为allDependencies是一个接受prereqs的函数，返回一个接受disliked并返回值的函数。这种函数返回函数技术非常有用。但这并不重要，我们可以这样写：

const allDependencies = (disliked, prereqs) => unique ([
  disliked, 
  ...prereqs .filter (([p]) => p == disliked) 
             .map (([_, c]) => c) 
             .flatMap (c => allDependencies (c, prereqs))
])

并这样称呼它：

  const ineligible = allDependencies (disliked, prereqs)

但我发现这种草率的方法更干净。

这可能与您所见过的其他递归不同，因为基本情况没有在许多地方那样清晰地描述。但它就在那里。当结果的依赖项列表为空时，我们将停止。在这种情况发生之前，我们一直在重复。

我发现主函数阅读起来非常简单，而且allDependencies助手也不算太糟。他们肯定简化了你的方法。

我不知道这个答案的运行时效率如何与您的版本相比。但是代码更简洁，甚至可以教一些更高级的技术。我希望它能帮上忙！