JavaScript--数据结构与算法(一)

雨点打透心脏的1/2处 2023-06-27 03:41 16阅读 0赞

## 算法： ##

这里的算法都是leetCode上的题目：[leetCode][]

github代码地址：[JavaScript--数据结构与算法][JavaScript--]

*  理解算法的本质学会挖掘"规律"
 *  通过"解题"夯实基础算法
 *  举一反三学会变通和延伸

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70][]

基础算法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 1][]

*  字符串
 *  数组
 *  正则表达式
 *  排序
 *  递归

数据结构

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 2][]

*  堆、栈
 *  队列
 *  链表
 *  矩阵
 *  二叉树

进阶算法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 3][]

*  贪心算法
 *  动态规划

## 环境搭建： ##

1.  ES6
2.  Jest ：[Jest文档][Jest]
3.  NPM：安装 [node.js][]
4.  Git：[git博客][git]

## 简单算法： ##

*  字符串

**        难度大的算法题目如何解？**

算法的本质是寻找规律并实现

**        如何找到规律？**

发现输入和输出的关系，循州突破口

**        复杂的实现怎么实现？**

实现是程序 + 数据结构的结合体(对程序有本质的认识，并且熟悉所有的数据结构)

*  数组
 *  正则
 *  排序
 *  递归

### 字符串 ###

*  反转字符串中的单词

知识点：

1.  String.prototype.split
2.  String.prototype.macth
3.  Array.prototype.map
4.  Array.prototype.reverse
5.  Array.prototype.join

思维方法

要熟悉所有的API，知道在某些场景的实际应用

代码实现：

// export default (str)=> {
    //   // 字符串按空格进行分隔，保存数组，数组的元素的先后顺序就是单词的顺序
    //   let arr = str.split(' ')
    //   // 对数组进行遍历，然后每个元素进行反转
    //   let result = arr.map(item => {
    //     return item.split('').reverse().join('')
    //   })
    //   return result.join(' ')
    // }
    
    // export default (str)=> {
    //   // 1. 字符串按空格进行分隔，保存数组，数组的元素的先后顺序就是单词的顺序
    //   // 2. 对数组进行遍历，然后每个元素进行反转
    //   return str.split(' ').map(item => {
    //     return item.split('').reverse().join('')
    //   }).join(' ')
    // }
    
    /* 正则表达式 */
    // export default (str) => {
    //   // 1. 字符串按空格进行分隔，保存数组，数组的元素的先后顺序就是单词的顺序
    //   // 2. 对数组进行遍历，然后每个元素进行反转
    //   return str.split(/\s/g).map(item => {
    //     return item.split('').reverse().join('')
    //   }).join(' ')
    // }
    
    export default (str) => {
      // 1. 字符串按空格进行分隔，保存数组，数组的元素的先后顺序就是单词的顺序
      // 2. 对数组进行遍历，然后每个元素进行反转
      return str.match(/[\w']+/g).map(item => {
        return item.split('').reverse().join('')
      }).join(' ')
    }

*  计数二进制子串

思维方法：

先找到规律，并用代码实现

代码实现：

// 正则表达式匹配
    // export default (str) => {
    //   var count = 0
    //   // 匹配条件
    //   function match (s) {
    //     let j = s.match(/(0+|1+)/)[0]
    //     let o = (j[0]^1).toString().repeat(j.length)
    //     let q = j + o
    //     if (s.startsWith(q)) {
    //       return true
    //     } else {
    //       return false
    //     }
    //   }
    
    //   // 按顺序截取字符串，满足条件数量加1
    //   for (let i = 0; i < str.length - 1; i++) {
    //     var sub = match(str.slice(i))
    //     if (sub) {
    //       count++
    //     }
    //   }
    //   return count
    // }
    
    /*
    * @param {string} s
    * @return {number}
    */
    export default (str) => {
      // pre 前一个数字连续出现的次数，cur当前数组连续出现的次数，result结果子串个数
      let pre = 0
      let cur = 1
      let result = 0
      for (let i = 0, len = str.length - 1; i < len; i++) {
        // 判断当前数字是否与后一个数字相同
        if (str[i] === str[i + 1]) { // 相同，则当前数字出现的次数cur加1
          cur++
        } else { // 不同，则当前数字事实上变成了前一个数字，当前数字的次数重置为1
          pre = cur
          cur = 1
        }
        if (pre >= cur) { // 前一个数字出现的次数 >= 后一个数字出现的次数，则一定包含满足条件的子串
          result++
        }
      }
      return result
    }

### 数组 ###

*  电话号码的字母组合(公式运算)

知识点：

1.  Array.prototype.splice

图解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 5][]

代码实现：

