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

叁歲伎倆 2023-07-03 08:07 20阅读 0赞

### 排序 ###

知识点：找规律，实现排序题目和变种排序的题目

参考文档：

*  [十大经典排序算法动画与解析][Link 1]
 *  [十分钟搞定时间复杂度][Link 2]

排序需要清楚时间复杂度和空间复杂度

时间复杂度是计算运行的次数，空间复杂度是计算占用的内存

题目：

*  冒泡排序

代码实现：

export default (arr) => {
      // 冒泡排序
      let len = arr.length
      // 通过i来控制边界
      for (let i = len - 1, swap; i > 0; i--) {
        for (let j = 0; j < i; j++) {
          swap = arr[j]
          if (swap > arr[j + 1]) {
            arr[j] = arr[j + 1]
            arr[j + 1] = swap
          }
        }
      }
      return arr
    }

*  选择排序

代码实现：

export default (arr) => {
      let len = arr.length
      for (let i = 0; i < len - 1; i++) {
        let min = arr[i]
        // 每轮需要比较的次数N-1
        for (let j = i + 1; j < len; j++) {
          if (arr[j] < min) {
            let c = min
            min = arr[j]
            arr[j] = c
          }
        }
        arr[i] = min
      }
      return arr
    }

*  按奇偶排序数组

代码实现：

export default (arr) => {
      // 进行升序排序
      arr.sort((a, b) => a - b)
      // 声明一个空数组用来存储奇偶排序后的数组
      let r = []
      // 记录奇数、偶数位下标
      let odd = 1
      let even = 0
      arr.forEach(item => {
        if (item % 2 === 1) {
          r[odd] = item
          odd += 2
        } else {
          r[even] = item
          even += 2
        }
      })
      return r
    }

*  数组中的第K个最大元素

代码实现：

// export default (arr, k) => {
    //   return arr.sort((a, b) => b - a)[k - 1]
    // }
    
    // 最佳性能
    export default (arr, k) => {
      let len = arr.length - 1
      for (let i = len, tmp; i > len - k; i--) {
        for (let j = 0; j < i; j++) {
          if (arr[j] > arr[j + 1]) {
            tmp = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = tmp
          }
        }
      }
      return arr[len - (k - 1)]
    }

*  最大间距

实现代码：

// export default (arr) => {
    //   // 如果数组长度小于2返回0
    //   if (arr.length < 2) {
    //     return 0
    //   }
    //   // 排序
    //   arr.sort()
    //   // 用它来保存相邻元素的最大差值
    //   let max = 0
    //   for (let i = 0, len = arr.length - 1, tmp; i < len; i++) {
    //     tmp = arr[i + 1] - arr[i]
    //     if (max < tmp) {
    //       max = tmp
    //     }
    //   }
    //   return max
    // }
    
    // 最优方法
    export default (arr) => {
      if (arr.length < 2) {
        return 0
      }
      let max = 0
      let len = arr.length - 1
      let space
      for (let i = len, tmp; i > 0; i--) {
        for (let j = 0; j < i; j++) {
          tmp = arr[j]
          if (tmp > arr[j + 1]) {
            arr[j] = arr[j + 1]
            arr[j + 1] = tmp
          }
        }
        if (i < len) {
          space = arr[i + 1] - arr[i]
          if (space > max) {
            max = space
          }
        }
      }
      // 防止没有计算arr[1] - arr[0]的差值
      return Math.max(max, arr[1] - arr[0])
    }

*  缺少的第一个正整数

代码实现：

// export default (arr) => {
    //   // 过滤掉非正整数
    //   arr = arr.filter(item => item > 0)
    //   // 正整数数组是不是为空
    //   if (arr.length) {
    //     // 升序，目的：方便从左到右取最小值
    //     arr.sort((a, b) => a - b)
    //     // 如果第一个元素不为1，返回1
    //     if (arr[0] !== 1) {
    //       return 1
    //     } else {
    //       // 从左边开始遍历，只要下一个元素和当前元素差值 > 1说明当前元素的下一个值(+1)为未出现的最小正整数
    //       for (let i = 0, len = arr.length - 1; i < len; i++) {
    //         if (arr[i + 1] - arr[i] > 1) {
    //           return arr[i] + 1
    //         }
    //       }
    //       // 如果数组是连续的正整数[1,2,3,4,5]
    //       return arr.pop() + 1
    //     }
    //   } else {
    //     return 1
    //   }
    // }
    
    // 最优性能
    export default (arr) => {
      arr = arr.filter(item => item > 0)
      // 实现选择排序，先拿到最小值，如果第一个元素不是1直接返回1，如果是1，就要比较相邻元素差值
      for (let i = 0, len = arr.length, min; i < len; i++) {
        min = arr[i]
        for (let j = i + 1; j < len; j++) {
          if (arr[j] < min) {
            let c = min
            min = arr[j]
            arr[j] = c
          }
        }
        arr[i] = min
        if (i > 0) {
          if (arr[i] - arr[i - 1] > 1) {
            return arr[i - 1] + 1
          }
        } else {
          if (min !== 1) {
            return 1
          }
        }
      }
      return arr.length ? arr.pop() + 1 : 1
    }

### 递归 ###

*  复原IP地址

代码实现：

export default (str) => {
      // 保存所有符合条件的IP地址
      let r = []
      // 分四步递归处理ip地址
      let search = (cur, sub) => {
        // 非法输入过滤，leetCode测试用例
        if (sub.length > 12) {
          return
        }
        // 边界条件
        if (cur.length === 4 && cur.join('') === str) {
          r.push(cur.join('.'))
        } else {
          // 还没分完。正常处理情况
          // 如果剩下的数字不到3个了，就按照剩下的循环；否则按照三位循环
          for (let i = 0, len = Math.min(3, sub.length), tmp; i < len; i++) {
            // 取出从0开始，i+1长度的子串，也就是1~len的子串
            tmp = sub.substr(0, i + 1)
            // 对取出的子串验证是否合法
            if (tmp - 256 < 0) {
              // 将这个合法的数字格式化（去掉前面的0），递归调用，进行下一次
              search(cur.concat([tmp * 1]), sub.substr(i + 1))
            }
          }
        }
      }
      // 第一次调用
      search([], str)
      return r
    }

*  串联所有单词的子串

还没有解决

[Link 1]: http://note.youdao.com/noteshare?id=d1c8efc1a6d35fecb7828dc3ef3bafe0
[Link 2]: https://www.jianshu.com/p/f4cca5ce055a