LeetCode 手记 04

Yourtion 创作于:2020-02-09     全文约 6349 字, 预计阅读时间为 19 分钟

LeetCode 手记 04

本周收获与反思

  • 多从整体的角度上思考,看看如何巧妙解答
  • 通过画图帮忙扩展思路,找出一些突破点
  • 深入了解 char 相关内容
  • 深入了解熟悉位操作
  • 需要更多地去分析理解题目中的内容
  • 【SQL】需要了解临时表的使用
  • 【SQL】熟悉 HAVING 的用法
  • 深入了解和熟悉二进制数字和位运算

Boyer-Moore 算法

Boyer-Moore 就是找nums的一个后缀suf,其中suf[0]就是后缀中的众数。

我们维护一个计数器,如果遇到一个我们目前的候选众数,就将计数器加一,否则减一。只要计数器等于 0 ,我们就将 nums 中之前访问的数字全部 忘记 ,并把下一个数字当做候选的众数。

我们可以放心地遗忘前面的数字,并继续求解剩下数字中的众数。最后,总有一个后缀满足计数器是大于 0 的,此时这个后缀的众数就是整个数组的众数。

112. 路径总和

https://leetcode-cn.com/problems/path-sum/

思路

解题的思路还是比较简单的

  1. 判断当前节点为 null 就返回 false
  2. 如果 sum 已经是 0 并且是已经是叶子节点,则说明已经找到解,返回 true
  3. 其他情况则递归处理左右子树,同时将 sum 减去当前节点值

https://leetcode-cn.com/submissions/detail/45468638/

反思

解法跟官方题解的递归解法一致,官方提供的迭代解法还是不太能理解,感觉整体上也没有递归那么简洁与易理解,同时也没有性能上的优势。

118. 杨辉三角

https://leetcode-cn.com/problems/pascals-triangle/

思路

通过简单的循环计算每行的元素,推入结果数组即可,其中:

  1. 每行的第一个和最后一个元素是 1
  2. 其他元素等于上一行的当前 index-1 的值加上上一行的当前 index 的值

https://leetcode-cn.com/submissions/detail/45478330/

反思

跟官方题解的方法基本一致,但是感觉官方解法中的代码太过于啰嗦的感觉,不如我写的版本那么简单。

119. 杨辉三角 II

https://leetcode-cn.com/problems/pascals-triangle-ii/

思路

没有想到具体的数学解法,还是跟上面的方法类似,只是不需要保存整个数据,只需要保留上一层的数据用于计算。

https://leetcode-cn.com/submissions/detail/45481754/

反思

公式法是把它看成一个组合数:n!/(k!(n−k)!)=(n∗(n−1)∗(n−2)∗...(n−k+1))/k!

121. 买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

思路

一直陷在两次循环的套路里面,只是简单地想到去掉一些不必要的循环,还是暴力解题的思路

https://leetcode-cn.com/submissions/detail/45615367/

反思

其实有个最简单的方法,就是循环一遍,找出最小值后找出其后的最大值,也就是找到最小的谷之后的最大的峰。

122. 买卖股票的最佳时机 II

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

思路

解题的思路比较简单,通过ij两个指针进行循环:

  1. 如果后面的值j比当前买入价格i还小,则 i 继续累加
  2. 如果当前值比之前的值小,那么就在上一次卖出,累计收益,同时把i买入指针置为当前位置
  3. 记得处理最后一个位置卖出的情况

https://leetcode-cn.com/submissions/detail/45654435/

反思

看了官方题解,我的方法使用了两次循环,跟题解的“峰谷法”类似。

但是“方法三:简单的一次遍历”的方法非常巧妙,通过转换每次计算峰谷转换成连续峰和谷的高度之差,使用一次遍历就完成了。遇到类似的问题,可以通过画图帮忙扩展思路。

125. 验证回文串

https://leetcode-cn.com/problems/valid-palindrome/

思路

通过i两个指针j,通过charAt()原位比较:

  1. 使用Character.isLetterOrDigit判断字母和数字
  2. 使用Character.toLowerCase进行大小写转换

https://leetcode-cn.com/submissions/detail/45675166/

反思

