# 数组相关
# 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(' ');
};