Hi! Have a good day!
0%

发表于

第一节

Q：

  1. 能否简要介绍一下你对HTML的了解？
  2. 你如何理解HTML5和过去版本的差异？
  3. 你有没有使用过语义化标记？它们的好处是什么？
  4. 对CSS有哪些基本的理解？如何添加样式到元素中？
  5. CSS选择器有哪些？你如何使用它们？
  6. 如何使页面布局响应式？
  7. 你有没有使用过CSS预处理器，如SASS或LESS？它们的好处是什么？
  8. 你如何优化网页性能？
  9. 如何处理跨浏览器兼容性问题？
  10. 你了解前端框架，如React或Angular吗？

A:

  1. HTML是一种标记语言，用于描述网页的结构和内容。它基本上由标签、属性和文本组成，可以用于创建网页中的文本、图像、链接、表格等内容。
  2. HTML5是HTML的最新版本，与之前的版本相比，它引入了许多新的标签和API，如header、footer、nav、video、audio等，同时还支持本地存储、绘图、拖放、多媒体等功能。HTML5不再需要像以前那样基于浏览器插件实现一些复杂的功能，使得网页开发更加便捷和高效。
  3. 语义化标记是指使用有意义的标签来描述网页中的文本内容。与无意义的标签相比，语义化标记能够为搜索引擎、屏幕阅读器等设备提供更加准确的信息，也可以为开发者提供更加易于理解和维护的代码。如使用

    标签表示页面主标题，

    标签表示段落等。

  4. CSS是一种用于描述网页呈现效果的样式表语言。它基本上由选择器和声明块组成，选择器用于选中需要样式化的元素，声明块用于定义这些元素的样式。
  5. CSS选择器有许多种，如元素选择器、类选择器、ID选择器、后代选择器、伪元素等。通过这些选择器可以选中页面中的元素，然后添加样式，如background-color、font-size等的样式。
  6. 响应式布局是指通过CSS中的媒体查询等技术，使得网页可以在各种设备上（如桌面电脑、平板电脑、手机等）自动适应不同的屏幕大小和设备类型。通常可以采用弹性布局、栅格系统等方式实现。
  7. CSS预处理器如SASS或LESS可以增强CSS的编写能力，包括使用变量、函数、嵌套规则、继承等特性，使得CSS代码更具可读性和可维护性。它们还支持模块化开发和自动化构建等功能，可以提高开发效率和代码质量。
  8. 优化网页性能可以从许多方面入手，如减少HTTP请求、压缩和缩小CSS、JavaScript和图片等资源，使用浏览器缓存、使用CDN等。此外，还可以优化DOM结构、减少JavaScript操作、使用异步加载等方式提高页面加载速度。
  9. 跨浏览器兼容性问题通常可以通过检测浏览器的支持情况，使用浏览器前缀、polyfill等技术来解决。可以使用工具如caniuse.com来查看不同浏览器的支持情况。使用现代的编译工具如webpack可以自动处理浏览器兼容性问题。
  10. 前端框架如React和Angular都是用于构建复杂的web应用程序的工具。它们提供了许多有用的特性和API，如组件化、状态管理、路由、数据绑定等。同时还支持开发工具和社区生态的支持，可以大大提高开发效率和质量。

第二节

Q：

  1. 您在开发中如何管理和组织您的CSS代码？
  2. 过渡效果和动画效果有什么本质上的区别，您是如何设置它们的？
  3. 您有没有使用过响应式开发框架，如Bootstrap？它们的好处是什么？
  4. 你的JavaScript基础如何？你如何处理异步代码？
  5. 知道什么是闭包吗？您可以举个例子吗？

A：

  1. 在CSS开发中，我通常使用一些方法来组织和管理代码，如BEM命名规范、模块化思想、嵌套规则等。BEM命名规范可以帮助我为各个组件分配独特的名称，使用BEM范例，该组件中的样式只会影响该组件，这样可以减少冲突并提高可维护性。另外，使用模块化可以将代码分解成单个或包含多个相关样式的小模块，每个单独编写并测试，更好地控制代码质量。最后，我通常尽量避免使用全局选择器和!important标志，以降低代码复杂度和扩展困难度。
  2. 过渡效果和动画效果都是实现网页动态特效的技术。区别在于，过渡效果是从一个状态向另一个状态进行平滑过渡的效果，如颜色渐变、大小变化、位置变化等；而动画效果则是在一段时间内呈现出一系列变化的效果，如旋转、缩放、翻转等。通常可以使用CSS属性如transition、animation、@keyframes等来定义过渡和动画效果。
  3. 是的，我曾经使用过响应式开发框架如Bootstrap。它们可以提供许多现成的UI组件和布局系统，使得前端开发更为高效。同时，这些框架还可以帮助开发者轻松构建响应式UI，适配各种设备分辨率，加快了页面容易的开发和适配和维护。
  4. 我有一定的JavaScript基础，之前也经常使用JavaScript进行开发。异步代码可以使用回调、Promise、async/await等方式来处理，以便在异步操作完成后执行适当的操作。具体执行细节，如有需求，我可以介绍更详细的内容。
  5. 闭包是指在函数内部定义的函数，并可以访问外部函数的变量的特殊函数。这些变量通常是外部函数的私有变量，无法从函数外部访问，通过使用闭包，可以将它们封装在函数内部，以保护和隔离它们。

第三节

Q:

  1. 你了解什么是跨站脚本攻击，如何防范它？
  2. 你熟悉什么是浏览器的“同源策略”，以及如何与JSONP、CORS相结合？
  3. 你如何使用Git来管理项目代码？你了解什么是分支吗？
  4. 你如何进行调试和测试代码？
  5. 你对前端安全性有什么具体的了解？

