LeetCode打卡

今日进度:405题.

周赛106总结。
922. Sort Array By Parity II   开一个新数组，简单扫一遍，把奇数放入奇数位，偶数放入偶数位。奇数位和偶数位用两个指针维护即可。
921. Minimum Add to Make Parentheses Valid  用stack，每次遇到')'，检查stack有没有"("，没有就把计数器+1，最后返回计数器+stack的size（剩余没配对的"(")
923. 3Sum With Multiplicity  O(n^2), 外层循环k指针，内层循环j指针，在循环j前，初始化一个unordered_map  "m"，然后每次检查m[target-A[j]-A[j]]，加入答案，最后再把A[j]放入m。即m只会存着A[0]...A[j-1]。
924. Minimize Malware Spread 总体思路是查找并查集大小最小的，且感染病毒结点数量为1的合集，然后返回感染病毒的结点。分为以下步骤。
step 0: 初始化并查集，感染结点数量，size。
step 1: 扫描一遍病毒结点列表， 记录最小值， 做默认数值
step 2: 遍历graph， 连接并查集， 并且维护并查集的size。（size只需要在unite结点函数里维护，只需要保证：若x是y的parent，x的size数值正确即可，y的size不需要正确）
step 3: 扫描一遍病毒结点列表， 标记每个并查集的感染数量（只标记parent）
step 4: 扫描一遍病毒结点列表， 感染数量为1的并查集，找最大的，如果一样大，找编号小的

nyorange 发表于 2018-10-14 11:04
打卡
本周在弄树
Invert Binary Tree

