数学算法
数学算法¶
不借助变量交换两个数字¶
function swap(a , b) {
b = b - a;
a = a + b;
b = a - b;
return [a,b];
}
罗马数字转换成整数¶
// https://leetcode.com/problems/roman-to-integer/description/
// https://en.wikipedia.org/wiki/Roman_numerals
// example "DCXXI" => 621
module.exports = function (s) {
const romanLetters = {
'M': 1000,
'CM': 900,
'D': 500,
'CD': 400,
'C': 100,
'XC': 90,
'L': 50,
'XL': 40,
'X': 10,
'IX': 9,
'V': 5,
'IV': 4,
'I': 1,
};
const arr = s.split('');
let index = 0;
let num = 0
let key = ''
for (let i = 0; i<arr.length; i++) {
const key = arr[i]
if(key !== 'V' || key !== 'M') {
if(romanLetters[key + arr[i+1]]) {
num += romanLetters[key + arr[i+1]]
i += 1
continue
}
}
num += romanLetters[key]
}
return num
}
反转整数¶
// https://leetcode.com/problems/reverse-integer/description/
/**
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:Input: 123 Output: 321
Example 2:Input: -123 Output: -321
*/
const reverseInteger = function (num) {
let isNegative = false;
if (Math.abs(num) !== num) {
isNegative = true;
}
// 可以先取绝对值，然后转换成字符串，就不需要replace了
let numstr = num + '';
numstr = numstr.replace('-', '');
const arr = numstr.split('');
arr.reverse();
const result = 0 + arr.join('') * (isNegative ? -1 : 1)
if (result >= (Math.pow(2, 31) - 1) || result <= -Math.pow(2, 31)) {
return 0;
}
return result;
};
判断回文数字¶
// https://leetcode.com/problems/palindrome-number/description/
// examples:123 false 121 true
module.exports = function (x) {
if (x < 0) {
return false;
}
var m = x;
var n = 0;
while(m > 0) {
n = (m % 10 + n * 10)
m = Math.floor(m / 10)
}
return n === x
}
背包问题¶
/**
* knapsack https://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98
* 背包问题
**/
function knapsack(capacity, size, value, n) {
var K = [];
for (let i = 0; i <= n; i++) {
K[i] = [];
}
for (let j = 0; j <= n; j++) {
for(let w=0;w<=capacity;w++) {
if(j==0 || w==0) {
K[j][w] = 0;
}else if(size[j-1] <= w) {
K[j][w] = Math.max(value[j-1] + K[j-1][w-size[j-1]],K[j-1][w]);
}else {
K[j][w] = K[j-1][w];
}
}
}
return K[n][capacity];
}
最长连续元素¶
/** find the max value in an consistant element in an array
* input: [1,1,2,4,-5,12,-3,1]
* output: 15
**/
function findMaxConsitantElement(a) {
let max = 0;
let t = [];
for(var i = 0;i<a.length;i++) {
t[i] = [];
t[i][0] = a[i];
if(t[i][0]>max) {
max = t[i][0];
}
for(var j = i+1;j<a.length;j++) {
t[i][j] = t[i][j-1] + a[j];
if(t[i][j]>max) {
max = t[i][j];
}
}
}
return max;
}
棋盘算法¶
/**
假设我们现在有一个 3 x 3 的井字棋游戏，我们用一个二维数组代表棋盘，’x’ 代表玩家 X 下的棋子，’o’ 代表玩家 O 下的棋子，’e’ 代表该格没有棋子。例如：
一个空白的棋盘以下面的二维数组表示
[ [‘e’, ‘e’, ‘e’],
[‘e’, ‘e’, ‘e’],
[‘e’, ‘e’, ‘e’] ]
如果玩家 X 在第一行第一列下了一步棋，玩家 O 在第二行第二列下了一步棋，则表示如下：
[ [‘x’, ‘e’, ‘e’],
[‘e’, ‘o’, ‘e’],
[‘e’, ‘e’, ‘e’] ]
现在需要一个 function，接受一个已有任意棋子的棋盘（和上面二维数组一样的格式），和玩家的标志（’x’ 或 ‘o'），返回该玩家下一步有几种可能的获胜方式（获胜方式以数组表示，[0, 0] 代表在第一行第一列下一步棋即可获胜，[2, 2] 代表在第三行第三列下一步棋即可获胜）。例如：
someFunction(
‘x’,
[ [‘o’, ‘e’, ‘e’],
[‘o’, ‘x’, ‘o’],
[‘x’, ‘x’, ‘e’] ]
)
// return [ [2, 2], [0, 1], [0, 2] ]
someFunction(
‘x’,
[ [‘x’, ‘o’, ‘o’],
[‘x’, ‘x’, ‘e’],
[‘e’, ‘o’, ‘e’] ]
)
// return [ [2, 2], [1, 2], [2, 0] ]
someFunction(
‘x’,
[ [‘x’, ‘x’, ‘o’],
[‘e’, ‘e’, ‘e’],
[‘e’, ‘e’, ‘e’] ]
)
// return [ ]
someFunction(
‘o’,
[ [‘o’, ‘o’, ‘o’],
[‘e’, ‘e’, ‘e’],
[‘e’, ‘e’, ‘e’] ]
)
return [ ]
*/
// find 'e' to check the empty coordinates
const findE = function (arr) {
const eCoor = [];
arr.forEach((row, i) => {
row.forEach((val, j) => {
if (val === 'e') {
eCoor.push([i, j])
}
});
})
return eCoor;
}
const checkVictory = function(x, y, role, arr, degree) {
arr[x][y] = role;
let result = false;
if (degree === 0) {
result = arr[x][0] === role && arr[x][1] === role && arr[x][2] === role;
} else if (degree === 90) {
result = arr[0][y] === role && arr[1][y] === role && arr[2][y] === role;
} else if (degree === 45) {
result = arr[0][0] === role && arr[1][1] === role && arr[2][2] === role;
} else if (degree === -45) {
result = arr[0][2] === role && arr[1][1] === role && arr[2][0] === role;
}
arr[x][y] = 'e';
return result;
}
// check if win to select the coordinate
const queryVictory = function (role, coors, arr) {
const victoryResults = [];
coors.forEach((item) => {
var x = item[0];
var y = item[1];
[-45, 0, 45, 90].forEach((degree) => {
if (checkVictory(x, y, role, arr, degree)) {
return victoryResults.push([x, y]);
}
})
});
return victoryResults;
}
module.exports = function getResult(role, arr) {
const result = [];
const eCoor = findE(arr);
if (eCoor.length === 0) {
return [];
}
return queryVictory(role, eCoor, arr);
}
斐波那契算法¶
canvas 画布
var canvas = document.querySelector('canvas');
canvas.width = 600;
canvas.height = 480;
var coor = {
x: 300,
y: 240,
};
var ctx = canvas.getContext('2d');
function draw(r, n ,prevR) {
if(n>2) {
switch(n%4) {
case 0 :
coor.y = coor.y - 5 * prevR;
coor.y = coor.y + 5 * r;
break;
case 1 :
coor.x = coor.x + 5 * prevR;
coor.x = coor.x - 5 * r;
break;
case 2 :
coor.y = coor.y + 5 * prevR;
coor.y = coor.y - 5 * r;
break;
case 3 :
coor.x = coor.x - 5 * prevR;
coor.x = coor.x + 5 * r;
break;
}
}
ctx.beginPath();
ctx.arc(coor.x,coor.y,5*r,Math.PI*0.5*(n),Math.PI*0.5*(n-1),true);
if(n>1) {
switch(n%4) {
case 0 :
ctx.moveTo(coor.x - 5*r,coor.y);
break;
case 1 :
ctx.moveTo(coor.x,coor.y + 5*r);
break;
case 2 :
ctx.moveTo(coor.x + 5*r,coor.y);
break;
case 3 :
ctx.moveTo(coor.x,coor.y-5*r);
break;
}
}
ctx.lineWidth = 1;
ctx.strokeStyle = '#fff';
ctx.stroke();
}
function getFibonacci(n) {
var fibarr = [];
var i = 0;
while(i<n) {
if(i<=1) {
fibarr.push(i);
}else{
fibarr.push(fibarr[i-1] + fibarr[i-2])
}
i++;
}
return fibarr;
}
var data = getFibonacci(10);
for(var i = 0,l=data.length;i<l;i++) {
if(data[i]!=0) {
draw(data[i],i,data[i-1]);
}
}
哈希表算法¶
两数之和¶
https://leetcode.com/problems/two-sum/description/
function twoSum(nums, target) {
const arr = nums;
const keyMap = {};
for (let i = 0, len = arr.length; i < len; i++) {
if (typeof keyMap[target - arr[i]] !== 'undefined') {
return [keyMap[target - arr[i]], i]
}
keyMap[arr[i]] = i;
}
return [i, j];
};
Last update:
November 23, 2021