算法题之线性数据结构

Author Avatar
GeniusFunny 12月 14, 2019
  • 在其它设备中阅读本文章

算法题之线性数据结构～～～

从尾到头打印链表

题目

输入一个链表的头节点，从尾到头反过来打印出每个节点的值，链表节点定义如下：

1
2
3
4
5
6
class Node {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

解决方案

  • 递归【栈】

    1
    2
    3
    4
    5
    6
    7
    8
    function listPrint(node) {
      if (node.next) {
        listPrint(node.next)
        console.log(node.val)
      } else {
        console.log(node.val)
      }
    }

用两个栈实现队列

题目

用两个栈实现一个队列；队列的声明如下，请实现它的两个函数appendTail、deleteHead，分别完成入队和出队操作。

1
2
3
4
5
6
7
8
class Queue {
  constructor() {
    this.stack1 = []
    this.stack2 = []
  }
  appendTail(node) {}
  deleteHead() {}
}

解决方案

  • 两个栈，一个栈用作入队使用，一个栈用作出队使用
  • 执行入队操作时，一律将元素push进A栈
  • 执行出队操作时
    • 若B栈非空，则B栈pop即可
    • 若B栈为空，则将A栈所有元素依次出栈到B栈，此时B栈顶部元素即为需要出队的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Queue {
  constructor() {
    this.stackA = []
    this.stackB = []
  }
  appendTail(node) {
    this.stackA.push(node);
  }
  deleteHead() {
    if (this.stackB.length) {
      return this.stackB.pop();
    } else {
      for(let i = 0, len = this.stackA.length; i < len; i++) {
        this.stackB.push(this.stackA.pop())
      }
      return this.stackB.pop();
    }
  }
}

镜像题目

用两个队列实现一个栈；栈的声明如下，请实现它的两个函数push、pop，分别完成入栈和出栈操作。

解决方案
  • 非空队列作为入栈选择 【第一次入栈无要求】
  • 当元素出栈时，将非空队列的元素（除队尾）依次入队到另一队列，队列中最后的元素即栈顶元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Stack {
  constructor() {
    this.queueA = []
    this.queueB = []
    this.flag = true // true表示往队列A入队，false表示往队列B入队，初始为true
  }
  static popHelper(from, to) {
    for (let i = 0, len = from.length; i < len - 1; i++) {
      to.push(from.shift())
    }
    return from.shift()
  }
  push(node) {
    if (this.flag) {
      this.queueA.push(node)
    } else {
      this.queueB.push(node)
    }
  }
  pop() {
    this.flag = !this.flag
    return this.flag ? Stack.popHelper(this.queueB, this.queueA) : Stack.popHelper(this.queueA, this.queueB)
  }
}

链表中倒数第k个节点

题目

输入一个链表，输出链表中倒数第k个节点，链表节点定义如下：

1
2
3
4
5
6
class ListNode {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

解决方案

  • 【遍历2次】链表长度 = 当前索引+ k值，可通过此公式求解

    • 首先计算出链表长度n 【遍历1次】
    • 开始新一轮链表遍历，判断k值是否等于n-索引
      • 若k值 = n - 索引，则该节点即为所求节点
      • 若k值 > n - 索引，则无解
      • 若k值 < n - 索引，循环继续
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function kToLast(head, k) {
      if (!head || k < 1) return;
      let len = size(head)
      if (len - k < 0) return;
      let index = 0;
      let current = head;
      while(index !== len - k) {
        current = current.next
        index++
      }
      return current.val
    }

  • 【遍历1次】倒数第个节点与尾节点相隔k-1个节点，双指针

    • 定义2个指针都在首节点（A、B指针）

    • A指针先走K-1步，此时A、B指针同时前进

    • 当A指针到达尾节点时，B指针所指指针即为倒数第k个节点

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      function kToLast(head, k) {
        if (k < 1 || !head) return;
        let currentA = currentB = head
        let index = 1;
        while(index < k && currentA) {
          currentA = currentA.next;
          index++;
        }
        if (!currentA && index < k) return;
        while(currentA) {
          if (currentA.next === null) {
            return currentB.val
          }
          currentA = currentA.next
          currentB = currentB.next
        }
      }

链表中环的入口节点

题目

如果一个链表中包含环，如何找出环的入口节点。

解决方案

