剑指 Offer 总结

1: 实现 Singleton （单例）模式

题目：设计一个类，我们只能生成该类的一个实例。

单例模式的定义是：保证一个类仅有一个实例，并提供一个访问它的全局访问点。

// Modal 类
class Modal {
  constructor(message) {
    this.message = message;
  }

  get getMessage() {
    return this.message;
  }
}

// 通过代理设计模式
// 使用闭包实现
const SingletonModal = (function () {
  let instance = null;
  return class SingletonModal {
    constructor(message) {
      if (instance === null) {
        instance = new Modal(message);
      }

      return instance;
    }
  };
})();

const Singleton1 = new SingletonModal("Singleton1");
const Singleton2 = new SingletonModal("Singleton2");

console.log(Singleton1 === Singleton2); // true
console.log(Singleton1.getMessage); // Singleton1
console.log(Singleton2.getMessage); // Singleton1

2: 数组中重复的数字

题目一：找出数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0 ～ n - 1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

例如，如果输入长度为 7 的数组 [2, 3, 1, 0, 2, 5, 3]

那么对应的输出是重复的数字 2 或者 3。

如不包含返回 false，如无效空指针返回 false

function duplicate(numbers) {
  if (!Array.isArray(numbers) && numbers !== null) return false;
  const length = numbers.length;

  // 如果值大于元素下标，返回 false
  for (let i = 0; i < length; ++i) {
    if (numbers[i] > length - 1) {
      return false;
    }
  }

  for (let i = 0; i < length; ++i) {
    while (i !== numbers[i]) {
      if (numbers[i] === numbers[numbers[i]]) {
        return numbers[numbers[i]];
      }
      let temp = numbers[i];
      numbers[i] = numbers[temp];
      numbers[temp] = temp;
    }
  }

  return false;
}
duplicate([2, 3, 1, 0, 2, 5, 3]); // 2
duplicate([1, 2, 3, 5]); // false
duplicate([1, 2, 3]); // false

题目二：不修改数组找出重复的数字

在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。

例如，如果输入长度为 8 的数组 [2, 3, 5, 4, 3, 2, 6, 7]

那么对应的输出是重复的数字 2 或者 3。

// 时间 O(n) 空间 O(n)
function duplicate(numbers) {
  if (numbers.length === 0) return false;

  const arr = [];
  for (let i = 0; i < numbers.length; ++i) {
    if (arr.includes(numbers[i])) {
      return numbers[i];
    }
    arr.push(numbers[i]);
  }

  return false;
}

const arr = [2, 3, 5, 4, 3, 2, 6, 7];
console.log(duplicate(arr));

// 时间 O(nlogn) 空间 O(1)
function duplicate(numbers) {
  if (numbers.length <= 0) return -1;

  let start = 1;
  let end = numbers.length - 1;

  while (end >= start) {
    let middle = ((end - start) >> 1) + start;

    let count = countRange(numbers, start, middle);
    if (end === start) {
      if (count > 1) {
        return start;
      } else {
        break;
      }
    }

    if (count > middle - start + 1) {
      end = middle;
    } else {
      start = middle + 1;
    }
  }
  return -1;
}

function countRange(numbers, start, end) {
  if (numbers.length === 0) return 0;

  let count = 0;
  for (let i = 0; i < numbers.length; ++i) {
    if (numbers[i] >= start && numbers[i] <= end) {
      ++count;
    }
  }
  return count;
}

const arr = [2, 3, 5, 4, 3, 2, 6, 7];
console.log(duplicate(arr)); // 3

3: 二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字 7，则返回 true；如果查找数字 5 ，由于数组不含有该数字，则返回 false。

const arr = [
  [1, 2, 8, 9],
  [2, 4, 9, 12],
  [4, 7, 10, 13],
  [6, 8, 11, 15],
];

function find(arr, num) {
  let found = false
  if (arr.length === 0) return found
  
  let row = 0
  let column = arr.length - 1

  while(row < arr.length && row >= 0 && column >= 0) {
    const rightTop = arr[row][column]
    if (rightTop === num) {
      found = true
      break
    } else if (rightTop > num) {
      --column
    } else {
      ++row
    }
  }
  return found
}

find(arr, 7)

思考：我们也可以选取左下角的数字。但我们不能选择左上角数字或者右下角数字。以左上角数字为例，最初数字 1 位于初始数组的左上角，由于 1 小于 7，那么 7 应该位于 1 的右边或者下边。此时我们既不能从查找范围内剔除 1 所在的行，也不能剔除 1 所在的列，这样我们就无法缩小查找范围。

const arr = [
  [1, 2, 8, 9],
  [2, 4, 9, 12],
  [4, 7, 10, 13],
  [6, 8, 11, 15],
];

function find(arr, num) {
  let found = false
  if (arr.length === 0) return found

  let row = arr.length - 1
  let column = 0

  while(column < arr.length && row >= 0 && column >= 0) {
    if (arr[row][column] === num) {
      found = true
      break
    } else if (arr[row][column] < num) {
      ++column
    } else {
      --row
    }
  }

  return found
}

find(arr, 7)

4: 替换空格

题目描述

请实现一个函数，把字符串中的每个空格替换成“%20”。

例如

输入: "We are happy"

输出: "We%20are%20happy"

# 1: 实现 Singleton （单例） 模式

# 2: 数组中重复的数字

# 3: 二维数组中的查找

# 4: 替换空格

1: 实现 Singleton （单例）模式

2: 数组中重复的数字

3: 二维数组中的查找

4: 替换空格