JS算法之脑洞大开

freeCodeCamp（部分）

问题描述：寻找两个数组的对称差集

代码块（思路1）：

function diffArray(arr1, arr2) {
  const newArr = [];
  //创建两个记录出现重复元素的字典，默认出现次数为1
  let arr1_map = new Map()
  let arr2_map = new Map()
  for(let i = 0; i < arr1.length; i++){
   arr1_map.set(arr1[i], 1)
  }
  for(let j = 0; j < arr2.length; j++){
    arr2_map.set(arr2[j], 1)
    }

//两两比较，若相同则，出现次数+1
  for(let key of arr1_map.keys()){
    for(let j = 0; j < arr2.length; j++){
      if(key === arr2[j]){
        arr1_map.set(key, arr1_map.get(key) + 1)
        arr2_map.set(key, arr2_map.get(key) + 1)
        console.log("****", arr1_map)
        console.log("++++++++++++++++++", arr2_map)
      }
    }
  }
//最后遍历两个数组，出现次数为1的元素即为所求
  for(let key of arr1_map.keys()){
    if(arr1_map.get(key) == 1){
      newArr.push(key)
    }
  }
  for(let key of arr2_map.keys()){
    if(arr2_map.get(key) == 1){
      newArr.push(key)
    }
  }

  return newArr;
}

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

---

问题描述：删除指定元素

思考：需要遍历接受到的参数（arguments

代码块：

function destroyer(arr) {
  for(let arg of arguments){
    //console.log("**",arg)
    if(arg == arr){
      continue
    }
    for(let i = 0; i < arr.length; i++){
      if(arr[i] == arg){
        delete arr[i]
      }
    }
    //最关键的一步，使用delete删除重复的元素，但是被删除的元素的值会被undefined代替，因此使用filter函数剔除undefined
    arr = arr.filter(Boolean)
  }
  return arr;
}

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

---

问题描述：给出一个源对象和一个集合对象，要求在集合对象中筛选出包含源对象所有键值的对象

思考：获取到需要寻找的每个对象的键key；遍历集合中的每个对象,使用filter函数进行过滤操作，过滤有两个条件，首先是判断是否存在这个键，其次是判断对应的值是否正确

使用到的API： Object.keys()；obj.hasOwnProperty()

代码块：

function whatIsInAName(collection, source) {
  let arr = [];
  // Only change code below this line

  //重点方法！！！获取到需要寻找的每个对象的键key
  let source_keys = Object.keys(source)

  //遍历集合中的每个对象,使用filter函数进行过滤操作，过滤有两个条件，首先是判断是否存在这个键，其次是判断对应的值是否正确
  arr = collection.filter(function (obj) {
    //信号量signal，每找到一个符合条件的键值，就+1，当signal的值为源对象键的数量时，则表示找到符合的对象
    let signal = 0
    for (let i = 0; i < source_keys.length; i++) {
      if(obj.hasOwnProperty(source_keys[i]) && obj[source_keys[i]] == source[source_keys[i]]) {
        signal ++
      }
    }
    if(signal == source_keys.length){
      return true
    }
    return false
  })

  console.log(arr)
  // Only change code above this line
  return arr;
}

whatIsInAName([{ first: "Romeo", last: "Montague" }, { first: "Mercutio", last: null }, { first: "Tybalt", last: "Capulet" }], { last: "Capulet" });

---

问题描述：将字符串转为小写，并且用-连接每一个单词

• spinalCase("This Is Spinal Tap") should return the string this-is-spinal-tap.

• Passed:spinalCase("thisIsSpinalTap") should return the string this-is-spinal-tap.

• Passed:spinalCase("The_Andy_Griffith_Show") should return the string the-andy-griffith-show.

• Passed:spinalCase("Teletubbies say Eh-oh") should return the string teletubbies-say-eh-oh.

• Passed:spinalCase("AllThe-small Things") should return the string all-the-small-things.

