1月刷题打卡帖

1月刷题打卡贴。
目标是每天5-10道题，记录要注意的地方。

也欢迎一起刷题打卡，互相监督，互相加油~

一起刷题吗？求加个微信互相督促吧

1.10
Permutation
无重复的n个数全排列 A(n,n)，用path.contains，或者也可以用start索引swap start i
无重复的n个数中k个的排列 A(n,k)，用path.contains，和上面唯一的区别是结束条件当path.size()==k时return
有重复的n个数全排列 A(n,n)，排列组合一旦有重复元素，用map做最简单，或者也可以用start索引。排列backtrack是从start+1，组合backtrack是从i+1。排列checkDupilcate是从start到i-1都要看，因为数组要swap就没有排序，没有排序重复元素就不会挨着一起，就都要check
Combination
无重复的n个数中k个的组合 C(n,k)，组合的关键是不走回头路，所以用start索引，但不用swap
有重复的n个数中k个的组合 C(n,k)，还是排列组合一旦有重复元素，用map最好做
Subset
无重复的n个数的所有子集，子集的关键是前序遍历的时候add to res，其他和组合一样，也是用start索引不走回头路
有重复的n个数的所有子集，和无重复的子集做法一样，只不过记得先排序，然后checkDuplicate时如果nums[i]和nums[i-1]相同，就跳过

valkyrior 发表于 2021-1-10 05:53
可以直接在这边打卡吗楼主？

可以的zszszs

1.1
Longest Substring Without Repeating Characters，滑窗
Plus One，不要转成int/long，in-place加一
Plus One Linked List，找到right most notNine的node，把它加一，后面都置为0
Add Binary，按位相加，不要忘了最后处理进位carry
Add Strings
Add to Array-Form of Integer，把K看作进位
Sum of Two Integers，由于java用two's complement表示数，所以不需要考虑正负，a^b就是answer，(a&b)<<1就是进位，直到进位不等于0返回answer

1.2
Multiply Strings
Add Two Numbers
Add Two Numbers II
Reverse Linked List
Reverse Linked List II，如果用递归，先写递归反转链表前N个元素，再处理第m个到第n个元素

1.3
Minimum Window Substring
Find K-Length Substrings With No Repeated Characters
Longest Substring with At Most Two Distinct Characters
Longest Substring with At Most K Distinct Characters
Find All Anagrams in a String，滑窗
Sliding Window Maximum，单调队列

1.4
Binary Search
Find First and Last Position of Element in Sorted Array
Coin Change
Number of Islands
Alien Dictionary，关键是每相邻两个word可以提出一个字典序，用这个build graph，然后用BFS或DFS拓扑排序就好

1.5
Kth Largest Element in an Array，randomized quick select或者min heap
Kth Largest Element in a Stream，min heap
Kth Smallest Element in a BST，inorder traversal
Top K Frequent Elements，quick select或者min heap
Shuffle an Array，Knuth Shuffle

1.6
区间问题 sort + 分情况处理：
Remove Covered Intervals，删除覆盖区间
Merge Intervals，合并区间
Interval List Intersections，区间交集
greedy问题：
Non-overlapping Intervals，相当于求无重叠区间的最大个数（区间调度问题），按end值升序排序，然后统计有几个不相交的区间，只不过这道题问的是要删除几个区间能保留无重叠区间最大个数，减一下就可以了
Minimum Number of Arrows to Burst Balloons，同样是区间调度问题，按end值升序排序，然后统计有几个不相交的区间
Jump Game，跳跃游戏，从第0个位置开始，看最远能跳到哪
Jump Game II，跳跃游戏，从第0个位置开始，看这个位置最多能跳到哪记为farthest，然后从i到curEnd这个范围内，更新farthest，farthest就是我们选好这一步跳到哪后，这一步能跳到的最远位置，当 i == curEnd时，说明所选择的这一步的所有都考虑过了，看next jump了

1.7
sweep line解决区间问题：
Insert Interval，找到位置插入，要么在前，要么在后，要么相交，相交的话更新newInterval start end，但是不加入res，因为还要看后面的
Remove Interval，分两种情况：不相交和相交，相交看a[0]<=b[1]&&b[0]<=a[1]，进入if再比较a[0],b[0]和a[1],b[1]，不相交比较简单，直接加上就可以
Data Stream as Disjoint Intervals，用binary search，找到应该插入的位置，然后和右边合并if need，然后和左边合并if need，能合并的前提是两个intervals挨着，即next[0]-cur[1]<=1
Meeting Scheduler，和昨天做的Interval List Intersections是一样的题，都是while(i<n1&&j<n2) 然后move i或j
Employee Free Time，用min heap sort by start time，然后类似merge intervals的做法，找到free time period

1.8
The Skyline Problem，sweep line暴力解法，还是数飞机的问题，起点为正的height值，终点为负的height值，注意sort时event发生时刻相同时，先起飞再降落，用TreeMap(based on红黑树)很快，只要curMax和preMax发生变化，不论变大变小，都说明天际线变化了，要add key point
Basic Calculator，加减括号，计算器都是一个模板，stack + recursion
Basic Calculator II，加减乘除
Basic Calculator III，加减乘除括号
Different Ways to Add Parentheses，分治法，还要再看下这个解法

可以直接在这边打卡吗楼主？