  • 指针P1、P2初始化时都指向头节点
  • 求出链表中环中的节点数n
    • 首先找出环中的节点，然后指针从环中任意节点前进，回到此节点时经历的节点数就是环中节点数
    • 要找到环中的节点，需要2个指针一快一慢，二者相遇的节点就是环中的一节点
  • P1先走n步，然后二者同时出发，相遇的节点即为环的入口
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
function getMeetingNode(head) {
  if (!head) return null
  let slow = head;
  let fast = head.next;
  while(slow !== null && fast !== null) {
    if (slow === fast) return fast;
    slow = slow.next;
    fast = fast.next;

    if (fast) {
      fast = fast.next
    }
  }
  return null
}
function entryNodeOfLoop(head) {
  let meetingNode = getMeetingNode(head);
  let nodesOfLoop = 0;
  if (head === null || meetingNode === null) return;
  let current = meetingNode;
  while(current !== null) {
    current = current.next;
    nodesOfLoop++;
    if (current === meetingNode) break;
  }
  let nodeA = head;
  for(let i = 0; i < nodesOfLoop; i++) {
    nodeA = nodeA.next
  }
  let nodeB = head;
  while(nodeA !== nodeB) {
    nodeA = nodeA.next
    nodeB = nodeB.next
  }
  return nodeA;
}

反转链表

题目

定义一个函数，输入一个链表的头节点后，反转该链表并输出反转后的链表头节点。链表节点定义如下：

1
2
3
4
5
6
class ListNode {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

解决方案

  • 中间节点进行处理时，首先要保留指向下一节点的引用
  • next：保存指向下一节点的引用
  • prev：指向上节点的引用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function reverseList(head) {
  if (!head) return null;
  let reverseHead = null;
  let current = head;
  let prev = null;
  while(current) {
    let next = current.next // 保留指向下一节点的引用
    if (!current.next) reverseHead = current // 如果后面没有节点，则此节点就是尾节点

    current.next = prev // 当前节点指向之前的节点，首节点指向null
    prev = current // 将之前的节点引用指向当前节点
    current = next // 前进到下一节点
  }
  head.next = null;
  return reverseHead;
}

删除链表节点

题目（一）在O(1)时间内删除链表节点

给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。链表节点与函数的定义如下

1
2
3
4
5
6
7
class ListNode {
  constructor(val) {
    this.val = val
    this.next = null
  }
}
function deleteNode(head, nodeToBeDeleted) {}
解决方案
  • 如果参数存在null，返回 【O(1)】
  • 链表中有多个节点，删除尾节点：需寻找到倒数第二节点然后进行删除操作 【O(n)】
  • 如果删除的不是尾节点，直接将被删除节点的下一个节点赋值到本节点【O(1)】
  • 链表只有一个节点，直接将头指针设置为null【O(1)】
  • 综合起来：算法时间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function deleteNode(head, nodeToBeDeleted) {
  if (!nodeToBeDeleted || !head) return;
  // 如果删除的不是尾节点，当前节点直接改为下一节点，，O(1)
  if (nodeToBeDeleted.next) {
    nodeToBeDeleted.val = nodeToBeDeleted.next.val
    nodeToBeDeleted.next = nodeToBeDeleted.next.next
  } else {
    // 如果被删除节点是尾节点, O(n)
    let current = head
    while(current.next !== nodeToBeDeleted) {
      current = current.next
    }
    current.next = null
  }
}

题目（二）删除链表中重复的节点

在一个排序的链表中，如何删除重复的节点？

解决方案
  • 判断当前节点与下一节点是否相同，若相同则删除下一节点，继续向前
  • 若当前节点为尾节点，则删除完毕
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function deleteRepeatNode(head) {
  if (head === null) return;
  let current = head;
  while(current !== null) {
    if (current.next) {
      if (current.val === current.next.val) {
        current.next = current.next.next
        current = current.next
      } else {
        current = current.next
      }
    }
  }
}

两个链表的第一个公共节点

题目

输入两个链表，找出他们的第一个公共节点

解决方案

