数组相关算法

LeetCode 算法入门

704. 二分查找

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const searchIndex = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    if (nums[middle] > target) {
      right = middle - 1;
    } else if (nums[middle] < target) {
      left = middle + 1;
    } else {
      return middle;
    }
  }
  return -1;
};

278. 第一个错误的版本

/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  // 二分查找
  return function (n) {
    let left = 1,
      right = n;
    while (left <= right) {
      const mid = Math.floor(left + (right - left) / 2);
      if (isBadVersion(mid)) {
        right = mid - 1; // 如果mid为bad，则右侧都为bad
      } else {
        left = mid + 1; // 如果mid不为bad，则左侧都不为bad
      }
    }
    return left;
  };
};

35. 搜索插入位置

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
};

977. 有序数组的平方

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  const newArr = [];
  const n = nums.length;
  let mid = -1;
  for (let i = 0; i < n; i++) {
    if (nums[i] < 0) {
      mid = i;
    } else {
      break;
    }
  }
  let l = mid;
  r = mid + 1;
  while (l >= 0 || r < n) {
    if (l < 0) {
      newArr.push(nums[r] * nums[r]);
      ++r;
    } else if (r === n) {
      newArr.push(nums[l] * nums[l]);
      --l;
    } else if (nums[l] * nums[l] < nums[r] * nums[r]) {
      newArr.push(nums[l] * nums[l]);
      --l;
    } else {
      newArr.push(nums[r] * nums[r]);
      ++r;
    }
  }
  return newArr;
};

189. 轮转数组

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const reverse = (nums, start, end) => {
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
};
var rotate = function (nums, k) {
  k %= nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  return nums;
};

// TAG: 我自己写的方法，未通过，没找到原因
var rotate = function (nums, k) {
  const n = nums.length;
  const newArr = new Array(n);
  k %= n;
  for (let i = 0; i < n; i++) {
    if (i < n - k) {
      newArr[k + i] = nums[i];
    } else {
      newArr[k - (n - i)] = nums[i];
    }
  }
  return newArr;
};

console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3));

283. 移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  const n = nums.length;
  let left = 0,
    right = 0;
  while (right < n) {
    if (nums[right]) {
      const temp = nums[left];
      nums[left] = nums[right];
      nums[right] = temp;
      left++;
    }
    right++;
  }
};

344. 反转字符串

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  const n = s.length;
  for (let left = 0, right = n - 1; left < right; ++left, --right) {
    [s[left], s[right]] = [s[right], s[left]];
  }
};

557. 反转字符串中的单词 III

方法一：（终极解法）

split + 反转 + join + 反转

const reverse = nums => {
  let start = 0,
    end = nums.length - 1;
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
  return nums;
};
var reverseString = function (s) {
  const n = s.length;
  let str = '';
  for (let i = n - 1; i >= 0; i--) {
    str += s[i];
  }
  return str;
};
var reverseWords = function (s) {
  let arr = s.split(' '); // ["Let's", "take", "LeetCode", "contest"]
  arr = reverse(arr); // ["contest", "LeetCode", "take", "Let's"]
  let str = arr.join(' '); // "contest LeetCode take Let's"
  str = reverseString(str); // "s'teL ekat edoCteeL tsetnoc"
  return str;
};

方法二：（我自己写的）

/**
 * @param {string} s
 * @return {string}
 */
var reverse = function (s) {
  const n = s.length;
  let str = '';
  for (let i = n - 1; i >= 0; i--) {
    str += s[i];
  }
  return str;
};
var reverseWords = function (s) {
  let arr = s.split(' ');
  const newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(reverse(arr[i]));
  }
  return newArr.join(' ');
};