日常leetcode刷题

刷题找工作，自娱自乐。


day 1

backTracking部分：

1863 Sum of All Subset XOR Totals （easy）
没啥亮点，直接backTracking遍历所有的subset，计算sum of xor

1239 Maximum Length of a Concatenated String with Unique Characters （medium）
主要逻辑还是遍历所有的可能组合，亮点在于如何判断string中只含有unique char， 常规的字符串遍历太费时间，引入bitmap的想法可以把判断过程的时间复杂度降到常数时间，用bit manipulation来更新bitmap

131  Palindrome Partitioning （medium）
遍历所有partitioning，然后依次判断是否是palindrome

95 Unique Binary Search Trees II （medium）
backTracking的外壳加上建立bst，数组已经是有序的，左右子树可以直接分配。

1799 Maximize Score After N Operations（hard）
backTracking的变种，2d backtracking，亮点在于如何去记录已经访问过的位置，用bitmap或者hash字典应该都可以

day 2:
backTracking (Cont.)

473 Matchsticks to Square （medium）
有点意思的变种，四条edge比较容易让人联想到dp，所以可以通过记录保存一些组合来减少时间复杂度。

679 24 Game （hard）
算24点，加括号容易让人去想先枚举所有的表达式，然后再计算表达式。实际上括号可以用改变运算顺序来替代，剩下的就没什么复杂的了。

638 Shopping Offers （medium）
其实是比较直接的backtracking，不过有点意思的地方是special offer可能是个sub-optimal的情况，可以提前剔除没有意义的special offer。

day 3:
backTracking (Cont.)

797 All Paths From Source to Target (medium)
毫无亮点的backtracking在有向图上的应用。

1723 Find Minimum Time to Finish All Jobs （hard）
binary search加上backtracking，没啥新意

90 Subsets II （medium）
针对有重复元素的数组找子集，先统计每个重复元素出现的频次，然后在backtracking，算是一个常见的变种。

1849 Splitting a String Into Descending Consecutive Values （medium）
没啥亮点，backtracking加上一个判断语句就可以了。。

980 Unique Paths III （hard）
凭什么是hard。。。。

698 Partition to K Equal Sum Subsets （medium）
和拼火柴差不多，没啥新意。

day 4:
DP:
dp不是太熟，写的有点问题

1326 Minimum Number of Taps to Open to Water a Garden (hard)
思路比较简单，愿问题是[0-n]的最优解决方案，子问题是当一个tap解决了[m-n]的情况，剩下的[0-m]的最优解决方案，总觉得答案有问题。

871 Minimum Number of Refueling Stops （hard）
问题可以定义为n次加油能跑的最远距离，但这样会慢，可以用贪心算法搜索最大的加油站，从n降到logn。

139 Word Break （medium）
dp 的常规case，可以利用存储meta data来减少计算的冗余度。

32 Longest Valid Parentheses（hard）
用stack很容易求解。dp的解法很抽象，需要找最长序列和左右括号位置之间的关联性。

偷懒才是生活的正常节奏。。。。

day N:
DP:
来几道medium热热身

198. House Robber
简单直接的dp，假设偷窃的发生的有序，可以降低系统的自由度和时间复杂度。

55. Jump Game
dp 不是最优的解法，但是这道题很适合新手练习top down和bottom up的dp写法。

740. Delete and Earn
在盗贼抢劫题（198）的基础上加了一个条件约束。

1277. Count Square Submatrices with All Ones
这道题最大的难点在于容易想当然了。用dp去求解的话，主问题是计算某个特定position为顶点的正方形的数量，然后循环遍历matrix中的所有position。确定了主问题之后的解法就很直接了当了。

day N+1:
DP:
2*medium+1*hard

935. Knight Dialer
平铺直叙。

518. Coin Change 2
很有意思的一道经典dp，主问题是用n种硬币拼单，子问题是用n-1种硬币，然后bottom up。

174. Dungeon Game
思路简单，但是不容易写对。关键点在于分析主问题和子问题的联系。

day N+2:
DP:
1*medium+1*hard

1048. Longest String Chain
反直觉，排序后居然会比不排序直接dfs+memory慢，dp部分比较直观

1611. Minimum One Bit Operations to Make Integers Zero
讨厌的位操作。。。看起来简单，一做就错。。。。

看到了过程感觉很励志