耶温笔记

外观

此页内容

『202408』每日积累

耶温

3312字约11分钟

2024-08-22

每日积累-每天一道题

千里之行，始于足下

每日学习一点，碎片化学习（算法或者面试题），记录下来，方便查阅。

注意点：

  • 学习自己不熟悉或者不熟练的知识点
  • 学习别人的优秀代码

『22』『算法』『两数之和』

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

我的思路：

  • 遍历数组，查看当前数组是否存在 target - nums[i] 的值
  • 如果存在，返回下标
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    // 循环遍历数组
    for (let i = 0; i < nums.length; i++) {
        // 查看是否存在 target - nums[i] 的值
        let num = target - nums[i]
        // 这里需要注意 i+1 是因为 i 之前的已经遍历过了
        if (nums.includes(num,i+1)) {
            // 这里需要注意 nums.includes(num,i+1) 是因为 nums 可能存在重复的元素
            return [i, nums.indexOf(num, i + 1)]
        }
    }
    // 如果没有找到，返回空数组
    return []
};

最快解法：

const twoSum = (nums, target) => {
    //创建一个对象 存储出现过的数字，和对应的索引
    const prevNums = {};
    for (let i = 0; i < nums.length; i++) {
        // 储存当前项      
        const curNum = nums[i];
        // 获取目标差值 target - nums[i]                 
        const targetNum = target - curNum;
        // 在prevNums中获取目标的索引        
        const targetNumIndex = prevNums[targetNum]; // 使用对象的方式储存，获取值会更快
        // 如果存在，直接返回 [目标元素的索引,当前索引]      
        if (targetNumIndex !== undefined) {
            return [targetNumIndex, i];
        } else {
            // 如果不存在，说明之前没出现过目标元素  
            // 存入当前的元素和对应的索引                      
            prevNums[curNum] = i;
        }
    }
}
//   作者：笨猪爆破组
//   链接：https://leetcode.cn/problems/two-sum/solutions/301539/qing-xi-de-bian-liang-ming-ming-bang-zhu-ji-yi-bu-/
//   来源：力扣（LeetCode）
//   著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

『23』『面试』『0.1 + 0.2』

浮点数：在 JavaScript 中，浮点数是通过 Number 类型来表示的。JavaScript 使用 IEEE 754 标准的双精度浮点数格式，这意味着它可以表示非常大的数和非常小的数，但在进行浮点数运算时可能会遇到精度问题。

  1. 浮点数表示范围
// 表示可以安全使用的整数范围。
console.log(Number.MAX_SAFE_INTEGER)
console.log(Number.MIN_SAFE_INTEGER)

// 表示最大值和最小值
console.log(Number.MAX_VALUE) // 1.7976931348623157e+308
console.log(Number.MIN_VALUE) // 5e-324
  1. 浮点数的精度问题
console.log(0.1 + 0.2)  // 输出 0.30000000000000004

解决方案：

  • 可以使用toFixed()方法格式化浮点数。需要注意的是toFixed()方法会四舍五入，所以可能会有精度问题。而且转换之后是字符串类型。需要在需要时再转换为数字类型。
let a = 0.1 + 0.2
console.log(a.toFixed(1))  // 输出 '0.3'
a = parseFloat(a.toFixed(1)) 
console.log(a) // 输出 0.3
  • 再进行计算时，可以将浮点数转换为整数进行计算，然后再转换回浮点数。
let a = 0.1;
let b = 0.2;
let sum = (a * 10 + b * 10) / 10; // 先乘以 10 再除以 10
console.log(sum); // 输出 0.3
  1. 浮点数计算封装方法

我们可以封装一个浮点数计算的方法，将浮点数转换为整数进行计算，然后再转换回浮点数。

    (function (global) {

        // 获取小数位数
        function getDecimalLength(num) {
            const str = num.toString();
            const dotIndex = str.indexOf('.');
            return dotIndex === -1 ? 0 : str.length - dotIndex - 1;
        }

        // 获取 所乘数
        function getFactor(a, b) {
            const factorA = getDecimalLength(a);
            const factorB = getDecimalLength(b);
            return Math.pow(10, Math.max(factorA, factorB));
        }

        const FloatMath = {
            add: function (a, b) {
                const factor = getFactor(a, b)
                return (a * factor + b * factor) / factor;
            },

            subtract: function (a, b) {
                const factor = getFactor(a, b)
                return (a * factor - b * factor) / factor;
            },

            multiply: function (a, b) {
                const factor = getFactor(a, b)
                return (a * factor) * (b * factor) / (factor * factor);
            },

            divide: function (a, b) {
                const factor = getFactor(a, b)
                return (a * factor) / (b * factor);
            },
        };

        // 将插件暴露到全局对象
        global.FloatMath = FloatMath;

    })(this);