思考：关键点是如何切割单词，可以通过比较字母之间的ASCII码来完成。需要使用的方法：str.charCodeAt()

代码块：

function spinalCase(str) {
  let str1 = []
  //将字符串一个一个地切割，存入数组
  for(let i = 0; i < str.length; i++){
    str1.push(str.charAt(i))
  }
  //按照大小写，对前后的单词进行切割
  for(let i = 0; i < str.length; i++){
    //一个单词的结尾是小写，同时下一个单词的开头是大写，通过他们的ASCII码来判断
    if(str1[i].charCodeAt() > str1[i + 1].charCodeAt() && str1[i + 1].charCodeAt() <= 90){

      //这条if用于替换下划线_
      if(str1[i].charCodeAt() == 95){
        str1.splice(i, 1, " ")
      }
      //添加占位的空格字符，将单词分割开来
      str1.splice(i + 1, 0, " ")
      //这里使用i++，是为了跳过占位的空格字符
      i++
    }
  }
  //将数组连接成字符串,先将字符都连起来，再用正则表达式进行分割，再用——连接，最后转小写
  str1 = str1.join("")
  str1 = str1.split(/\W+/)
  str1 = str1.join('-')
  str1 = str1.toLowerCase()
  console.log(str1)
  return str1;
}

spinalCase('This Is Spinal Tap');

---

问题描述：Pig Latin is a way of altering English Words. The rules are as follows:

- If a word begins with a consonant, take the first consonant or consonant cluster, move it to the end of the word, and add ay to it.

- If a word begins with a vowel, just add way at the end.

思考：注意字符串的拼接等操作，重点是对元音字母的判断（位置）

代码块：

function translatePigLatin(str) {
  //元音数组
  let vowels = new Set(['a', 'e', 'i', 'o', 'u'])
  //遍历每个字母，查看一个单词是否存在有元音
  for(let i = 0; i < str.length ; i++){
     //有元音
    if(vowels.has(str[i])){
        //如果在单词首位
      if(i == 0){
        str = str + 'way'
        //console.log('1:', str)
        return str
        }
        //如果在单词中间
      else{
        //对字符串都切割转为数组，方便操作
        str = str.split("")
        //temp_str用于保存第一个元音前的所有辅音（单个或者多个）
        let temp_str = str.slice(0, i)
        temp_str = temp_str.join('')

        str.splice(0, i, '')
        str = str.join('')
        str = str + temp_str + 'ay'
        //console.log('2:', str)
        return str
      }
    }
  }
  //如果for循环结束后也没找到一个元音字母（全为辅音字母
  return str + 'ay'
}

translatePigLatin("consonant");

---

问题描述：Perform a search and replace on the sentence using the arguments provided and return the new sentence.

First argument is the sentence to perform the search and replace on.

Second argument is the word that you will be replacing (before).

Third argument is what you will be replacing the second argument with (after).

Note: Preserve the case of the first character in the original word when you are replacing it. For example if you mean to replace the word Book with the word dog, it should be replaced as Dog

思考：先使用indexOf方法找到要替换单词的首字母索引，然后判断要替换单词的位置（是否位于句首，句首的话要将替换的单词首字母大写）

代码块：

function myReplace(str, before, after) {

  let index = str.indexOf(before);
  //判断单词的位置（句首），如果为大写
  if (str[index] === str[index].toUpperCase()) {
    after = after.charAt(0).toUpperCase() + after.slice(1);
  } else {//如果为小写
    after = after.charAt(0).toLowerCase() + after.slice(1);
  }
  str = str.replace(before, after);
  return str;
}

myReplace("A quick brown fox jumped over the lazy dog", "jumped", "leaped");

---

问题描述：Pairs of DNA strands consist of nucleobase pairs. Base pairs are represented by the characters AT and CG, which form building blocks of the DNA double helix.

The DNA strand is missing the pairing element. Write a function to match the missing base pairs for the provided DNA strand. For each character in the provided string, find the base pair character. Return the results as a 2d array.

