JavaScript Algorithms and Data Structures(九)

发表于 更新于 分类于 ， 本文字数： 10k 阅读时长 ≈ 9 分钟

freeCodeCamp —- JavaScript Algorithms and Data Structures

中级算法

1. 范围内的数字求和

我们会传入一个由两个数字组成的数组。 给出一个含有两个数字的数组，我们需要写一个函数，让它返回这两个数字间所有数字（包含这两个数字）的总和。 最低的数字并不总是第一位。

例如，sumAll([4,1]) 应返回 10，因为从 1 到 4（包含 1、4）的所有数字的和是 10。

1
2
3
4
5
6
7
8
9
10
11
12
function sumAll(arr) {
  const a =Math.max(arr[0],arr[1]);
  const b =Math.min(arr[0],arr[1]);
  let sum = 0;
  for(let i = b;i <= a;i++){
    sum +=i; 
  }
  return sum
}

sumAll([1, 4]);
console.log(sumAll([1, 4]))

2. 数组的对称差

比较两个数组并返回一个新数组，包含所有只在其中一个数组中出现的元素，排除两个数组都存在的元素。 换言之，我们需要返回两个数组的对称差。

注意：返回数组中的元素顺序不会影响挑战的测试结果。

1
2
3
4
5
6
7
function diffArray(arr1, arr2) {
  return arr1
    .concat(arr2)
    .filter(item => !arr1.includes(item) || !arr2.includes(item));
}

diffArray([1, 2, 3, 5], [1, 2, 3, 4, 5]);

3. 过滤数组元素

你将获得一个初始数组（destroyer 函数中的第一个参数），后跟一个或多个参数。 从初始数组中移除所有与后续参数相等的元素。

注意： 你可以使用 arguments 对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function destroyer(arr) {
  const valsToRemove = Object.values(arguments).slice(1);
  const filteredArray = [];

  for (let i = 0; i < arr.length; i++) {
    let removeElement = false;
    for (let j = 0; j < valsToRemove.length; j++) {
      if (arr[i] === valsToRemove[j]) {
        removeElement = true;
      }
    }
    if (!removeElement) {
      filteredArray.push(arr[i]);
    }
  }
  return filteredArray;
}

destroyer([1, 2, 3, 1, 2, 3], 2, 3);

4. 找出包含特定键值对的对象

创建一个查看对象数组（第一个参数）的函数，并返回具有匹配的名称和值对的所有对象的数组（第二个参数）。 如果要包含在返回的数组中，则源对象的每个名称和值对都必须存在于集合中的对象中。

比如，如果第一个参数是 [{ first: "Romeo", last: "Montague" }, { first: "Mercutio", last: null }, { first: "Tybalt", last: "Capulet" }]，第二个参数是 { last: "Capulet" }。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function whatIsInAName(collection, source) {

  const souceKeys = Object.keys(source);

  // filter the collection
  return collection.filter(obj => {
    for (let i = 0; i < souceKeys.length; i++) {
      if (obj[souceKeys[i]] !== source[souceKeys[i]]) {
        return false; 
      }
    } 
    return true;   
  });
}

5. 短线连接格式

将字符串转换为短线连接格式。 短线连接格式是小写单词全部小写并以破折号分隔。

1
2
3
4
5
6
7
8
9
10
11
function spinalCase(str) {
  // Replace low-upper case to low-space-uppercase
  str = str.replace(/([a-z])([A-Z])/g, "$1 $2");
  // Split on whitespace and underscores and join with dash
  return str
    .toLowerCase()
    .split(/(?:_| )+/)
    .join("-");
}

spinalCase("The_Andy_Griffith_Show")

6. 儿童黑话

儿童黑话也叫 Pig Latin，是一种英语语言游戏。 规则如下：

  • 如果单词以辅音开头，就把第一个辅音字母或第一组辅音簇移到单词的结尾，并在后面加上 ay。

  • 如果单词以元音开头，只需要在结尾加上 way。