A:

  1. 跨站脚本攻击（XSS攻击）是指攻击者利用漏洞在网站上注入恶意代码，从而获取用户的隐私信息或执行攻击者的恶意操作。要防范XSS攻击，可以通过以下几种方式：

    • 对用户输入的数据进行过滤和验证，防止恶意代码被注入

    • 对输出到页面的数据进行编码，避免脚本和HTML代码被解释执行

    • 设置HTTP响应头X-XSS-Protection标志，提示浏览器开启内置的XSS防御机制

    • 使用Content Security Policy（CSP）来限制网页只加载指定来源的资源，从而防止跨站点脚本攻击

  2. 同源策略是浏览器的安全机制，它限制了一个网页从另一个源加载资源的能力，目的是保护用户的隐私和安全。JSONP和CORS都是用于解决跨域问题的技术。JSONP通过动态创建<script>标签，将JSON数据包装成一个回调函数，并通过URL参数传递给服务器，从而实现跨域请求数据。而CORS通过在HTTP请求头中添加特定的标志，告知服务器允许跨域请求，从而实现了更为安全的跨域请求。

  3. 我通常使用Git进行项目代码的管理。使用Git可以通过版本控制轻松地记录代码的变更历史，方便开发者进行协作和追踪问题。在进行Git分支管理时，可以使用main分支作为主要分支，再新建分支来实现代码的临时更改或测试等，以确保程序的稳定性不受影响。

  4. 在调试代码时，我通常使用浏览器内置的开发人员工具（如Chrome浏览器的开发者工具）来对代码进行调试。此外，还可以使用断点调试、console.log、try..catch等方式来进行调试。在测试方面，我通常会首先进行单元测试、集成测试，以及端到端的功能测试，来确保代码的正确性和可维护性。devtools。

  5. 前端安全性主要是指通过一系列措施来保护用户和网站免遭各种网络攻击和威胁。例如，使用HTTPS协议加密数据传输、过滤用户输入、限制资源访问、实现访问控制、缓存控制等。此外，还需要定期更新网站软件和插件，并设置合适的备份和恢复策略。

第四节

  1. 您能介绍一下AngularJS和ReactJS之间的区别吗？您使用过它们中的任一个吗？
  2. 您使用过哪些前端工具/框架，比如npm、Webpack、gulp等等？
  3. 对于性能优化，你有哪些具体的提升方案？
  4. 您如何管理Web应用程序的状态？
  5. 在前端开发中，您会遇到哪些常见的安全漏洞，如何预防它们？

A：

  1. AngularJS和ReactJS都是当今最流行的前端框架之一。AngularJS是一个MVVM框架，通过双向数据绑定实现数据驱动视图，提供了丰富的指令和服务来实现常见功能。ReactJS则是一个声明式、组件化的库，以JavaScript中的函数和组件为基础来构建应用程序。不同之处在于AngularJS更适合复杂的企业应用和大型项目，而ReactJS则更适合构建快速、高性能的单页应用程序。

我使用过AngularJS和ReactJS。当我需要构建大型企业级应用时，我更倾向于使用AngularJS进行开发，因为它具有更多的内置功能和丰富的支持生态系统，例如控制器、服务、路由等。ReactJS则更适合构建小到中型应用程序，因为它可以更好地处理组件化开发的概念。

  1. 我经常使用npm作为包管理器，它可以快速地安装和更新依赖项。Webpack和Gulp则通常用于打包、构建和自动化构建流程。使用这些工具可以使前端开发更加高效和简洁。例如，通过Webpack的模块化处理，可以实现对多个JavaScript文件和CSS文件的打包和缩小处理，同时也可以优化加载和渲染速度。

  2. 性能优化是前端开发过程中的重要部分，可以通过以下几种方式进行优化：

    • 减少HTTP请求，通过CDN来加速文件加载速度

    • 合并和压缩JavaScript和CSS文件，减少页面加载时间

    • 减少DOM元素，使页面加载更快，渲染更流畅

    • 优化图像和视频，通过压缩和缓存来减少带宽和加载时间

    • 优化JavaScript代码，例如避免无限循环、减少闭包的数量等

  3. 对于Web应用程序的状态管理，我通常使用Redux来管理状态。Redux是一个JavaScript状态容器，它可以存储和管理复杂的状态，确保应用程序的组件可以共享数据和交互。Redux还支持时间旅行功能，可以让开发者通过历史状态来调试应用程序和追踪错误。

  4. 在前端开发中，常见的安全漏洞包括XSS攻击、CSRF攻击和网站劫持等。要解决这些问题，可以通过以下几种方式：

    • 进行用户输入和数据验证，避免遭受跨站脚本攻击

    • 在CSRF攻击防御上，考虑使用类似于Token的方式来确保用户身份的合法性

    • 使用HTTPS协议，保证数据传输过程的安全性

    • 对网站进行扫描、监控和预防，确保安全性或者实施WAF等控制措施来保护网站。

第五节

  1. 您如何了解并遵循W3C标准，确保您的网站符合规范？
  2. 您如何进行代码的优化和压缩，以便提高网站性能？