测试使用

    console.log(FloatMath.add(0.1, 0.2)); // 0.3
    console.log(FloatMath.add(1, 0.2)); // 1.2
    console.log(FloatMath.add(1, 0.233333)); // 1.233333
    console.log(FloatMath.add(0.1, 0.222));// 0.322
    console.log(FloatMath.subtract(0.3, 0.111));// 0.189
    console.log(FloatMath.subtract(0.3, 2));// -1.7
    console.log(FloatMath.multiply(0.1, 0.2));// 0.02
    console.log(FloatMath.multiply(0.1, 10));// 1
    console.log(FloatMath.multiply(0.5, 0.8));// 0.4
    console.log(FloatMath.divide(0.3, 1));// 0.3
    console.log(FloatMath.divide(0.1, 0.31));// 0.3225806451612903
    console.log(FloatMath.divide(100, 1.1)); // 90.9090909090909

『24』『算法』『两数相加』

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

eg：输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8]

我的思路：

  • 遍历链表，每一项相加
  • 相加结果大于10，进位
// 定义链表节点 JS本身没有提供链表的相关方法，需要自己实现
class ListNode {
    constructor(val) {
        this.val = val;        // 节点的值
        this.next = null;   // 指向下一个节点的引用，初始为 null
    }
}
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    let head = new ListNode(0); // 创建一个虚拟头节点
    let current = head; // 当前节点指针
    let carry = 0;  // 进位
    while (l1 || l2 || carry) { // 遍历两个链表 需要注意 当l1 l2 都为空时 也需要判断carry是否为0
        let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry; // 计算当前节点的值
        carry = Math.floor(sum / 10); // 计算进位
        current.next = new ListNode(sum % 10);  // 创建新节点
        current = current.next; // 移动指针
        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }
    return head.next;
};

需要注意的是，在本地测试时，需要自己创建链表测试。

const l1 = new ListNode(2);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);

const l2 = new ListNode(5);
l2.next = new ListNode(6);
l2.next.next = new ListNode(4);

console.log(addTwoNumbers(l1, l2))

『25』『代码』『一次性函数』

实现可以处理带参数的函数，并且在第一次调用时会执行函数，后续调用将返回第一次调用的结果。

定义一个一次性函数插件。

(function (global) {
    // 一次性函数插件
    function once(fn) {
        let executed = false; // 标记函数是否已执行
        let result; // 存储函数的返回值

        return function (...args) {
            if (!executed) {
                executed = true; // 设置标记为已执行
                result = fn.apply(this, args); // 执行函数并保存结果
            }
            return result; // 返回函数的结果
        };
    }

    // 将插件暴露到全局对象
    if (typeof module === 'object' && typeof module.exports === 'object') {
        // CommonJS 支持
        module.exports = once;
    } else {
        // 浏览器环境
        global.once = once;
    }
})(this);

引入使用。

<script src="./index.js"></script>
<script> 
const sayHello = once(function(name) {
    console.log(`Hello, ${name}!`);
    return `Hello, ${name}!`;
});
sayHello('Alice'); // 输出: Hello, Alice!
sayHello('Bob');   // 不会输出任何内容
</script>

『26』『算法』『无重复字符的最长子串』

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。 eg:输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

我的解法:

var lengthOfLongestSubstring = function (s) {
    let str = '', num = 0; // str为当前无重复字符的子串，num为最长子串的长度
    for (let i = 0; i < s.length; i++) { // 遍历字符串
        let index = str.indexOf(s[i]); // 判断当前字符是否在子串中
        if (index !== -1) str = str.slice(index + 1); // 如果在子串中，则截取子串中该字符后面的部分
        str += s[i]; // 将当前字符添加到子串中
        num = str.length >= num ? str.length : num; // 更新最长子串的长度
    }
    return num;
};

『27』『算法』『寻找两个正序数组的中位数』

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

我的解法：

var findMedianSortedArrays = function (nums1, nums2) {
    var arr = nums1.concat(nums2); // 合并两个数组 
    arr.sort((a, b) => a - b); // 对数组进行排序
    var len = arr.length; // 获取数组的长度
    if (len % 2 === 0) { // 如果数组长度为偶数
        return (arr[len / 2] + arr[len / 2 - 1]) / 2;// 返回中间两个数的平均值
    } else { // 如果数组长度为奇数
        return arr[(len - 1) / 2]; // 返回中间的数
    }
};

二分法查找：

