- 写在前面
- 关于“模拟题”和“算法题”及主观难度评价
- 第一批
- 1791. 设备编号（模拟）
- 1792. 服务器集群网络延时（排序、数学）
- 1793. 给定差值的组合（哈希表）
- 1787. 最长元音子串（模拟）
- 1788. 计算面积（模拟、哈希表）
- 1794. 最长的指定瑕疵度的元音子串
- 1789. 简易内存池（模拟、设计）
- 1790. 合法的 mac 地址（模拟）
- 1795. 最佳路径（BFS、层序遍历）
- 第二批
- 1807. 矩阵转置（数学）
- 1808. 整理工号（模拟）
- 1812. 求矩阵列的最大值中的最小值（模拟）
- 1813. 用给定的数字组成 IP 地址（递归回溯、全排列）
- 1809. 最佳升级时间窗（滑窗）
- 1810. 日志敏感信息屏蔽（哈希表、模拟）
- 1814. 代码缩进（脑筋急转弯、差分数组）
- 1811. 素数行李箱密码（BFS、层序遍历）
- 第三批
- 1822. 电话拦截（模拟、排序）
- 1825. 按身高和体重排队（排序）
- 1826. 整数对最小和（TopK）
写在前面
这是一篇萌新友好的 Golang 题解合集，只要你看得懂 Golang、LeetCode 刷过 100 道题左右都能看懂。文章直到我刷完所有题目之前都会持续更新。
题解仅代表我个人使用并且 AC 的解法，不一定是最佳解法，可能还有 CleanCode 扣分，如果大家发现文中的错误或有更好的解法可以在评论区提出，我看到之后会第一时间修正并补充到文中。
每一道题目我都给出了题目考察的知识点、我个人对这道题难度的主观评价和我的解法的复杂度分析。由于我不擅长分析时间复杂度，所以时间复杂度和空间复杂度分析很可能有错误，欢迎各位大佬赐教。\
关于“模拟题”和“算法题”及主观难度评价
可信考试科目一有两个平台可以报：iLearning(OJ) 和 LeetCode。据说 iLearning 偏模拟，LeetCode 偏算法，本人由于没考过 iLearning 所以不做评价。
由于本人主刷 LeetCode，科目一也都是报 LeetCode，习惯了做 LeetCode 那种纯算法题，因此刷 OJ 这种模拟题刷得快要裂开了，一天顶多刷 1 - 2 道，所以更新可能比较慢。等这批案例开放刷得差不多之后会考虑开一篇刷 LeetCode Top 100 的文章。
这篇文章中的题目绝大多数都是“模拟题”，使用的算法最难也就是滑窗、BFS、DP、递归回溯等不算特别难的算法，至于贪心、复杂二分、线段树、AVL 树、Trie 等很复杂的算法目前还没有见到，数据结构方面到目前为止只见过一道使用图和一道使用堆（TopK）的题目。从算法的角度来说，一般 OJ 的中等题相当于 LeetCode 的 Easy，困难题相当于 LeetCode 的 Medium，但如果从读题的角度来讲，OJ 上很多题目的读题难度都不低，而题目考察的基本都是读题，且细节非常多，基本需要彻底理解题意才能知道如何解决这道题，甚至可能读完题都搞不懂这题到底在考什么算法。。。所以文中的主观难度评价都是基于使用的算法难度和对细节处理的要求来确定的，如果按照读题难度的话估计很多都是困难。
总而言之，这些题目中除了困难之外基本上暴力都能 AC，所以别想太多，暴力就完事了！！！暴力过不了或者存在比暴力更简单的解法的题目我会特别标注。
第一批
1791. 设备编号（模拟）
难度：简单；主观评价：简单。
直接用 strconv.Itoa() 转换成字符串进行判断即可。
时间复杂度：O(n * m)，其中 n 为 start 到 end 之间的数字个数，m 为数字位数，最大为 5。对于 start 到 end 之间的每一个数字都要转换为字符串并遍历转换后的字符串进行判断。
空间复杂度：O(n)，只使用了常数个数的存储空间。
1792. 服务器集群网络延时（排序、数学）
难度：简单；主观评价：简单。
数学问题，考中位数的特性。
如果 len(arr) 为奇数，则直接取 arr 的中位数编号的服务器作为主服务器；如果 len(arr) 为偶数，则取 arr 排序后中间两个编号的任意一个都可以。
对数组排序之后取中位数，并选定相应编号的服务器作为主服务器。选定主服务器之后，按照题目说明计算答案即可。
ps: 这道题暴力也可以，不会超时，不过代码太复杂了，不如中位数的解法简单易懂。
时间复杂度：O(nlogn)，为排序算法的时间复杂度。
空间复杂度：O(1)，只使用了常数个数的存储空间。
1793. 给定差值的组合（哈希表）
难度：简单；主观评价：中等。
第一反应暴力，但是由于问题规模非常大，大到 GoLand 的调试控制台都装不下，所以暴力会超时，只能用时间复杂度 O(n) 的算法。
这也就是为什么我认为这道题可以算中等难度，因为能暴力的都没啥难度。
题目有个“双指针”标签，但是暂时没想到比较好的双指针解法（猜测可能类似于 LeetCode 第 11 题“Container With Most Water”，如果大家想到双指针怎么解可以留个评论），后来想到这道题是“两数之差”，或许可以转换成 LeetCode 第一题“Two Sum”并且使用哈希表处理，这个思想可以去 LeetCode 上看官方题解来学习。
本题和两数之和的不同之处在于：
- 因为题目是“两数之差”，所以哈希表保存的是数组当前元素与目标值的和。
- 本题中，一个数字可以多次使用（比如-1 / 5 / -1 -2 1 2 0）中，-1、1、0、2 这几个数字都会多次使用，而不像两数之和中那样不能重复使用。所以，需要遍历 array 数组两次：一次构建哈希表，一次判断。
时间复杂度：O(n)，需要遍历数组两次。
空间复杂度：O(n)，哈希表占用的空间与数组长度成正比。
1787. 最长元音子串（模拟）
难度：简单；主观评价：简单。
按照题目要求进行循环模拟即可，这题所用的循环模拟的方法其实就是找符合某种条件的最长子串问题的最简单的方法（复杂一点的是双指针、滑窗等）。
一开始考虑的太复杂，导致 WA 了好几次，想到了现在的办法之后回头一看：就这？所以说不要在前一天晚上没睡好的时候刷 OJ，而且刷这些题千万别想复杂，最好的解法可能就是你下意识想到的那个。。。
时间复杂度：O(n)，需要遍历字符串一次。
空间复杂度：O(1)，只使用了常数个数的存储空间。
1788. 计算面积（模拟、哈希表）
难度：简单；主观评价：简单。
使用 for 循环模拟题目中提到的绘图过程。
这里我使用了哈希表来辅助计算：哈希表的 key 为受到命令影响的 x 值，在模拟的过程中，每走一步都使用哈希表判断一下是否会有命令影响这一步，如果有，则根据该 key 的 value 改变 y 值，然后将这一步绘制的长方形的面积加入总面积中。
当然，为了减小空间复杂度，也可以不用哈希表而直接根据 cmd 数组来计算面积。这样可以将空间复杂度优化到 O(1)，但是不如哈希表的方法直观，建议萌新采用哈希表法。
时间复杂度：O(max(n, stopPoint))，其中 n 为 cmds 数组的长度，需要遍历一次 cmds 数组生成哈希表，再遍历 stopPoint 次。
空间复杂度：O(n)，哈希表占用的空间与 cmds 数组的长度成正比。
1794. 最长的指定瑕疵度的元音子串
难度：简单；主观评价：简单。
滑窗入门题，具体看注释。
ps: 这个 AC 代码在最大圈复杂度（13）上扣了分，大家提交的时候记得多拆几个函数出来降低圈复杂度。
时间复杂度：O(n)，需要遍历数组一次。
空间复杂度：O(1)，只使用了常数个数的存储空间。
1789. 简易内存池（模拟、设计）
难度：中等；主观评价：简单。
看起来很麻烦、代码很长，其实非常简单，与其说是模拟题不如说是设计题，只是考察读题能力和对特殊情况的判断，具体看注释。
这道题最大的坑是题目没写明白，题目中的“不会释放已申请的内存块的中间地址”不是输入约束而是需要处理的特殊条件之一！！！这害得我白白多了一个 WA。。。
其他的部分都很简单，按照题目要求模拟就行了。
ps：我的代码不是最优解，如果要再优化的极致一点需要添加一个标记数组 [100]bool{} 用于标记某个起始地址开始的某块是否已经被成功分配，这样就能省略掉这个 tryAlloc() 函数，减少一次循环。
时间复杂度：O(n)，执行一次分配需要遍历内存池一次并遍历被分配的内存块一次，执行一次释放需要遍历释放的内存块一次。
空间复杂度：O(1)，内存池的大小是固定的，所以只使用了常数个数的存储空间。
1790. 合法的 mac 地址（模拟）
难度：中等；主观评价：简单。
本来想用滑窗，但是想了半天却发现滑窗过不了样例 2，遂放弃，后来想到一个合法的 mac 地址肯定只有 17 个字符，于是想到了模拟的方法。
具体来说就是每次从输入的字符串中取出相邻的 17 个字符，然后尝试使用 - 或者 : 分割，再判断分割出来的子串是否均为二位 16 进制数，也未尝不是一种滑窗（？）。
如果两种分隔符混用，则分割后肯定有一部分的长度是大于 2 的，此时直接返回 false 即可，最后用哈希表进行去重。
时间复杂度：O(n^2)（不确定），对于每一个 17 个字符组成的子串都需要单独遍历该子串一次。
空间复杂度：O(n)，去重使用的哈希表的长度与输入字符串中的不同合法 mac 地址的个数成正比。
1795. 最佳路径（BFS、层序遍历）
难度：困难；主观评价：中等。
BFS（层序遍历）应用题，具体看注释。
看到有向带权图的最短路径，第一反应其实是 Dijkstra，但是由于这道题存在 Dijkstra 无法处理的情况：经过的顶点更少的路径权值比经过节点更多的路径高，所以只能 BFS。
与常见 BFS 题目最大的区别就是对于终点的处理：遍历到终点时，不能把终点标记为 visited，否则会出现同层其他顶点访问不到终点的情况。
另外我很久没做这种邻接矩阵的 BFS 了，一般做的都是那种给你个矩阵和起始位置让你判断上下左右四个点那种，遇到像这样的“典型 BFS”直接歇菜。但是做完了回头一看也不难，没有用到什么很高深的知识点或者完全没接触过的算法，肯定算不上困难，但是不会层序遍历的肯定做不出这道题，所以主观评价给个中等吧。
ps: 这道题感觉稀疏图的情况比较常见，如果用邻接表的话可能会更好一点，当然这题问题规模比较小，用邻接矩阵也不会 OOM。
ps2: 执行耗时最短的那位老哥的解法实在是太秀了，大家可以 AC 之后去看一下，反正我是学不来。。。
时间复杂度：O(n)，每个节点都需要被访问至少一次（终点会被访问多次）。
空间复杂度：O(n)，队列中的元素个数与问题规模成正比。
标签：遍历,题目,萌新,题解,复杂度,Golang,哈希,LeetCode,模拟 From： https://www.cnblogs.com/gongxianjin/p/17178298.html