7月缺米的来刷题/Mock interview活动

0704 Day4 打卡四题

1504. Count Submatrices With All Ones，DP，在每个mat[i, j]，统计以此处为右下角的矩形的个数，具体来说，用dp[i, j, 0]记录mat[i, j]左边有多少连续的1，dp[i, j, 1]记录mat[i, j]上边有多少连续的1，那么以mat[i, j]为右下角的矩形的个数为sum_{k=0}^{k<dp[i, j, 1]}(min_{i-k<=x<=i}dp[x, j, 0])
1503. Last Moment Before All Ants Fall Out of a Plank，trick question，只要比较往右走的蚂蚁中最左边的 与 往左走的蚂蚁中最右边的 掉落时间即可，当两只蚂蚁碰面时，想象他们只交换了各自的id，并不会影响他们的行动方向
1502. Can Make Arithmetic Progression From Sequence，sort，one-pass check   
264. Ugly Number II，注意到第n+1个ugly number一定是通过前n个数乘以2/3/5得到的，于是可以直接构造。使用三个pointer分别跟踪最小的未被2，3，或5乘过的ugly number，每次直接比较nums[idx2]*2, nums[idx3]*3, nums[idx5]*5即可

07/04 第四天 三题 今天参加了周赛
判断能否形成等差数列 只需求前两个数的差 然后判断后面相邻两个数差是否等于该值
所有蚂蚁掉下来前的最后一刻开始被第二题卡住了 不过最后想明白了  转变方向后可以等效看作继续向前 因为距离总的是等价的 所以排序后在 取两端时间较大即可
丑数2 实际上可以等效为构造序列 每次由前面的数乘以三个因子 然后取较小值 更新三个指针

七月第五天

今天还是菜
1. ugly number II: 在july challenge里面，之前做过这道题结果今天也不太记得了lol，ugly number 都是之前的ugly number乘以
    2/3/5，所以可以用ind2, ind3, ind5分别表示2，3，5的数量，每次选最小的，num = min(dp[ind2]*2, dp[ind3]*3, dp[ind5]*5),
    再把对应的indices加一，直到排到n个数
2. arranging coins：这个用binary search做的但是好慢，也可以直接算，constraint是k*(k+1)/2<=n, complete square 之类的也能算
3. valid triangle number: 这个有点类似three sum，先把array sort一下，从第三个数开始，把每条当成三角形最长的边，
    然后再左边的value里面用two pointer，如果nums[left] + nums[right] > nums[ind], 就说明可以组成三角形，同时在left右边的value
    也可以组成三角形，所以每次res += right - left，再把right向左移，不然的话向右移left找三角形
4. toeplitz matrix: 如果每个元素和左上角元素相等，就是toeplitz，所以只需要用double loop检查matrix[i][j]是不是等于matrix[i-1][j-1]
5. longest repeating character replacement: 学了一下sliding window，用一个array 记count，end - start + 1就是当前window size，
    每次update maxCount，如果window大小减去maxCount大于k，就往前挪，每次也要update max length

第四天打卡
今天刷了5题

Before All Ants Fall Out of a Plank
Can Make Arithmetic Progression From Sequence
Friendly Movies Streamed Last Month
Clone N-ary Tree
Ugly Number II

我还是怕二维数组，周赛出现二维数组，我看了看，就没心思做了。这方面一直没有搞透。

今天刚看到这个帖子，是我刷题的第一天

今天刷了三道SQL Hard题目

第一题：615. Average Salary: Departments VS Company
稍微卡了一下，想一下子写出来，还是需要先把每个月公司的平均收入算出来，再把每个月每个department的平均收入算出来，JOIN起来再CASE WHEN 就行
第二题：579. Find Cumulative Salary of an Employee
这个题没写出来，学到了一种新的行处理的办法，通过 ROWS PRECEDING来把行往后计算，另外一种方法是根据BEWTEEN来JOIN，这个要在select 和group by 看清楚到底是哪个table里面的数据
第三题： 262. Trips and Users
还算简单，通过JOIN和CASE WEHN 判断条件就行了

今天刷的五道题：
14, 125, 151, 347, 209

Day 3打卡 7/4 LC8题

07/04
4题
开始向dp进军

打卡第一天

三题
201 202 203

打卡第一天 2020.07.05
1010. 总持续时间可被 60 整除的歌曲 https://leetcode-cn.com/problems ... ns-divisible-by-60/
605. 种花问题 https://leetcode-cn.com/problems/can-place-flowers/

解题思路：
1010 题，一开始想着两层遍历，复杂度在 O(N^2) 了；后面用额外的一个数组seconds来记录余数的个数，并且单独处理余数大小为 0 和 30 的情况，这两种情况下可以看作是简单的组合数了（在k个数中任找2个数进行组合），个数为 k*(k-1)/2；剩下的情况就是前后一起遍历数组 seconds[i++]*seconds[j--] 直到 i>=j时。

605 题，这道题可以用贪心算法解决，从前往后遍历，遇到0之后，判断前后是否都是0，如果是，那么这个位置上就可以种花了，计数器相应的增加；不过要单独考虑一下首尾两个位置的情况，只要一边是0就可以满足要求。