南风知我意的技术博客

Appearance

一、时间复杂度题型 ​

1.将一个数组旋转 k 步 ​

  • 输入一个数组 [1, 2, 3, 4, 5, 6, 7]
  • k = 3 ,即旋转 3 步
  • 输出 [5, 6, 7, 1, 2, 3, 4]

思路一：把末尾的元素挨个 pop , 然后 unshift 到数组前面 思路二：把数组拆分，最后 concat 拼接到一起

  • 思路一：把末尾的元素挨个 pop , 然后 unshift 到数组前面

    js
    /**
 * 旋转数组 k 步 - 使用 pop 和 unshift
 * @param arr 数组
 * @param k 旋转 k 步
 * @return {*} 数组
 */
function rotate1(arr, k) {
  const { length } = arr;
  if (!k || length === 0) return arr;
  // 取绝对值
  const step = Math.abs(k % length)

  for (let i = 0; i < step; i++) { // O(n)
    const n = arr.pop()
    if (n !== null) {
      arr.unshift(n) // 数组是一个有序结构，unshift 操作非常慢 O(n)
    }
  }
  return arr
}

  • 思路一：思路二：把数组拆分，最后 concat 拼接到一起

    js
    /**
 * 旋转数组 k 步 - 使用 concat
 * @param arr
 * @param k
 */
function rotate2(arr, k) {
  const { length } = arr;
  if (!k || length === 0) return arr;
  // 取绝对值
  const step = Math.abs(k % length);

  const part1 = arr.slice(-step); // O(1)
  const part2 = arr.slice(0, length - step);
  const part3 = part1.concat(part2)

  return part3;
}

  • 测试用例

    js
    const rotate1 = require("../array-rotate")
const rotate2 = require("../array-rotate")

describe('数组反转', () => {

  it('正常情况 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = 3;

    const res = rotate1(arr, k);
    expect(res).toEqual([5,6,7,1,2,3,4])
  });

  it('数组为空 ',  () => {
    const arr = [];
    const k = 3;

    const res = rotate1(arr, k);
    expect(res).toEqual([])
  });

  it('k 是负值 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = 3;

    const res = rotate1(arr, k);
    expect(res).toEqual([5,6,7,1,2,3,4])
  });

  it('k 是 0 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = 0;

    const res = rotate1(arr, k);
    expect(res).toEqual(arr)
  });

  it('k 不是一个数字 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = '';

    const res = rotate1(arr, k);
    expect(res).toEqual(arr)
  });


  it('正常情况 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = 3;

    const res = rotate2(arr, k);
    expect(res).toEqual([5,6,7,1,2,3,4])
  });

  it('数组为空 ',  () => {
    const arr = [];
    const k = 3;

    const res = rotate2(arr, k);
    expect(res).toEqual([])
  });

  it('k 是负值 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = 3;

    const res = rotate2(arr, k);
    expect(res).toEqual([5,6,7,1,2,3,4])
  });

  it('k 是 0 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = 0;

    const res = rotate2(arr, k);
    expect(res).toEqual(arr)
  });

  it('k 不是一个数字 ',  () => {
    const arr = [1,2,3,4,5,6,7];
    const k = '';

    const res = rotate2(arr, k);
    expect(res).toEqual(arr)
  });
})

  • 复杂度分析

    • 思路一：时间复杂度 O(n ^ 2)，空间复杂度 O(1)
    • 思路二：时间复杂度 O(1)， 空间复杂度 O(n)

