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

坚持打卡第5天， 参加周赛1  Water Bottles， 算术题， 注意空瓶子转化公式推导
2 Number of Nodes in the Sub-Tree With the Same Label DFS深度优先搜索，helper函数返回26个字母每个的count
3  Maximum Number of Non-Overlapping Substrings 贪心算法，先找到每个character的左右便捷，然后根据题目规则，左右延伸range,直到生成一个合法的substring.
4 Find a Value of a Mysterious Function Closest to Target 前缀和+暴力枚举注意提前终止loop，因为函数的定义，是字符串位取与&，所以preSum是单调变小的
5  Course Schedule II 宽度优先搜索BFS + 记录每个node的入度
6  Add Binary 双指针 从后往前按位模拟计算，记录carry位

7/19 Day 9 打卡

#287 - Find the duplicate number
这次用了Floyd's Tortoise and Hare - cycle detection

day1
二进制的操作

single-number-ii
        给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
single-number-iii
        给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
number-of-1-bits
        编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
counting-bits
        给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
        另外一种动态规划解法

今天刷了3题，最新的contest第三题medium还不知道怎么做，想了不少时间
Number of Nodes in the Sub-Tree With the Same Label
Water Bottles
Add Binary

day 16

mock 是shortest path， 面试官问我如果不能用bfs怎么办，呆掉。。。

lc 10+
Linked List Random Node   5 minutes ago
AcceptedjavaPancake Sorting   8 minutes ago
AcceptedjavaGame of Life   26 minutes ago
AcceptedjavaTop K Frequent Words   3 hours, 48 minutes ago
AcceptedjavaBurst Balloons   4 hours, 2 minutes ago
AcceptedjavaBurst Balloons   4 hours, 19 minutes ago
AcceptedjavaTwo Sum IV - Input is a BST   5 hours, 13 minutes ago
Wrong AnswerjavaTwo Sum IV - Input is a BST   5 hours, 14 minutes ago
AcceptedjavaTwo Sum IV - Input is a BST   5 hours, 16 minutes ago
Runtime ErrorjavaTwo Sum IV - Input is a BST   5 hours, 17 minutes ago
Wrong AnswerjavaTwo Sum IV - Input is a BST   5 hours, 22 minutes ago
Runtime ErrorjavaTwo Sum IV - Input is a BST   5 hours, 23 minutes ago
AcceptedjavaMaximum Number of Non-Overlapping Substrings   5 hours, 46 minutes ago
AcceptedjavaMaximum Number of Non-Overlapping Substrings   8 hours, 17 minutes ago
AcceptedjavaNumber of Nodes in the Sub-Tree With the Same Label   8 hours, 47 minutes ago
AcceptedjavaNumber of Nodes in the Sub-Tree With the Same Label   9 hours, 12 minutes ago
AcceptedjavaNumber of Nodes in the Sub-Tree With the Same Label   9 hours, 13 minutes ago
Wrong AnswerjavaNumber of Nodes in the Sub-Tree With the Same Label   9 hours, 16 minutes ago

714. 买卖股票的最佳时机含手续费 dp问题真的完全没头绪。。
看了解答，stock交易问题可以将第i天的状态分解成第i-1天状态操作后的结果
914. 卡牌分组
bucket count后求最大公约数即可
上班没太多时间写
求加米~

刷了一下午题，又累又晕。

谢谢各位大佬给分，继续努力. 继续给楼上的3位努力的同学加分。

D18：  打卡第18天 (UTC: 20/07/2020)

继续学习 dp

1 climbing-stairs （70）

状态：dp[i]走到i点的方案数
转移方程：dp[i] = dp[i-1]+dp[i-2]，因为只能走一步或者两步，所以只能从前一个或者两个格子过来。
初始化：dp[0] = 1;dp[1] = 1;dp[2] = 2
结果：d[n]

2 Jump game (55)
状态：dp[i]，是否能从起点跳到i点

取决于前面是否存在点j：

从起点是否能跳到j点：dp[j]
从j是否能跳到i：j+nums[j]>=i
转移方程：dp[i] = dp[j] && j+nums[j]>=i
初始化：dp[0]=1
答案：dp[nums.length - 1]，最后一个元素的状态

Day 28, solved 1 problem.

Tip:
LC 204, use recursion can be very simple.

打卡第16天 2020.07.20

167 两数之和 II - 输入有序数组