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

7/8/20

1143 Longest Common Subsequence
双序列dp，可以用滚动数组优化空间

221 Maximal Square
简单想到的是用presum但是时间复杂度有O(n*m*min(n, m))
DP优化到O(n*m)，可以用滚动数组空间优化到O(min(n, m))
dp[i][j] = maximal length of square with matrix[i][j] as the lower right corner
if matrxi[i][j] = 0, dp[i][j] = 0
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

155 Min Stack
要求O(1) time for all operations，再用一个stack存min

今天的三题

• 3Sum 要点是先排序，然后loop第一个元素，后面两个元素和就成了2sum, 用双指针就好了
• Minimum Cost to Make at Least One Valid Path in a Grid 要点是Dijkstra algorithm, 维护一个dist 矩阵存到每个方格的最小dist
• Count Submatrices With All Ones 单调栈，维护一个height array 记录当前column的height， 同时维护一个sum array 记录以这个column 为右边的matrix的个数
  

打卡第三天。
1. 关键在于确定interval的左右情况， 用min， max确定interval，最后确定右边界情况
2. 读文件， stack的应用
3. 2的变形，stack的应用加上属性

7.8 打卡

1. Coin path. DP，关键是要用一个next 数组维护路径。
2. Form Largest Integer With Digits That Add up to Target. DP, 问题关键是首先用dp找1 - target范围内每个target能组成的最多的数，接着从后往前找最大的数。
3. Digit Count Range. 关键一步是count[i, j] = count[0, j] - count[0, i - 1].  问题转化成类似于Number of Digits one 类似的问题

美东7/8 打卡第二天
250
主要原因还是对递归理解不深，注意 1需要了解到左子树和右子树已经是Univalue子树的情况下 只需要比较root和左右子树的值即可判断 2采用第二种传父值方法时，需要在左右子树都为uni子树 同时当前节点与传过来的父值相等时才可以返回true
99
注意1. 需要换的前后两个点的判断条件不一样 2.inorder的循环写法 3.morris循环法（头太疼了不想看 大致看了看明天继续仔细研究
96
dp 不算难 没什么感想

另外推荐大家不着急面试的买个中文版会员啊 79一个月 内容一样 解析还贼详细

7月打卡第五天，5道， 404， 653， 783，993， 606

打卡第五天，麻烦楼下的朋友们记得加米谢谢了

Palindrome Partitioning DFS + Backtrack 比较标准的练手题
Subset
Subset II

Easy Greedy:
Lemonade Change
一个简单的Amazon Tag，找第一大和第二大数的题
Maximum Product of Two Elements in an Array

Leetcode July Challenge
Three SUM --> O(N^3) Brute force -> O(N^2) TwoSum + 外面一个for loop 要注意二种重复情况，
第一个是 [-3,1,1,2,2,]  -3 会找到 [-3,1,2] 这时候左右指针同向移动，又会发现一个 [-3,1',2']，这个时候就需要如果找到一个满足条件的答案，需要移动左右指针直至没有重复元素。
第二个也是类似 在for loop 那一层需要判断是否和前一个数字重复,不然就会出现 使用了相同数字作为-C 这个target, 再上一个相同数字的时候你已经找到了答案  A+B = -C

打卡 7.8 Day8
今天刷了binary search的practice 题以及 July challenge：3Sum 共计6题

20200707:
3: 0015, 0235, 0236, 0419, 0708
4: 0295
5: 0480