LeetCode刷题笔记（700-799）
LeetCode刷题笔记（700-799）
【700】二叉搜索树中的搜索
解题记录
这题相当于在二叉搜索树中搜索是否存在某一个数，由于二叉搜索树左侧的节点一定不大于根节点，右侧的节点一定不小于根节点，利用这个性质这题是很简单的。
相关标签
树
【704】二分查找
解题记录
这题找到一个解释的十分详细的题解，已经转载至个人博客。
相关标签
二分查找
【709】转换成小写字母
解题记录
顺序判断每一个字符是否是大写字母，是大写字母的就在ASCII码的基础上进行转换，最后拼接为新的字符串。
相关标签
字符串
【717】1比特与2比特字符
解题记录
由0开头的必然是1比特字符，由1开头的必然是2比特字符，读取到0，前进一位，读取到1，前进两位，直到读取到字符串末尾，设置变量标记当前读取的为1比特或2比特字符，最后读取标记变量就知道最后一个读取的是什么字符了。
相关标签
数组
【724】寻找数组的中心索引
解题记录
首先求出数组和，以第1个元素为起点，此时左侧和为0，右侧和为 数组和 - 左侧和 - 第1个元素 ，不断向右读取新的数并更新左侧和和右侧和，比较左侧和右侧和就能得到数组的中心索引。
相关标签
数组
【728】自除数
解题记录
判断一个数是否是自除数，将每一位取出来与自己取余是否为0就可以进行判断了。
相关标签
数学
【744】寻找比目标字母大的最小字母
解题记录
由于给定的字符列表已经完成排序，所以直接遍历找到第一个大于当前字母的字符即可，如果找不到说明当前目标字母是最大的，但是由于比较时字符是循环出现的，所以如果找不到更大的字符，返回数组的第一个字符。
相关标签
二分查找
【746】使用最小花费爬楼梯
解题记录
这题的题目描述挺不清晰的。第N级楼梯的花费是在离开或跨越第N楼梯的一瞬间产生的，我们需要知道从每一级楼梯离开需要的最小花费，最小花费到达顶部有哪两种可能呢？一种从最后一级台阶离开，一种从倒数第二级台阶一次性跨越两级台阶离开，从最后一级台阶和倒数第二级台阶两者离开的花费中较小者就是本题所求，以最后一级台阶为例，要知道最后一级台阶离开的最小花费，需要先明确，怎么才能从最后一级台阶离开。
第一种方法，从倒数第二级台阶先到最后一级台阶，然后离开，花费为离开倒数第二级台阶的最小花费与最后一级台阶的花费之和。
第二种方法，从倒数第三级台阶跨越两级到最后一级台阶，然后离开，花费为离开倒数第三级台阶的最小花费与最后一级台阶的花费之和。
也就是说，每一级台阶的最小花费需要对比前两级台阶的最小花费才能得到，这题可以使用动态规划。首先求出从第一级台阶离开的最小花费，也就是 cost[0] ，再求从第二级台阶离开的最小花费，由于题目规定了起点可以选择0或1，所以第二级台阶离开的最小花费并不依赖于第一级台阶，也就是 cost[1] 。
我们可以用数组保存每级台阶的最小花费，但是由于每级台阶的花费只依赖前两级的花费，所以其实可以节省一些空间，使用两个变量保存。从第N级台阶离开的最小花费，就等于离开第N-1级与第N-2级台阶的最小花费中的最小值，再加上从第N级台阶离开的花费，也就是 cost[N] ，不断的递归计算，最后剩下的两个变量即为离开最后一级台阶和倒数第二级台阶的花费，求出两者的最小值就是本题所求。
相关标签
数组、动态规划
【747】至少是其他数字两倍的最大数
解题记录
这题只要计算出最大和第二大的数的下标即可，Swift简洁的语法在做这题上帮助不小。直接使用元组交换的语法就可以交换新的最大值、次大值与旧的最大值、次大值，赞美一波Swift。
相关标签
数组
【748】最短完整词
解题记录
首先用哈希表保存牌照每个字符出现的次数，然后遍历所有给定单词，对每个单词创建新的哈希表统计字符出现次数，然后从牌照哈希表中取出每一个键值对，判断单词哈希表中是否存在且次数不少于，就能判断一个单词是否是完整词，找出所有完整词中最短的即可。
相关标签
哈希表
【762】二进制表示中质数个计算置位
解题记录
本题两部分，求一个数二进制表示1的位数以及求质数。二进制1的位数可以用按位于运算得到，质数也是循环判断即可。我看到最优做法将1-20的质数保存到集合中，由于数字转换为二进制最高不超过20位，相当于省去了求质数的步骤，只需要求出1的位数判断是否在集合中即可，集合很小，这个判断几乎是常数级的时间复杂度，我个人感觉这么做有点奇怪，如果给定的数更大，就不通用了，或者必须扩大质数集合。但是确实很巧妙的利用了题目条件。
相关标签
位运算
【766】托普利茨矩阵
解题记录
如果一个矩阵是N*M的，那么总共需要判断N+M-3条对角线，每一条对角线的起点都位于矩阵的第一行或第一列上，只需要在第一行或者第一列上依次移动起点，不断判断以该点为起点的对角线是否具有一致性即可。
相关标签
数组
【771】宝石与石头
解题记录
简单的哈希表题目，记录宝石的种类，遍历石头，一旦发现是宝石就将计数器加一，最后返回计数器。
相关标签
哈希表
【784】字母大小写全排列
解题记录
利用Swift数组灵活的特性，其他语言可以使用队列，使用一个数组结构保存所有排列可能，初始化的时候置入一个空字符串，如果读取到数字，将存储结构中的每一个字符末尾添加上数字。
如果读取到字母，移除存储结构中第一个元素，再向存储结构中依次存入移除元素与读取到的字母的大小写拼合的版本。
相关标签
位运算，回溯算法
【788】旋转数字
解题记录
首先对数字进行分类。
第一类：0、1、8，旋转后保持不变；
第二类：2、5、6、9，旋转后变成不一样的数字；
第三类：3，4，7，旋转后不是数字。
对一个数是否是好数的判断标准就是不能出现第三类数字，也不能只出现第一类数字，也就是只要出现第二类数字并且没出现第三类数字，就是好数。
相关标签
字符串