LeetCode打卡

开始打卡激励自己。

昨天补卡：
这题的思想主要是在a^2+b^2 == t^2 == c的寻找过程中，逐渐增加a，若是看成一个圆形，坐标(a, b)，半径为t的话，可以发现只需要检查y轴到y=x这条线之间45度角的范围。且在那段范围里，若每次a+1, b要么保持不变，要么b-1， 因为圆上切线斜率<=1，所以b减少的比a增加的要少。
为了减少乘法次数。先计算起始的a^2+b^2 = 0*0 + int(sqrt(c)) * int(sqrt(c))，然后逐渐增加a。减少b
可以利用(a+1)^2 +b^2 = a^2 + 2a + 1 +b^2，快速从a^2+b^2 => (a+1)^2 +b^2
可以再次利用(a+1)^2 +(b-1)^2 = a^2 + 2a + 1 + b^2 - 2b +1，快速从(a+1)^2+b^2=>(a+1)^2+(b-1)^2。
c++风格：
class Solution {
public:
    bool judgeSquareSum(int c) {
        int a = 0, b = sqrt(c), t=b*b;
        while (a <= b) {
            if (t == c) return true;
            t += 2*(a++)+1;
            if (t > c) {
                t -= 2*(b--)-1;
            }
        }
        return false;
    }
};

Python风格：
这个注意，a和t可以连等，哪怕进行了a = a+1这样的操作，这两个操作平级，不互相干扰，可交换顺序
class Solution:
    def judgeSquareSum(self, c):
        a, b = 0, int(math.sqrt(c))
        t = b*b
        while a <= b:
            if t == c:
                return True
            a, t = a + 1, t + 2 *a + 1
            if t > c:
                b, t = b - 1, t - 2*b + 1
        return False

今日打卡：
19. Remove Nth Node From End of List
此题我用的方法和标准答案不太一样。因为N是到list end的距离，所以递归后再更新距离。
C++我是传了一个x 引用，Python不能做这样的操作，不得已用self.x，object里面的全局变量x记录距离。Java也可以用class里面的全局x，但不需要self这样的前缀。
class Solution:
    def removeNthFromEnd(self, head, n):
        self.x = 0
        def remove(node):
            if not node:
                return None
            node.next = remove(node.next)
            self.x += 1
            return node if self.x != n else node.next
        return remove(head)

补充内容 (2018-10-30 02:54):
昨天题目题号：633. Sum of Square Numbers

补充内容 (2018-10-30 10:03):
19。后来看了答案的双指针法，也很好。注意点时n == list的长度时，要有一个dummy(空head)结点，双指针从那里开始走，才能成功删除head结点，还要注意通过设n==1，检验退出条件是count < n还是count<=n

今天复盘了一下周赛，和一些矩阵、dp题。
周赛105：
1-LC917   两端双指针brute force
2-LC918   Maximum Sum Circular Subarray,  转化为sum前缀和求区间最小，单调增deque，从头顶取最小值即可。保持增是因为后面的元素Y会block掉前面>=Y的元素X。
3-LC919  模拟赛的时候太困写的很繁琐，总体思路是保持两个queue/vector，一个是父结点层，一个是未来的父结点层。讨论一下complete和In-complete两种情况。重写时用的是vector/index模拟queue，可以避免父结点层遍历完后还得把结点放回去。
4-LC920  一开始忽略了所有歌都要出现一次这个条件，之后用的dp。
dp[i][j]: i首歌，填满j个位置的方法数量。位置和歌的编号从1开始。
1) 位置j上的歌之前没出现
    i * dp[i-1][j-1]   (位置j上的歌一共i种可能，剩下(i-1)首歌要填充剩余(j-1)个位置)
2) 位置j上的歌之前出现过
    (i-K) * dp[i][j-1] (位置j上的歌一共i-K种可能, i首歌要填充j-1个位置)