使用了 java 类库而不是对 char 直接进行大小比较,可能会对性能有一定影响,但是在使用现成的类库比起自己造轮子更好呢?

136. 只出现一次的数字

https://leetcode-cn.com/problems/single-number/

思路

解法相对比较暴力,没有使用额外的存储空间,需要循环整个数组多次,如果找到另外一个数字就把两个位置置为 0,直到整个数组处理完。

https://leetcode-cn.com/submissions/detail/45764062/

反思

一直没有想到线性时间解决的方法(考虑过 hash 表,但是想到要额外的空间),大概有个思路,但是没想到位操作的方法,a⊕b⊕a=(a⊕a)⊕b=0⊕b=b,其实只要循环一次,使用res ^= num[i]即可。

还有另外一个方法也值得学习2∗(a+b+c)−(a+a+b+b+c)=c,只要返回2 * sum(set(nums)) - sum(nums),虽然需要多一倍多空间,但是也比暴力法好。

141. 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

思路

用来一个取巧的方法,其实准确来说可能还是错误的(只是样例测试不出来),将遍历过的节点设置为Integer.MAX_VALUE,如果再遇到就认为有环。

https://leetcode-cn.com/submissions/detail/45844979/

反思

其实正确的方法应该是使用快慢双指针法,通过快慢双指针的移动,快指针(两倍速)必然先到尾部,否则两个指针必然相遇。还一个使用 HashSet 的方法,之前也没考虑到。

155. 最小栈

https://leetcode-cn.com/problems/min-stack/

思路

思路还是比较简单,对于栈就还是使用 Java 提供的Stack,主要考虑下面几个点:

  1. 使用min保存当前最小值,使用minCount保存当前最小值有几个
  2. 因为有可能有多个最小值,需要保证最小值被pop后不需要重新计算一次
  3. 当最小值都被pop了,需要重新计算一次最小值和数量

https://leetcode-cn.com/submissions/detail/45852682/

反思

可能更加好的一个实现是通过一个两个值(当前值,当前最小值)的链表(或者两个栈)来保存,虽然牺牲了一些存储空间,但是性能也要更强(通过空间换时间)。

160. 相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

思路

首先想出了最暴力最简单的写法,同时也是验证一下测试样例和方法的正确性,性能很差。

https://leetcode-cn.com/submissions/detail/45931791/

接下来使用了HashSet进行哈希存储,总体感觉还行,但是没用想到不使用额外存储空间同时为线性时间的解法。

https://leetcode-cn.com/submissions/detail/45934723/

反思

官方解法中的双指针法确实非常巧妙,通过将较长的链表指针指向较短链表头部,从而消除了两个链表的长度差,只要两者相等即为相交,否则两个指针同时到达尾部null

167. 两数之和 II - 输入有序数组

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

思路

一看到是有序数组就想到使用二分法,但是没用出很好的解法,只能通过二分法加快暴力搜索的速度,答案其实不是特别满意。

https://leetcode-cn.com/submissions/detail/45971242/

反思

官方题解的双指针法确实非常巧妙,充分利用了题目中有序数组还有唯一解的性质,从前后两端移动指针,直到找到唯一解。

168. Excel 表列名称

https://leetcode-cn.com/problems/excel-sheet-column-title/

思路

其实思路很简单,就是简单的进制转换,记得处理当没用余数的情况。

https://leetcode-cn.com/submissions/detail/45980629/

反思

跟官方解法基本一致,但是不懂得通过char的特性简化操作(char)('A' + c - 1),该有就是使用sb.insert(0, x)从前面插入。

169. 多数元素

https://leetcode-cn.com/problems/majority-element/

思路

没有想到很好的方法,只能通过哈希计数的方式解题,通过空间换时间的方法,但是跑出来的结果却是不怎样。

https://leetcode-cn.com/submissions/detail/46063801/

反思

官方解法提出了很多种,除了暴力解法和我使用的哈希表,我认为最有启发的是“排序法”(直接排序数组,返回中间的元素)。

还有“Boyer-Moore 投票算法”,通过遗忘前面的非众数从而得到结果,非常巧妙。

171. Excel 表列序号

https://leetcode-cn.com/problems/excel-sheet-column-number/

思路

