数据结构与算法

回文字符串判断

参考

介绍

• 回文( Palindromes )，在中文文当中是指倒着念和顺着念都是相同的，前后对称，例如“上海自来水来自海上”；在英文文当中是指正着看和反着看都相同的单词，例如“madam”；而对于数字，又称之为回文数，是指一个像“16461”这样的对称的数，即这个数的数字按相反的顺序重新排列后得到的数和原来的数一样。

  题目

• 判断给定的字符串，如果字符串是一个Palindromes，那么返回true，反之返回false

  实现

• reverse() ```javascript function Palindromes(str) { // \w 匹配所有字母和数字以及下划线；\W与之相反； // [\W] 表示匹配下划线或者所有非字母非数字中的任意一个；/g全局匹配 let reg = /[\W]/g; let newStr = str.replace(reg, ‘’).toLowerCase();// 过滤特殊符号 let reverseStr = newStr.split(‘’).reverse().join(‘’) return reverseStr === newStr; // 与 newStr 对比 }

// 或者 function Palindromes(str){ const len = str.length if(len == 0 || len == 1) return true const strReverse = str.split(‘’).reverse().join(‘’) return str == strReverse ? true : false }

实际上这里做了很多步对数组的操作，字符转数组 翻转数组 再转字符串，所以这里性能也不是很好。以为数组是引用类型，要改变这个数组，需要开辟新的堆地址空间。
- for 循环实现
```javascript
// 考虑到性能问题，我们可以比较一半的字符串内容即可
function Palindromes(str = ''){
  const len = str.length
  if(len == 0 || len == 1) return true
  for (let i = 0; i < Math.floor(len / 2); i++){
    if (str[i] !== str[len - 1 - i]) {
      return false
    }
  }
  return true
}

队列实现

介绍

• 先进者先出

• 入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

  实现

• 数组实现

• 链表实现

  数组队列实现

• 主要考虑到 队空 与 队满 的情景 ```javascript class ArrayQueue { constructor(initLength = 10) { this.items = [] //数组 this.items.length = initLength //初始化数组的大小

  this.head = 0 // 表示队头下标 this.tail = 0 // 队尾下标

  } // 入队 enqueue(item) { if (this.tail === this.items.length) {

  if(this.head === 0) return false // tail ==n && head==0，表示整个队列都占满了
  //数据往前挪
  for(let i = this.head; i < this.tail; i++) {
    this.items[i - this.head] = this.items[i]
  } 
  // 更新 head 和 tail
  this.tail = this.tail - this.head
  this.head = 0

  } this.items[this.tail] = item this.tail++ return true; }

  // 出队 dequeue() { if(this.head === this.tail) { //表示队空

  return null

  } const ret = this.items[this.head] this.head++ return ret } }

const arrqueue = new ArrayQueue(10)

arrqueue.enqueue(‘1’) arrqueue.enqueue(‘2’) arrqueue.enqueue(‘3’)

console.log(arrqueue.items); // [‘1’, ‘2’, ‘3’] console.log(arrqueue.dequeue()); // 1

<a name="RgYNc"></a>
#### 数组循环队列实
<a name="NuBZt"></a>
### 递归
[参考](https://time.geekbang.org/column/article/41440)
<a name="rfP0f"></a>
#### 满足的三个条件
1. 一个问题的解可以分解为几个子问题的解
1. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
1. 存在递归终止条件
<a name="Q4oL5"></a>
#### 如何写递归代码
1. 最关键的是写出递推公式
1. 找到终止条件
1. 剩下将递推公式转化为代码
**  住： 主要是递推公式，先例举几项，在找规律，最后总结递推公式**
<a name="R1JTR"></a>
#### 题目
1. 假设你正在爬楼梯。需要 _n_ 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？**注意：**给定 _n_ 是一个正整数。[参考](https://leetcode-cn.com/problems/climbing-stairs/)
```javascript
var climbStairs = function(n) {
    if(n === 1) return 1
    if(n === 2) return 2
    return climbStairs(n-1) + climbStairs(n-2)
};
climbStairs(2) // 2
climbStairs(3) // 3

性能优化

