leetcode 记录

好久没刷题了..  刷题使我快乐

相关答题记录在我的 git 上:https://github.com/xunge0613/leetcode-practice

2018年6月7日18:03:19

771. Jewels and Stones

描述:
统计在字符串B中出现的A字符中的字符个数

想法:
1  练习算法题,先实现、再优化
2 目的是为了让自己进步,所以需要不断的练习,感悟
3 自己完成以后,学习其他人优秀的代码
4 看完别人的代码以后,对比一下,找一找自己的不足之处或者薄弱之处:函数式,代码优雅、可读性

思路:
1 遍历字符串 S
扩展:JS 各种遍历
扩展:reduce
2 查找 S 中的字符串是否在 J 中

记录:
1 第一次提交 60ms
2 第二次想尝试优化一下,用 map 来缓存记录,结果发现运行速度更慢了
3 第三次回到第一次的方法,
4 第四次,参考大佬们的代码,用函数式写了一下.. 运行速度疑似变快了一点点,但是代码确实整洁了许多.

回顾:
耗时 30 min 开发
耗时 1 hour 思考、学习、记录

821. Shortest Distance to a Character

想法:
1 将端点坐标记录在数组中
2 相应的距离通过端点坐标来进行计算(分为3段)
每个端点的值用 indexOf() 的值来记录
最初到第一个端点:倒序输出即可
最后一个端点到结束:总字符串长度 减去 该端点到起点的线段长度,正序输出即可
其余情况:实际上转换为了一道数学题,1 2 3 2 1 (5),计算 5 的展开式……
判断是奇数还是偶数,然后对称位置加上同样的数,最后补上端点自身的 0,对于奇数,中间的那位数也要补上,偶数则不需要. 对于 0 的话,作为偶数,但不进入循环,直接补上自身的 0
3 复杂度预计为 o(n*pn*(pv /2)) ??? pn 为端点的个数 、pv 为端点的值

知识储备:
1 数组拼接 concat
2 字符串分割 substring

记录:
1 第一次提交,WA,没有考虑到奇数情况的端点处理(tempResult[element – index – 1]),此处未减 1
2 第二次提交,通过,68ms,但貌似提交总数有点少,不知道自己的运行效率如何。估计只能算一般,甚至更糟。

2018年6月6日16:41:17

7. Reverse Integer

描述:
给定32位带符号整数,返回倒序后的数字

分析:
1 倒序
2 判断正负数 ,并相应处理
3 倒序后,开头0的处理
4 判断大数(> 2^31 – 1 or < -2^31),并相应处理

记录:
第一次提交答题时由于没有判断大数,所以 WA 了.. 用 js 写感觉好偷懒……

34. Search for a Range

描述:在有序数组中,查找某一特定值在数组中所在范围;不存在则返回 [-1,-1];复杂度不能超过 O(log n).

分析:
本质上就是一个搜索,分别查找最小索引和最大索引,而且数组已经排序过,所以用二分查找比较合适。
每一次二分查找,都是通过循环,调整临时的最大、最小索引,不断逼近,查找出此次的极值(最小或最大),

记录:
第一次尝试使用的是二分法查找,结果写了半天写不下去了,觉得逻辑有问题.
第二次尝试,改用最基础的正向遍历和反向遍历完成了答题,一次通过,运行速度超过了92%的js提交…… 60ms
第三次尝试,学习了讨论区里大佬们的算法,改成对最小索引和最大索引分别进行二分查找,运行速度超过了98%的js提交… 56ms

思考:
作图更有助于理解本题
中间值就是每一次进行查询的索引
在二分查找过程中,会遇到几种搜索情况:
第一种,未命中,且当前值小于待查询值,于是设置最小索引值为中间值 + 1(向右查询)
第二种,未命中,且当前值大于待查询值,于是设置最大索引值为中间值 – 1(向左查询)
第三种,已命中,若当前查找最小索引,则设置最大索引值为中间值 – 1,(向左查询)
第四种,已命中,若当前查找最大索引,则设置最小索引值为中间值 + 1,(向左查询)
当最大索引值与最小索引值相同时,此时的中间值,就是最终确定下来的边界值

Leave a Reply

Your email address will not be published. Required fields are marked *

3 × 1 =