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

慕容清 发表于 2020-07-18 20:30:07
打卡第十天
几道需要辅助栈的题目。

打卡第十一天：

LinkedList 4题

Day 6:
练习binary search
First Bad Version: binary search
Time Based Key-Value Store: binary search used in correct timestamp search
Random Pick with Weight: binary search used in finding the correct index
Search a 2D Matrix: two binary search: 1. row-wise, 2, column-wise
Two Sum II - Input array is sorted: two pointers in different directions
Kth Smallest Element in a Sorted Matrix: keep min heap/binary search(count num of elements less than the mid)

Jul 19 打卡第18天，5道题
1520. Maximum Number of Non-Overlapping Substrings, greedy思想，meeting-room，重点在于extend range;
505. The Maze II, 其实就是普通的BFS，trick就是在于多一个while循环一直走到底，之后会再回退一步，会利用一个dist数组存放start到point的最短距离；

day5
3 题，还都是偏简单的medium，捂脸

刷题打卡第7天
29. Divide Two Integers 这道题很奇怪，实际上是用bit shift来实现除法，可以用is来实现XOR的功能判断正负，然后两层循环可以计算出商。
19. Remove Nth Node From End of List 这是一道中等题，关键是想明白如何一遍就能找到倒数第n的，其实设置两个指针就行，linkedlist都是这么玩的，一个快一个慢，然后当快的到底的时候，慢的正好在n-1的位置上。
22. Generate Parentheses 一开始想到写一个函数用栈来判别括号是否有效，然后遍历全部的。后来发现只要记录左括号和右括号的数目就能判别是否有效，如果没有中括号和大括号的话。然后就写了递归来实现，实现后发现自己写的还是过于复杂，递归传参的时候只要传string就可以了。

day 13
第一题sliding window，最麻烦的部分是读懂题
第二题道理很简单，recursion比iteration简单很多
第三题道理和第二题一样，但是处理linked list的pointer比较麻烦

菜鸡七月第二十天！

1. add binary: July challenge 里面的，加的是string的话就每次通过s.charAt(i) - '0'的话来求当前digit，然后就是从右loop的普通加法，
    每次carry的时候因为是binary就用2，用string builder 最后reverse一下
2. multiply string: 两数相乘的时候str1 ith digit, str2 jth digit, 乘出来的两位数应该放在i+j, i+j+1的index上面，从右向左乘每个digit，
    记得每次加上之前在i+j+1的之前的carry，最后再用string builder如果不是0的话串在一起
3. candy: 这个可以用greedy，先把所有array存成1，然后过两遍，第一遍先看当前index左边，如果当前比左边greedy index大，就把
    arr[index]设成arr[index-1]+1，再从右边过一遍，如果当前index比在右边的大，就把arr[index]取当前arr[index]和arr[index+1]+1的
    最大值
4. remove duplicate letters: 可以用recursion，每次先找最小的最左边的s[i],  是最greedy的choice，然后再去掉s[i]左边的substring，
    再把s[i]右边的相同letter换掉
5. lemonade change: 比较简单，simulate一下，可以用five, ten来存当前剩余的零钱，注意如果换20的时候可以拿10+5换，或者5*3来换

做了一题palindrome的题，拿到题目一开始没什么思绪，看了discussion才知道用backtrack做，有了方向其实并不难。
第二题是第一题的变种，尝试用相同方法做，结果有的case TLE了，明天尝试用dp的方法。

今天刷了至少6题： 主要集中在binary search 和 dp了。