技术面试的问题解决模式:解释频率计数器模式

2020年12月30日10:54:00 发表评论 28 次浏览

本文概述

在上一篇文章中, 我分享了有关如何准备软件开发人员面试.

在本文中, 我将稍作讨论, 并讨论可用于解决技术面试问题的常见模式。我们将讨论频率计数器深度模式, 以帮助你有效地解决它。

什么是"频率计数器"模式?

频率计数器模式使用对象或集合来收集值和这些值的频率。

此模式通常与Array或一个String, 并可以避免嵌套循环(二次时间复杂度O(n²))。

什么时候应该使用频率计数器模式?

当你有多个要相互比较的数据时, 频率计数器模式最有用。让我带你看一个例子, 看看运行中的频率计数器。

" SameSquared"练习

  • 编写一个名为同平方接受两个数组
  • 该函数应返回trueif每一个第一个数组中的值在第二个数组中具有对应的值平方
  • 值的频率必须相同

最佳结果是什么?

编写函数后, 我们应该期待同平方函数返回这些值。

sameSquared([1、2、3], [4、1、9]);//正确

sameSquared([1, 2, 3], [1, 9]);//错误

sameSquared([1, 2, 1], [4, 4, 1]);//错误

sameSquared([2, 3, 6, 8, 8], [64, 36, 4, 9, 64]);//正确

入门

首先, 使用函数关键字, 我们使用标识符创建一个函数同平方:

