Heim > Artikel > Web-Frontend > Detaillierte Erläuterung des Js-Interviewalgorithmus
Detaillierte Erläuterung des Js-Interviewalgorithmus
- 亚连Original
- 2018-05-26 10:03:183632Durchsuche
Der Aufstieg der KI hat dazu geführt, dass jeder den Algorithmen immer mehr Aufmerksamkeit schenkt. Als Front-End-Ingenieur sind Algorithmen oft unsere Schwäche. Dieser Artikel ist eine Übersetzung aus einer ausländischen Interviewfrage. Listet einige Interviewfragen auf, die einfach mit Algorithmen zusammenhängen
Empfohlene verwandte Artikel : Die umfassendste Sammlung von js-Interviewfragen im Jahr 2020 (aktuell)
Primzahlen
F: Wie würden Sie eine Primzahl verifizieren?
A: Eine Primzahl kann nur durch sich selbst und 1 teilbar sein. Also werde ich eine While-Schleife ausführen und 1 hinzufügen. (Schauen Sie sich das Codebeispiel an. Wenn Sie es nicht verstehen können, ist es nicht Ihr Ding. Gehen Sie zurück und lernen Sie zuerst die Grundlagen von JavaScript und kommen Sie dann zurück.)
Methode 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); // = falseF: Können Sie es besser machen?
A: Ja. Der Divisor erhöht sich jeweils um eins. Nach 3 kann ich 2 hinzufügen. Wenn eine Zahl durch eine gerade Zahl teilbar ist, ist sie auch durch 2 teilbar.
Zusätzlich: Wenn Sie den Divisor nicht auf diese Zahl erhöhen müssen. Sie können früher aufhören. Lassen Sie es mich in den folgenden Schritten erklären (Sie können es bei Bedarf ein paar Mal lesen)
Schritt eins: Keine Zahl ist durch eine Zahl teilbar, die größer als die Hälfte ist. Beispielsweise wird 13 niemals durch 7,8,9 teilbar sein ... es kann sogar die Hälfte einer geraden Zahl sein. Zum Beispiel ist 16 durch 8 teilbar, aber niemals durch 9, 10, 11, 12...
Fazit: Eine Zahl wird niemals durch eine Zahl teilbar sein, die größer als die Hälfte ihres Wertes ist. Wir können also 50 % weniger Loopings durchführen.
Der zweite Schritt nun, wenn eine Zahl nicht durch 3 teilbar ist. (Wenn es durch 3 teilbar ist, dann ist es keine Primzahl). Dann ist es durch keine Zahl größer als 1/3 seines Wertes teilbar. Beispielsweise ist 35 nicht durch 3 teilbar. Daher wird sie niemals durch eine Zahl größer als 35/3 teilbar sein, niemals durch 12, 13, 14... Wenn Sie eine gerade Zahl wie 36 nehmen, wird sie niemals durch 13, 14, 15 teilbar sein.
Schlussfolgerung: Eine Zahl ist durch ein Drittel ihres Wertes teilbar.
Schritt 3, zum Beispiel haben Sie eine Zahl 127. 127 ist nicht durch 2 teilbar, daher sollten Sie höchstens 63,5 ankreuzen. Zweitens ist 127 nicht durch 3 teilbar. Sie prüfen also auf 127/3, ungefähr 42. Es ist nicht durch 5 teilbar, der Teiler sollte kleiner als 127/5 sein, also etwa 25, nicht 7. Also, wo hören wir auf?
Schlussfolgerung: Der Divisor wird kleiner sein als math.sqrt(N)
Methode 2
Machen Sie sich keine Sorgen, wenn Sie es nicht verstehen können, einfach lass es in Ruhe. Es spielt keine Rolle, ob Sie kein Forscher sind.
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); // = falsePrimfaktoren
F: Wie finde ich alle Primfaktoren einer Zahl?
A: Führen Sie eine While-Schleife aus. Beginnen Sie mit der Division durch 2. Wenn die Division nicht möglich ist, notieren Sie den Divisor, bis Sie fertig sind.
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]F: Wie hoch ist die Laufzeitkomplexität? Können Sie es besser machen?
A: O(n). Sie können den Divisor bei 3 beginnen und bis 2 addieren. Denn wenn eine Zahl durch eine gerade Zahl teilbar ist, ist sie auch durch 2 teilbar. Daher ist eine Division durch gerade Zahlen nicht erforderlich. Darüber hinaus wird es keinen Faktor geben, der größer als die Hälfte seines Wertes ist. Wenn Sie es komplizierter machen möchten, verwenden Sie die ergänzenden Konzepte aus der ersten Frage.
Fibonacci (Fibonacci)
F: Wie erhalte ich die n-te Fibonacci-Zahl?
A: Ich erstelle ein Array und beginne mit der Iteration.
Die Fibonacci-Reihe ist eine der beliebtesten Interviewfragen für Einsteiger. Das müssen Sie also lernen.
Methode 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); // = 144F: Wie hoch ist die Laufzeitkomplexität?
A: O(n);
F: Können Sie es rekursiv machen?
Methode 2
function fibonacci(n){
if(n < =1) {
return n;
} else {
return fibonacci(n-1) + fibonacci (n-2);
}
}
fibonacci(12); // = 144F: Wie hoch ist die Laufzeitkomplexität?
A: O(2n); Details zur Zeitkomplexität
Größter gemeinsamer Teiler
F: Wie würden Sie zwei Was finden? der größte gemeinsame Teiler von Zahlen?
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); // = 1Algorithmisches Paradigma
Entschuldigung. Ich kann es mir auch nicht erklären. Weil ich es selbst in 80 % der Fälle nicht verstehen kann. Mein Trainer für Algorithmenanalyse hat mir das erzählt und es aus den Unterrichtsnotizen geklaut (ich war übrigens ein guter Schüler!)
function greatestCommonpisor(a, b){
if(b == 0)
return a;
else
return greatestCommonpisor(b, a%b);
}HINWEIS: Benutzen Sie Ihr Gehirn, um es zu verstehen.
Deduplizierung
F: Wie würden Sie doppelte Mitglieder aus einem Array entfernen?
A: Führen Sie eine Schleife aus und speichern Sie ein Objekt/assoziatives Array. Wenn ich ein Element zum ersten Mal finde, setze ich seinen Wert auf „true“ (was mir sagt, dass das Element einmal hinzugefügt wurde). Wenn ich dieses Element im Objekt finde, füge ich es nicht in das Rückgabearray ein.
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]Zwei sortierte Arrays zusammenführen
F: Wie füge ich zwei sortierte Arrays zusammen?
A: Ich werde für jedes Array einen Zeiger behalten (schauen Sie sich den Code an und notieren Sie dies).
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]Werte zweier Zahlen austauschen, ohne temporäre Variablen zu verwenden
F: Wie tausche ich zwei Zahlen aus, ohne temporäre Variablen zu verwenden?
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;
}上面是我整理给大家的，希望今后会对大家有帮助。
相关学习推荐：javascript视频教程
Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung des Js-Interviewalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!