  • 蛮力法，不推荐

  • 解决方法二：时间O(n+m)，空间O(m+n)【从尾比较】

    • 开辟两个栈，分别存储两个链表的元素
    • 将两个链表的元素分别入栈
    • 栈顶即为两个链表末尾节点，依次出栈
    • 当栈顶元素不等时，上一个节点即为第一个公共节点

  • 解决方法二：时间O(n+m)，空间O(1)

    • 计算出两个链表之间的长度差异n

    • 长链表先走n步，然后二者同时走

    • 相同的节点即为第一个公共节点

      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
      function findPublicNode(listA, listB) {
        if (listA === null || listB === null) return null;
        let currentA = currentB = null;
        let lenA = lenB = 0;
        let diff = 0;

        while(currentA) {
          lenA++;
          currentA = currentA.next;
        }
        while(currentB) {
          lenB++;
          currentB = currentB.next;
        }
        let diff = lenA - lenB;
        currentA = listA;
        currentB = listB;
        if (diff > 0) {
          // list A更长
          while(diff-- > 0) currentA = currentA.next
        } else if (diff === 0) {
          diff = Math.abs(diff);
          while(diff-- > 0) currentB = currentB.next
        } else {
          return listA;
        }
        while(currentA && currentB) {
          if (currentA === currentB) return currentA;
        }
        return null
      }

合并两个排序的链表

题目

输入两个递增排序的链表，合并这两个链表并使得新链表中的节点仍然是递增排序的。

解决方案

迭代 or 递归

  • 时间复杂度O(n+m)，空间复杂度O(n+m)

  • 两个链表首节点之间最小元素即为新链表的首节点。

  • 循环遍历比较两个链表的节点，二者小的加入新链表。

  • 当遍历完一个链表时，只需将另一链表剩余的节点一次添加进新链表即可。

    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
    function mergetList(listA, listB) {
      if (!listA) return listB;
      if (!listB) return listA;
      if (!listA || !listB) return null;

      let currentA = listA;
      let currentB = listB;
      let listC = null;
      let currentC = listC;

      while(currentA && currentB) {
        if (currentA.val <= currentB.val) {
          if (!listC) {
            listC = new ListNode(currentA.val);
            currentC = listC;
          } else {
            let node = new ListNode(currentA.val);
            currentC.next = node;
            currentC = currentC.next;
          }
          currentA = currentA.next;
        } else {
          if (!listC) {
            listC = new ListNode(currentB.val);
            currentC = listC;
          } else {
            let node = new ListNode(currentB.val);
            currentC.next = node;
            currentC = currentC.next;
          }
          currentB = currentB.next;
        }
      }
      while(currentA) {
        let node = new ListNode(currentA.val);
        currentC.next = node;
        currentC = currentC.next;
        currentA = currentA.next;
      }
      while(currentB) {
        let node = new ListNode(currentB.val);
        currentC.next = node;
        currentC = currentC.next;
        currentB = currentB.next;
      }
      return listC;
    }

包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push、pop的时间复杂度都是O(1)

解决方案

  • 定义两个栈，一个数据栈用来储存元素，另一个栈为辅助栈（储存每次元素入栈时的最小元素）
  • 入栈时，元素直接入数据栈，除此之外：
    • 若元素大于min，将min压入辅助栈
    • 若元素不大于min，则元素压入辅助栈
  • 出栈时：弹出数据栈和辅助栈 栈顶元素
  • 执行min操作时
    • 直接返回辅助数组首元素
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
class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
    this.mins = []
  }
  push(val) {
    let node = new Node(val);
    if (!this.top) {
      this.top = node;
      this.mins.push(node)
    } else {
      if (this.mins[0].val >= node.val) {
        this.mins.unshift(node)
      } else {
        this.mins.push(this.mins[0])
      }
      node.next = this.top;
      this.top = node;
    }
  }
  pop() {
    let top = this.top
    if (this.pop === null) return null
    this.mins.pop()
    this.top = this.top.next
    return top
  }
  min() {
    return this.mins[0]
  }
}

栈的压入、弹出序列

题目

输入两个整数序列，第一个序列表示出栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相同，例如，序列「1，2，3，4，5」是某栈的压栈序列，序列「4，5，3，2，1」是该压栈序列对应的一个弹出序列，但「4，3，5，1，2」就不可能是该压栈序列的弹出序列。

解决方案