For example, for the input GCG, return [["G", "C"], ["C","G"], ["G", "C"]]

The character and its pair are paired up in an array, and all the arrays are grouped into one encapsulating array.

思考：碱基对之间的关系可以用对象形式表示，需要使用到in这个关键字，在遍历DNA单链时（单个碱基），判断其所属与那个关系。在使用in关键字过程中，要明白格式：（变量 in 对象）

　　当“对象”为数组时，“变量”指的是数组的“索引”；

　　当“对象”为对象是，“变量”指的是对象的“属性”。

代码块：

function pairElement(str) {
  //将特殊关系 对象化
  let AT_pair = {'A': 'T', 'T': 'A'}
  let CG_pair = {'C': 'G', 'G': 'C'}
  //返回的DNA双链
  let DNA_double_helix = []

  //拆解成一个一个的”碱基“数组
  let DNA_single_helix = str.split('')
  for(let d of DNA_single_helix){
    //如果属于AT匹配关系
    if(d in AT_pair){
      let AT_pairs = [d, AT_pair[d]]
      console.log(AT_pairs)
      DNA_double_helix.push(AT_pairs)
    }
    else{//如果属于CG匹配关系
      let CG_pairs = [d, CG_pair[d]]
      console.log(CG_pairs)
      DNA_double_helix.push(CG_pairs)
    }
  }
  return DNA_double_helix;
}

pairElement("GCG");

---

问题描述：Find the missing letter in the passed letter range and return it.

If all letters are present in the range, return undefined.

思考：ASCII码？相邻的字母？作差？字符转换需要用到的方法charCodeAt()，fromCharCode()

代码块：

function fearNotLetter(str) {

  let ascii_str = []
  for(let i = 0; i < str.length; i++){
      ascii_str.push(str[i].charCodeAt())
  }
  for(let i = 0; i < ascii_str.length - 1; i++){
    if(ascii_str[i+1] - ascii_str[i] !== 1){
      console.log(String.fromCharCode(ascii_str[i]))
      return String.fromCharCode(ascii_str[i]+1)
    }
  }
  return undefined;
}

fearNotLetter("abce");

---

问题描述：Write a function that takes two or more arrays and returns a new array of unique values in the order of the original provided arrays.

In other words, all values present from all arrays should be included in their original order, but with no duplicates in the final array.

The unique numbers should be sorted by their original order, but the final array should not be sorted in numerical order.

思考：投个只因（机），将数组全部连接起来concat，然后扔进一个集合Set去重，然后在使用Array.from()转换为数组并返回

代码块：

function uniteUnique(arr) {

  let array_group = []
  for(let i = 0; i < arguments.length; i++){
    array_group = array_group.concat(arguments[i])
  }
  //console.log(array_group)
  let result_array = new Set(array_group)
  //let final_result = new Array(result_array) 这是错误的用法，会得到一个空数组...
  //正确做法：使用Array.from(obj)
  let final_result = Array.from(result_array)
  //console.log(final_result)
  return final_result;
}

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

---

问题描述：Find the smallest common multiple of the provided parameters that can be evenly divided by both, as well as by all sequential numbers in the range between these parameters.

The range will be an array of two numbers that will not necessarily be in numerical order.

For example, if given 1 and 3, find the smallest common multiple of both 1 and 3 that is also evenly divisible by all numbers between 1 and 3. The answer here would be 6.

思考：寻找一个有序序列的最小公倍数，可以从头开始，比如序列abcdef，先寻找a，b的最大公倍数，并将结果保存起来（scm）。遍历序列，重复以上步骤。寻找最小公倍数的关键判断条件（scm * k % num2 !== 0）

代码块：

