# 数组相关

# LeetCode 算法入门

# 704. 二分查找 (opens new window)

/**
 * @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. 第一个错误的版本 (opens new window)

/**
 * 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. 搜索插入位置 (opens new window)

/**
 * @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. 有序数组的平方 (opens new window)

/**
 * @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. 轮转数组 (opens new window)

/**
 * @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. 移动零 (opens new window)

/**
 * @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. 反转字符串 (opens new window)

/**
 * @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 (opens new window)

方法一:(终极解法)

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(' ');
};
更新时间: 3/28/2022, 2:24:02 PM