  • 定义一个辅助栈
  • 若弹出序列的首元素与辅助栈栈顶元素相同，则弹出序列索引后移同时辅助栈弹出栈顶
  • 若不同，则将入栈序列首元素压入辅助栈中，直到辅助栈栈顶元素与弹出序列首元素相同；
  • 若压入序列都已入栈，辅助栈栈顶元素与弹出序列元素仍不同，则该弹出序列不是该压栈序列的弹出序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function judgeStackSequence(pushSequence = [], popSequence = []) {
  // 如果栈顶就是待出栈序列元素，则直接出栈
  // 若栈顶不是待出栈序列元素，则将待入栈序列元素入栈，直到待出栈元素入栈
  // 若入栈序列全部入栈，仍栈顶仍不是出栈序列待出栈序列，则判断出栈序列不是该入栈序列的弹出序列
  let stack = [];
  if (!pushSequence.length || !popSequence) return false;
  while(popSequence.length) {
    console.log(stack[stack.length-1], popSequence[0])
    if (stack[stack.length-1] === popSequence[0]) {
      popSequence.shift()
      stack.pop()
    } else {
      if (!pushSequence.length) break;
      stack.push(pushSequence.shift())
    }
  }
  return popSequence.length ? false : true;
}

复杂链表的复制

题目

请实现函数clone，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一节点，还有一个bibling指针指向链表中的人一节点或null。节点的定义如下

1
2
3
4
5
6
7
class ComplexListNode {
  constructor(val = 0) {
    this.val = val
    this.next = null
    this.sibling = null
  }
}

解决方案

  • 复制节点链接在原节点后，最后拆分链表【时间O(n)】

    • 复制节点：遍历原节点，将复制节点作为原节点下一节点

    • 调整sibling：遍历原节点，将原节点的sibling的下一节点设置为复制节点的sibling

    • 拆分链表：奇数节点拼接起来就是原链表，偶数节点拼接起来就是新链表

      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
      function cloneComplexList(head) {
        if (!head) return null;
        let current = head;
        while(current) {
          let node = new ComplexListNode(current.val);
          node.next = current.next
          current.next = node;
          current = current.next.next;
        }
        current = head;

        while(current) {
          if (current.sibling) {
            current.next.sibling = current.sibling.next;
          }
          current = current.next.next;
        }
        current = head; 

        let cloned = head.next; 
        let clonedCurrent = cloned;
        while(current) {
          clonedCurrent = current.next; 
          current.next = current.next.next; 

          if (!current) break; 

          clonedCurrent.next = current.next;
          current = current.next;
          clonedCurrent = clonedCurrent.next; 
        }
        return cloned;
      }

  • 定一个哈希表，A作为key，A’作为val。【时间O(n)、空间O(n)】

    • 复制节点，存储哈希表：遍历原链表一遍，建立一个复制后的链表，同时整个过程哈希表中存储【A-A’】的键值对。

    • 调整sibling，读取哈希表：同时遍历2个链表，若A的sibling指向C，则A’的sibling则指向哈希表存储的C对应的C’。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      function cloneComplexList(head) {
        if (!head) return null;
        const cloned = new ComplexListNode(head.val);
        const map = new Map();
        let current = head.next;
        let clonedCurrent = cloned;
        while(current) {
          let node = new ComplexListNode(current.val)
          clonedCurrent.next = node;
          map.set(current, node);
          clonedCurrent = clonedCurrent.next;
          current = current.next;
        }
        current = head;
        clonedCurrent = cloned;
        while (current) {
          if (current.sibling) {
            clonedCurrent.sibling = map.get(current.sibling)
          }
          current = current.next
          clonedCurrent = clonedCurrent.next
        }
        return cloned;
      }

###

Powered by Hexo
Theme - Material