A:

  1. 了解并遵循W3C标准是确保网站符合规范的关键。W3C标准并不是某个工具或框架的附属品，相反，它是一组规范、约定和准则，用于确保Web内容的无障碍性、可用性、可靠性和互用性。为了确保网站符合W3C标准，我通常采用以下几种方法：

    • 遵循HTML和CSS的最佳实践，确保语义和结构的正确性，使用标准命名约定和样式表，减少使用非标准元素和属性

    • 使用W3C验证器或其他工具来检查网页的正确性，确定网页是否符合规范

    • 参考W3C标准文档来学习和理解标准规范，特别是HTML、CSS和JavaScript方面的规范内容

    • 跟踪最新的W3C规范和技术变化，并在实践中应用它们

  2. 优化和压缩代码可以帮助提高网站性能，加快页面加载时间。我通常会采用以下几种方法进行代码的优化和压缩：

    • 通过删除无用的代码、注释和空格来减小文件大小

    • 将多个JavaScript和CSS文件合并成一个文件，以减少HTTP请求

    • 采用对JavaScript和CSS进行压缩的方法，如WebPack的UglifyJsPlugin和CSSO等

    • 使用几种前端性能优化技巧，如图像和视频的优化、延迟加载、懒加载和DFS deferred loading来优化网站性能。

需要注意的是，代码的优化和压缩不一定能改善性能，并且可能会使代码更难以阅读和维护。当进行优化时，需要谨慎地选择需要压缩和优化的代码，以确保其可读性和正确性。

Else

懒加载和延迟加载两者的本质区别在于其加载时机的不同。

懒加载是指将页面中的某些元素（如图片、视频等）的加载延迟到这些元素进入用户视野之前，当用户开始滚动页面时才进行加载。比如，当用户滚动到页面某个区域时，此时位于该区域内的图片才开始加载。懒加载通常使用 JavaScript 实现，可以提升页面的加载速度和用户的体验。懒加载可以在用户开始加载时只加载首屏图片，页面其余部分的图片可以在下滑到页面底部的过程中逐步加载。

而延迟加载是指在页面的首次请求中，将某些资源（如 JavaScript、CSS 文件）的加载延迟到页面内容被渲染完成之后、或当页面需要使用该资源时再进行加载。延迟加载可以减小首屏渲染所需时间，在客户端空闲时再加载后续的资源，从而提高页面加载效率。常见的延迟加载方式有使用 async 和 defer 属性，将 JavaScript 文件异步加载，或者将 CSS 文件放在页面底部等。

总的来说，懒加载和延迟加载都是优化页面性能和用户体验的有效手段，但两者的使用场景和应用方式有所不同。懒加载通常用于图片和其他资源的加载上，而延迟加载则用于 JavaScript、CSS 文件等资源的加载上。

发表于

2418. 按身高排序

==Easy==

给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高 降序 顺序返回对应的名字数组 names 。

示例 1：

输入：names = ["Mary","John","Emma"], heights = [180,165,170]
输出：["Mary","Emma","John"]
解释：Mary 最高，接着是 Emma 和 John 。

题解

新开一个数组 ，以序数对应 names 数组，值对应 height 数组。

用选择排序更新 height 的值，同时更新 idx[i] 的值。

最后更新 names 数组即可。

vector sortNames(vector& names, vector& heights) {
    int n = heights.size(); // 记录人数
    vector idx(n); // 建立长度为 n 的下标数组
    for (int i = 0; i < n; i++) {
        idx[i] = i; // 将下标数组初始化为 [0, 1, 2, ..., n-1]
    }

    // 选择排序 heights，并记录下标变化
    for (int i = 0; i < n - 1; i++) { // 循环 n-1 次
        int max_idx = i; // 记录身高最高的人的下标
        for (int j = i + 1; j < n; j++) { // 从 i+1 的位置开始循环
            if (heights[idx[max_idx]] < heights[idx[j]]) { // 如果出现更高的人
                max_idx = j; // 更新最高的人的下标为 j
            }
        }
        swap(idx[i], idx[max_idx]); // 将当前位置 i 和最高的人的位置 max_idx 进行交换
    }

    // 按顺序将 names 中的名字加入结果数组
    vector res(n); // 建立长度为 n 的结果数组
    for (int i = 0; i < n; i++) { // 循环 n 次
        res[i] = names[idx[i]]; // 将原始 names 中对应下标的名字存入结果数组
    }

    return res; // 返回排序后的名字数组
}

发表于

1163. 按字典序排在最后的子串

==Hard==

给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

示例 1：

输入：s = "abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

题解

我们注意到，如果一个子串从位置 iii 开始，那么字典序最大的子串一定是 $s[i,..n−1]$，即从位置 $i$ 开始的最长后缀。因此，我们只需要找出字典序最大的后缀子串即可。

我们使用双指针 $i$ 和 $j$，其中指针 $i$ 指向当前字典序最大的子串的起始位置，指针 $j$ 指向当前考虑的子串的起始位置。另外，用一个变量 $k$ 记录当前比较到的位置。初始时 $i=0, j=1, k=0$。

每一次，我们比较 $s[i+k]$ 和 $s[j+k]$：

如果 $s[i+k]=s[j+k]$，说明 $s[i,..i+k]$ 和 $s[j,..j+k]$ 相同，我们将 $k$ 加 1，继续比较 $s[i+k]$ 和 $s[j+k]$；