2. 判断字符串是否括号匹配 ​

  • 一个字符串 s 可能包含 {} () [] 三种括号
  • 判断 s 是否括号匹配的
  • 如（a{b}c）匹配，而 {a(b 或 {a(b}c) 就不匹配

考察的知识点：栈

algorithm-stack.png

栈 VS 数组

  • 栈，逻辑结构。理论模型，不管如何实现，不受任何语言的限制。
  • 数组，物理结构。真实的功能实现，受限于编程语言。

思路：

  • 遇到左括号 {([ 就压栈
  • 遇到右括号 })] 就判断栈顶，匹配则出栈
  • 最后判断 length 是否为 0

  • 代码题解

    js
    /**
 * 判断左右括号是否匹配
 * @param left
 * @param right
 * @return {boolean}
 */
function isMatch(left, right){
  if (left === '{' && right === '}') return true;
  if (left === '[' && right === ']') return true;
  if (left === '(' && right === ')') return true;
  return false;
}

/**
 * 判断是否括号匹配
 * @param str str
 */
function matchBracket(str) {
  const { length } = str;
  if (length === 0) return true;

  const stack = [];

  const leftSymbols = '{[(';
  const rightSymbols = '}])';

  for (let i = 0; i < length; i++) {
    if (leftSymbols.includes(str[i])) {
      stack.push(str[i]);
    } else if (rightSymbols.includes(str[i])) {
      const top = stack[stack.length -1];
      if (isMatch(top, str[i])) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}

module.exports = matchBracket

  • 测试用例

    js
    
/**
 * @description 括号匹配
 * @author eastern
 */
const matchBracket = require("../match-bracket")

describe('括号匹配', () => {
  it('正常情况', function () {
      const str = "{a(b[c]d)e}f";
      const res = matchBracket(str);
      expect(res).toBe(true);
  });

  it('不匹配', function () {
    const str = "{a(b[c]d)e}f}";
    const res = matchBracket(str);
    expect(res).toBe(false);
  });

  it('括号顺序不一致', function () {
    const str = "{a(b}[c]d)ef";
    const res = matchBracket(str);
    expect(res).toBe(false);
  });

  it('空字符传', function () {
    const str = "";
    const res = matchBracket(str);
    expect(res).toBe(true);
  });
})

  • 复杂度分析

    • 时间复杂度 O(n) 空间复杂度 O(n)

3. 两个栈实现一个队列 ​

  • 请用两个栈，实现一个队列
  • 功能 add delete length

队列：

  • 先进先出
  • API: add delete length algorithm-queue.png

数组实现队列：

  • 队列是逻辑结构，抽象模型
  • 简单的，可以用数组、链表实现
  • 复杂的队列服务，需要单独设计。

  • 代码题解

    js
    /**
 * @description 两个栈 - 一个队列
 * @author eastern
 */
class Queue {
  stack1 = [];
  stack2 = []

  /**
   * 入队
   * @param n
   */
  add(n) {
    this.stack1.push(n)
  }

  delete() {
    let res;
    const stack1 = this.stack1;
    const stack2 = this.stack2;

    // 将 stack1 所有元素移动到 stack2 中
    while (stack1.length) {
      const n = stack1.pop()
      if (n !== null) {
        stack2.push(n)
      }
    }

    // stack2 pop
    res = stack2.pop()

    // 将 stack2 所有元素 "还给" stack1
    while (stack2.length) {
      const n = stack2.pop()
      if (n !== null) {
        stack1.push(n)
      }
    }
    return res;
  }

  get length() {
    return this.stack1.length
  }
}

module.exports = Queue

  • 测试用例

    js
    const Queue = require("../two-stacks-one-queue")

describe('两个数组一个栈',() => {
  it('add and length', function () {
    const q = new Queue();
    expect(q.length).toBe(0);

    q.add(100);
    q.add(200);
    q.add(300);
    expect(q.length).toBe(3);
  });

  it('delete', function () {
    const q = new Queue();
    q.add(100);
    q.add(200);
    q.add(300);
    expect(q.delete()).toBe(100);
    expect(q.length).toBe(2);
  });
})

  • 复杂度分析

    • 时间复杂度：add O(1); delete O(n)
    • 空间复杂度：整体是 O(n)

4. 定义一个 JS 函数，反转单向链表 ​

Released under the MIT License.

Copyright © 2021-present eastern