📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: ztamber
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 7月缺米的来刷题/Mock interview活动

   
🔗
QWERTYUIOPAS 2020-7-3 01:43:00 | 只看该作者
全局:

Day 2, 0702, 7道。

日子有点过乱了。。。今早+昨晚算0702,今晚的算明天的吧。

Find and replace in String:
一开始以为idx数组是排好序的,其实并灭有。自己写了个class都存起来,sort然后从后往前插入。看了一下答案,最快的人用一个int[]存了要换的target的idx和S idx的映射,然后用stringbuilder一个一个看append谁。比我聪明多了。。

Number of closed islands.
自己写了一个全bfs的码。。。从边上的0开始,见到mark成1。然后在grid里找到0就count++然后bfsmark成1. 看了一下答案。dfs快很多。最快的是dfs return boolean,这样遇见边这个dfs就是false,一个双循环结束。。。感觉自己好蠢。

split array into consecutive subsequences
完全没写出来。以为这个跟昨天做那道差不多。结果发现完全不一样。看了答案,用两个map,一个存count,一个存tail,每次找到一个值,先update count -1,然后向前找有没有能用的tail,找到了就update那个tail,然后自己是新的tail。没有前就向后找两个,如果都在,就update最后那个做tail,update这后面二位的count。这是如何想到的。。。

longest String chain
我自己写了个无脑dfs,先用长度sort了input,这样做dfs的话,树的每层都是一样长的string,而且跟下一层差1,然后先遇到的就可以直接mark visited,以后见到直接过。写了个diff,用count++-- <0判断差1. 最后竟然5%过了。。。然后看答案发现是个dp。。。自己蠢的感觉更强烈了。

重写了一遍 delete nodes and return forest,post order, recursion用TreeNode保持关系。爽

Divide Array in Sets of K consecutive Numbers
跟上次分牌的题一摸一样,用treeMap搞定。

Hand of Straights
这个就是跟上个一样的treeMap题。我自己写了个 list of pair计数,然后sort,然后用 前w个不断比较,出问题return false。也还行吧,这个没用过treemap没办法。。。



评分

参与人数 4大米 +5 收起 理由
慕容清 + 1 赞一个
hy0v0 + 2 给你点个赞!
4552dosen + 1 给你点个赞!
jerryzzf + 1 加油

查看全部评分

回复

使用道具 举报

🔗
jerryzzf 2020-7-3 04:03:55 | 只看该作者
全局:

连续第 16 天打卡,完成 5 道 Backtracking, Tree, Binary Search 题:(4/5)
1. Letter Combinations of Phone Numbers
2. Generate Parentheses
3. Combination Sum
4. Binary Watch
5. Count Complete Tree Nodes

Tips 总结:
1. The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem;
2. Conceptually, the partial candidates are represented as the nodes of a tree structure, known as potential search tree;
3. The backtracking algorithm traverses this search tree recursively, from the root down, in depth-first order. At each node c, the algorithm checks whether c can be completed to a valid solution:
· NOT POSSIBLE: the whole sub-tree rooted at c is skipped (pruned)
· ALREADY A VALID SOLUTION: reports it to the user
· POTENTIAL PARTIAL SOLUTION: recursively enumerates all sub-trees of c
4. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node.
5. "Count Complete Tree Nodes" is such a GREAT tree problem!!!!

Screen Shot 2020-07-02 at 12.52.30 PM.png (214.76 KB, 下载次数: 3)

Screen Shot 2020-07-02 at 12.52.30 PM.png

评分

参与人数 3大米 +4 收起 理由
ztamber + 1 给你点个赞!
hy0v0 + 2 给你点个赞!
4552dosen + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
4552dosen 2020-7-3 04:25:36 | 只看该作者
全局:
打卡 7.2 Day 2
今天刷了Recursion I 的explore card, 总体比较简单,加上今日份7月份leetcode challenge, 一共9道题,难度分布应该在easy-medium之间。Recursion 的memorization应用还是需要通过后续的联系变得更加熟练。
更多图片 小图 大图
组图打开中,请稍候......

评分

参与人数 3大米 +4 收起 理由
慕容清 + 1 赞一个
ztamber + 1 给你点个赞!
hy0v0 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
hy0v0 2020-7-3 04:49:58 | 只看该作者
全局:
7.2 打卡第一天

1. Search in Rotated Sorted Array II
2. Linked List Cycle
3. Expression Add Operators
4. Maximum Length of Pair Chain

评分

参与人数 3大米 +3 收起 理由
jinliYYQ945 + 1 给你点个赞!
慕容清 + 1 赞一个
ztamber + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
 楼主| ztamber 2020-7-3 05:05:56 | 只看该作者