请把传入的字符串根据上述规则翻译成儿童黑话并返回结果。 输入的字符串一定是一个小写的英文单词。

1
2
3
4
5
6
7
8
9
10
11
12
function translatePigLatin(str) {
  let consonantRegex = /^[^aeiou]+/;
  let myConsonants = str.match(consonantRegex);
  return myConsonants !== null
    ? str
        .replace(consonantRegex, "")
        .concat(myConsonants)
        .concat("ay")
    : str.concat("way");
}

translatePigLatin("consonant");

7. 搜索与替换

要写一个字符串的搜索与替换函数，它的返回值为完成替换后的新字符串。

这个函数接收的第一个参数为待替换的句子。

第二个参数为句中需要被替换的单词。

第三个参数为替换后的单词。

注意： 在更换原始单词时保留原始单词中第一个字符的大小写。 即如果传入的第二个参数为 Book，第三个参数为 dog，那么替换后的结果应为 Dog

1
2
3
4
5
6
7
8
9
10
11
12
function myReplace(str, before, after) {
  if (/^[A-Z]/.test(before)) {
    after = after[0].toUpperCase() + after.substring(1)
  } else {
    after = after[0].toLowerCase() + after.substring(1)
  }

  return str.replace(before, after);
}


myReplace("Let us go to the store", "store", "mall")

8. DNA 配对

脱氧核糖核酸组由核酸对组成。 基本配对的字符是 AT and CG，这些字符形成了 DNA 双螺旋的构件。

DNA 链缺少配对元素。 写一个函数来匹配缺失的 DNA 字符串。 对于提供的字符串中的每个字符，找出基本的配对字符。 返回二维数组的结果。

例如，传入 GCG 时，应返回 [["G", "C"], ["C","G"], ["G", "C"]]。

字符和它的配对组成一个数组，所有配对数组放在一个数组里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function pairElement(str) {
  // create object for pair lookup
  const pairs = {
    A: "T",
    T: "A",
    C: "G",
    G: "C"
  };
  // map character to array of character and matching pair
  return str
    .split("")
    .map(x => [x, pairs[x]]);
}

pairElement("GCG");

9. 寻找缺失的字母

写一个函数，找出传入的字符串里缺失的字母并返回它。

如果所有字母都在传入的字符串范围内，返回 undefined。

1
2
3
4
5
6
7
8
9
10
11
12
13
function fearNotLetter(str) {
  for (let i = 0; i < str.length; i++) {

    const charCode = str.charCodeAt(i);
    if (charCode !== str.charCodeAt(0) + i) {
//  String.fromCharCode() 方法返回由指定的 UTF-16 代码单元序列创建的字符串。
      return String.fromCharCode(charCode - 1);
    }
  }
  return undefined;
}

fearNotLetter("abce");

10. 集合排序

编写一个带有两个或更多数组的函数，并按原始提供的数组的顺序返回一个新的唯一值数组。

换句话说，所有数组中出现的所有值都应按其原始顺序包括在内，但最终数组中不得重复。

去重后的数字应按其出现在参数中的原始顺序排序，最终数组不应按数字大小进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function uniteUnique(arr) {
  let newArr = Object.values(arguments)
  let a = [];
  let b = [];
  for(let i = 0 ;i <newArr.length;i++ ){
    a = a.concat(newArr[i]);  
  }
  for(let j = 0 ;j < a.length;j++){
    if(!b.includes(a[j]) ){
      b.push(a[j])
    }
  }
 return b 

}

uniteUnique([1, 3, 2], [5, 2, 1, 4], [2, 1]);

11. 转换 HTML 字符实体

