LeetCode刷题笔记（800-899）
LeetCode刷题笔记（800-899）
【804】唯一摩尔斯密码词
解题记录
用数组保存摩尔斯密码，通过ASCII码取到对应的摩尔斯密码，计算出单词的摩尔斯密码后保存到哈希表，最后返回哈希表中键值对的个数即为所求。
相关标签
字符串
【806】写字符串需要的行数
解题记录
使用一个变量记录行数，一个变量记录宽度，读取到字符通过ASCII码取到对应的宽度，如果当前宽度加上当前字符的宽度不超过100就继续加，超过了就另起一行，很简单的逻辑。
相关标签
数组
【811】子域名访问计数
解题记录
遍历给定的域名，首先将访问次数与域名分离开，再将域名以英文句号为标志，分割为子域名，从子域名中取出子域名，与次数一起作为键值对保存到哈希表，不断取出新的子域名，拼接得到更长的子域名。以 100 www.baidu.com 为例，分割后得到 [www, baidu. com] 这个子域名数组和100这个次数，首先取出 com ，将 com: 100 作为键值对保存，然后取出 baidu ，拼接得到 baidu.com ，将 baidu.com: 100 作为键值对保存，以此类推。当每一个域名都处理完毕后，再遍历哈希表中的键值对，按照题目的格式进行输出即可。
相关标签
哈希表
【812】最大三角形面积
解题记录
这题想了半天想不出来，看了题解挺失望的，最优的方案竟然就是暴力循环，既然没有什么巧妙的题解，为什么还要将这题放到题库里呢？暴力方式很简单，从点集中遍历任意三个点的所有可能组合，根据三个点的坐标计算三角形面积，最后返回最大值即可。
相关标签
数学
【819】最常见的单词
解题记录
首先遍历字符串，将字符串中的每个单词保存到哈希表中，得到单词出现的次数。然后遍历哈希表，找到最大的不在禁用单词列表中的单词。
相关标签
字符串
【824】山羊拉丁文
解题记录
分割字符串得到每个单词，根据单词的位置以及开头字母进行相应的处理然后存入结果中即可。
相关标签
字符串
【830】较大分组的位置
解题记录
双指针遍历字符串，双指针指向相同字符时一个指针向后移动，得到每一段相同字符的长度，如果长度不小于3，将双指针作为边界位置添加到结果数组中，注意双指针的边界条件即可。
相关标签
数组
【832】翻转图像
解题记录
要完成两个操作，反转数组和0-1互换，两个操作其实可以在一次遍历中完成，遍历的时候原数组从后往前遍历，将遍历元素0-1反转后添加到结果中即可。
相关标签
数组
【836】矩形重叠
解题记录
一开始没想明白，写了很复杂的判断语句也有遗漏的情况，另两个矩形分别叫a、b，两个矩形不重叠其实只需要满足：
a的最左侧比b的最右侧还要靠右
a的最右侧比b的最左侧还要靠左
a的底部比b的顶部还靠上
a的顶部比b的底部还靠下
四个条件满足任意一个即可，通过每个矩形左下角和右上角的坐标很容易就能判断。
相关标签
数学
【840】矩阵中的幻方
解题记录
又是一个只能暴力循环求解的题目，遍历矩阵中每一个点，判断以该点为左上角的3X3矩阵是否是幻方，判断幻方首先判断矩阵中是否出现了1-9以外的元素，出现就一票否决，然后判断矩阵中是否有9个元素，不是的话也一票否决，然后开始正式判断，先计算第一行之和，作为标准和，然后计算剩余的每一行和每一列和对角线，与标准和进行比较，判断是否满足每一行每一列与两条对角线都相等的条件，不满足也一票否决，最后没有被否决的结果可以作为一个幻方，计数器自增。这题更简洁的做法是将3阶幻方的8种可能保存到集合中，这样只需要将每个矩阵进行判断是否在集合中即可。
相关标签
数组
【844】比较含退格的字符串
解题记录
这题我使用了栈，如果读取到退格符号就弹出栈顶元素，否则将读取到的元素压入栈，最后栈中剩下的就是字符串结果，然后比较两个字符串即可。如果要实现常数级的空间复杂度，需要从后向前扫描字符串，扫描到退格符号就将符号前的第一个不是退格字符的字符删除，最后剩下的也是字符串结果。
相关标签
栈、双指针
【849】到最近的人的最大距离
解题记录
每次找到新的座位，就将新的座位与上一个座位的位置进行比较，找到两个座位最中间的座位，就是当前两个座位可以找到的最大距离空座位。
相关标签
数组
【852】山脉数组的峰顶索引
解题记录
这题在二分查找的基础上略微进行修改，常规的二分查找命中条件是中位下标对应的数就是要找的数，这题命中条件是中位下标对应的数左右两侧均比它小。
相关标签
二分查找
【859】亲密字符串
解题记录
对于一组亲密字符串，有两种可能，一种是两个字符串完全相等，通过交换两个相同的字符实现题意，另一种就是字符串中有且只有两个地方不一样。对于两种情况分别处理，第一种情况对字符串进行计数，检查是否有某一个字符出现2次以上，出现2次以上意味着可以交换该字符。对于第二种情况，使用双指针指向两个字符串的起点，遍历字符串，第一次发现两个字符不一样时，记录下此时的两个字符，如果再出现两个字符不一样，判断两个字符与第一次记录的两个字符是否满足逆序关系，如果不是就可以直接返回false。每次出现不一样的字符时维护一个计数器，最后观察计数器是否为2即可得到答案。
相关标签
字符串
【860】柠檬水找零
解题记录
由于题目限定了只会收到5、10、20三种面值的钱，所以对于这三种面值分别处理即可。对于5，不需要找钱，只需要将持有的5块钱的数量加一即可；对于10，如果没有持有5块钱，就无法找零，返回false，否则可以找零，持有的10块加一，5块减一；对于15比较复杂，找零要么为3张5元，要么为1张5元1张10元，要分别判断受伤的纸币是否满足这些条件。这题如果纸币面值更多样就不能用分类讨论的思想解题了。
相关标签
贪心算法
【867】转置矩阵
解题记录
这题很简单，遍历每一个数组中的元素，将其映射到行、列坐标互换的位置即可。
相关标签
数组