8月刷题/Mock interview接龙活动（缺米刷题的来）

Day 7

1048 Longest String Chain
用了一个hashmap存String 到 length的pair，然后遍历这个arr，每个str都去掉每一个char试试能不能找到，能找到就存找到的len + 1，找不到就存1。写完发现这是个dp。。。所以dfs + memo也可以写。我自己写了个adjacent list 做了个map然后取一个一个找parent然后记长度。感觉不是很有必要buildMap。。。

453 Minimum moves to equal array elements
挺别扭的，想了半天没想到。看答案发现是逆向思维，然后数数就行。所有加相当于一个减，找到min之后记所有差值就完事了。。。

535 Encode and Decode TinyUrl
写了个generate key的方法，每次随机搞然后用map存。也可以直接用hashcode()。

593 valid square
直接算四个边 + 两个对角线长度，比较就完了

72 Edit distance
挺经典的二维dp，两个str是两个轴，然后每个点从三个点更新 dp[i][j] 从 dp[i - 1][j] dp[i][j - 1] dp[i - 1][j - 1]中最小值 + 1。这个题起始点有点烦，如果用n + 1会方便一些，就是说从0个字母改成每一位都是i就行。然后直接可以更新，用n的话就挺多corner
case

944 Delete columns to make sort
非常简单的水题，每一行比较，不行就delete++ 就完事

今日3道

8/10
171Excel Sheet Column Number


88
Merge Sorted Array
一开始想错方向 从前面开始
之后看解答从后面一下就结束了

91
Decode Ways
Dynamic programming

509
Fibonacci Number
Dynamic programming

8/10 188 309 11 42 334 双指针的运用很广泛，买股票dp可以考虑状态转换方程通解

补上昨天的题目。

继续刷题，刷不能快速完成的题目

每日三题。。day10

Excel Sheet Column Number - 这题不是“水”这个字能形容的了。。
Permutations - 简单的递归，也没有复杂的边界条件
Climbing Stairs - 直接了当的DP

补昨天的记录 8月9 日 刷题第九天 打卡第九天

昨天做了2道题, 题目还是做少了，加油！
1. Find an element in a sorted matrix;
Assumption:
the matrix is sorted.
the matrix not containing any duplicates elements.
the matrix is not null.

Analysis && High level:
This a sorted matrix, so it could be transferred from a matrix into an array, so I can use the binary search to find the element by using O(logN) time complexity;

Details:
I would use two pointers, which is the left and right pointers
The left pointer represents the smallest element in the unprocessed range, the right pointer represents the largest element in the unprocessed range. During the process, cut half of the range and use the left half as the target range to process, never rule out the right answer.
And left starts from the leftMost and right Starts from the rightMost, two pointers comes toward each other and the terminal condition is the gap of the two pointers is less than 2;
During the process, I will use a mid pointer which is the middle pointer of the search range, compare its element towards its target, if it is smaller than the target, move the left pointer; else if it is larger than the target, move the right pointer, else return the position;

Outside of the loop, I would check the left and right position separately and find if any of them is equals to target, return the position (if applicable) or return {-1, -1}.

2. Find K closest elements in the array
-check the corner case including the array is not null or the array is empty and the k is smaller or equals to 0
-then find the largestSmallerEqual
-then use a while loop to traverse the array in a comparing order;

日期: 8/10/2020
题目: [7]
171. Excel Sheet Column Number
930. Binary Subarrays With Sum
1092. Shortest Common Supersequence
1105. Filling Bookcase Shelves
1143. Longest Common Subsequence
1540. Can Convert String in K Moves
1542. Find Longest Awesome Substring

Day 48, solved 1 problem.

Tip: Use BFS.