如果 $s[i+k]<s[j+k]$，说明 $s[j,..j+k]$ 的字典序更大。此时，我们更新 $i=i+k+1$，并将 $k$ 重置为 0。如果此时 $i≥j$，那么我们将指针 $j$ 更新为 $i+1$，即 $j=i+1$。这里我们跳过了以 $s[i,..,i+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[j,..,j+k]$ 为起始位置的后缀子串。

同理，如果 $s[i+k]>s[j+k]$，说明 $s[i,..,i+k]$ 的字典序更大。此时，我们更新 $j=j+k+1$，并将 $k$ 重置为 0。这里我们跳过了以 $s[j,..,j+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[i,..,i+k]$ 为起始位置的后缀子串。

最后，我们返回以 $i$ 为起始位置的后缀子串即可，即 $s[i,..,n−1]$。

https://leetcode.cn/problems/last-substring-in-lexicographical-order/solutions/2242562/python3javacgotypescript-yi-ti-yi-jie-sh-3amj/

class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size();
        int i = 0, j = 1, k = 0;
        
        // 遍历所有可能的子串起始位置 i 和 j
        while (j + k < n) {
            if (s[i + k] == s[j + k]) {     // 如果相同，则继续比较后面的字符
                k++;
                continue;
            } else if (s[i + k] < s[j + k]) { // 如果 s[i + k] < s[j + k]，i 跳到 j+1，k 置为 0
                i += k + 1;
                k = 0;
                if (i >= j) {               // 如果发现 i 已经超过[j,n)了，就更新 j=i+1
                    j = i + 1;
                }
            } else {                        // 如果 s[i + k] > s[j + k]，j 跳到下一个后缀的起始位置 k+1,j
                j += k + 1;                 // 跳到下一个后缀的起点
                k = 0;                      // k 重新置为0
            }
        }
        return s.substr(i);                 // 返回最后一个子串
    }
};

发表于

1105. 填充书架

给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。

按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。

  • 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。

每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

示例 1：

img 
输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。

题解

显然dp。

对于每本书，我们有两种选择：

  1. 将这本书放在新的一层上；
  2. 将这本书放在当前层上。

状态转移方程：$dp[i] = min(dp[i], dp[j-1] + maxHeight)$

class Solution {
public:
    int minHeightShelves(vector>& books, int shelfWidth) {
        int n = books.size();

        // 初始化动态规划数组
        int dp[n+1];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            // 第一种情况：将当前书放在新的一层上
            dp[i] = dp[i-1] + books[i-1][1];  
            // 第二种情况：将书放在当前层上
            int width = books[i-1][0];  // 第 i 本书的宽度
            int height = books[i-1][1];     // 第 i 本书的高度     
            for (int j = i-1; j > 0 && width + books[j-1][0] <= shelfWidth; j--) {  // 将当前书放在当前层上，从后往前尝试每一本书
                height = max(height, books[j-1][1]);  // 找到当前层上所有书籍的最大高度
                width += books[j-1][0];		// 更新 width 的值 
                dp[i] = min(dp[i], dp[j-1] + height);  // 计算当前状态的最小高度
            }
        }

        return dp[n];
    }
};

发表于 更新于

4-22美团笔试

19：00 - 21：00 第二个算法题没写出来，估摸着也寄了

20个专业单选 10个应用算术题 2个编程题