请将字符串中的 &、<、>、"（双引号）和 '（单引号）转换为相应的 HTML 字符实体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function convertHTML(str) {
  // Split by character to avoid problems.
  var temp = str.split("");
  // Since we are only checking for a few HTML elements, use a switch
  for (var i = 0; i < temp.length; i++) {
    switch (temp[i]) {
      case "<":
        temp[i] = "&lt;";
        break;
      case "&":
        temp[i] = "&amp;";
        break;
      case ">":
        temp[i] = "&gt;";
        break;
      case '"':
        temp[i] = "&quot;";
        break;
      case "'":
        temp[i] = "&apos;";
        break;
    }
  }

  temp = temp.join("");
  return temp;
}

//test here
convertHTML("Dolce & Gabbana");

12. 求斐波那契数列中的奇数之和

写一个函数，参数为一个正整数 num，返回值为斐波那契数列中，小于或等于 num 的奇数之和。

斐波那契数列的前两个数字是 0 和 1。 后面的每个数字由之前两数相加得出。 斐波那契数列的前七个数字分别为：0、1、1、2、3、5、8。

比如，sumFibs(10) 应该返回 10。 因为斐波那契数列中，比 10 小的数字只有 1、1、3、5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function sumFibs(num) {
  let prevNumber = 0;
  let currNumber = 1;
  let result = 0;
  while (currNumber <= num) {
    if (currNumber % 2 !== 0) {
      result += currNumber;
    }
    currNumber += prevNumber;
    prevNumber = currNumber - prevNumber;
  }

  return result;
}

// test here
sumFibs(75024);

13. 质数求和

质数（prime number）是大于 1 且仅可以被 1 和自己整除的数。 比如，2 就是一个质数，因为它只可以被 1 和 2（它本身）整除。 相反，4 不是质数，因为它可以被 1, 2 和 4 整除。

请完成 sumPrimes 方法，使其返回小于等于传入参数数字的所有质数之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function sumPrimes(num) {
  // Helper function to check primality
  function isPrime(num) {
    const sqrt = Math.sqrt(num);
    for (let i = 2; i <= sqrt; i++) {
      if (num % i === 0)
        return false;
    }
    return true;
  }

  // Check all numbers for primality
  let sum = 0;
  for (let i = 2; i <= num; i++) {
    if (isPrime(i))
      sum += i;
  }
  return sum;
}

14. 找出数字范围内的最小公倍数

找到给定参数的最小公倍数，可以被这两个参数整除，也可以被指定范围内的所有整数整除。

注意，较小数不一定总是出现在数组的第一个元素。

例如，如果给定 1 和 3，找到 1 和 3 的最小公倍数，也可以被 1 到 3 之间的所有数字整除。 这里的答案将是 6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function smallestCommons(arr) {
  const [min, max] = arr.sort((a, b) => a - b);
  const numberDivisors = max - min + 1;
  // Largest possible value for SCM
  let upperBound = 1;
  for (let i = min; i <= max; i++) {
    upperBound *= i;
  }
  // Test all multiples of 'max'
  for (let multiple = max; multiple <= upperBound; multiple += max) {
    // Check if every value in range divides 'multiple'
    let divisorCount = 0;
    for (let i = min; i <= max; i++) {
      // Count divisors
      if (multiple % i === 0) {
        divisorCount += 1;
      }
    }
    if (divisorCount === numberDivisors) {
      return multiple;
    }
  }
}

smallestCommons([1, 5]);

15. 根据参数删除数组元素

给定数组 arr，从数组的第一个元素开始，用函数 func 来检查数组的每个元素是否返回 true。 如果返回 false，就把这个元素删除。 持续执行删除操作，直到某个元素传入 func 时返回 true 为止。

然后在条件满足后返回数组的其余部分，否则， arr 应作为空数组返回。

1
2
3
4
5
6
7
8
9
10
11
12
function dropElements(arr, func) {
  while (arr.length > 0 && !func(arr[0])) {
    arr.shift();
  }
  console.log(arr)
  return arr;
}

// test here
dropElements([1, 2, 3, 4], function(n) {
  return n >= 3;
});

16. 数组扁平化