var findMedianSortedArrays = function (nums1, nums2) {
    // 确保 nums1 是较短的数组
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1]
    }

    // 获取数组的长度
    let m = nums1.length
    let n = nums2.length

    // 定义中位数的位置
    let medianIndex = Math.floor((m + n + 1) / 2)

    // 定义左右指针
    let left = 0
    let right = m 

    while (left <= right){ // 二分查找
        // 计算 num1 中间位置
        let midnum1 = Math.floor((left + right) / 2)
        // 计算 num2 中间位置 根据中位数的位置计算 num2 中间位置
        // 中位数的位置 = (m+n+1)/2
        let midnum2 = medianIndex - midnum1

        // 定义num1 和 num2 中间 左右边界数据
        let left1 = midnum1 === 0? -Infinity : nums1[midnum1 - 1]
        let right1 = midnum1 === m? Infinity : nums1[midnum1]
        let left2 = midnum2 === 0? -Infinity : nums2[midnum2 - 1]
        let right2 = midnum2 === n? Infinity : nums2[midnum2]   
        // 比较 num1 和 num2 中间 左右边界数据
        // 根据比较结果 移动左右指针 继续二分查找 或者 返回中位数
        if(left1 > right2){ 
            // num1 中间位置的左边数据大于 num2 中间位置的右边数据
            // 说明 num1 中间位置的左边数据过大 移动右指针
            right = midnum1 - 1
        }else if(left2 > right1){ 
            // num1 中间位置的右边数据小于 num2 中间位置的左边数据
            // 说明 num1 中间位置的右边数据过小 移动左指针
            left = midnum1 + 1
        }else{ 
            // num1 和 num2 中间 左右边界数据符合要求
            // 计算中位数
            if((m + n) % 2 === 1){
                // 如果是奇数个 中位数就是 num1 和 num2 中间 左边界数据中较大的那个
                return Math.max(left1, left2)
            }else{ 
                // 如果是偶数个 中位数就是 左边界的最大值和右边界的最小值 的平均值
                return (Math.max(left1, left2) + Math.min(right1, right2)) / 2
            }
        }
    }
}

『28』『算法』『二分法查找』

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

var findTargetIndexArrays = function (nums, target) {
    let right = nums.length - 1 // 右指针
    let left = 0 // 左指针
    while (left <= right) { // 左指针小于右指针
        let mid = Math.floor((right + left) / 2) // 中间指针
        if (nums[mid] == target) { // 找到目标
            return mid
        } else if (nums[mid] > target) { // 目标在左半部分
            right = mid - 1 // 右指针移动到中间指针左边
        } else {
            left = mid + 1 // 左指针移动到中间指针右边
        }
    }
    return -1
}

『29』『面试』『ESM与CommonJS模块』

ESM和CommonJS是两种不同的模块化规范，它们之间的主要区别在于它们如何处理模块的导入和导出。

CommonJS是Node.js的模块化规范，它使用require和module.exports来导入和导出模块。CommonJS模块是同步加载的，这意味着它们在执行时会阻塞代码的执行，直到模块加载完成。

ESM是ECMAScript 6引入的模块化规范，它使用import和export来导入和导出模块。ESM模块是异步加载的，这意味着它们不会阻塞代码的执行，可以在模块加载完成之前继续执行其他代码。

提示

关于 ESM 与 CommonJS 模块的详细内容可以查看：JavaScript-ESM与CommonJS）

『30』『面试』『事件循环机制（Event Loop）』

事件循环（Event Loop）是 JavaScript 中处理异步操作的核心机制。它使得 JavaScript 能够在单线程环境中执行非阻塞的代码，处理事件和执行回调函数。

提示

关于 Event Loop 的详细内容可以查看：JavaScript-Event Loop）

『31』『算法』『最长回文子串』

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。

输入：s = "cbbd" 输出："bb" 思路：

  • 回文子串：正着读和反着读都一样的字符串
  • 回文子串的长度可能是奇数也可能是偶数
  • 如果是奇数回文子串，那么中间的字符一定在字符串中，我们只需要找到中间的字符，然后向两边扩散，判断是否相等
  • 如果是偶数回文子串，那么中间的两个字符一定在字符串中，我们只需要找到中间的两个字符，然后向两边扩散，判断是否相等

我的解法：

var longestPalindrome = function (s) {
    let maxStr = s[0] // 最长回文子串 默认值
    for (let i = 0; i < s.length; i++) {
        // 奇数回文子串
        isPlaindrome(i, i + 1) 
        isPlaindrome(i, i)  
    }
    function isPlaindrome(l, r) {
        // 回文子串
        while (s[l] === s[r] && l >= 0 && r < s.length) { 
            l-- // 左指针
            r++ // 右指针
        }
        
        let str = s.slice(l + 1, r) // 截取子串
        if (str.length > maxStr.length) { // 判断是否是最大回文子串
            maxStr = str
        }
    }
    return maxStr
};