1. 单选

  1. 作业调度

    HRRN（Highest Response Ratio Next，最高响应比优先）调度算法是一种用于作业调度的非抢占式算法，是对响应比优先（RR）算法的改进。

    HRRN调度算法中，每个作业的响应比定义为（等待时间 + 服务时间）/服务时间。当一个作业被放到CPU中运行时，它的响应比将随时发生变化。每当一个作业加入就绪队列时，将对每个作业的响应比计算一次，并选取响应比最高的作业进行调度。

  2. 二叉树中序/后序遍历

    二叉树遍历是指按照一定的规则对二叉树中的节点进行访问。常用的二叉树遍历方式包括前序遍历、中序遍历和后序遍历。以下是它们的具体定义：

    • 前序遍历（先序遍历）：先访问根节点，然后访问左子树，最后访问右子树。
    • 中序遍历：先访问左子树，然后访问根节点，最后访问右子树。
    • 后序遍历：先访问左子树，然后访问右子树，最后访问根节点。

  3. 同步请求子进程还是主进程

    在浏览器环境中，同步请求通常是在主进程中执行的，而不是在子进程中执行。这是因为主进程是负责整个页面加载和渲染的进程，在执行同步请求时，它会被阻塞，直到请求完成并返回结果。如果同步请求在子进程中执行，那么子进程将会被阻塞，导致页面响应速度变慢，甚至出现假死现象。

  4. 大数据量高并发如何缓解

    Q：分库分表都可以缓解写入压力吗

    A：分库分表可以缓解单台MySQL服务器的写入压力，但是并不能完全解决高并发写入压力。因为在分库分表之后，写入压力是分散到了多台MySQL服务器上，但是每台MySQL服务器上的写入压力仍然可能会很高，会导致单台MySQL服务器的性能瓶颈和故障。分库分表只是将写入压力分散到多台服务器上，从而可以提高系统的并发能力和稳定性，但单台服务器的写入性能仍然可能成为瓶颈。

    Q：数据库分离可以缓解写入压力吗

    A：数据库分离可以缓解写入压力。在数据库分离的情况下，可以将不同的数据和应用程序分布在不同的数据库中，从而减少单个数据库的写入压力，提高整个系统的性能。

  5. SQL

  6. 进程 并发性

    进程的并发性是指多个进程在同一时间内同时运行的能力。在计算机系统中，多个进程可以在同一时刻被操作系统调度到不同的 CPU 核心或者处理器中并行执行，从而实现进程的并发性。

  7. 查找效率

    提高查找效率的方式有很多，主要包括以下几种：

    1. 索引优化：创建合适的索引，可以大大提高查找效率。索引可以加速数据的查找以及表的连接等操作，如 B+ 树索引、哈希索引、全文索引等。
    2. 分区技术：在大型数据表中，可以将表根据某个字段进行分区，从而实现数据的快速查找。在进行查询时，只需要对某个分区进行查询即可，而不需要扫描整张表。
    3. 缓存技术：可以将常用或热门的数据缓存起来，以减少查询次数，提高查询速度，如 Redis、Memcached 等缓存技术。
    4. 搜索引擎：通过搭建搜索引擎，可以实现全文检索功能，提高查询效率，如 Solr、Elasticsearch 等搜索引擎。
    5. 分布式查询：在大型数据处理场景下，可以通过分布式查询的方式，将查询请求分散到多个节点上进行处理，提高查询效率，如 Hive、SparkSQL、Hadoop 等大数据处理框架。

    除了上述方式，还可以采用优化 SQL 语句、硬件性能优化、使用缓存或者 NoSQL 数据库等方式来提高查询效率。不同的场景和需求需要不同的优化方式进行结合使用，以满足具体的业务需求。

  8. epoll 查找元素的时间复杂度：O(1)

    epoll 是一种高效的 I/O 事件通知机制，在 Linux 操作系统中被广泛应用于网络编程中，能够有效避免传统 select 和 poll 模型中，随着监听文件描述符数量增多，事件通知效率下降的问题。epoll 的事件管理模型是基于事件触发实现的。它通过 epoll_ctl 将需要监听的 socket 文件描述符注册到 epoll 模型中，再通过 epoll_wait 系统调用来等待这些事件的发生。

    epoll 的时间复杂度是 O(1)，因为它用红黑树来存储文件描述符，而红黑树具有对数时间复杂度 O(logn) 的特点，它可以在一些比较大的 file descriptor 中快速定位到要处理的事件，而不需要轮询，因此效率高于 select 和 poll 模型。

    综上所述，epoll 作为一种高效的 I/O 事件通知机制，它具有时间复杂度低、高效性强、可扩展性好的特点，被广泛应用于大规模高并发的网络编程中。

  9. BFS

    BFS（Breadth First Search），又称广度优先搜索，是从起始点开始逐层扫描整张图，先一层一层搜索，直到找到目标点为止。在搜索过程中，使用一个队列来保存每一层的所有节点，先进先出，逐层递进，直到搜索到目标节点为止。BFS 的时间复杂度为 O(|V|+|E|)，其中 |V| 表示节点个数，|E| 表示边数。

    DFS（Depth First Search），又称深度优先搜索，是从起始点开始一直往深处搜索，直到找到目标节点为止。在搜索过程中，从起始节点开始，递归地搜索它的相邻节点，每次只选择其中一个节点继续深入，直到找到目标节点或者没有相邻节点为止。DFS 的时间复杂度为 O(|V|+|E|)，其中 |V| 表示节点个数，|E| 表示边数。

    BFS 和 DFS 都有各自的优缺点，在不同的应用场景中可以选择不同的算法。BFS 算法可以找到最短路径，但是需要占用大量的存储空间，其空间复杂度为 O(|V|)，当图中节点较多时，空间开销较大；DFS 算法则可以快速地搜索整张图，但是不能一定找到最短路径，存在搜索深度较深时容易陷入死循环的问题。因此，在实际应用中，需要综合考虑应用场景、搜索结果等的优缺点进行选择。

  10. 适配器模式本质

    适配器模式的本质是将一个已有的接口转化为另一个客户端所需要的接口，以适应不同的环境和需求。它属于结构型设计模式，可以在不改变接口前提下，将原始接口转换为目标接口，使得不兼容的类可以一起工作。

    适配器模式的主要作用是提高代码的复用性和可扩展性。

  11. 递归成立的条件

    递归需要满足以下两个条件才能实现：

    1. 递归调用：在函数体内直接或间接地调用自身。
    2. 结束条件：在递归调用的过程中，一定要存在一个条件，当满足这个条件时，递归调用停止，从而结束递归。

  12. SQL

  13. 图

    连通图是指无向图或有向图中，任意两个顶点之间都存在一条路径，也就是说图中的任意两个顶点都是连通的。无向图中的连通图也被称为连通分量。如果一个无向图有 k 个连通分量，则该图的连通性为 k。

    不连通图是指无向图或有向图中，存在某些顶点之间没有直接相连的路径，也就是说图中有些顶点是不连通的。无向图中，不连通的部分可以被视为若干个由连通部分组成的图，每个连通部分都是一个连通分量。

  14. 水题

  15. 表字段 NULL

    非空是 NOT NULL

  16. ARP协议 单播 广播

    ARP（Address Resolution Protocol）是用于将IP地址转换为MAC地址的协议，常用于局域网中。在ARP请求中，主机会向网络中的所有主机广播ARP请求，以获取某个IP地址对应的MAC地址。因此，ARP协议接收时是广播的。

  17. 辗转相除

  18. 信号量可用资源

    当前信号量表示目前剩余资源，临界区 = 总信号量 - 当前信号量，等待 = 待处理信号 - 剩余资源

  19. GDB打印元素

    GDB（GNU Debugger）是一种功能强大的调试器，是 GNU 软件开发工具集的一部分。

  20. IMAP协议

    IMAP（Internet Message Access Protocol，互联网邮件访问协议）是一个用于从邮件服务器上获取邮件的标准协议。

    IMAP协议的主要功能是让客户端可以直接在邮件服务器上管理邮件，有如下主要特点：

    1. 支持多个客户端同时访问同一个邮箱，比POP3更加适合多设备使用，如手机、平板、笔记本等。
    2. 支持在线邮件阅读，可实现邮件在服务器上的搜索、筛选、排序等高级功能。
    3. 支持邮件的部分下载，节省网络流量，提高效率。
    4. 通过IMAP客户端，可以在邮件服务器上创建、删除、移动邮件，比POP3更加强大和灵活。
    5. IMAP协议和邮件本身的数据结构更加复杂，需要在服务器上消耗更多的资源和时间，因此需要更高的硬件配置。
    6. 支持通过字符串搜索邮件内容。

    IMAP协议在电子邮件传输和管理中扮演着重要的角色，具有更丰富的功能和更强的灵活性，也成为了当前比较流行的邮件协议。

