アルゴリズムの基礎の簡単なアルゴリズム
9433 ワード
本論文は簡単な線形アルゴリズムといくつかの数値計算を含み、また更新し続ける.
rgbと16進は互いに変換します.
ある無秩序配列を指定して、任意の2つの要素の間の最大の差を求めます.ここでは、差の計算において小さい要素の下付きが大きな要素の下付きより小さくなければならないことに注意してください.
ある無秩序配列を指定すると、新しい配列outputに戻る必要があります.ここで、output[i]は元の配列の中でiと表記された要素以外の要素積であり、O(n)複雑度で実現されることが必要です.
例えば、シーケンス1,2,3,4,5は、あるスタックの圧入順序であり、シーケンス4,5,2,1は、このスタックシーケンスに対応する1つのポップアップシーケンスであるが、4,3,5,1,2は、このスタックシーケンスのポップアップシーケンスであることが不可能である.
rgbと16進は互いに変換します.
function rgb2hex(r,g,b){
return "#" + ((r<<16)+(g<<8)+b).toString(16);
}
function hex2rgb(str){
var arr = str.match(/[0-9a-f]{2}/ig);
return {
r: parseInt(arr[0], 16),
g: parseInt(arr[1], 16),
b: parseInt(arr[2], 16)
};
}
整型配列の中の積の最大の3つの数を探し出します.var original_array = [-10, -7, -29, -4, -1, -10, -70];
var result = findMPTN(original_array);
console.log(result);
function findMPTN(arr){ //findMaxiumProductorOfThreeNumbers
var len = arr.length;
sorted_arr = arr.sort(function(a,b){return a-b;});
var pro1 = 1, pro2 = sorted_arr[len - 1];
for(var i = 1; i <= 3; i++){
pro1 *= sorted_arr[len - i];
}
pro2 *= sorted_arr[0];
pro2 *= sorted_arr[1];
return pro1 > pro2 ?
[sorted_arr[len - 3], sorted_arr[len - 2], sorted_arr[len - 1]] :
[sorted_arr[0], sorted_arr[1], sorted_arr[len - 1]];
}
大かっこが閉じているかどうかを判断します.var expression = "{{}}{}{}"
var expressionFalse = "{}{{}";
console.log(isBalanced(expression)); // true
console.log(isBalanced(expressionFalse)); // false
console.log(isBalanced("")); // true
function isBalanced(exp){
var stack = [];
var arr = exp.split("");
var len = arr.length, cur;
while(cur = arr.shift()){
if(cur === "{") stack.push(cur);
if(cur === "}") stack.pop();
}
if(stack.length !== 0) return false;
return true;
}
二つの倉庫を使って入隊と出隊を実現する.Array.prototype.enqueue = function(item){
return this.push(item);
};
Array.prototype.dequeue = function(){
var tempStack = [];
var cur, temp;
while(cur = this.pop()){
tempStack.push(cur);
}
temp = tempStack.pop();
while(cur = tempStack.pop()){
this.push(cur);
}
return temp;
};
連続配列中の欠落数を探しています.var array = [2, 5, -1, 9, -6, 3, 7];
var result = findLost(array);
console.log(result);
function findLost(arr){
if(arr.length <= 1) return null;
var sortedArr = arr.sort(function(a,b){return a-b;});
var i = sortedArr.shift();
var cur = sortedArr.shift();
var result = [];
do{
i++;
if(cur === i) cur = sortedArr.shift();
else result.push(i);
}while(cur);
return result;
}
配列中の要素の最大差分値計算ある無秩序配列を指定して、任意の2つの要素の間の最大の差を求めます.ここでは、差の計算において小さい要素の下付きが大きな要素の下付きより小さくなければならないことに注意してください.
var array = [7, 8, 4, 9, 9, 15, 3, 1, 10];
var result = findLargestDifference(array);
console.log(result);
function findLargestDifference(arr){
var min = arr[0];
var diff = 0;
for(var i = 1, len = arr.length; i < len; i++){
if(arr[i] < min){
min = arr[i];
continue;
}
if(arr[i] - min > diff){
diff = arr[i] - min;
}
}
return diff;
}
配列中の要素積ある無秩序配列を指定すると、新しい配列outputに戻る必要があります.ここで、output[i]は元の配列の中でiと表記された要素以外の要素積であり、O(n)複雑度で実現されることが必要です.
var firstArray = [2, 2, 4, 1];
var secondArray = [0, 0, 0, 2];
var thirdArray = [-2, -2, -3, 2];
console.log(productExceptSelf(firstArray)); // [8, 8, 4, 16]
console.log(productExceptSelf(secondArray)); // [0, 0, 0, 0]
console.log(productExceptSelf(thirdArray)); // [12, 12, 8, -12]
function productExceptSelf(arr){
var result = [];
var pro = 1;
var len = arr.length;
for(var i = 0; i < len; i++){
result.push(pro);
pro *= arr[i];
}
pro = 1;
for(i = len - 1; i >= 0; i--){
result[i] *= pro;
pro *= arr[i];
}
return result;
}
配列平準化var arr = [1,2,[1,3,[2,[2,3,3],[2,5]]],[6,3]];
//
function flat(arr,result=[]){
if(arr.constructor !== Array) return [arr];
var length = arr.length;
arr.forEach(function(item){
if(item.constructor !== Array) result.push(item);
else result = flat(item, result);
});
return result;
}
var flatted = flat(arr);
console.log(flatted); //[1, 2, 1, 3, 2, 2, 3, 3, 2, 5, 6, 3]
//
var arr=[1,3,4,5,[6,[0,1,5],9],[2,5,[1,5]],[5]];
var flatter = arr => arr.reduce((a, b) => a.concat(Array.isArray(b) ? flatter(b) : b), []);
console.log(flatter(arr)); //[1, 2, 1, 3, 2, 2, 3, 3, 2, 5, 6, 3]
// , :
var flatten = a => a.join().split(',');
console.log(flatten(arr)); //["1", "2", "1", "3", "2", "2", "3", "3", "2", "5", "6", "3"]
文字列の中で最も多い文字と数を検索します."ababccdeaeajxac".split('').sort().join('').match(/(\w)\1*/g).reduce(function(a,b){ return a.length > b.length ? a : {char: b[0], length: b.length};}, {char: '', length: 0}); //{char: "a", length: 5}
文字列検索String.prototype.indexOf = String.prototype.indexOf || function(str){
if(str.length > this.length) return -1;
var len = 0;
var _this = this.split(''), str = str.split('');
var lenA = str.length, this_len = this.length;
var temp;
for(var i = 0, j = 0; j < lenA; i = 0, j = temp + 1, len = 0){
debugger;
while(str[i] !== _this[j] && j < this_len){
j++;
}
temp = j;
while(str[i] === _this[j] && j < this_len){
len++;
i++;
j++;
}
if(len === lenA) return temp;
}
return -1;
}
文字列検索(KMPアルゴリズム)String.prototype.indexOf = String.prototype.indexOf || function(str){
var next = [];
var n = this.length;
var m = str.length;
calcNext(str,next);
for (var i = 0,q = 0; i < n; ++i){
while(q > 0 && str[q] != this[i])
q = next[q-1];
if (str[q] === this[i]){
q++;
}
if (q === m){
return i - m + 1;
}
}
return -1;
function calcNext(str){
var m = str.length;
next[0] = 0;
for(var q = 1, k = 0; q < m; ++q){
while(k > 0 && str[q] != str[k])
k = next[k-1];
if (str[q] == str[k]){
k++;
}
next[q] = k;
}
}
}
チェーンの有無を確認します.function hasCircle(head){ //
var pos1 = head;
var pos2 = head;
while(pos2){
pos1 = pos1.next;
pos2 = pos2.next !== null ? pos2.next.next : null;
if(pos1 === pos2) return true;
}
return false;
}
つの数の2進数の中で1の個数を求めます.function numberOf1(n){
if(n < 0){
n = n >>> 0;
}
var arr = n.toString(2).split('');
return arr.reduce(function(a,b){
return b === "1" ? a + 1 : a;
},0);
}
反転リンク/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function reverseList(pHead){
var newHead, temp;
if(!pHead){
return null;
}
if(pHead.next === null){
return pHead;
} else {
newHead = ReverseList(pHead.next);
}
temp = pHead.next;
temp.next = pHead;
pHead.next = null;
temp = null;
return newHead;
}
スタック順出力かどうかを判断する例えば、シーケンス1,2,3,4,5は、あるスタックの圧入順序であり、シーケンス4,5,2,1は、このスタックシーケンスに対応する1つのポップアップシーケンスであるが、4,3,5,1,2は、このスタックシーケンスのポップアップシーケンスであることが不可能である.
function isPopOrder(pushV, popV){
if(!pushV.length || !popV.length){
return false;
}
var temp = [];
var popIndex = 0;
var len = pushV.length;
for(var i = 0; i < len; i++){
temp.push(pushV[i]);
while(temp.length && temp[temp.length - 1] === popV[popIndex]){
temp.pop();
popIndex++;
}
}
return temp.length === 0;
}
文字列内の文字の全配列を取得します(重複なし)function permutation(str){
if(!str || str.length === 0){
return [];
}
var result = [];
var arr = str.split('');
var temp = '';
ordering(arr);
result = result.filter(function(item, index){ //
return result.indexOf(item) === index;
});
return result;
function ordering(tempArr){
if(tempArr.length === 0){
result.push(temp);
return;
}
for(var i = 0; i < tempArr.length; i++){
temp += tempArr[i];
insideArr = tempArr.concat();
insideArr.splice(i,1);
ordering(insideArr);
temp = temp.substring(0, temp.length - 1); //
}
}
}
リングチェーンのあるエントリノードを検索します./*function ListNode(x){
this.val = x;
this.next = null;
}*/
function EntryNodeOfLoop(pHead){
if(!pHead){
return null;
}
var meeting = meetingNode(pHead);
if(!meeting){
return null;
}
var nodeLoop = 1;
var node1 = meeting;
while(node1.next != meeting){
node1 = node1.next;
nodeLoop++;
}
node1 = pHead;
for(var i = 0; i < nodeLoop; i++){
node1 = node1.next;
}
var node2 = pHead;
while(node1 != node2){
node1 = node1.next;
node2 = node2.next;
}
return node1;
function meetingNode(node){
if(!node || !node.next){
return null;
}
var slow = node.next;
var fast = slow.next;
while(fast && slow){
if(fast === slow){
return fast;
}
slow = slow.next;
fast = fast.next;
if(fast){
fast = fast.next;
}
}
return null;
}
}