function smallestCommons(arr) {
  let scm = 0
  let num2 = 0

  if(arr[0] > arr[1]){
    let temp = arr[0]
    arr[0] = arr[1]
    arr[1] = temp
  }
  //最小公倍数初始化为第一个数
  scm = arr[0]
  //从第二个数开始
  for(let i = arr[0]; i < arr[1]; i++){
    num2 = i + 1
    let k = 1
    //判断是否为最小公倍数
    while((scm * k % num2 !== 0)){
      k++
    }
    //更新最小公倍数
    scm = scm * k
    console.log('scm', scm, i)
  }
  return scm;
}

---

问题描述：Create a function that sums two arguments together. If only one argument is provided, then return a function that expects one argument and returns the sum.

For example, addTogether(2, 3) should return 5, and addTogether(2) should return a function.

Calling this returned function with a single argument will then return the sum:

var sumTwoAnd = addTogether(2);

sumTwoAnd(3) returns 5.

If either argument isn’t a valid number, return undefined.

思考：关键在于typeof的使用，以及闭包的应用（嵌套函数

代码块：

function addTogether() {

  let args = arguments
  //如果只接收一个参数，判断是否为数值类型
  if(args.length == 1){
    if(typeof(args[0]) == 'number'){
      return function f(x){
        if(typeof(x) == 'number'){
          return args[0] + x
        }
        return undefined
      }
    }
  }
  //如果接收两个参数
  if(typeof(args[0]) == 'number' && typeof(args[1]) == 'number'){
    //console.log(args[1])
    return args[0] + args[1];
  }
  return undefined
}

//addTogether(2,3);

---

---

---

最大子数组

输入是以数字组成的数组，例如 arr = [1, -2, 3, 4, -9, 6].

任务是：找出所有项的和最大的 arr 数组的连续子数组。

写出函数 getMaxSubSum(arr)，用其找出并返回最大和。

JS小案例合集

①贪吃蛇

HTML：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <link rel="stylesheet" href="./css/index.css">
</head>
<body>
    <div class="container">
        <!-- 开始游戏按钮 -->
        <button class = 'startBtn'>Play</button>
        <!-- 暂停游戏按钮 -->
        <button class = 'pauseBtn'>Pause</button>
    </div>
    <script src="./js/config.js"></script>
    <script src="./js/index.js"></script>
</body>
</html>

CSS：

*{
    margin: 0;
    padding: 0;
}

.container {
    width: 600px;
    height: 600px;
    background: purple;
    border: 20px solid royalblue;
    margin: 20px auto;
    display: flex;
    justify-content: center;
    align-items: center;
    position: relative;
}
/* 按钮公共样式 */
.container button {
    border: none;
    outline: none;
}