全局:
打卡第二天       
        • Longest Valid Parentheses
                ○ dp [i]: include the index i, the longest valid parentheses we can get
                        § case one if  "(", left += 1
                        § case two if  ")" and left > 1, we got a valid parentheses, but need to check (1) any parentheses within it
                                                                                                                              (2) any parentheses before it
                        § Time O(n), Space O(n)
        • Regular Expression Matching
                ○ dp[i][j]: s[: j + 1] match p[: i + 1]
                        § coner case: s is '', p is 'a*', first update the dp[i][0] with dp[i - 2][0] if p[i - 1] == "*"
                        § case 1: == or '.', dp equal to the left corner
                        § case 2: p[i -1] = '*':
                        Time O(n), Space O(n*m)      
       
        •  Wildcard Matching
                ○ dp[i][j], pattern到 i index 之前的字符与s 到j 的字符是否valid match
                ○ corner case: s ""    p "a*", first update the dp[i][0] with dp[i - 1][0]      
                ○ case 1: == or "?"  =>  equal to the left corner
                ○ case 2: "*":
                                □ delete "*"
                                □ fill letter   
                                   fill as prev letter

评分

参与人数 2大米 +2 收起 理由
夏夜的未央 + 1 给你点个赞!
慕容清 + 1 赞一个

查看全部评分

回复

使用道具 举报

🔗
jinliYYQ945 2020-7-3 07:15:52 | 只看该作者
全局:
7月2号:
973. K Closest Points to Origin heap泛型,
泛型写起来比较简单干净,comparing(p->p[0]*p[0]+p[1]*p[1]),
但是也要掌握一般写法,new PriorityQueue<>(
            new Comparator<int[]>(){
                public int compare(int[] a, int[] b){
                    return a[0]*a[0]+a[1]*a[1] - (b[0]*b[0]+b[1]*b[1]);
                }
            }
        );
253. Meeting Rooms II
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
            intervals.length, (int[] a, int[] b)->(a[1]-b[1]));  前面放的是intervals的大小
先将会议开头排序,heap里面放的是会议结尾,先poll,覆盖整合之后再offer到和heap里
692. Top K Frequent Words
可以将Map.Entry<String, Integer>作为比较元素,也可以将String 作为比较元素
347. Top K Frequent Elements
和692一样,可以用Map.Entry<String, Integer>和String两种方法写一下

评分

参与人数 3大米 +3 收起 理由
ztamber + 1 赞一个!
wil_lian + 1 给你点个赞!
夏夜的未央 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
conghao2016 2020-7-3 07:22:27 | 只看该作者
全局:
今天继续刷7+1=8题。。。第三遍了。。冲啊

image.png (254.47 KB, 下载次数: 3)

image.png

评分

参与人数 4大米 +4 收起 理由
DL + 1 给你点个赞!
yaozheng + 1 给你点个赞!
wil_lian + 1 给你点个赞!
夏夜的未央 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

全局:
打卡刷题07/02

1. 935. Knight Dialer https://leetcode.com/problems/knight-dialer/
总结:
首先看到这个题目, 看到每个数字可以跳到另外的数字,这个insight告诉了我们这是个DP的题。
那就可以开始写dp的公式 f(1, n) = f(6, n-1) + f(8, n-1).
最后 f(0, N) + f(1, N) + ... + f(9, N) = sum(dp)
其实并不是个dp的难题。但是从图和问题联系到DP要有这个思路。


2. 75. sort color https://leetcode.com/problems/sort-colors/
总结
我把这个题目总结成一个想法题目。
想法题的意思就是这个题目并不难写,但是想法解题思路比较巧妙。
这种题目做过了之后,复习的时候其实都不用写code,但是要想清楚思路。
这个题目的想法就是3个pointer, low, hi, middle. middle从low走到hi把遇到的每个元素根据大小assign给low和hi。


3. 378 Kth Smallest Element in a Sorted Matrix
总结:
其实有两个解法minHeap和binary search
重点是两个方法的时间复杂度不一样 Minheap是O(mlogn) binary search是O(log(m*n))
比起来应该binary search的时间复杂度好一点

评分

参与人数 4大米 +4 收起 理由
DL + 1 给你点个赞!
mereflora + 1 给你点个赞!
yaozheng + 1 给你点个赞!
wil_lian + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
wil_lian 2020-7-3 10:05:04 | 只看该作者
全局:
今天三题90/120/661

image.png (37.41 KB, 下载次数: 2)

image.png

评分

参与人数 3大米 +3 收起 理由
DL + 1 给你点个赞!
mereflora + 1 给你点个赞!
yaozheng + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
yaozheng 2020-7-3 10:21:42 | 只看该作者
全局:
Jul 2 打卡第2天,7道题
1066. Campus Bikes II, DFS; 题解状态压缩的DP,用bit位表示bike当前状态,n=4,8种状态,1<<n; 如果dp[state]>0, 直接返回;
592. Fraction Addition and Subtraction, res=“0/1”初始化,然后add方法乘法以及约分,注意sign的处理;
373. Find K Pairs with Smallest Sums, 需要利用好排序的条件,下一次可能的smallest pair;最开始将某一个数组与另一个的nums[0]全部加入队列,之后每次出队列一个就加入一个;需要维护好当前在nums1中的位置…
796. Rotate String, (A+A).contains(B);

评分

参与人数 1大米 +1 收起 理由
mereflora + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

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

本版积分规则

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