1.找出整型數(shù)組中乘積最大的三個(gè)數(shù)
思路：1.先進(jìn)行排序
? ? ? ? ? ? 2.考慮出現(xiàn)最大值的時(shí)候出現(xiàn)的情況? 兩負(fù)一正，三正
var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];
computeProduct(unsorted_array); // 21000
function sortIntegers(a, b) {
? return a - b;
}
// greatest product is either (min1 * min2 * max1 || max1 * max2 * max3)
function computeProduct(unsorted) {
? var sorted_array = unsorted.sort(sortIntegers),
? ? product1 = 1,
? ? product2 = 1,
? ? array_n_element = sorted_array.length - 1;
? // Get the product of three largest integers in sorted array
? for (var x = array_n_element; x > array_n_element - 3; x--) {
? ? ? product1 = product1 * sorted_array[x];
? }
? product2 = sorted_array[0] * sorted_array[1] * sorted_array[array_n_element];
? if (product1 > product2) return product1;
? return product2
};
2.尋找連續(xù)數(shù)組中的缺失數(shù)
1.通過相減去找一個(gè)數(shù)字
var array_of_integers = [2, 5, 1, 4, 9, 6, 3, 7];
findMissingNumber(array_of_integers); //8
function findMissingNumber(array_of_integers, upper_bound, lower_bound) {
? var sum_of_integers = 0;
let arr=array_of_integers.concat().sort();
? for (var i = 0; i < array_of_integers.length; i++) {
? ? sum_of_integers += array_of_integers[i];
? }
? theoretical_sum = (arr[0]+arr[arr.length-1])*(arr[arr.length-1]-arr[0]+1)/2;
? return (theoretical_sum - sum_of_integers)
}
3.數(shù)組去重
// ES6 Implementation? ?效率高
var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]
var Arr=[1,2,3,2,4,4,1];
var arr = [Arr[0]]; //創(chuàng)建一個(gè)臨時(shí)數(shù)組,并將要去重?cái)?shù)組的第一項(xiàng)存入臨時(shí)數(shù)組
for(var i = 1; i < Arr.length; i++) { //從要去重?cái)?shù)組第二項(xiàng)開始遍歷
? if (arr.indexOf(this[i]) == i){ //判斷臨時(shí)數(shù)組中是否存有當(dāng)前項(xiàng)，沒有則執(zhí)行
? arr.push(this[i]); //將當(dāng)前項(xiàng)push到臨時(shí)數(shù)組中
? }
}
4.數(shù)組中元素最大差值計(jì)算
給定某無序數(shù)組，求取任意兩個(gè)元素之間的最大差值，注意，這里要求差值計(jì)算中較小的元素下標(biāo)必須小于較大元素的下標(biāo)。譬如[7, 8, 4, 9, 9, 15, 3, 1, 10]這個(gè)數(shù)組的計(jì)算值是 11( 15 - 4 ) 而不是 14(15 - 1)，因?yàn)?15 的下標(biāo)小于 1。
1.先定義第一個(gè)為最小值，與最大相差值為1
2.循環(huán)獲取后面比最小值小的，賦值給最小值
3.循環(huán)中獲取比當(dāng)前最小值大的，并且比當(dāng)前值減去最小值大于相差值的值賦給相差值
var array = [7, 8, 4, 9, 9, 15, 3, 1, 10];
// [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15`
// Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1.
findLargestDifference(array);
function findLargestDifference(array) {
? // 如果數(shù)組僅有一個(gè)元素，則直接返回 -1
? if (array.length <= 1) return -1;
? // current_min 指向當(dāng)前的最小值
? var current_min = array[0];
? var current_max_difference = 0;
? // 遍歷整個(gè)數(shù)組以求取當(dāng)前最大差值，如果發(fā)現(xiàn)某個(gè)最大差值，則將新的值覆蓋 current_max_difference
? // 同時(shí)也會(huì)追蹤當(dāng)前數(shù)組中的最小值，從而保證 `largest value in future` - `smallest value before it`
? for (var i = 1; i < array.length; i++) {
? ? if (array[i] > current_min && (array[i] - current_min > current_max_difference)) {
? ? ? current_max_difference = array[i] - current_min;
? ? } else if (array[i] <= current_min) {
? ? ? current_min = array[i];
? ? }
? }
? // If negative or 0, there is no largest difference
? if (current_max_difference <= 0) return -1;
? return current_max_difference;
}
5.數(shù)組中元素乘積
給定某無序數(shù)組，要求返回新數(shù)組 output ，其中 output[i] 為原數(shù)組中除了下標(biāo)為 i 的元素之外的元素乘積，要求以 O(n) 復(fù)雜度實(shí)現(xiàn)：
var firstArray = [2, 2, 4, 1];
var secondArray = [0, 0, 0, 2];
var thirdArray = [-2, -2, -3, 2];
productExceptSelf(firstArray); // [8, 8, 4, 16]
productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12]
function productExceptSelf(numArray) {
? var product = 1;
? var size = numArray.length;
? var output = [];
? numArray.forEach(val=>{
? ? product*=val;
? })
? for (var i = size - 1; i > -1; i--) {
? ? ? output[i] = product/numArray[i] ;
? }
? return output;
}
6.數(shù)組交集
給定兩個(gè)數(shù)組，要求求出兩個(gè)數(shù)組的交集，注意，交集中的元素應(yīng)該是唯一的。
var firstArray = [2, 2, 4, 1];
var secondArray = [1, 2, 0, 2];
function checksameValues(firstArray,secondArray){
? let arr=[];
? firstArray.forEach((val)=>{
? ? if(secondArray.indexOf(val)!==-1&&arr.indexOf(val)===-1){
? ? arr.push(val);
? ? }
? })
? return arr;
}
checksameValues(firstArray,secondArray)
7.字符串顛倒字符串
給定某個(gè)字符串，要求將其中單詞倒轉(zhuǎn)之后然后輸出，譬如"Welcome to this Javascript Guide!" 應(yīng)該輸出為 "emocleW ot siht tpircsavaJ !ediuG"。
var string = "Welcome to this Javascript Guide!";
// Output becomes !ediuG tpircsavaJ siht ot emocleW
var reverseEntireSentence = reverseBySeparator(string, "");
// Output becomes emocleW ot siht tpircsavaJ !ediuG
var reverseEachWord = reverseBySeparator(reverseEntireSentence, " ");
function reverseBySeparator(string, separator) {
? return string.split(separator).reverse().join(separator);
}
7.二進(jìn)制轉(zhuǎn)換
通過某個(gè)遞歸函數(shù)將輸入的數(shù)字轉(zhuǎn)化為二進(jìn)制字符串：
decimalToBinary(3); // 11
decimalToBinary(8); // 1000
decimalToBinary(1000); // 1111101000
function decimalToBinary(digit) {
? if(digit >= 1) {
? ? // If digit is not divisible by 2 then recursively return proceeding
? ? // binary of the digit minus 1, 1 is added for the leftover 1 digit
? ? if (digit % 2) {
? ? ? return decimalToBinary((digit - 1) / 2) + 1;
? ? } else {
? ? ? // Recursively return proceeding binary digits
? ? ? return decimalToBinary(digit / 2) + 0;
? ? }
? } else {
? ? // Exit condition
? ? return '';
? }
}
8.二分搜索
function recursiveBinarySearch(array, value, leftPosition, rightPosition) {
? // Value DNE
? if (leftPosition > rightPosition) return -1;
? var middlePivot = Math.floor((leftPosition + rightPosition) / 2);
? if (array[middlePivot] === value) {
? ? return middlePivot;
? } else if (array[middlePivot] > value) {
? ? return recursiveBinarySearch(array, value, leftPosition, middlePivot - 1);
? } else {
? ? return recursiveBinarySearch(array, value, middlePivot + 1, rightPosition);
? }
}