/* 开始按钮 */
.startBtn {
    width: 150px;
    height: 60px;
    border-radius: 15px;
    box-shadow: 3px 4px 0px 0px #1564ad;
    background:linear-gradient(to bottom, #79bbff 5%, #378de5 100%);
    background-color:#79bbff;
    color: #fff;
    font-size: 18px;
    font-weight: bold;
    display: block;
}

.pauseBtn {
     width: 150px;
    height: 60px;
    border-radius: 15px;
    box-shadow: 3px 4px 0px 0px #8a2a21;
    background:linear-gradient(to bottom, #c62d1f 5%, #f24437 100%);
    background-color:#c62d1f;
    color: #fff;
    font-size: 18px;
    font-weight: bold;
    display: none;
}

JS：

config.js配置文件

/* 游戏相关配置
config文件一般用于放置数据信息
*/

//地图对象
let gridData = []

//设置网格宽高
let tr = 30
let td = 30

//蛇身体的大小
let snakeBody = 20

//设置新的蛇头的旧的蛇头之间的位置关系，能够计算出新的蛇头的坐标
let directionNum = {
    left: {x: -1, y: 0, flag: 'left'},
    right: {x: 1, y: 0, flag: 'right'},
    top: {x: 0, y: -1, flag: 'top'},
    bottom: {x: 0, y: 1, flag: 'bottom'},
}

/* 蛇的基本信息 
snakePos数组的长度表示蛇的长度，domConent表示蛇的头身的样式
flag表示区别头身
*/
let snake = {
    //蛇的初始移动方向
    direction: directionNum.right,

    //蛇的初始位置
    snakePos: [
        {x: 0, y: 0, domContent: '', flag: 'body'},
        {x: 1, y: 0, domContent: '', flag: 'body'},
        {x: 2, y: 0, domContent: '', flag: 'body'},
        {x: 3, y: 0, domContent: '', flag: 'head'},
    ]
}

//设置食物的基本信息
let food = {
    x: 0, y: 0, domContent: '',
}

//游戏分数
let score = 0

//计时器
let timeStopper = null

//游戏速度
let speed = 60

index.js主程序文件

/* 
绘制蛇的方法
*/
function drawSnake() {
    for (let i = 0; i < snake.snakePos.length; i++) {
        if (!snake.snakePos[i].domContent) {
            snake.snakePos[i].domContent = document.createElement('div')
            snake.snakePos[i].domContent.style.position = 'absolute'
            snake.snakePos[i].domContent.style.width = snakeBody + 'px'
            snake.snakePos[i].domContent.style.height = snakeBody + 'px'
            snake.snakePos[i].domContent.style.left = snake.snakePos[i].x * snakeBody + 'px'
            snake.snakePos[i].domContent.style.top = snake.snakePos[i].y * snakeBody + 'px'

            if (snake.snakePos[i].flag === 'head') {
                snake.snakePos[i].domContent.style.background = 'red'
            } else {
                snake.snakePos[i].domContent.style.background = 'green'
            }
            document.querySelector('.container').append(snake.snakePos[i].domContent)
        }
    }
}

/* 
绘制食物
*/
function drawFood() {
    //食物坐标是随机的，且不能生成在蛇头或者蛇身

    //写一个while循环，直到生成符合条件的坐标
    while (true) {
        let isRepeated = false
        //随机生成一个坐标
        food.x = Math.floor(Math.random() * tr)
        food.y = Math.floor(Math.random() * td)
        //开始循环判断，食物坐标和当前蛇的位置坐标进行比较
        for (let i = 0; i < snake.snakePos.length; i++) {
            if (snake.snakePos[i].x === food.x && snake.snakePos[i].y === food.y) {
                isRepeated = true
                break
            }
        }
        //如果没有重复
        if (!isRepeated) {
            break
        }
    }

    if (!food.domContent) {
        food.domContent = document.createElement('div')
        food.domContent.style.width = snakeBody + 'px'
        food.domContent.style.height = snakeBody + 'px'
        food.domContent.style.position = 'absolute'
        food.domContent.style.backgroundColor = 'yellow'

        document.querySelector('.container').append(food.domContent)
    }
    food.domContent.style.left = food.x * snakeBody + 'px'
    food.domContent.style.top = food.y * snakeBody + 'px'
}

/* 初始化 */
function initGame() {
    //初始化地图
    for (let i = 0; i < tr; i++) {
        for (let j = 0; j < td; j++) {
            gridData.push({
                x: j,
                y: i
            })
        }
    }
    //绘制蛇
    drawSnake(snake)
    //绘制食物
    drawFood()
}

//碰撞检测，判断蛇头是否撞到食物，身体，墙壁
function isCollided(newHead) {
    let info = {
        isCollided: false,
        isEat: false,
    }
    //如果撞到墙壁
    if (newHead.x < 0 || newHead.x >= td || newHead.y < 0 || newHead.y >= td) {
        info.isCollided = true
        return info
    }
    //如果撞到自己
    for (let i = 0; i < snake.snakePos.length; i++) {
        if (newHead.x === snake.snakePos[i].x && newHead.y === snake.snakePos[i].y) {
            info.isCollided = true
            return info
        }
    }
    //如果吃到食物
    if (newHead.x === food.x && newHead.y === food.y) {
        score++
        info.isEat = true
        return info
    }
    return info
}

function resetConfig() {
    score = 0
    snake = {
        //蛇的初始移动方向
        direction: directionNum.right,

        //蛇的初始位置
        snakePos: [
            { x: 0, y: 0, domContent: '', flag: 'body' },
            { x: 1, y: 0, domContent: '', flag: 'body' },
            { x: 2, y: 0, domContent: '', flag: 'body' },
            { x: 3, y: 0, domContent: '', flag: 'head' },
        ]
    }
    food = {
        x: 0, y: 0, domContent: '',
    }
}

/* 蛇的移动方法 */
function snakeMove() {
    let oldHead = snake.snakePos[snake.snakePos.length - 1]
    //新的蛇头的坐标
    let newHead = {
        domcontent: '',
        x: oldHead.x + snake.direction.x,
        y: oldHead.y + snake.direction.y,
        flag: 'head'
    }
    let collisionResult = isCollided(newHead)
    if (collisionResult.isCollided) {
        if (window.confirm(`
            游戏结束，当前得分为${score}，是否要重新开始游戏？
            `)) {
            //重新开始游戏
            document.querySelector('.container').innerHTML = `
                <!-- 开始游戏按钮 -->
                <button class = 'startBtn' style = 'display:none'>Play</button>
                <!-- 暂停游戏按钮 -->
                <button class = 'pauseBtn' style = 'display:none'>Pause</button>
            `
             resetConfig()
             drawSnake()
             drawFood()
            /* 这一句出问题....，加了这一句后 无法重新开始游戏 */
            //clearInterval(timeStopper)


        } else {
            //退出游戏
            document.onkeydown = null
            document.querySelector('.container').onclick = null
            clearInterval(timeStopper)
        }
        return
    }
    //将旧的头修改成身体
    oldHead.flag = 'body'
    oldHead.domContent.style.background = 'green'
    snake.snakePos.push(newHead)
    //如果吃到食物，则重新生成食物
    if (collisionResult.isEat) {
        drawFood()
    } else {
        //没吃到食物，需要移除最后一个元素（蛇的最后一段,也就是数组的第一个元素
        document.querySelector('.container').removeChild(snake.snakePos[0].domContent)
        snake.snakePos.shift()
    }
    //重新绘制蛇
    drawSnake()
}

function startGame() {
    timeStopper = setInterval(function () {
        snakeMove()
    }, speed)
}

/* 绑定事件 */
function bindEvent() {
    //1.键盘事件，决定蛇的移动方向
    document.onkeydown = function (e) {
        console.log(e.key)
        if ((e.key === 'ArrowUp' || e.key.toLowerCase() === 'w') && snake.direction.flag !== 'bottom') {
            snake.direction = directionNum.top
        }
        if ((e.key === 'ArrowDown' || e.key.toLowerCase() === 's') && snake.direction.flag !== 'top') {
            snake.direction = directionNum.bottom
        }
        if ((e.key === 'ArrowLeft' || e.key.toLowerCase() === 'a') && snake.direction.flag !== 'right') {
            snake.direction = directionNum.left
        }
        if ((e.key === 'ArrowRight' || e.key.toLowerCase() === 'd') && snake.direction.flag !== 'left') {
            snake.direction = directionNum.right
        }
    }
    //2.开始游戏，蛇动
    startGame()

    //3.点击容器暂停
    document.querySelector('.container').onclick = function (e) {
        //console.log(e.target)
        //通过事件委托，判断用户点击的是container容器还是暂停按钮
        if (e.target.className === 'container') {
            document.querySelector('.pauseBtn').style.display = 'block'
            clearInterval(timeStopper)
        } else {
            document.querySelector('.pauseBtn').style.display = 'none'
            startGame()
        }
    }
}

/* 游戏主方法 */
function main() {
    //用户点击了开始游戏之后，再开始后面的操作
    document.querySelector('.startBtn').onclick = function (e) {
        e.stopPropagation()
        document.querySelector('.startBtn').style.display = 'none'
        //初始化游戏(已完成)
        initGame()
        //绑定事件，让游戏动起来
        bindEvent()
    }
}
main()