2. 算法题

1. 计算水题

好久没写 C++ 了，要注意多个变量初始化的时候记得分开写。

√：

double up = 0, down = 0;

X：

double up, down = 0;

写 js 写习惯了是这样的。

#include 
using namespace std;
int point[2000];
int score[2000];

int main()
{
  int T;
  scanf ("%d", &T);
  while (T--) {
    int n, x = 0;
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; ++i) {
        scanf ("%d", &point[i]);
    }
    for (int i = 0; i < n; ++i) {
        scanf ("%d", &score[i]);
    }

    bool flag;
    flag = true;
    double up = 0, down = 0;
    for (int i = 0; i < n; ++i) {
        if (score[i] < 60) {
            flag = false;
            break;
        }
    }
    if (flag == false) {
        printf("No\n");
        continue;
    }
    for (int i = 0; i < n; ++i) {
        up += point[i] * score[i];
        down += point[i];
    }
    double res = up / down;
    if (res >= x) {
        printf("Yes\n");
        continue;
    } else {
        printf("No\n");
    }
  };
  return 0;
}

2. 完全背包问题

n种作物，m的时间，接下来三行

第一行t，表示每种作物成熟所需时间

第二行a，表示作物成本

第三行b，表示卖出作物的价格

输出最大收益

c[i]=b[i]-a[i]表示单一作物的收益

f[i][j]表示可以选择前i种作物，总时间为j的情况下的最优解

f[n] [m]==>最终结果

f[ 0 ] [j]=0
f[i][0]=0

状态转移方程
f[i][j]=max(f [ i - 1 ] [ j ],c[i]+f[i][j-t[i]])

计算第i行的时候，确定的是第i种作物种几个
决策： 0/1 01背包
k 完全背包

for i=1..n
for j=1..m
f[i][j]=k* c[i]+f[ i-1 ] [j-k * t[i]]

把第三次循环的 k 优化掉了，原因是不需要计算同一行前一个已经计算过的冗余部分，直接拿前一个的计算结果即可，因为前面计算过的已经找到了最优的解。

示例

#include 
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;

    int w[n+1], v[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    int dp[V+1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }

    cout << dp[V] << endl;
    return 0;
}

发表于

1027. 最长等差数列

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

题解：dp

/**
 * @param &#123;number[]&#125; nums
 * @return &#123;number&#125;
 */
var longestArithSeqLength = function(nums) &#123;
    const n = nums.length;
    const dp = new Array(n).fill(0).map(() => new Map()); // 初始化 dp 数组，每个位置对应一个哈希表，用于存储以该位置为结尾、以其差值为公差的等差数列的长度

    let res = 2; // 初始化结果为 2，因为任意两个数都是等差数列

    for (let j = 1; j < n; j++) &#123; // 枚举等差数列的最后一项
        for (let i = 0; i < j; i++) &#123; // 枚举等差数列的倒数第二项
            const d = nums[j] - nums[i]; // 计算等差数列的差值

            if (dp[i].has(d)) &#123; // 如果 dp[i] 中存在该差值
                dp[j].set(d, dp[i].get(d) + 1); // 转移，更新以 nums[j] 结尾、以差值 d 为公差的等差数列的长度为 dp[i].get(d) + 1
            &#125; else &#123; // 如果 dp[i] 中不存在该差值
                dp[j].set(d, 2); // 初始化以 nums[j], nums[i] 为首尾、以差值 d 为公差的等差数列的长度为 2
            &#125;

            res = Math.max(res, dp[j].get(d)); // 更新全局最长等差子序列的长度 res
        &#125;
    &#125;

    return res; // 返回最长等差数列的长度
&#125;;

发表于

2413. 最小偶倍数

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

示例 1：

输入：n = 5
输出：10
解释：5 和 2 的最小公倍数是 10 。

题解

休闲

/**
 * @param &#123;number&#125; n
 * @return &#123;number&#125;
 */
var smallestEvenMultiple = function(n) &#123;
    if (n % 2 === 0) &#123;
        return n;
    &#125; else &#123;
        return n * 2;
    &#125;
&#125;;

发表于

1187. 使数组严格递增

给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

如果无法让 arr1 严格递增，请返回 -1。

示例 1：

输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

题解：动态规划

首先需要将 arr2 排序去重，并记为 list。

定义 dp[i] [j] 表示对于 arr1 的前 i 个元素，且替换了 j 个元素之后，序列的末尾数字的最小值。

将 dp 数组初始化，对于 dp[0] [0]，为了方便后面的转移，其值设为 -1。

对于 dp[i] [j]，有以下几种情况：

  • 如果当前 arr1[i-1] 大于 dp[ i-1] [j]，说明不用替换，直接添加 arr1[ i-1]。
  • 如果 j > 0，且 dp[ i-1] [ j-1] 不为 INF，说明可以选择替换掉前面的某个数字，使得后面更容易增加。此时找到 list 中大于 dp[ i-1] [ j-1] 的最小值进行替换。
  • 如果 i == n 且 dp[i] [j] 不为 INF，说明已经处理完所有元素且序列严格递增，直接返回 j。

最终返回如果需要替换的次数，即为 dp[n] [j] 中最小不为 INF 的 j 值。

