刷题记录帖子

LC 171 Excel Sheet Column Number

Easy 题，就是 26 进制题目的变体。

不过写法上，其实也有点讲究，更好地解法不是一遍遍计算 26^n 的结果，而是应该这样，

不过实际检验下，发现其实也没多大优化。。。估计是太短了，同时其他计算才是主要部分。

274. H-Index， 275. H-Index II

两个题目其实是一个思路，都是找到何时的 cut-off value

题目的定义非常不清晰，推荐这个视频的讲解 https://www.youtube.com/watch?v=CjKJDloMnwE，其实就是找到一个 max M 使得有大于 M 的 paper citations >= M.

M 其实有一些列的值都可以，找这些当中最大的那个。

需要注意的是 Bisect 的时候，第二种 case 的考虑

代码值得记忆，

还是接昨天的题目，发现可以用 基数排序( ) 因为可能的范围就是 【0，n】 当然也要做一个简化。就是凡是大于 n 的值，都统计在 n 那个 桶。

参考这个视频，讲解的很好。

https://maxming0.github.io/2020/08/11/H-Index/

LC 119 Pascal's Triangle II

我的解法虽然简化了空间使用，但是还是没有这个解法好， https://maxming0.github.io/2020/08/12/Pascals-Triangle-II/

原地修改 prev 行的数组，但是如果正向求和会改动原始的记录，但是如果倒着求和就可以解决， 因为每次相加得到的后一个结果不会影响前面的数字。

参考代码，这个代码的重构也很好，很多 edge case 可以合并。

LeetCode 409 Longest Palindrome

这道题目其实是个纸老虎，看着要 DP 但是仔细研究条件，

“find the length of the longest palindromes that can be built with those letters.”

== > 这个是不要求字符串顺序的，那就瞬间 easy 题了。

直接统计每个字符出现的次数，然后偶数直接全部使用，奇数减一就是偶数即可使用，当然最后要知道如果动用了奇数，只能有一个奇数字符多出现一次，作为中心。参考视频， https://www.youtube.com/watch?v=DJJbgeJBIGc&t=0s

代码如下，

LC 967 Numbers With Same Consecutive Differences

这个就是 BFS 的变体，但是如何简洁地得到答案，写出精炼的答案，还是需要打磨自己的结果。

本来考虑用 list 去存 每位的数字，然后 combine 起来，这个 %10 取末位 digit。

参考这个帖子还是感觉收获很多的，
https://maxming0.github.io/2020/ ... cutive-Differences/

主题里面 edge case 的处理，

824. Goat Latin

简单题，但是如何把答案写的简单明了就不容易了，官方的 答案，相当硬核，easy 题的 hard 做。。。学习下，
通过 Python 切片做选择， string 可以直接索引，不需要转换。
同时简化合并多余的 if-else 分支。

1. 
   
2. class Solution:
   
3.     def toGoatLatin(self, S: str) -> str:
   
4.         def proc(idx, word):
   
5.             if word[0] not in 'aeiouAEIOU':
   
6.                 word = word[1:] + word[0]
   
7. 
   
8.             return word + 'ma' + ('a' * idx)
   
9. 
   
10.         return ' '.join([proc(i, w) for i, w in enumerate(S.split(), 1)])
    
11. 
    

复制代码

824. Goat Latin

简单题，但是如何把答案写的简单明了就不容易了，官方的 答案，相当硬核，easy 题的 hard 做。。。学习下，
通过 Python 切片做选择， string 可以直接索引，不需要转换。
同时简化合并多余的 if-else 分支 == > 虽然题目说了 两个分支，但是可以合并成一个 if 就可以了。

1. 
   
2. class Solution:
   
3.     def toGoatLatin(self, S: str) -> str:
   
4.         def proc(idx, word):
   
5.             if word[0] not in 'aeiouAEIOU':
   
6.                 word = word[1:] + word[0]
   
7. 
   
8.             return word + 'ma' + ('a' * idx)
   
9. 
   
10.         return ' '.join([proc(i, w) for i, w in enumerate(S.split(), 1)])
    
11. 
    

复制代码

Leetcode 905. Sort Array By Parity

https://leetcode.com/problems/sort-array-by-parity/solution/

简单题，其实比较难的是 in-place transform。

参考这个答案，

Approach 3: In-Place
Intuition

If we want to do the sort in-place, we can use quicksort, a standard textbook algorithm.

Algorithm

We'll maintain two pointers i and j. The loop invariant is everything below i has parity 0 (ie. A[k] % 2 == 0 when k < i), and everything above j has parity 1.

Then, there are 4 cases for (A[i] % 2, A[j] % 2):

If it is (0, 1), then everything is correct: i++ and j--.

If it is (1, 0), we swap them so they are correct, then continue.

If it is (0, 0), only the i place is correct, so we i++ and continue.

If it is (1, 1), only the j place is correct, so we j-- and continue.

Throughout all 4 cases, the loop invariant is maintained, and j-i is getting smaller. So eventually we will be done with the array sorted as desired.

LC 497 Random Point in Non-overlapping Rectangles

u1s1,我看错题目了，参考这个帖子看懂题目发现还是比较简单的, 题目描述的太委婉了，

write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

这句的含义展开来，居然是，按照 每个矩形的point 数选择 rect ，再随机返回。我还特点用 set 排除。

参考这个帖子， https://maxming0.github.io/2020/ ... lapping-Rectangles/

后一种解法很好，善于使用 Python 内置的函数巧妙解决。