跟之前的 Excel 序号问题一样,也是进制转换的问题:

  1. 通过从后往前循环并使用s.charAt(i) - 'A'获得当前位的乘数
  2. 使用k *= 26在循环中不断增长当前位的底数
  3. 计算int b = n >= 26 ? 0 : 1解决进位过程的问题
  4. 最后将每位字母的结果累加即可

https://leetcode-cn.com/submissions/detail/46068259/

反思

看了别人的题解后发现,其实从前往后累加计算才是更加简单的解法,只需要ans = ans * 26 + num即可。

172. 阶乘后的零*

https://leetcode-cn.com/problems/factorial-trailing-zeroes/

思路

看了一下数据,一开始觉得主要计算乘的过程会有多少 2 和 5 出现即可,但是写代码的过程考虑错误,直接返回了n / 5,结果一直没有结果,最后看了题解才有了思路。

https://leetcode-cn.com/submissions/detail/46075012/

反思

对于题目还是要多研究验证,通过多个方法进行对比,可以写出更多测试样例更好,方便找规律。

解法:先把n更新n = n / 5,然后再累加计算n / 5即可。

175. 组合两个表

https://leetcode-cn.com/problems/combine-two-tables/solution/zu-he-liang-ge-biao-by-leetcode/

思路

这是一道 SQL 的题目,比较简单,就用LEFT JOIN连接两个表。

https://leetcode-cn.com/submissions/detail/46211212/

反思

跟官方题解一致

176. 第二高的薪水*

https://leetcode-cn.com/problems/second-highest-salary/submissions/

思路

还是一道 SQL 的题目,基本的方法是做了,但是一直解决不了null的问题(不存在的情况下要输出 null),最后发现需要使用临时表。

https://leetcode-cn.com/submissions/detail/46212160/

反思

不管是IFNULL或者是临时表,都是需要将原来写出来的查询作为一个子查询的。

181. 超过经理收入的员工

https://leetcode-cn.com/problems/employees-earning-more-than-their-managers/

思路

一开始就想到JOIN,还想用HAVING,其实join后只要用where查一下就可以了。

https://leetcode-cn.com/submissions/detail/46214869/

反思

更加简单的方法是直接select两个表,通过where组合一下就 OK 了

182. 查找重复的电子邮箱

https://leetcode-cn.com/problems/duplicate-emails/

思路

一开始想使用HAVING,但是没用对,使用了临时表子查询的方法。

https://leetcode-cn.com/submissions/detail/46213242/

反思

写出来的 SQL 还是没有题解的那么优雅,总算明白了HAVING的使用方式。

183. 从不订购的客户

https://leetcode-cn.com/problems/customers-who-never-order/

思路

想到使用NOT IN解题,还是比较简单的,直接把订单表的客户 ID 查出来,然后用NOT IN查一下就可以了。

https://leetcode-cn.com/submissions/detail/46215817/

反思

跟官方解法一致。

189. 旋转数组

https://leetcode-cn.com/problems/rotate-array/

思考

解题的思路比较简单,首先是不使用额外的空间,所以都是原地进行替换,但是没有想到怎么样才能不需要循环k次的方法,所以解题效果不是很理想

https://leetcode-cn.com/submissions/detail/46418437/

反思

190. 颠倒二进制位

https://leetcode-cn.com/problems/reverse-bits/

思考

不懂怎么进行二进制操作,直接把它转换成字符串,然后反转,第一次解答错了,因为忘记在后面补 0。

https://leetcode-cn.com/submissions/detail/46430183/

反思

应该使用二进制操作解题,用一个变量res去存储结果,依次得到要转换数字的低位,然后依次保存到res中。res每得到一位后进行左移腾出位置保存下一位。

191. 位 1 的个数

https://leetcode-cn.com/problems/number-of-1-bits/

思路

还是使用字符串的解法,通过转换成字符串在计算 1 的个数

https://leetcode-cn.com/submissions/detail/46432096/

反思

应该通过二进制解法将数字跟掩码1进行逻辑与运算,都可以让我们获得这个数字的最低位。检查下一位时,我们将掩码左移一位。

原文链接:https://blog.yourtion.com/leetcode-java-04.html