嵌套数组扁平化成一维数组。 必须考虑到各种深度的嵌套层级。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function steamrollArray(arr) {
  const flattenedArray = [];
  // Loop over array contents
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      // Recursively flatten entries that are arrays
      //  and push into the flattenedArray
      flattenedArray.push(...steamrollArray(arr[i]));
    } else {
      // Copy contents that are not arrays
      flattenedArray.push(arr[i]);     
    }
  }

  return flattenedArray;
};

// test here
steamrollArray([1, [2], [3, [[4]]]]);

17. 翻译二进制字符串

请实现一个函数，把传入的二进制字符串转换成英文句子。

二进制字符串会以空格分隔。

1
2
3
4
5
6
7
8
9
10
11
12
13
function binaryAgent(str) {
  var biString = str.split(" ");
  var uniString = [];
  for (var i = 0; i < biString.length; i++) {
    uniString.push(String.fromCharCode(parseInt(biString[i], 2)));
  }
  return uniString.join("");
}

// test here
binaryAgent(
  "01000001 01110010 01100101 01101110 00100111 01110100 00100000 01100010 01101111 01101110 01100110 01101001 01110010 01100101 01110011 00100000 01100110 01110101 01101110 00100001 00111111"
);

18. 一切都是True

检查谓词（第二个参数）在集合（第一个参数）的所有元素是否为 truthy。

换句话说，你将获得一个对象的数组集合。 如果数组中的每个对象里，pre 对应属性值均为 truthy，则返回 true。 否则，返回 false 。

JavaScript 中，如果一个值在 Boolean 的上下文中的执行结果为 true，那么我们称这个值是 truthy 的。

别忘了，你可以使用点号表示法或方括号表示法（[]）来访问对象的属性。

1
2
3
4
5
6
7
8
9
10
11
function truthCheck(collection, pre) {
  let counter = 0;
  for (let c in collection) {
    if (collection[c].hasOwnProperty(pre) && Boolean(collection[c][pre])) {
      counter++;
    }
  }
  return counter == collection.length;
}

truthCheck([{ name: "Quincy", role: "Founder", isBot: false }, { name: "Naomi", role: "", isBot: false }, { name: "Camperbot", role: "Bot", isBot: true }], "isBot");

19. 可选参数

创建一个将两个参数相加的函数。 如果只提供了一个参数，则返回一个需要一个参数并返回总和的函数。

比如，addTogether(2, 3) 应该返回 5。 而 addTogether(2) 应该返回一个函数。

调用这个返回的函数，为它传入一个值，会返回两个值的总和：

1
var sumTwoAnd = addTogether(2);

sumTwoAnd(3) 应返回 5。

如果任一参数不是有效数字，则返回 undefined。

1
2
3
4
5
6
7
8
9
10
function addTogether() {
  const [first, second] = arguments;
  console.log(arguments)
  console.log([first, second])
  if (typeof (first) === "number") {
    if (typeof (second) === "number") return first + second;
    if (arguments.length === 1) return (second) => addTogether(first, second);
  }
}

20. 创建一个人员对象

用以下方法填充对象构造函数：

1
2
3
4
5
6
getFirstName()
getLastName()
getFullName()
setFirstName(first)
setLastName(last)
setFullName(firstAndLast)

运行测试以查看每个方法的预期输出。 方法接收一个参数，因此必须要有一个参数，并且其类型应该为字符串。 这些方法必须是与对象交互的唯一可用方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const Person = function(firstAndLast) {
  let fullName = firstAndLast;

  this.getFirstName = function() {
    return fullName.split(" ")[0];
  };

  this.getLastName = function() {
    return fullName.split(" ")[1];
  };

  this.getFullName = function() {
    return fullName;
  };

  this.setFirstName = function(name) {
    fullName = name + " " + fullName.split(" ")[1];
  };

  this.setLastName = function(name) {
    fullName = fullName.split(" ")[0] + " " + name;
  };

  this.setFullName = function(name) {
    fullName = name;
  };
};

const bob = new Person("Bob Ross");
console.log(bob.getFullName());