数据结构

1、线性结构

线性结构中的数据元素是按顺序排列的，每个元素有唯一的前驱和后继。

1.1 数组（Array）

  1. 定义：一组固定大小、类型相同的元素集合
  2. 特点：支持随机访问，时间复杂度为𝑂(1)
  3. 缺点：插入和删除操作效率较低（需要移动元素）

1.2 链表（Linked List）

  1. 定义：由节点组成，每个节点包含数据和指向下一个节点的指针
  2. 类型：单链表、双链表、循环链表
  3. 特点：动态内存分配，插入和删除效率高，但随机访问较慢

1.2 栈（Stack）

  1. 定义：后进先出（LIFO）的数据结构
  2. 操作：push（入栈）、pop（出栈）
  3. 应用：函数调用、表达式求值、括号匹配等

1.3 队列（Queue）

  1. 定义：先进先出（FIFO）的数据结构
  2. 类型：普通队列、双端队列（Deque）、优先队列（Priority Queue）
  3. 应用：任务调度、消息队列等

2、非线性结构

非线性结构中的数据元素可能有一个或多个前驱和后继。

2.1 树（Tree）

  1. 定义：由节点和边组成的层级结构，每个节点有一个父节点和多个子节点
  2. 特殊类型：
    1. 二叉树：每个节点最多有两个子节点
    2. 完全二叉树：叶子节点尽量集中在左侧
    3. 二叉搜索树（BST）：左子树节点值小于根节点，右子树节点值大于根节点
    4. 平衡树：AVL树、红黑树
  3. 应用：文件系统、语法解析、数据库索引（B树/B+树）等

2.2 图（Graph）

  1. 定义：由顶点（Vertices）和边（Edges）组成的数据结构
  2. 类型：
    1. 无向图、有向图
    2. 权重图：边有权重
  3. 表示方法：邻接矩阵、邻接表
  4. 应用：网络路由、社交网络分析等

3、哈希表

  1. 定义：通过哈希函数将键映射到数组中的位置以存储数据
  2. 特点：查找、插入、删除操作的平均时间复杂度为O(1)
  3. 解决冲突的方法：链地址法、开放寻址法
  4. 应用：字典、缓存等

4、数据结构的选择

  1. 数据量的大小
  2. 数据的插入、删除、查找频率
  3. 算法对时间复杂度和空间复杂度的要求
  4. 数据的特性（是否有顺序、是否重复等）

链表

链表介绍

  1. 线性结构。 数组、链表。 数组在内存中是连续的，所以通过下标查找性能好，但是删除和新增会导致整个数组变化性能反而不好。链表就反之。
  2. 非线性结构。树、堆。

    反转链表

    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
    //题目
    输入：1->2->3->4->null;
    输出：4->3->2->1->null;
    //思路
    1. 把当前节点的next属性指向它的前一个节点


    //实现
    function listNode(val){
       this.val = val;   //当前节点
       this.next = null;  //该节点指向下一个节点
    }

    const reverseList = function (list){
       if(list === null || list.next === null){
           return list;
       }
       let pre = null, cur = list;
       while(cur !== null){
          let next = cur.next;  //保存临时变量
          cur.next = pre;  //当前节点next指向前一个
          pre = cur;
          cur = next;
       }

       return pre;
    }

删除链表中第N个节点

算法

洗牌算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//要求：新生产的数组元素下标和原数组元素下标不能重复

//思路
// 1. 倒序循环这个数组
// 2. 取值范围从1-N(数组的长度)随机数K
// 3. K 与 N 交换
// 4. 直到循环到数组的第一位


//代码(大概率出现位置没有改变)
Array.prototype.Shuffle = function(){
  for(let i = this.length-1; i >= 0; i--){
      let randomIndex = Math.floor(Math.random() * (i+1));
      let itemIndex = this[randomIndex];
      this[randomIndex] = this[i];  //交换
      this[i] = itemIndex;
  }
  return this;
}


//代码改进

判断正整数是否对称

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//要求：12321、 1234321


//思路： 原数和倒序数相等则可以判断对称


//代码实现：
function reverse(n){
  let result = 0;
  //对数字依次求模，从右至左求出数字每一位
  while(n){
    result = result * 10 + n % 10;  //%10得到最后一位数，  %100得到最后二位数
    n = parseInt(n / 10);     //去除个位数其他的数
  }
  return result;
}

function isMirror(n){
  if(n === reverse(n))return true;
  return false;
}

判断10进制整数包含多少个n[0 - 9]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//要求： 不能通过转换为String，然后通过循环来判断

//思路： 一位一位数进行对比

//代码实现：
function count(num, n){
   let count = 0;
   while(num){
      let currNum = num % 10;   //求模得到最后一个数
      num = parseInt(num / 10);  //去除最后一位数
      if(currNum === n){
         count++;
      }
   }
   return count;
}

寻找重复数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//要求：从一个数组找出重复数

//思路：  1. 利用sort()进行从排序  2. 前面和后面进行对比

//代码实现：
function findDuplicate(arr){
  let newArr = [];
  arr.sort();
  for(let i=0; i<arr.length; i++){
     if(arr[i] === arr[i+1] && newArr.indexOf(arr[i]) < 0){
        newArr.push(arr[i]);
     }
  }
  return newArr;
}