const INF = 0x3f3f3f3f;
var makeArrayIncreasing = function(arr1, arr2) &#123;
    arr2.sort((a, b) => a - b); // 将 arr2 排序
    const list = [];
    let prev = -1;
    for (const num of arr2) &#123; // 去重
        if (num !== prev) &#123;
            list.push(num);
            prev = num;
        &#125;
    &#125;
    const n = arr1.length;
    const m = list.length;
    const dp = new Array(n + 1).fill(0).map(() => new Array(Math.min(m, n) + 1).fill(INF)); // 初始化 dp 数组
    dp[0][0] = -1; // 为了方便后面的转移，设 dp[0][0] = -1
    for (let i = 1; i <= n; i++) &#123;
        for (let j = 0; j <= Math.min(i, m); j++) &#123;
            if (arr1[i - 1] > dp[i - 1][j]) &#123; // 如果当前元素大于序列的最后一个元素
                dp[i][j] = arr1[i - 1];
            &#125;
            if (j > 0 && dp[i - 1][j - 1] !== INF) &#123; // 如果可以进行替换操作
                const idx = binarySearch(list, j - 1, dp[i - 1][j - 1]); // 查找严格大于 dp[i - 1][j - 1] 的最小元素
                if (idx !== list.length) &#123;
                    dp[i][j] = Math.min(dp[i][j], list[idx]);
                &#125;
            &#125;
            if (i === n && dp[i][j] !== INF) &#123; // 如果已经处理完所有元素且序列严格递增，直接返回替换次数
                return j;
            &#125;
        &#125;
    &#125;
    return -1; // 如果无法使 arr1 严格递增，返回 -1
&#125;

const binarySearch = (list, low, target) => &#123;
    let high = list.length;
    while (low < high) &#123; // 二分查找
        const mid = low + Math.floor((high - low) / 2);
        if (list[mid] > target) &#123;
            high = mid;
        &#125; else &#123;
            low = mid + 1;
        &#125;
    &#125;
    return low;
&#125;;

发表于

1043. 分隔数组以得到最大和

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

题解

先通过动态规划预处理出位置 i 前的一个子区间的最大值，即 max，再利用动态规划求出位置 i 的最优解，即将位置 i 之前分成一个长度为 j 的区间和一个长度为 i - j 的区间，前者的最大值即为 max。随着不断前进，将得到整个数组的解。注意在第二层循环中，我们需要设置 j 的起点，也就是确保至少一次划分，以方便初始化 dp[1~k]，也就是最开始为 arr[0], arr[0] * 2, arr[0] * 3, …。时间复杂度为 $O(n^2)$。

var maxSumAfterPartitioning = function(arr, k) &#123;
    const n = arr.length;
    const dp = new Array(n + 1).fill(0); // dp[i] 表示将前 i 个元素分隔变换后能够得到的元素最大和
    for (let i = 1; i <= n; i++) &#123; // 遍历每个位置
        let max = 0; // 初始化最大值
        const deque = []; // 定义一个单调队列
        // 从右到左遍历前 i 个元素，找出长度不超过 k 的子数组的最大值
        for (let j = i - 1; j >= 0 && i - j <= k; j--) &#123;
            max = Math.max(max, arr[j]);
            deque.unshift(max); // 将最大值加入队列头部
            const length = i - j; // 子数组长度为 i-j
            if (length === 1) &#123; // 如果子数组长度为 1，直接使用该元素的值进行赋值
                dp[i] = Math.max(dp[i], arr[j]);
            &#125; else &#123; // 否则，使用最大值乘以当前长度与 dp[j] 中的较大值进行赋值
                dp[i] = Math.max(dp[i], deque[0] * length + dp[j]);
            &#125;
        &#125;
    &#125;
    return dp[n]; // 返回 dp[n] 即为答案
&#125;;

发表于

1026. 节点与其祖先之间的最大差值

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例 1：

img

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

题解

var maxAncestorDiff = function(root) &#123;
    let result = &#123; 
        V: 0 
    &#125;;  // 记录最大差值
    dfs(root, result);
    return result.V;
&#125;;

function dfs(root, result) &#123;
    if (!root) &#123;
        return &#123; max: -Infinity, min: Infinity &#125;;
    &#125;
    
    let &#123; max: maxLeft, min: minLeft &#125; = dfs(root.left, result);  // 左子节点的最大值和最小值
    let &#123; max: maxRight, min: minRight &#125; = dfs(root.right, result);  // 右子节点的最大值和最小值
    
    // 计算当前节点子树中的最大值和最小值
    let maxVal = Math.max(root.val, maxLeft, maxRight);
    let minVal = Math.min(root.val, minLeft, minRight);
    
    // 更新最大值
    if (root.left) &#123;
        let diff = Math.abs(root.val - minLeft);
        if (diff > result.V) &#123;
            result.V = diff;
        &#125;
        diff = Math.abs(root.val - maxLeft);
        if (diff > result.V) &#123;
            result.V = diff;
        &#125;
    &#125;
    if (root.right) &#123;
        let diff = Math.abs(root.val - minRight);
        if (diff > result.V) &#123;
            result.V = diff;
        &#125;
        diff = Math.abs(root.val - maxRight);
        if (diff > result.V) &#123;
            result.V = diff;
        &#125;
    &#125;
    
    return &#123; max: maxVal, min: minVal &#125;;
&#125;

如果直接使用 result = 0 来初始化结果，则会导致 result 存储的是一个数字，而不是一个对象。这样在 DFS 遍历过程中，我们无法直接修改 result 的值，而需要额外声明一个变量来保存最大差值。具体来说，我们需要在递归函数的返回值中返回最大差值，然后在计算当前节点的最大差值时，将递归返回的最大差值和当前节点的差值进行比较，取两者中的较大值作为新的最大差值。

