LeetCode刷题笔记（300-399）
LeetCode刷题笔记（300-399）
【344】反转字符串
解题记录
双指针分别指向字符串首末，交换指针指向的元素并移动指针直到两个指针碰撞。
相关标签
双指针、字符串
【345】反转字符串中的元音字母
解题记录
最初我把字符串原封不动的保存为字符串，由于Swift对字符串取字符以及修改特定位数的字符十分繁琐不方便且效率低，虽然我想到双指针的解题思路，但是最终还是导致超时。后来将字符串转存为数组，返回的时候再转为字符串，大大提高了对字符串的操作效率，在这题的解题过程中还学习到一个小技巧，就是Swift中的交换语法。
1 | |
相关标签
双指针、字符串
【349】两个数组的交集
解题记录
遍历第一个数组，并将出现过的元素存储到哈希表中，再遍历第二个数组，将重复出现的元素的value值自增，也就是两个数组的交集，同时添加到数组中即可完成，一次通过此题。
相关标签
排序、哈希表、双指针、二分查找
【350】两个数组的交集II
解题记录
与349类似，区别在于遍历第一个数组时需要讲出现过的元素出现的次数同时存储到哈希表中，遍历第二个数组的时候对出现的元素的次数自减并添加到数组中，直到次数为0或者已经遍历完第二个数组。这题还有一个附加问题，如果数组已经排好序，可以使用双指针分别指向两个数组的起始，在指针向后移动的过程中对重复的元素进行计数。如果两个数组长度差距过大，需要选择将小的数组进行哈希映射，减小哈希表所占空间。
相关标签
排序、哈希表、双指针、二分查找
【367】有效的完全平方数
解题记录
类似于计算一个数的平方根，可以从1到该数的一半进行二分查找，但是需要注意二分查找的细节，每次更改前后指针时需要令其在中间的基础上往相应的方向挪动一位，否则会出现无限循环的现象。
相关标签
数学、二分查找
【383】赎金信
解题记录
这题最开始我对杂志字符串进行遍历，使用哈希表存储出现过的字符以及出现的次数，对赎金信字符串遍历时减去出现次数，如果出现次数为0或者哈希表中没有记录，说明在赎金信中的字符出现次数大于杂志中出现的字符，返回false。但是哈希表的耗时并不理想，由于这题需要存储的是字符串以及出现的次数，可以使用数组存储出现的次数，因为题目说明可以假设字符串只包括小写字母，所以可以将字符的ASCII码减去97对应的数作为字符串的下标即可，思路不变，但使用数组相比使用哈希表效率大大提升。
相关标签
字符串
【387】字符串中的第一个唯一字符
解题记录
先将字符串转存为字符串数组方便操作，遍历一遍将每个字符出现的次数存储到数组中，字符对应的ASCII码-97就是数组的下标，完成统计后对字符串数组再次遍历，查询出现过的次数，如果次数为1返回当前字符的下标，否则返回-1完成本题。
相关标签
哈希表、字符串
【389】找不同
解题记录
这题就是【136】只出现一次的数字的字符串版本，最初我使用的是类似于哈希表的方法，与前两天做的题目类似，对字符串遍历，查询出现次数为1的字符，没有想到之前学到的使用异或的方法，举一反三的能力还是不足啊，但是在Swift中无法直接对字符进行位运算，需要将字符转换为ASCII码，对ASCII码进行位运算，再将得到的结果ASCII码转换为字符，一来一去我发现实际上耗费的时间和传统做法相差无几。
相关标签
位运算、哈希表
【392】判断子序列
解题记录
这题有一个后续挑战，一开始做的时候我就准备按照后续挑战的要求来做，我的思路是将t串的所有字符出现过的位置记录到一个二维数组中，由于s串较短，储存好t串的字符出现位置后遍历s串，观察s串中前后两个字母在t串中出现的位置是否前后对应，但是遇到了问题。观察两个串，“leetcode”与“leeeeeeeeetcode”，第一个串中出现了三次e，最后一次e在最末尾，但是在第二个串中，e的第三次出现位于第4个字母，无法匹配，除非寻找第二个串中是否有e出现在d后面，但这么做的话问题就会变的异常复杂，遂暂时放弃后续挑战。题目本身使用双指针可以解决，两个指针指向两个串，字母相等则两个指针都向后移，不相等则只将长串的指针向后移，但是有一个疑惑的地方，最初我将两个串都转换为数组进行双指针操作，但是耗时很不理想，由于指向较长串的指针无论发生什么情况一定要向后移，所以我修改为较长串使用for循环，只对较短串的指针操作，耗时大大缩短，不知道是什么原理。
相关标签
贪心算法、二分查找、动态规划