寻找2个字符串最大公共子串

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//要求：

//思路： 1. 2个字符串构成矩阵结构（行列结构）  2. 对矩阵中每一项进行对比看是否匹配（1匹配0不匹配 3. 然后求出对角线最长为1的那一段序列，即为最大公共子串


//代码实现：
function findMaxSubStr(str1, str2){
  if(str1.length === 0 || str2.length ===0){
    return '';
  }

  let len1 = str1.length;
  let len2 = str2.length;
  let arr = [];
  let maxLen = 0;  //公共子串长度
  let maxPos = 0;  //公共子串最后一个字符位置

  for(let i=0; i<len1; i++){
    for(let j=len2-1; j>=0; j--){
       if(str1.charAt(j) == str2.charAt(i)){
         //匹配
         if(i===0 || j===0){
           arr[j] = 1;
         }else{
           arr[j] = arr[j-1]+1;
         }
       }else{
         //不匹配
         arr[j] = 0;
       }
       if(arr[j] > maxLen){
           maxLen = arr[j];
           maxPos = j;
       }
    }
  }
   return str1.substr(maxPos - maxLen + 1, maxLen);
}

//代码优化
//思路： 公共子串肯定<=Math.min(str1, str2)、 而且还是连续的、而且还是str1和str2的子串

function findMaxSubstr(str1 = '', str2 = ''){
    if (str1 == '' || str2 == '') {
        return '';
    }
    let maxSubStr = '';
    let len1 = str1.length;
    let len2 = str2.length;

    //找出str1、str2中较小字符串;
    //如果str1.length > str2.length, 就强制让str1变为最小字符串
    if (len1 > len2) {
        let temp = str1;
        str1 = str2;
        str2 = temp;
        len1 = str1.length;
        len2 = str2.length;
    }

    for (let i = len1; i > 0; i--) {
        for (let j = 0; j <= len1 - i; j++) {
            maxSubStr = str1.substr(j, i);  //j:开始位置， i:长度
            if (str2.indexOf(maxSubStr) > -1) {
                return maxSubStr;
            }
        }
    }
    return '';
}

对比版本号大小

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
31
32
33
34
35
//思路
1. 通过位数一个个对比

//实现
function compareVersion(curVer, oldVer){
   if(curVer && oldVer){
       let arr1 = curVer.split('.');
       let arr2 = oldVer.split('.');
       let minLen = Math.min(arr1.length, arr2.length);
       let position = 0;
       let diff = 0;

       //循环位数对比
       while(position < minLen){
         diff = parseInt(arr1[position]) - parseInt(arr2[position]);
         //相同的位数指不一样就跳出循环体， 比较diff
         if(diff != 0){
            break;
         }
         position++;
       }

       if(diff == 0){
           //curVer位数大于oldVer，且前面的值相等
          return (arr1.length - arr2.length) > 0;
       }else{
          //curVer和oldVer中间位数指不相等
          return diff > 0;
       }

   }else{
     console.error('请输入版本号');
     return false;
   }
}

爬楼梯算法

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
31
32
33
34
35
//题目
假设在爬楼梯，需要n阶才能到达楼顶，每次可以爬1或者2个台阶， 有多少不同方法爬到楼顶？

//思路
1. 运用递归思路， 就是自己间接或者直接调用自己。 （递归可能会导致内存的溢出）
2. 用循环的方式减少递归的内存消耗

//解法
const climbing = function(n){
   if(n < 1) return 0;
   if(n === 1 || n === 2){
      return n;
   }else{
      return climbing(n-2) + climbing(n-1);
   }

}


const climbing = function(n){
   if(n < 1) return 0;
   if(n === 1 || n === 2){
      return n;
   }

   let sum = 0;  //累计
   let preStep = 2; //2个台阶
   let prepreStep = 1; //一个台阶
   for(let i=3; i<=n; i++){
      sum = preStep + prepreStep;  //累计
      prepreStep = preStep;   //
      preStep = sum;
   }
   return sum;
}

有序数组旋转求出最小值

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
31
32
33
34
35
36
37
//题目
原 array：[0, 1, 2, 4, 5, 6, 7]
rotate 之后就是：[4, 5, 6, 7, 0, 1, 2]
输出：最小值 0

//思路
1. 遍历所有值，用一个变量记录最小值
2. 二分查找(每次排除一半数据，留下另一半再进行对比)

//具体实现
example: arr = [4, 5, 6, 7, 0, 1, 2];

1. 中间值和最右边值进行对比， 如果中间值大于最右边值则认为最小值在右边区域。 left = middle + 1 (+1因为right > middle)
2. 中间值和最右边值进行对比， 如果中间值小于最右边值则认为最小值在左边区域。 right = middle (最小值可能是middle本身)
3. while终止条件: left == right

const findMin = function (arr = []){
   if(arr.length <= 0){
        return -1;
   }
   let left = 0;
   let right = arr.length - 1;
   while(left < right){
      let middle = left + Math.floor((right - left) / 2);
      if(arr[middle] > arr[right]){
         left = middle + 1;
      }
      else if (nums[mid] == nums[right]){ //[2, 2, 1, 2]  middle == right
         right --;
      }
      else{
         right = middle;
      }
   }
   return arr[left]; // arr[left] = arr[right]
}
findMin([4, 5, 6, 7, 0, 1, 2]);