发表于

2409. 统计共同度过的日子数

Alice 和 Bob 计划分别去罗马开会。

给你四个字符串 arriveAlice ，leaveAlice ，arriveBob 和 leaveBob 。Alice 会在日期 arriveAlice 到 leaveAlice 之间在城市里（日期为闭区间），而 Bob 在日期 arriveBob 到 leaveBob 之间在城市里（日期为闭区间）。每个字符串都包含 5 个字符，格式为 "MM-DD" ，对应着一个日期的月和日。

请你返回 Alice和 Bob 同时在罗马的天数。

你可以假设所有日期都在 同一个 自然年，而且 不是 闰年。每个月份的天数分别为：[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 。

示例 1：

输入：arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
输出：3
解释：Alice 从 8 月 15 号到 8 月 18 号在罗马。Bob 从 8 月 16 号到 8 月 19 号在罗马，他们同时在罗马的日期为 8 月 16、17 和 18 号。所以答案为 3 。

题解

主要还是输入处理的问题，将日期字符串分割，然后处理为日期数。

/**
 * @param &#123;string&#125; arriveAlice
 * @param &#123;string&#125; leaveAlice
 * @param &#123;string&#125; arriveBob
 * @param &#123;string&#125; leaveBob
 * @return &#123;number&#125;
 */
const monthDays = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];

var countDaysTogether = function(arriveAlice, leaveAlice, arriveBob, leaveBob) &#123;
    // 用数组 `sum` 存储每个月的天数累加和
    let sum = [0];
    for (let i = 0; i < monthDays.length; ++i) &#123;
        sum.push(sum[i] + monthDays[i]);
    &#125;
    // 分别计算两个人到达日期和离开日期的天数
    let aA = calc(arriveAlice, sum);
    let lA = calc(leaveAlice, sum);
    let aB = calc(arriveBob, sum);
    let lB = calc(leaveBob, sum);
    // 根据到达和离开日期的天数计算旅行天数，即两个时间段的重合部分
    return Math.max(0, Math.min(lA, lB) - Math.max(aA, aB) + 1);
    
&#125;;

// 计算日期所对应的天数
function calc(day, sum) &#123;
    let month = parseInt(day.substring(0, 2));
    let date = parseInt(day.substring(3));
    return sum[month - 1] + date;
&#125;

发表于

4.15 米哈游笔试

20:00 - 22:00 看起来基本是寄了

10个单选 10个不定项选择 3个算法题

选择题涉及：进程线程、TCP/UDP、js 原型，resolve，输入输出，css flex模型

算法题

首先我不熟悉输入输出，在这个 ACM 的界面磨蹭了半天才开始写，有点抽象

然后后面就基本没时间写了

1. 正整数

给一个偶数位正整数，分割成两部分后求和，求和的最小值。

例如输入4321，输出64。

思路基本上是从中间切，或者中间的+1-1位置切

但是从中间切就过了85%了，乐

2. 反应

给一个 n * m 的矩形，格子内随机存在 T 和 I，如果 T 和 I 处在相邻位置（上下左右）会反应。

输出反应后的矩形

输入：
3 4
T I T .
. . . I
. T . I

输出：
. . . .
. . . I
. T . I

思路就是遍历，然后看上下左右有没有相反的元素，开一个新布尔数组用于记录该位置有没有反应，先全值为 false，反应了就置 true。最后再遍历一遍统一处理输出。

3. 猜数组

有两个数组 a 和 b，遵循以下规律：

  • $b_i = a_i + a_{i+1}$
  • a.length = b.length + 1
  • a 数组的元素均为正整数

给你 a 数组的长度和 b 数组，返回 a 数组所有可能的情况的数量。

输入：
3
3 4

输出：
2

解释：数组 a 有可能是[1,2,2]或[2,1,3],共两种情况，故返回2.

思路：寻找 $a_0$ 的大小范围即可

因为 a 数组的元素均为正整数，所以显然 b 数组的元素也都是正整数。

当 $a_0$ 确定了，后面的数字也就跟着确定了，于是问题转化为确定 $a_0$ 的范围。

从 $a_i > 0$ 着手：因为 $b_i = a_i + a_{i+1}$ ，所以可以举例：

  • 首先，$a_0 >0$ ；

  • $i=0$ 时， $b_0 = a_0 + a_{1}$， => $a_1 = b_0 - a_0$ ，因为 $a_1 > 0$ ，=> $b_0-a_0>0$ ，=> $a_0 < b_0$ 。

    因为已经知道 $b_0$ 的值，所以此时 $0<a_0<b_0$ 。

  • $i=1$ 时，可以得到 $a_0 > -b_1+b_0$ ；

  • $i=2$ 时，可以得到 $a_0 < b_2 -b_1+b_0$ ；

  • $i=3$ 时，可以得到 $a_0 > b_3 + b_2 -b_1+b_0$ ；

至此得到规律，当处理到 b 数组的偶数位时，限制的是 $a_0$ 的上限；当处理到 b 数组的奇数位时，限制的是 $a_0$ 的下限。

所以只需要从头开始遍历 b 数组，取两个数 max、min 为上下限，当处理到奇数位时如果大于min则更新，当处理到偶数为时如果小于max则更新。特殊情况，若 max < min 则返回0。

最后返回 max - min - 1 即可（因为 $a_0$ 的取值范围是 (min, max)，即从 min+1 到 max-1的数字的数量）。