刷题记录帖子

Leetcode 231. Power of Two,  8/30 June

补充一个解法，发现还可以利用 n&(-n) == n 来判断

因为负数的表示是这样的

在计算机中，负数以其正值的补码形式表达
什么叫补码呢？这得从原码，反码说起。
原码：一个整数，按照绝对值大小转换成的二进制数，称为原码。
比如 00000000 00000000 00000000 00000101 是 5的 原码。
反码：将二进制数按位取反，所得的新二进制数称为原二进制数的反码。
取反操作指：原为1，得0；原为0，得1。（1变0; 0变1）
比如：将00000000 00000000 00000000 00000101每一位取反，得11111111 11111111 11111111 11111010。
称：11111111 11111111 11111111 11111010是 00000000 00000000 00000000 00000101 的反码。
反码是相互的，所以也可称：
11111111 11111111 11111111 11111010 和00000000 00000000 00000000 00000101 互为反码。
补码：反码加1称为补码。
也就是说，要得到一个数的补码，先得到反码，然后将反码加上1，所得数称为补码。
比如：00000000 00000000 00000000 00000101的反码是：11111111 11111111 11111111 11111010。
那么，补码为：
11111111 11111111 11111111 11111010 + 1 = 11111111 11111111 11111111 11111011
所以，-5 在计算机中表达为：11111111 11111111 11111111 11111011。

作者：FantJ
链接：https://www.jianshu.com/p/6c518e7b4690
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

当然，你正常不会这么写，因为比如对于 Java 8 bit 的整数表示范围都是 2^8 - 1 ~ -(2^8) 所以不需要担心超过的问题。因为这样的情况下，只有一个可能是全部 111111 的，那就是负数。。。事实也对得上。

LC 35. Search Insert Position 刷题基操了，binary search 因为 sorted array
然后就是找到返回下标，找不到返回 left。当然相应的写法需要匹配，mid +- 1, left <= right

LeetCode 75 Sort Colors, 还是比较经典的 one-pass 都知道需要交换，但是具体怎么交换还是充满了小技巧的。不然很可能程序不通过，所谓知易行难，只有知行合一才是最好的方法。
还是要稳一手。
Debug 了半天。
One-pass 的核心就是建立两个 stack 一个在低位，确保 0 都在正确位置，一个在高位确保 2 都在正确位置。

LC 1029. Two City Scheduling

Greedy + DP

Greedy 告诉大家如何找到排序依据，其实就是 —— 如果全去 A，再根据差值（A-B）从小到大排序，所以前面去 A，后面去 B。因为前面差值小，后面差值大，所以前面都去 A 这样会更小。

DP：

1.         
   
2. 
   
3.         # dp[i][j]
   
4.         # Among the first i people :
   
5.         #                   j people will go to A city
   
6.         #                 i-j people will go to B city
   
7.         # this will lead to N+1 and N+1 and diag format since
   
8.         # the dp matrix is symetric
   
9.         # dp[0][0] = 0
   
10.         # dp[i][0] = sum(cost_B) since no one to A
    

复制代码

参考了，https://www.youtube.com/watch?v=3A98vh5zsqw&feature=youtu.be，

LC 1029. Two City Scheduling  

值得注意的是，DP 的初始值最好是特别大的值，这样才能保证得到最优的结果，否则按照之前的设置会出现岔子。

1431. Kids With the Greatest Number of Candies Easy 题目感觉周赛凑数的。
理解题意，就是加上 extra 能不能大于 max
1464. Maximum Product of Two Elements in an Array 也是周赛凑数题目。
就是找到第一和第二大的元素。

380. Insert Delete GetRandom O(1)  
其实这道题目最难设计的是 delete， insert 直接插入最后，GetRandom 得到 total number 然后利用字典下标查找都是可以实现 O(1) 的。

那么其实实现就是如何删除，因为 array 删除会引起下标的移动，所以最好的方法就是这里的方法，利用最后一个元素 ( 选它是因为方便得到下标，你前面已经记录了总共有多少元素。当然也可以用头元素)——然后覆盖被删除元素。

当然如果本身就是删除最后一个元素也没关系，其实啥都不用变，你就自己覆盖自己吧，然后再被删除就行。

1450. Number of Students Doing Homework at a Given Time

Easy 题目，估计也是周赛流出来凑数的题目，直接比较 t1,t2 和 queryTime 对比。
Python 学到的一点就是可以用 zip 来写，这样可以同时遍历两个 list 写的代码更 Pythonic。

LeetCode 368  Largest Divisible Subset
经典的一维 dp，参考了这个讲解， https://www.youtube.com/watch?v=8tDM_pfmlrw&t=1020s
第一个要素是，排序，这样减少了整除的大小考虑。
第二个最关键的部分就是，你只需要考虑 i th 元素的结果是对于 前面 0 ~ i-1 的结果加上一个的结果，主要原因是整除，只要考虑最小的那个元素可以整除 set 里面最大的那个就行，因为一个可以整除的 set 可以表示成最小元素的倍数。

当然我喜欢这个解法，非常清晰，https://www.youtube.com/watch?v=21tD6yXc0LM&t=3s