欢迎交流`

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)

拿到了pure storage的offer，超级开心。不过决定还是间歇性的刷题和参加leetcode/codeforces比赛，保持大脑解题的活跃性。接下来是Xmotor的onsite，给自己加油

感觉不应该一直只要C++刷题，今天尝试了用Python刷每日一题，决定接下来把自己的刷题语言切换为Python和Java。Java相对熟练了，所以Python优先，如果一题存在两种解法，尽量Python写一种，Java写另外一种。
847. Shortest Path Visiting All Nodes
Python：
1. 使用dictionary存路径，但是dictionary的key为tuple，格式为d[(a,b)]或者d[a,b]

2. dictionary可以有默认值防止KeyError，d = collections.dict(lambda: ?)

3. 也可以用存tuple的set来记录出现的结点, s = set(), s.add((a,b))
    add = insert (unordered_set) in C++ = add (Set) in Java
    not a in s = s.find(a) == s.end() in C++ = !s.contains(a) in Java

4. 用deque实现queue，que = collections.deque(某个关于i的表达 for i in range(N))
append = push (queue) in C++ = push_back (deque) in C++ = offer (Queue) in Java = offer_last (Deque) in Java

popleft = front+pop(queue) in C++ = front+pop_front(deque) in C++ = peek +poll(Queue) in Java = peek_first + poll_first(Deque) in Java

len(que) == 0 = que.empty() in C++ = que.isEmpty() in Java

补昨天打卡 两题 + 今天1题
50. Pow(x, n)
Python3 整数除法用"//"， 只有Python2 可用"/"。
注意-2147483648取绝对值后会溢出。

913. Cat and Mouse
这题要用逆推进行BFS，先把所有状态的胜利者更新为0 （DRAW），然后把胜利结果确定的状态(mouse, cat, turn)压入queue中，并更新这些状态的胜利者(res[mouse][cat][turn])。mouse==0胜利者为mouse，mouse==cat胜利者为cat。
然后开始BFS，注意只把胜利结果不为DRAW的放入queue中，同时queue中取出的状态，只用来更新胜利结果不为DRAW的父状态。
假设父状态A->子状态 存在一条有向边。然后这个父状态一共连接了3个子状态
父状态A->B1
            ->B2
            ->B3
若父状态的turn是mouse，且某个子状态的turn是mouse的话，父状态正好轮到mouse走，mouse一定能走到胜利结果为mouse的那个子状态上。turn为cat，某个子状态胜利者是cat的情况亦然。所以turn == 子状态的胜利者时，可以立刻标记父状态并压入queue里。
若父状态的turn是mouse，且所有子状态的turn是cat的话，父状态正好轮到mouse走，mouse无论怎么走，都会走到胜利结果为cat的子状态上。turn为cat，所有子状态胜利者是mouse的情况亦然。
但问题是我们在用子状态更新父状态，如果知道一个父状态的所有子状态都是和父状态的turn有相反胜利者呢？
我们把父状态到子状态的有向边数量标记为out[mouse][cat][turn]（出度），当用一个子状态更新父状态时，若父的turn和子的胜利者相反，就减少父状态的出度。当出度减为0，说明我们已经遍历过所有父状态指向它对应子状态的边。这说明父状态里面轮到可以行走的动物怎么走都无法胜利，标记该状态并压入队列。
注意更新turn == cat的出度时，要排除掉位置0。因为cat不能走到0。

Python 913 笔记：
1. 用Yield代替return一个list，效率更高。
2. deque状态压入可以用tuple deque.append((a,b,c)) 这样效率比list高
3. 把辅助函数定义在主函数里面，可以避免使用self，写起来方便。
4. 定义parent函数，合并turn为cat和mouse的情况，可以精简代码。

今日题目记录：
33 367 243 414 532
主攻Python3 语法。
1) 如果某个数x初始值为None, 判断是否为None要用 if x != None，不能直接if x，会错
2) min函数同C++，直接用min，而不是math.min
3) for i, num in enumerate(nums)，couter在前面。
4)整数 ：// 2  或者>>1，不要写成"/ 2"
5) Unique元素
from collections import OrderedDict
nums = list(OrderedDict.fromkeys(nums))
6) if a or b, a == 0的时候会返回b
所以
if a == None:
    return b
return a
这种写法比较安全
7) 最小值:
import sys
a = -sys.maxsize
8) 当使用for key in d这种方式遍历dictionary的时候，若dictionary有lambda默认值，那么不能直接检查任意新key，因为调用默认值会影响dictionary大小，应该查 if new_key in d。否则会出现dictionary改变长度这种runtime error。
9) 获取counter个数：d = collections.Counter(nums)
10) 一行浓缩，利用sum函数
sum(k > 0 and x - k in d or k == 0 and d[x] > 1 for x in d)
可以数出所有所有为True的item个数

今晚周赛终于前100啦，开心，比赛时用了C++，现在用Python复盘一次。
1
929. Unique Email Addresses
直接brute force的string操作题。
Python语法点：
1) str.split('+', 1) 可以分解成最多2个元素， s.split('+') 可以多次分解
2) str.replace('.', '') 这可以替换、删除某个元素
3) s = set()， set小写

2
930. Binary Subarrays With Sum
解法：
一个map，初始化放入sum[0]，然后依次更新sum值，查找map，并更新map（当前sum）。事后发现sum数组应该优化为单一sum。
Python语法：
没什么特别注意点，同C++写法相近。

3
931. Minimum Falling Path Sum
解法：
普通dp，注意处理j > 0, j < m-1这两个边界情况，初始值为第一行数值。注意n==1的时候，初始化时要更新ans。
Python注意点：
1)初始化二维数组：dp = [[0 for i in range(m)] for j in range(2)] =》初始化二维的滚动数组

4
932. Beautiful Array
解法：
按照奇偶性拆分Array，因为A[k] * 2 == 俩奇数相加的和 or 俩偶数相加的和，当奇树在左边，偶数在右边时，对于任意一个数x，若x为奇数，不用担心俩偶数相加，若x为偶数，不要考虑俩奇树相加的情况，因为奇偶组已经彻底分离。这样对于奇数组，只需要考虑两个奇数相加 == A[k]，那么可以把奇数组想象成新的子问题，例如1357映射为1234，最后解法应该是一一对应的，那就相当于把原问题分解成了两个子问题。N折半了。
注意最后边界是N==1，一开始的时候写了一些多余边界，比赛时顾虑到AC率。不过事后还是优化到了N==1 1个边界。
Python 解法:
[2*x-1 for x in solve(mid)] + [2*x for x in solve(N-mid)]， Python的倒装回溯方式能写的很简练。

昨天补卡：
这题的思想主要是在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

这几天忙的没打卡QAQ。回头补上。今天又来了offer，两个compete中，希望最后能有个好选择…
来offer了所以有一丢丢松懈，不过周赛和每日一题还是要保证的，大半年练出来的手感不能丢，鼓励自己！！