LC84、85：
最早使用的是单调栈双向扫两遍的通解方法。重新尝试了单向法。最精妙的地方时计算不是发生在一个元素被压入栈前，而是发生在元素被弹出栈时。弹出元素Y的时候，查看前一个元素X(<Y的最近元素），同时因为Y是由某个<=Y的Z导致发生了弹出，所以Y的右半边也得到了考虑（相当于第二遍反向扫）。
之前我比较担心右半边发生的是<=而不是精确的<。但后来通过例子发现这不影响答案。

例如:   1 3 3 1
压入第二个3的时候导致前面的3弹出，此时计算的出来的矩阵面积为3，但其实以第1个3为高的矩阵最大是【3,3】（面积6）。
如果有这种高连续相等的情况，压入最后的1的时候，必然能得到矩阵面积6。因为单调栈单调递增，第1个3已经被第2个3导致弹出。
也就是说，若是按照双向扫描（两边查找<当前高的边界）理解这道题，一串连续相等的高，其实只有最右的高，被计算出了有意义的面积数值。
当然也可以把单向扫描法中压入栈的元素理解成exclusive右边界，面积理解为这个右边界以左的最大面积，这样理解的话，每一个时刻的面积值其实都是有意义的。相当于不断拓展右边界。
注意：最后需要加虚拟-1右边界，使得前面的元素发生弹出。

LC363
目前只想到了O(n^2mlogm)的解法，如果n比较大，可以选择换个方向O(m^2nlogn)
利用前缀和area[i][j](从matrix[0][0] ... matrix[i-1][j-1])
总觉得很慢还可以优化。。

LC621
使用一个banned队列记录当前不能实施的任务，在时间合理后更新priority queue， priority queue会把数量较大的任务前置。基本上来说是一种贪心做法。

LC 265. Paint House II
周日模拟面试的时候试了这道题。我定义的状态不太一样。解起来没问题，就是很难在白板上描述。
非常规定义:
//dp[i][j]: 涂第(i-1)个房子，不用颜色j的最小cost
//dp[i][j] = min(dp[i-1][k]) + costs[i-1][j];
注意处理只有1种颜色，1个房子的特殊情况-> cost[0][0]
时间效率优化：只需要记录最小值和第二小值。
用prev_id, prev_min, prev_min2还有now_id, now_min, now_min2分别标记上一行和当前行的最小值的列，最小值，和第二小值。
注意首行初始化！！
注意优化完时间后，可以把空间优化为O(1), 用dp表示dp[i][j]。

Codeforces 模拟赛 512-Div.2 总结
A In Search of an Easy Problem  - 找到1个1就标记flag并退出，然后根据是不是至少出现一个1输出答案。
B Vasya and Cornfield - 基本上只要落在[0,0,n,n]正方形区域外部，或者斜长方形旁边的4个小三角形里，就不在斜长方形里面。小三角形都是等边三角形，以45度角为基准，到那个顶点的x方向距离<y方向距离即可.
case 1：左下角小三角
if (x >= 0 && x < d && d - x > y) flag = false;  
case 2： 左上角小三角
if (d < y && y <= n && n - d - x > n - y) flag = false;
case 3：右上角小三角
if (n - d < x && x <= n && x - (n-d) > n - y) flag = false;
case 4:   右下角小三角
if (d < x && x <= n && x - d > y) flag = false;
case 5:  正方形外面
if (x < 0 || x > n || y < 0 || y > n) flag = false;

C - Vasya and Golden Ticket
记录所有数值的sum，观察发现sum <= 9 * 100 = 900，900以内的数如果做因式分解，产生的组合特别有限。
1）特殊处理sum为0的情况（即所有digits为0，那么怎么切分都可以）
2）快速处理出900以内的prime number，用not_prime bool数组和primes vector记录
3)  用这些prime对sum进行因式分解，因子和因子数量存进一个vector
4）dfs，尝试所有可能的能被sum整除的数（除了sum自己），只要有一个可以就返回true
5）写一个ok函数，它能把ticket按照这个数进行切分，看可不可以

