查看: 594|回复: 6
收起左侧

日常leetcode刷题

|只看干货
kingwx666 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
刷题找工作,自娱自乐。


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字典应该都可以











上一篇:寻找刷题伙伴
下一篇:边上班 边刷题 打卡
 楼主| kingwx666 2021-10-27 05:57:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
本帖最后由 kingwx666 于 2021-10-26 16:58 编辑

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。
回复

使用道具 举报

 楼主| kingwx666 2021-10-28 04:02:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
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)
和拼火柴差不多,没啥新意。
回复

使用道具 举报

 楼主| kingwx666 2021-10-29 08:36:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎

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的解法很抽象,需要找最长序列和左右括号位置之间的关联性。

回复

使用道具 举报

 楼主| kingwx666 2021-11-8 11:17:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
偷懒才是生活的正常节奏。。。。

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。确定了主问题之后的解法就很直接了当了。


回复

使用道具 举报

 楼主| kingwx666 2021-11-9 04:56:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
day N+1:
DP:
2*medium+1*hard

935. Knight Dialer
平铺直叙。

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

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

使用道具 举报

 楼主| kingwx666 2021-11-10 05:21:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎

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

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表