今回は、JS の一般的な数学アルゴリズムについてまとめました。JS の数学アルゴリズムを使用する際の注意点は何ですか?実際の事例を見てみましょう。
素数
Q: 素数はどのように検証しますか?
A: 素数はそれ自体と 1 でのみ割り切れます。そこで、while ループを実行して 1 を追加します。 (コード例を見てください。理解できない場合は、あなたの仕事ではありません。最初に戻って JavaScript の基本を学び、それから戻ってきてください。)
方法 1
function isPrime(n){
var pisor = 2;
while (n > pisor){
if(n % pisor == 0){
return false;
}
else
pisor++;
}
return true;
}
isPrime(137); // = true
isPrime(237); // = falseQ: もっと上手にできますか? ?
A: はい。約数は 1 ずつ増加します。 3 の後に 2 を足すことができます。数値が偶数で割り切れる場合は、2 で割り切れます。
追加: この数まで除数を増やす必要がない場合。早めにやめることもできます。以下の手順で説明しましょう (必要に応じて、さらに数回読んでください)
ステップ 1、半分より大きい数で割り切れる数字はありません。 たとえば、13 は 7、8、9 で割り切れることはありません...偶数の半分になることもあります。 たとえば、16 は 8 で割り切れますが、9、10、11、12 では割り切れません...
結論: 数値は、その値の半分より大きい数値で割り切れることはありません。 したがって、ループを 50% 減らすことができます。
ステップ 2、数値が 3 で割り切れない場合。 (3 で割り切れる場合は、素数ではありません)。したがって、その値の 1/3 を超える数では割り切れません。たとえば、35 は 3 で割り切れません。したがって、35/3 より大きい数で割り切れることはなく、12、13、14 で割り切れることもありません...36 のような偶数を取得する場合、13、14、15 で割り切れることはありません。
結論: 数値はその値の 3 分の 1 で割り切れます。
ステップ 3 たとえば、数値 127 があるとします。127 は 2 で割り切れないため、最大 63.5 を確認する必要があります。次に、127 は 3 で割り切れません。したがって、127/3 約 42 にチェックを入れることになります。これは 5 で割り切れません。約数は 7 ではなく、約 25 である 127/5 未満である必要があります。それで、どこに立ち寄ればいいでしょうか？
結論: 約数は math.sqrt(N) より小さくなります
方法 2
理解できなくても心配しないで、放っておいてください。研究者でなくても大丈夫です。
function isPrime(n)
{
var pisor = 3,
limit = Math.sqrt(n);
//check simple cases
if (n == 2 || n == 3)
return true;
if (n % 2 == 0)
return false;
while (pisor <= limit)
{
if (n % pisor == 0)
return false;
else
pisor += 2;
}
return true;
}
isPrime(137); // = true
isPrime(237); // = false素因数
Q: 数値のすべての素因数を見つけるにはどうすればよいですか?
A: while ループを実行します。 2で除算を開始します。除算できない場合は、完了するまで除数を記録します。
function primeFactors(n){
var factors = [],
pisor = 2;
while(n>2){
if(n % pisor == 0){
factors.push(pisor);
n= n/ pisor;
}
else{
pisor++;
}
}
return factors;
}
primeFactors(69); // = [3, 23]Q: 実行時間の複雑さはどれくらいですか? もっと上手くできるでしょうか？
A: O(n)。約数は 3 から始めて、最大 2 まで足すことができます。なぜなら、偶数で割り切れる数値は 2 で割り切れるからです。したがって、偶数で割る必要はありません。さらに、その値の半分より大きい係数は存在しません。複雑にしたい場合は、質問 1 の補足的な概念を使用してください。
Fibonacci (フィボナッチ)
Q: n番目のフィボナッチ数を取得するにはどうすればよいですか?
A: 配列を作成し、反復処理から始めます。
フィボナッチ数列は、初心者にとって最も人気のある面接の質問の 1 つです。 したがって、これを学ばなければなりません。
方法 1
function fibonacci(n){
var fibo = [0, 1];
if (n <= 2) return 1;
for (var i = 2; i <=n; i++ ){
fibo[i] = fibo[i-1]+fibo[i-2];
}
return fibo[n];
}
fibonacci(12); // = 144Q: 実行時間の複雑さはどれくらいですか?
A: O(n);
Q: 再帰的にできますか?
方法 2
function fibonacci(n){
if(n < =1) {
return n;
} else {
return fibonacci(n-1) + fibonacci (n-2);
}
}
fibonacci(12); // = 144Q: 実行時間の複雑さはどれくらいですか?
A: O(2n); 時間計算量の詳細
最大公約数
Q: 2 つの数値の最大公約数はどうやって見つけますか?
function greatestCommonpisor(a, b){
var pisor = 2,
greatestpisor = 1;
//if u pass a -ve number this will not work. fix it dude!!
if (a < 2 || b < 2)
return 1;
while(a >= pisor && b >= pisor){
if(a %pisor == 0 && b% pisor ==0){
greatestpisor = pisor;
}
pisor++;
}
return greatestpisor;
}
greatestCommonpisor(14, 21); // 7
greatestCommonpisor(69, 169); // = 1アルゴリズムパラダイム
ごめんなさい。私にも説明できません。 なぜなら、私自身も8割理解できないからです。 私のアルゴリズム分析コーチがこれを教えてくれて、授業ノートから盗みました (ちなみに私は優秀な生徒でした!)
function greatestCommonpisor(a, b){
if(b == 0)
return a;
else
return greatestCommonpisor(b, a%b);
}注: これを理解するには頭を使ってください。
体重を減らす
Q：你将如何从数组中删除重复的成员？
A： 执行一个循环，并保存一个对象/关联数组。如果我第一次找到一个元素，我会设置它的值为真（这将告诉我元素添加一次）。如果我在对象中找到这个元素，我不会将它插入到返回数组中。
function removeDuplicate(arr){
var exists ={},
outArr = [],
elm;
for(var i =0; i<arr.length; i++){
elm = arr[i];
if(!exists[elm]){
outArr.push(elm);
exists[elm] = true;
}
}
return outArr;
}
removeDuplicate([1,3,3,3,1,5,6,7,8,1]); // = [1, 3, 5, 6, 7, 8]合并两个排序的数组
Q： 怎样合并两个已排序数组？
A： 我将为每个数组保留一个指针（看代码，并注意这个）。
function mergeSortedArray(a, b){
var merged = [],
aElm = a[0],
bElm = b[0],
i = 1,
j = 1;
if(a.length ==0)
return b;
if(b.length ==0)
return a;
/*
if aElm or bElm exists we will insert to merged array
(will go inside while loop)
to insert: aElm exists and bElm doesn't exists
or both exists and aElm < bElm
this is the critical part of the example
*/
while(aElm || bElm){
if((aElm && !bElm) || aElm < bElm){
merged.push(aElm);
aElm = a[i++];
}
else {
merged.push(bElm);
bElm = b[j++];
}
}
return merged;
}
mergeSortedArray([2,5,6,9], [1,2,3,29]);// = [1, 2, 2, 3, 5, 6, 9, 29]不通过临时变量交换两个数的值
Q：如何在不使用临时变量的情况下交换两个数字？
function swapNumb(a, b){
console.log('before swap: ','a: ', a, 'b: ', b);
b = b -a;
a = a+ b;
b = a-b;
console.log('after swap: ','a: ', a, 'b: ', b);
}
swapNumb(2, 3);
// = before swap: a: 2 b: 3
// = after swap: a: 3 b: 2位操作：对不起，我无法向你解释这一点。 Kinjal Dave建议到 logical conjunction理解它。将浪费您30分钟。
function swapNumb(a, b){
console.log("a: " + a + " and b: " + b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
console.log("a: " + a + " and b: " + b);
}
swapNumb(2, 3);
// = a: 2 and b: 3
// = a: 3 and b: 2字符串反向
Q：如何在JavaScript中反转字符串？
A：可以遍历字符串并将字母连接到新字符串。
方法1
function reverse(str){
var rtnStr = '';
for(var i = str.length-1; i>=0;i--){
rtnStr +=str[i];
}
return rtnStr;
}
reverse('you are a nice dude');
// = "edud ecin a era uoy"Q：你知道在现代浏览器中串联效果很好，但在像IE8这样的旧浏览器中会变慢。 还有什么不同的方法，可以扭转一个字符串？
A：当然.我可以使用数组，也可以添加一些检查。如果字符串是NULL或其他字符串，这将失败。让我也做一些类型检查。使用此数组类似于在某些服务器端语言中使用字符串缓冲区。
方法2
function reverse(str){
var rtnStr = [];
if(!str || typeof str != 'string' || str.length < 2 ) return str;
for(var i = str.length-1; i>=0;i--){
rtnStr.push(str[i]);
}
return rtnStr.join('');
}Q： 运行时间复杂度是多少？
A： O(n)；
Q：可以做得更好？
A：我可以遍历索引的一半，它会节省一点点。 （这是没用的，可能不会打动面试官）
方法3
function reverse(str) {
str = str.split('');
var len = str.length,
halfIndex = Math.floor(len / 2) - 1,
revStr;
for (var i = 0; i <= halfIndex; i++) {
revStr = str[len - i - 1];
str[len - i - 1] = str[i];
str[i] = revStr;
}
return str.join('');
}Q：这有效，但你可以做递归的方式吗？
A：可以。
方法4
function reverse (str) {
if (str === "") {
return "";
} else {
return reverse(str.substr(1)) + str.charAt(0);
}
}方法5
Q：你可以在方法中使用任何构建，使它更清洁吗？
function reverse(str){
if(!str || str.length <2) return str;
return str.split('').reverse().join('');
}方法6
Q：你可以做反向函数作为字符串扩展吗？
A：我需要将这个函数添加到String.prototype，而不是使用str作为参数，我需要使用this
String.prototype.reverse = function (){
if(!this || this.length <2) return this;
return this.split('').reverse().join('');
}
'abc'.reverse();
// = 'cba'单词反转
Q：你如何在句子中颠倒单词？
A：您必须检查整个字符串的空白区域。确定是否可能有多个空格。
//have a tailing white space
//fix this later
//now i m sleepy
function reverseWords(str){
var rev = [],
wordLen = 0;
for(var i = str.length-1; i>=0; i--){
if(str[i]==' ' || i==0){
rev.push(str.substr(i,wordLen+1));
wordLen = 0;
}
else
wordLen++;
}
return rev.join(' ');
}内置方法的快速解决方案：
function reverseWords(str){
return str.split(' ').reverse();
}原位反转
Q: 如果你有一个字符串如”I am the good boy”， 怎样变为 “I ma eht doog yob”？ 注意这些单词位置不变但是被反转了。
A: 要做到这一点，我必须做字符串反向和字反转。
function reverseInPlace(str){
return str.split(' ').reverse().join(' ').split('').reverse().join('');
}
reverseInPlace('I am the good boy');// = "I ma eht doog yob"Q: ok。好的，你能不使用内置反向函数做到吗？
A: (内心独白)有没有搞错！！
//sum two methods. //you can simply split words by ' ' //and for each words, call reverse function //put reverse in a separate function //if u cant do this, //have a glass of water, and sleep
第一个非重复字符
Q: 怎么在字符串中找到第一个非重复字符？
A: 有什么条件吗？
A: 比如是否区分大小写？
面试官可能会说No。
A: 是长字符串还是短字符串？
Q: 这些有什么关系吗？
A:例如，如果它是一个非常长的字符串，说一百万个字符，我想检查是否有26个英文字符正在重复。 我可能会检查是否所有字符都在每200个字母中重复（例如），而不是循环遍历整个字符串。 这将节省计算时间。
Q: 简单起见， 这个字符串是 “the quick brown fox jumps then quickly blow air”。
function firstNonRepeatChar(str){
var len = str.length,
char,
charCount = {};
for(var i =0; i<len; i++){
char = str[i];
if(charCount[char]){
charCount[char]++;
}
else
charCount[char] = 1;
}
for (var j in charCount){
if (charCount[j]==1)
return j;
}
}
firstNonRepeatChar('the quick brown fox jumps then quickly blow air');// = "f"这有一个问题，不能再循环中及时退出。
删除重复的字符
Q: 怎样删除字符串中的重复字符？
A: 这与第一个非重复字符非常相似。你应该问一些类似的问题。它是区分大小写的吗？。
如果面试官说，这是区分大小写的，那么你就很轻松了。 如果他说不。你可以使用string.toLowercase（）来把字符串。面试官可能不喜欢这个方法。 因为返回字符串不会拥有相同的大小写。 所以
function removeDuplicateChar(str){
var len = str.length,
char,
charCount = {},
newStr = [];
for(var i =0; i<len; i++){
char = str[i];
if(charCount[char]){
charCount[char]++;
}
else
charCount[char] = 1;
}
for (var j in charCount){
if (charCount[j]==1)
newStr.push(j);
}
return newStr.join('');
}
removeDuplicateChar('Learn more javascript dude'); // = "Lnmojvsciptu"回文检查
Q: 如何检查一个字符串是否是回文？
A: 把字符串反转，如果反转前后相等，那么它就是回文。
function isPalindrome(str){
var i, len = str.length;
for(i =0; i<len/2; i++){
if (str[i]!== str[len -1 -i])
return false;
}
return true;
}
isPalindrome('madam')
// = true
isPalindrome('toyota')
// = false或者
function checkPalindrom(str) {
return str == str.split('').reverse().join('');
}类似的：在 O(n)时间复杂度内判断一个字符串是否包含在回文字符串内。你能在O（1）时间解决问题吗？
找缺失的数字
Q: 在一个1到100的未排序数组中找到缺失的数，你怎么做？
说明：数组中的数字为1到100。 数组中只有一个数字缺失。数组未排序。找到缺少的数字。
A: 你必须表现得像是在想很多。然后讨论n＝n（n＋1）／2的线性级数之和
function missingNumber(arr){
var n = arr.length+1,
sum = 0,
expectedSum = n * (n+1)/2;
for(var i = 0, len = arr.length; i < len; i++){
sum += arr[i];
}
return expectedSum - sum;
}
missingNumber([5, 2, 6, 1, 3]);
// = 4注意： 这个会返回任意长度数组中缺失的那个
两数之和
Q: 在一个未排序的数组中找出是否有任意两数之和等于给定的数？
A: 简单！双重循环。
function sumFinder(arr, sum){
var len = arr.length;
for(var i =0; i<len-1; i++){
for(var j = i+1;j<len; j++){
if (arr[i] + arr[j] == sum)
return true;
}
}
return false;
}
sumFinder([6,4,3,2,1,7], 9);
// = true
sumFinder([6,4,3,2,1,7], 2);
// = falseQ: 时间复杂度？
A: O(n2)。
Q: 有更优解？
A: 我想想。我可以用一个对象来存储当前元素和和值的差值。当我拿到一个新元素，如果这个元素的差值在对象中存在，那么我就能判断出是否存在。
function sumFinder(arr, sum){
var differ = {},
len = arr.length,
substract;
for(var i =0; i<len; i++){
substract = sum - arr[i];
if(differ[substract])
return true;
else
differ[arr[i]] = true;
}
return false;
}
sumFinder([6,4,3,2,1,7], 9);
// = true
sumFinder([6,4,3,2,1,7], 2);
// = false最大和
Q: 找到任意两个元素的最大总和？
A: 这实际上非常简单直接。 找到两个最大的数字并返回它们的总和
function topSum(arr){
var biggest = arr[0],
second = arr[1],
len = arr.length,
i = 2;
if (len<2) return null;
if (biggest<second){
biggest = arr[1];
second = arr[0];
}
for(; i<len; i++){
if(arr[i] > biggest){
second = biggest;
biggest = arr[i];
}
else if (arr[i]>second){
second = arr[i];
}
}
return biggest + second;
}统计零
Q: 统计从1到n的零总数？
A: 如果 n = 100，则0的数目将是11（0,10,20,30,40,50,60,70,80,90,100）。 请注意，100有两个0.这个看起来很简单，但有点棘手
说明：所以这里的重点是。 如果你有一个1到50的数字，那么这个数值就是5，就是50除以10.然而，如果这个数值是100，这个数值是11，你将得到100/10 = 10和 10/10 = 1。 那就是你将如何在一个数字中得到更多的零，如（100，200，1000）；
function countZero(n){
var count = 0;
while(n>0){
count += Math.floor(n/10);
n = n/10;
}
return count;
}
countZero(2014);
// = 223子字符串
Q: 在字符串中匹配子字符串？
A: 在迭代字符串时将使用指针（一个用于字符串，另一个用于子字符串）。 然后用另一个变量来保存初始匹配的起始索引。
function subStringFinder(str, subStr){
var idx = 0,
i = 0,
j = 0,
len = str.length,
subLen = subStr.length;
for(; i<len; i++){
if(str[i] == subStr[j])
j++;
else
j = 0;
//check starting point or a match
if(j == 0)
idx = i;
else if (j == subLen)
return idx;
}
return -1;
}
subStringFinder('abbcdabbbbbck', 'ab')
// = 0
subStringFinder('abbcdabbbbbck', 'bck')
// = 9
//doesn't work for this one.
subStringFinder('abbcdabbbbbck', 'bbbck')
// = -1排列
Q: 如何获取字符串中的所有排列？
A: 根据您对算法的了解程度，这可能会很困难。、
function permutations(str){
var arr = str.split(''),
len = arr.length,
perms = [],
rest,
picked,
restPerms,
next;
if (len == 0)
return [str];
for (var i=0; i<len; i++)
{
rest = Object.create(arr);
picked = rest.splice(i, 1);
restPerms = permutations(rest.join(''));
for (var j=0, jLen = restPerms.length; j< jLen; j++)
{
next = picked.concat(restPerms[j]);
perms.push(next.join(''));
}
}
return perms;
}相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！
推荐阅读：
以上がJS の一般的な数学アルゴリズムの概要の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