• 添加边界条件
  • 重复计算
• 我们可以通过一个数据结构（比如散列表）来保存已经求解过的值，当递归调用该值时，可以先去数据结构里看下是否已经求解过了，这样可以减少很多不必要的计算

// 函数的记忆优化
function memorize(fn){
  var cache = {}
  return function(){
    // 定义一个独一无二的 key,来存value
    var key = arguments.length + Array.prototype.join.call(arguments)
    console.log('key', key)
    if(cache[key]){
      return cache[key]
    }
    cache[key] = fn.apply(this, arguments)
    return cache[key]
  }
}
const func = memorize(climbStairs)
// 比如 n=30 时， 采用 memorize 执行时间明显降低

• 将递归代码改写为非递归代码

  • 空间复杂度降低，执行时间也得到大幅度提升

    var climbStairs = function(n) {
    if(n === 1) return 1
    if(n === 2) return 2
    let res = 0
    let per = 2
    let prepre = 1
    for(let i =3; i <= n; i++) {
    res = per + prepre // 前两项和
    prepre = per // prepre 值 变成 per
    per = res // per 值变成 每次计算的结果
    }
    return res
    }

    总结

• 递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现

排序

参考

冒泡排序（Bubble Sort）

实现原理

• 数组中有 n 个数，比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过 n-1（数组的 length - 1） 轮，就完成了所有数的排序。

实现步骤

1. 首先我们先找出数组中最大的数，把它放在数组的最后面 ```javascript var arr = [3,4,1,2];

for(let i = 0; i < arr.length - 1; i++) { if(arr[i] > arr[i+1]) { // 如果前者大于后者，就交换位置 let temp = arr[i] arr[i] = arr[i+1]; arr[i+1] = temp } }

// arr 为 [ 3, 1, 2, 4 ]

2. 然后，我们能找到数组中最大的数，放到最后，这样重复 arr.length - 1 次，便可以实现数组按从小到大的顺序排好了。
```javascript
var arr = [3,4,1,2];
for(let j = 0; j < arr.length -1; j++) {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] > arr[i+1]) {
      let temp = arr[i]
      arr[i] = arr[i+1];
      arr[i+1] = temp
    }
  }
}
// arr 为 [ 1, 2, 3, 4 ]

1. 虽然上面的代码已经实现冒泡排序了，但就像注释中提到的，内层 for 循环的次数写成，i < arr.length - 1 ，是不是合适呢？ 我们想一下，当第一次，找到最大数，放到最后，那么下一次，遍历的时候，是不是就不能把最后一个数算上了呢？因为他就是最大的了，不会出现，前一个数比后一个数大，要交换位置的情况，所以内层 for 循环的次数，改成 i < arr.length - 1 -j ，才合适，看下面的代码。

   var arr = [3, 4, 1, 2];
   function bubbleSort (arr) {
   if (arr.length <= 1) return
   for (var j = 0; j < arr.length - 1; j++) {
    // 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数
    for (var i = 0; i < arr.length - 1 - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
   }
   return arr;
   }
   bubbleSort(arr);

2. 我们想下这个情况，当原数组是，
   arr = [1,2,4,3];
   在经过第一轮冒泡排序之后，数组就变成了
   arr = [1,2,3,4];
   此时，数组已经排序完成了，但是按上面的代码来看，数组还会继续排序，所以我们加一个标志位，如果某次循环完后，没有任何两数进行交换，就将标志位 设置为 true，表示排序完成，这样我们就可以减少不必要的排序，提高性能。 ```javascript var arr = [3, 4, 1, 2]; function bubbleSort (arr) { if (arr.length <= 1) return for (var j = 0; j < arr.length - 1; j++) { // 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数 for (var i = 0; i < arr.length - 1 - j; i++) { var flag = false if (arr[i] > arr[i + 1]) { //交换

    var temp = arr[i];
    arr[i] = arr[i + 1];
    arr[i + 1] = temp;
    flag = true  // 表示有数据交换

   } } if(!flag) { // 如果没有数据交换，提前退出 break } } return arr; }

console.log(‘arr—‘, bubbleSort(arr)); ```