js解leetcode(63)-简单

1.魔术索引

题目：

魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

思路：简单的话，就是依次遍历，这个就不列代码了。这里说说二分法。

因为数组是有序的，所以可以借助二分法实现。首先，我们将数组每个成员减去下标，这样只需要找到成员为0的下标。

在理想情况下，只有1个元素符合条件，那么，假设第i个元素是0，那么左侧是负数，右侧是正数，所以简单的二分法。重点是多个元素为0，

比如[0,2,2,2]，处理之后变成了[0,1,0,-1].还是用二分法，不过，如果中间位置的成员是0，那么往左找。如果中间位置不为0，先往左找，如果左侧返回结果是-1，那么再往右侧。

理想情况，时间复杂度O(logn)，极端情况，时间复杂度是O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMagicIndex = function(nums) {
  nums = nums.map((item, index) => {
    return item - index;
  });
  const l = nums.length;
  const search = (left, right) => {
    if (!nums[left]) return left;
    const mid = ~~((left + right) / 2);
    if (left == mid) return !nums[right] ? right : -1;
    if (!nums[mid]) return search(left, mid);
    const leftV = search(left, mid - 1);
    if (leftV < 0) return search(mid + 1, right);
    return leftV;
  };
  return search(0, l - 1);
};

2.汉诺塔问题

题目：

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

思路：这个游戏应该很多人玩过。其实是一个递归问题。假设盘子是ABC

只有一个盘子时，直接从A到C。

两个盘子时，先将一个盘子移到B，然后将最下面的盘子移到C，然后将第一个盘子移到C。。。

有n个盘子，将n-1个盘子移到B，然后将一个盘子移到C，然后将n-1个盘子移到C

发现了吗，就是以递归。对于n>1，分为三步即可

/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @return {void} Do not return anything, modify C in-place instead.
 */
var hanota = function (A, B, C) {
  const move = (n, from, cache, to) => {
    if (n === 1) {
      to.push(from.pop());
    } else {
      move(n - 1, from, to, cache);
      move(1, from, cache, to);
      move(n - 1, cache, from, to);
    }
  };
  move(A.length, A, B, C);
};

3.颜色填充

题目：

编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。

待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的横坐标为 sr 纵坐标为 sc。需要填充的新颜色为 newColor 。

「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。

请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。

思路：深度优先遍历即可

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function(image, sr, sc, newColor) {
  const h = image.length;
  if (!h) return image;
  const w = image[0].length;
  const color = image[sr][sc];
  if (color == newColor) return image;
  const dfs = (i, j) => {
    if (i < 0 || i >= h) return;
    if (j < 0 || j >= w) return;
    if (image[i][j] !== color) return;
    image[i][j] = newColor;
    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
  };
  dfs(sr, sc);
  return image;
};

4.合并排序的数组

题目：

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

思路：插入排序或者归并排序的最后一步

/**
 * @param {number[]} A
 * @param {number} m
 * @param {number[]} B
 * @param {number} n
 * @return {void} Do not return anything, modify A in-place instead.
 */
var merge = function(A, m, B, n) {
  let left = 0,
    right = 0;
    A.splice(m)
  while (right < n) {
    while (A[left] < B[right] && left < m + right) {
      left++;
    }
    A.splice(left, 0, B[right]);
    left++;
    right++;
  }
  return A;
};

5.稀疏数组搜索

题目：稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。

思路：单次遍历没什么好说的，二分可以说一下。

如果遇到空字符串，边界往右扩张(可以理解成mid往右+，直到遇到字符串，这时才比较)

因为字符串是有序的，所以可以比较

/**
 * @param {string[]} words
 * @param {string} s
 * @return {number}
 */
var findString = function(words, s) {
    let left = 0
    let right = words.length - 1
    while (left <= right) {
        let mid_bak = mid = (left + right) >> 1
        // 重点：对空字符串的处理，除了mid右移以外，还要处理右侧超出边界的问题
        while (mid <= right && !words[mid]) {
            mid++;
        }
        // console.log(left, mid, right)
        // 右侧超出边界后压缩边界
        if (mid > right) {  // 若mid超出右边界(即为右边界+1), 说明mid至right处都为空字符串
            right = mid_bak - 1; // 压缩右边界至mid_bak的位置
            continue;   // 进行下一次循环
        }
        if (words[mid] > s) {
            right = mid - 1
        } else if (words[mid] < s) {
            left = mid + 1
        } else {
            return mid
        }
    }

    return -1
};