export default (str) => {
      // 建立电话号码键盘映射
      let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
      // 把输入字符串按单字符分隔变成数组，234 => [2, 3, 4]
      let num = str.split('')
      // 保存键盘映射后的字母内容，如 23 => ['abc', 'def']
      let code = []
      num.forEach(item => {
        if (map[item]) {
          code.push(map[item])
        }
      })
      let comb = (arr) => {
        // 临时变量用来保存前两个组合的结果
        let tmp = []
        // 最外层的循环是遍历第一个元素，里层的循环是遍历第二个元素
        for (let i = 0, il = arr[0].length; i < il; i++) {
          for (let j = 0, jl = arr[1].length; j < jl; j++) {
            tmp.push(`${arr[0][i]}${arr[1][j]}`)
          }
        }
        // 如果是str为234，执行第一次返回的arr结果为
        // [[ad, ae, af, bd, be, bf, cd, ce, cf],'ghi']
        arr.splice(0, 2, tmp)
        if (arr.length > 1) {
          comb(arr)
        } else {
          return tmp
        }
        return arr[0]
      }
      return comb(code)
    }

*  卡牌分组(归类运算)

知识点：

1.  认真读题，每一个关键词都可能是突破点
2.  Array.prototype.every

代码实现：

export default (arr) => {
      // 对这副牌进行排序，升序，降序都可以
      arr.sort((a, b) => a - b)
      let min = Number.MAX_SAFE_INTEGER
      let dst = []
      let result = true
      if (arr.length > 1) {
        for (let i = 0, len = arr.length, tmp = []; i < len; i++) {
          tmp.push(arr[i])
          for (let j = i + 1; j < len - 1; j++) {
            // 当相邻的下标相等时，则向tmp数组push i+1下标的值
            // 不相等时，则把临时变量数组tmp保存在dst数组中
            if (arr[i] === arr[j]) {
              tmp.push(arr[j])
            } else {
              if (min > tmp.length) {
                min = tmp.length
              }
              // 数组是引用类型，所以用下面的方法开辟一个新的空间来拷贝tmp
              dst.push([].concat(tmp))
              // 用下面的方法清空数组才是最正确的
              tmp.length = 0
              i = j
              break
            }
          }
        }
        dst.every(item => {
          // 判断dst数组下标的值能否被正整数min取模运算除尽为0
          if (item.length % min !== 0) {
            result = false
            // 跳出循环
            return false
          }
        })
      } else {
        result = false
      }
      return result
    }

*  种花问题(筛选运算)

知识点：

1.  问题抽象、数学建模、动态输入

图解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 6][]

代码实现：

export default (arr, n) => {
      // 计数器
      let max = 0
      for (let i = 0, len = arr.length - 1; i < len; i++) {
        if (arr[i] === 0) {
          if (i === 0 && arr[1] === 0) {
            max++
            i++
          } else if (arr[i - 1] === 0 && arr[i + 1] === 0) {
            max++
            i++
          }
        }
      }
      return max >= n
    }

*  格雷编码(二进制运算)

图解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 7][]

代码实现：

export default (n) => {
      // 递归函数，用来算输入为n的格雷编码序列
      let make = (n) => {
        if (n === 1) {
          return ['0', '1']
        } else {
          let prev = make(n - 1)
          let result = []
          let max = Math.pow(2, n) - 1
          for (let i = 0, len = prev.length; i < len; i++) {
            result[i] = `0${prev[i]}`
            result[max - i] = `1${prev[i]}`
          }
          return result
        }
      }
      return make(n)
    }

### 正则表达式 ###

参考文档：[正则表达式][Link 1]

*  重复的子字符串

知识点：

重视基础、知识全面

代码实现：

export default (str) => {
      var reg = /^(\w+)\1+$/
      return reg.test(str)
    }

*  正则表达式匹配

图解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 9][]

代码实现：

export default (str, mode) => {
      // 对模式变量进行正则筛选
      let modeArr = mode.match(/([a-z.]\*)|([a-z]+(?=([a-z.]\*)|$))/g)
      let cur = 0
      let strLen = str.length
      for (let i = 0, len = modeArr.length, m; i < len; i++) {
        // 对于模式分为三类，.*|a*|cdef
        m = modeArr[i].split('')
        // 如果第二位是*表示是有模式的
        if (m[1] === '*') {
          if (m[0] === '.') {
            cur = strLen
            break
          } else {
            while (str[cur] === m[0]) {
              cur++
            }
          }
        } else {
          for (let j = 0, jl = m.length; j < jl; j++) {
            if (m[j] !== str[cur]) {
              return false
            } else {
              cur++
            }
          }
        }
      }
      return cur === strLen
    }

[leetCode]: https://leetcode-cn.com/
[JavaScript--]: https://github.com/HZhen/JavaScript---algorithm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200102200128777.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200102200430991.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200102200518939.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200102200601495.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[Jest]: https://jestjs.io/docs/zh-Hans/getting-started
[node.js]: https://nodejs.org/en/
[git]: https://blog.csdn.net/wo_921110/article/details/102838181
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200203142709540.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200203143158134.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200203165909380.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200204095720248.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[Link 1]: https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Guide/Regular_Expressions
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200204105059821.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200204105605333.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvXzkyMTExMA==,size_16,color_FFFFFF,t_70