D
先讲讲比赛时候的做法。
题目要求找x、y为整数的点使得形成的三角形面积小于n*m/k (2<=k), 但点的x数值必须在[0,n]之间，y数值必须在[0,m]之间。最早的想法是直接把三角形弄两条直角边放在x轴和y轴上，面积为nm/2，但不能证明“如果这种做法找不到解的话，选取别的位置也一定没有解”。先脑部一个任意位置的三角形已经满足条件（都是整数点），然后把三角形向下向左平移整数距离直到两个端点和x轴和y轴碰上。这样能确保所有坐标数值对比原来的三角形要么不变，要么变小，原来坐标若不越界，那么新变换的三角形也一定不越界。（旋转不保证坐标不越界）
若是平移后，d > a，那么以y = (b+c) / 2为对称轴做镜像对称，可以使得新得到的三角形d' < a'，且坐标还是不越界（坐标都被限制在变换前[0,0, a, a]这个矩阵中）
极端情况：b = 0， d = 0等不影响计算面积。
a(b+c)-ab/2-dc/2-(a-d)(b+c)/2 = n*m/k
化简得:  ac+bd = 2nm/k
因为a, c, b, d为整数，那么 k | 2nm.
1) 若k为奇数
把k 拆解成 g1, g2使 g1 * g2 == k  而且 g1 | n +  g2 | m
g1 = gcd(n, k)
g2 = k / g1
因为k >= 2, g1, g2必然有一个>=2, 若g1 >= 2
a = n / g1 * 2
c = m / g2
若g1 == 1, g2 >= 2
a = n / g1
c = m / g2 * 2
2) 若k为偶数
直接 k = k / 2 然后拆解k成g1 g2
a = n / g1
c = m / g2

E、F、G模拟赛时来不及看。。下次看看能不能做

补充内容 (2018-10-15 02:54):
D题最后发现，b和d就是可以永远为0也能找到答案...

补充内容 (2018-10-15 03:00):
忘了说明D题平移加镜像变换后顶点为(a, 0)  (0, b) (d, b+c)

73. Set Matrix Zeroes
3. Longest Substring Without Repeating Characters
334. Increasing Triplet Subsequence
163. Missing Ranges

明后天48h的面试，刚开始打卡就要暂停了。督促自己周六继续刷。
今日总结：
73 - 内存要求In-place时可利用已有空间，但注意这部分空间定义上的改变，涉及到这部分数据的修改或者查看要小心是否冲突
3 - 及时记录所有一闪而过的想法，从中拓展。
334 - 题目中如果刻意提到一些常数（如Triplet），可能在暗示能用非数组的常数变量解决问题
163 - 注意int overflow，应该向考官咨询

重新恢复打卡。争取9月份前满300。
8.13 274

8.13
最新进度283。
看到讨论区的时候，对自己代码的冗长和易读程度很失望，就怕因为冗长当场会来不及完成。感觉自己还是太心急了，当答案和自己的解法效率相近就会偷懒不愿读。
绝对明天从主做改成主看，特别是得观察下自己这几天做过的题，其他人是怎么精简代码和保持可读性的。

8.17
最新进度300题。完成了一个小阶段目标。接下来争取多看些新题新思路以及训练mock interview。

最近注意到的一些薄弱点：
1. LinkList, Double Linked List和BinaryTree，操作性比较强的题容易细节出错。
2. 解法含Greedy思维的题，这部分题比较刁钻，也很散乱，目前还是只能多想、多看题解、多总结
3. 利用Heap对时间的某一部分进行LogN优化的各种题以及变种，能解决3-4种常规的，但遇到新类型还是会卡。
4. 利用单调deque/stack，能把O(n^2)、O(nlgn) 优化到O(n)的题，每次隐约觉得跟这个类型沾边的新题，容易想不出合适的构造方法。
5. 和随机性、启发式思维沾边的题，还没习惯，容易蒙圈。

当前进度305。
练了一阵子英语和mock up，最近没刷题。今天开始重新打卡。
之前面试被坛子里的内推人拒绝了。感觉自己项目这块还有些薄弱。
从今天开始，减少刷题量，把重心转移到项目上，争取修改的简历能过简历关。

今天开始刷题，打卡。