function sameSquared() {

我们的职能同平方需要两个参数, 第一个数组和第二个数组。在此示例中, 我们传递了这些值[1, 2, 3]和[4, 1, 9].

function sameSquared(firstArr, secondArr) {

检查边缘情况

在我们的功能块内部, 我们要解决一些边缘情况。首先, 我们需要检查两个参数是否具有真实值, 即不 null, 未定义, 等等。

我们可以通过使用!操作员。如果firstArrorsecondArr是虚假的, 我们回来false.

function sameSquared(firstArr, secondArr) {
  if (!firstArr || !secondArr) return false;

我们要考虑的下一个边缘情况是确保两个数组的长度相同。如果他们不同, 我们知道他们可以不包含相等数量的共享值。

通过检查长度两个参数的属性, 我们可以确定它们是否相同。如果不是, 我们返回false.

function sameSquared(firstArr, secondArr) {
  if (!firstArr || !secondArr) return false;
  if (firstArr.length !== secondArr.length) return false;

建立一个"字典"以避免嵌套循环

我们需要跟踪至少一个数组中的所有值。为此, 为了避免嵌套循环, 我们可以将这些值存储在哈希表(对象)中。我打电话给我抬头.

function sameSquared(firstArr, secondArr) {
  if (!firstArr || !secondArr) return false;
  if (firstArr.length !== secondArr.length) return false;

  const lookup = {};

用一个的循环, 我们遍历firstArr。里面的的块, 我们将密钥分配给值*值.

此键/值对中的值为频率计数器这反映了在特定值中"看到"多少次了firstArr.

首先, 我们检查抬头包含一个条目值*值, 如果有, 我们添加1对此。如果不是, 我们将值分配给0然后添加1.

function sameSquared(firstArr, secondArr) {
  if (!firstArr || !secondArr) return false;
  if (firstArr.length !== secondArr.length) return false;

  const lookup = {};

  for (value of firstArr) {
    lookup[value * value] = (lookup[value * value] || 0) + 1;
  }

一旦firstArr完成循环后, 抬头应该包含以下值:

{
  1: 1, 4: 1, 9: 1
}

比较数组值

现在, 我们已经遍历了firstArr并将它们分别存储平方值, 我们想将这些值与secondArr.

我们首先创建另一个的循环。在我们新产品的第一行的块, 我们写一个条件语句来检查是否来自我们的当前值secondArris不在我们里面抬头。如果不是, 我们停止循环并返回false.

如果来自secondArr在我们的抬头, 我们要减少该条目的值。我们可以使用-=赋值运算符。

function sameSquared(firstArr, secondArr) {
  if (!firstArr || !secondArr) return false;
  if (firstArr.length !== secondArr.length) return false;

  const lookup = {};
  for (value of firstArr) {
    lookup[value * value] = (lookup[value * value] || 0) + 1;
  }
  for (secondValue of secondArr) {
    if (!lookup[secondValue]) return false;
      lookup[secondValue] -= 1;
    }

完成循环后, secondArr, 我们的抬头应该具有以下值:

{
  1: 0, 4: 0, 9: 0
}

包装我们的" sameSquared"功能

如果我们完成遍历secondArr不回false, 这意味着我们firstArr包含所有处于平方状态的值secondArr。因此, 我们返回true在外面的循环。

function sameSquared(firstArr, secondArr) {
  if (!firstArr || !secondArr) return false;
  if (firstArr.length !== secondArr.length) return false;

  const lookup = {};
  for (value of firstArr) {
    lookup[value * value] = (lookup[value * value] || 0) + 1;
  }
  for (secondValue of secondArr) {
    if (!lookup[secondValue]) return false;
    lookup[secondValue] -= 1;
  }
  return true;
}

让我向你展示另一个示例, 该示例在编码评估中非常常用(因此你以前可能已经看到过此问题)。

" isAnagram"练习

  • 编写一个名为isAnagram接受两个字符串
  • 该函数应返回true如果两个字符串参数是字谜彼此的

最佳结果是什么?

编写函数后, 我们应该期待isAnagram函数返回这些值。

isAnagram(" silent", " listen");//正确

isAnagram(" martin", " nitram");//正确

isAnagram(" cat", " tag");//错误

isAnagram(" rat", " tar");//正确

入门

首先, 使用函数关键字, 我们使用标识符创建一个函数isAnagram:

function isAnagram() {

我们的职能isAnagram需要两个参数, 第一个String一秒钟String。在此示例中, 我们传递了这些值, 无声和听.

function isAnagram(firstStr, secondStr) {

检查边缘情况

与我们的第一个示例一样, 在功能块的前几行中, 我们要处理一些边缘情况。

如同isAnagram, 我们需要检查两个参数是否具有真实值, 即不 null, 未定义, 等等。我们可以通过使用!操作员。如果firstStrorsecondStr是虚假的, 我们回来false.

function isAnagram(firstStr, secondStr) {
  if (!firstStr || !secondStr) return false;

我们要考虑的下一个边缘情况是确保两个数组的长度相同。如果他们不同, 我们知道他们可以不包含相等数量的共享值。

通过检查长度两个参数的属性, 我们可以确定它们是否相同。如果不是, 我们返回false

function isAnagram(firstStr, secondStr) {
  if (!firstStr || !secondStr) return false;
  if (firstStr.length !== secondStr.length) return false;

建立一个"字典"以避免嵌套循环

记住, 我们使用的是频率计数器模式, 我们需要跟踪至少一个数组中的所有值。现在我们知道处理此问题的最佳方法是将这些值存储在哈希表(对象)中。为了保持一致, 我称我为抬头再次。

function isAnagram(firstStr, secondStr) {
  if (!firstStr || !secondStr) return false;
  if (firstStr.length !== secondStr.length) return false;

  const lookup = {};

用一个的循环, 我们遍历firstStr。里面的的块, 我们将键分配给表达式的结果值*值.

此键/值对中的值为频率计数器这反映了在特定值中"看到"多少次了firstStr.

使用三元运算符, 我们检查抬头包含一个条目值*值, 如果可以, 我们使用+ =赋值运算符将值增加1。如果没有, 我们只需将值分配给1.

function isAnagram(firstStr, secondStr) {
	if (!firstStr || !secondStr) return false;
    if (firstStr.length !== secondStr.length) return false;

	const lookup = {};

	for (first of firstStr) {

    	lookup[first] ? (lookup[first] += 1) : (lookup[first] = 1);

  }

一旦firstStr完成循环后, 抬头应该包含以下值:

{
  s: 1, i: 1, l: 1, e: 1, n: 1, t: 1
}

比较数组值

现在, 我们已经遍历了firstStr并存储它们的值, 我们希望将这些值与secondStr.

我们首先创建另一个的循环。在我们新产品的第一行的块, 我们写一个条件语句来检查是否来自我们的当前值secondStris不在我们里面抬头。如果不是, 我们要停止迭代并返回false.

否则, 如果来自secondStr is在我们的抬头, 我们要减少该条目的值。我们可以使用-=赋值运算符。

function isAnagram(firstStr, secondStr) {
  if (!firstStr || !secondStr) return false;
  if (firstStr.length !== secondStr.length) return false;

  const lookup = {};

  for (first of firstStr) {
    lookup[first] ? (lookup[first] += 1) : (lookup[first] = 1);
  }

  for (second of secondStr) {
    if (!lookup[second]) return false;
    lookup[second] -= 1;
  }

完成循环后, secondStr, 我们的抬头应该具有以下值:

{
  s: 0, i: 0, l: 0, e: 0, n: 0, t: 0
}

包装我们的" isAnagram"功能

如果我们完成遍历secondStr不回false, 这意味着我们firstStr包含中的所有值secondStr。因此, 我们返回true在外面的循环。

function isAnagram(firstStr, secondStr) {
  if (!firstStr || !secondStr) return false;
  if (firstStr.length !== secondStr.length) return false;

  const lookup = {};

  for (first of firstStr) {
    lookup[first] ? (lookup[first] += 1) : (lookup[first] = 1);
  }

  for (second of secondStr) {
    if (!lookup[second]) return false;
    lookup[second] -= 1;
  }
  return true;
}

综上所述

我希望对频率计数器模式的深入了解会有所帮助。现在你已经知道了这种模式的工作原理, 我相信你将能够通过更高层次的技能展示给面试官留下深刻的印象。

在我的下一篇文章中, 我将讨论另一种称为"滑动窗口"的常见问题解决模式。感谢你的阅读和愉快的采访!

一盏木

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: