缺大米的请参加这个刷题/Mock interview活动

Day 8, 06/10/2020, Two pointers, 3 solved.

今天刷了5题，不过有几题很难理解。首先是super egg这题，暂时还不能领悟Lee大神的思路，还得再看看。其次是merge stone实在太难了，但居然还是要考，不懂哪个人出这种题目。

第八天 嘻嘻~
368. Largest Divisible Subset 需要先sort，然后在DP，直接DP并不能优化时间复杂度。

打卡 9 天
1. Swim in Rising Water : c++ priority_queue is implemented in maxHeap, so {-time, y*n+x} can make the smaller at front. x= node.second%n, y=node.second/n;
2. Reverse Nodes in k-Group: First write the reverse function, newHead = reverseKGroup(a, b), a->next = reverseKGroup(b, k)
3. Network Delay Time: Floyd_Warshall traverse all the pairs.

今天刷的六道题：
1） 在按升序排列的数组中，查找第一个比指定参数大的数。可以直接查找，也可以使用binary search。
2） 在不使用乘除法的前提下计算两个整数的差。这里有一个数字溢出的细节，可以表达的负数比正数的相反数小1，需要特别计算。可以依次将被除数乘二，来减少查找次数。
3） 返回二叉树下的所有路径：这个题比较直接。使用DFS就可以。注意处理树为空的特例
4） 返回一个正整数每一位数字的和。因为答案只可能是0到9， 所以是一个周期循环的问题。除了特例以外，就是对9的余数。
5）找出ugly number。按照定义直接判断
6） 判断一个字符串是否可以是回文字符串。使用哈希表对出现的字符计数。Time Submitted        Question        Status        Runtime        Language
6 minutes ago        Palindrome Permutation        Accepted        20 ms        python
12 minutes ago        Ugly Number        Accepted        12 ms        python
27 minutes ago        Add Digits        Accepted        28 ms        python
53 minutes ago        Binary Tree Paths        Accepted        16 ms        python
53 minutes ago        Binary Tree Paths        Runtime Error        N/A        python
54 minutes ago        Binary Tree Paths        Runtime Error        N/A        python
1 hour, 17 minutes ago        Divide Two Integers        Accepted        36 ms        python
1 hour, 18 minutes ago        Divide Two Integers        Wrong Answer        N/A        python
2 hours ago        Search Insert Position        Accepted        60 ms        python

今天做了一道coin change 的题，觉得非常有意思。最近陆续接触了几道knapsack的问题，本质上是优化问题，解决办法就是通过dynamic programming来一步步找到最终解。凡是能用recursion解决的问题，都能转化成DP.

day5_coding.rar (11.46 KB, 下载次数: 0)

2020-6-11 13:05 上传

点击文件名下载附件
day5
下载积分: 大米 -1 颗

Day 5:

1. Number of Islands.
2. Unique Paths.
3. Triangle.

Day 6:

Did 5 problems today.. Mostly DP

6.10打卡四题

1425. Constrained Subsequence Sum： 解法为DP，可以使用Deque优化，快速从前k个candidate中找到最大值
35. Search Insert Position： Leetcode June Challenge， Binary Search基础题
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit：解法为Sliding Window，难点在于要快速找到（O(1)）滑动窗口的过程中的最大最小值，使用monotonic deque可是实现此目的（可参考Leetcode 239 Sliding Window Maximum）
636. Exclusive Time of Functions：Stack的应用

06/10 第九天 继续继续

每日温度 如果从前向后 需要记录多个位置 但如果从后向前 那么只需判断后面一个就行 可以看作类似动态规划
对称的二叉树 利用第归 分成三种情况 左右均空 左右其中一个空另一个非空 左右均不空 需要直相等并且 左右子树对陈
验证外星语词典 字符串转换成字符数组 然首遍历解决