【算法】js算法题

js算法题

---

请实现一个instanceof，让以下代码可正常运行

/**
 自定义instanceof 
*/
function instanceOf(left, right) {
    // 请完善以下代码，不能使用原生instanceof
}

class A{}
class B extends A {}
class C{}

const b = new B()
// 输出 true
console.log(instanceOf(b,B))
// 输出 true
console.log(instanceOf(b,A))
// 输出 false
console.log(instanceOf(b,C))

解析

• 这道题考察的是你对 JavaScript 中 instanceof 运算符的理解和实现能力。instanceof 运算符用于检测对象是否属于某个类或其原型链上的类。

实现思路

• 是检查对象的原型链是否包含目标类的原型。具体来说，你需要检查对象的 proto 属性链，直到找到目标类的原型或到达原型链的末尾（即 proto 为 null）为止。如果找到目标类的原型，则返回 true；否则返回 false。

答案

function instanceOf(left, right) {
    let proto = left.__proto__; // 获取 left 对象的原型
    while (proto) {
        if (proto === right.prototype) {
            return true; // 如果找到目标类的原型，则返回 true
        }
        proto = proto.__proto__; // 继续检查上一级原型
    }
    return false; // 如果遍历完整个原型链都没找到目标类的原型，则返回 false
}

class A {}
class B extends A {}
class C {}

const b = new B();

console.log(instanceOf(b, B)); // 输出 true
console.log(instanceOf(b, A)); // 输出 true
console.log(instanceOf(b, C)); // 输出 false

请模拟实现new操作符，使下面代码正常运行

function myNew(constructor, ...rest) {
 // 请在此处完善代码，不能直接使用 new 操作符
}
function Fun(name,sex) {
  this.name = name
  this.sex = sex
}
Fun.prototype.getUserInfo = function() {
  return `我的姓名${this.name},我的性别${this.sex}`
}

const fun = myNew(Fun,'子君','男')
// 我的姓名子君，我的性别男
console.log(fun.getUserInfo())

解析

• 这道题考察的是对 JavaScript 中构造函数、原型链以及 new 操作符的理解和掌握程度。

四线思路

• 创建一个空对象 obj，这个对象将成为构造函数调用时的 this。
• 将 obj 的原型链指向构造函数的原型对象，以便实现继承构造函数原型上的属性和方法。
• 使用 apply 或者 call 方法调用构造函数，将 this 设置为新创建的 obj，并传入参数。
• 判断构造函数是否返回了一个对象，如果是，则直接返回该对象。
• 如果构造函数没有返回对象，则返回新创建的 obj 对象。

答案

function myNew(constructor, ...args) {
  var obj = {};
  obj.__proto__ = constructor.prototype;
  var result = constructor.apply(obj, args);
  if (typeof result === "object" && result !== null) {
    return result;
  }
  return obj;
}
function Fun(name, sex) {
  this.name = name;
  this.sex = sex;
}
Fun.prototype.getUserInfo = function () {
  return `我的姓名${this.name},我的性别${this.sex}`;
};

const fun = myNew(Fun, "子君", "男");
// 我的姓名子君，我的性别男
console.log(fun.getUserInfo());

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。例如，输入abcabcbb，那么无重复字符的最长子串是 abc，长度为 3。

解析

这道题考察的是编程中的问题解决能力和算法思维。

实现思路

• 使用两个指针 left 和 right 分别表示滑动窗口的左右边界，初始时都指向字符串的开头（索引为 0）。
• 使用一个哈希表来存储字符在当前窗口中的位置，键为字符，值为该字符在字符串中的索引位置。
• 遍历字符串，每次移动右指针 right，直到遇到重复字符为止。
• 更新窗口的最大长度，并将遇到重复字符的位置更新为窗口的左边界 left。
• 重复步骤 3 和步骤 4，直到遍历完整个字符串。
• 最后返回窗口的最大长度。

答案

function lengthOfLongestSubstring(s) {
    const n = s.length; // 获取字符串的长度
    let maxLen = 0; // 初始化最长子串长度为0
    let left = 0; // 初始化滑动窗口的左边界为0
    const charIndexMap = {}; // 创建一个哈希表用于存储字符在当前窗口中的位置

    for (let right = 0; right < n; right++) { // 遍历字符串
        const char = s[right]; // 获取当前字符
        if (charIndexMap[char] !== undefined && charIndexMap[char] >= left) { // 如果当前字符在哈希表中存在且在当前窗口范围内
            left = charIndexMap[char] + 1; // 更新左边界为当前字符在哈希表中上次出现位置的下一个位置
        }
        charIndexMap[char] = right; // 更新当前字符在哈希表中的位置为当前右指针的位置
        maxLen = Math.max(maxLen, right - left + 1); // 更新最长子串长度
    }

    return maxLen; // 返回最长子串长度
}

const str = "abcabcbb"; // 测试用例
console.log(lengthOfLongestSubstring(str)); // 输出: 3