1月刷题打卡帖

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

可以的zszszs

1.9
N-Queens
N-Queens II
Grid Illumination
Reverse Words in a String，如果in-place with O(1) extra space，用双指针移动chars，reverse whole string，再reverse each word
Permutations，可以记录path，也可以用nums array通过swap current first element(待固定的元素)and位置i元素来做

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]相同，就跳过

1.10
Partition Label
Maximal Square
Next Permutation
SubArray Sum
Spiral Matrix

1.11
Remove Duplicates from Sorted Array，原地删除有序数组中的重复元素，双指针，都换到前面
Remove Duplicates from Sorted Array II，一样的方法，只不过用cnt记录下重复出现次数不要超过2
Remove Duplicates from Sorted List，一样的方法
Remove Duplicates from Sorted List II，这个不一样，凡是重复出现过的元素都不要，所以虽然还是双指针，但要注意单链表元素相同的比较用cur和cur.next比较，skip sublist of duplicates
Remove LinkedList Elements，链表，原地删除指定value的所有元素，双指针
Remove Element，数组，原地删除指定value的所有元素，挪到数组前面
Move Zeroes，先用上题方法，把所有非零元素挪到前面，然后把slow及之后都置0

1.11
First Missing Positive
Word Search
Container with Water

1.12
Binary Tree Preorder / Inorder / Postorder / Level Order Traversal
Inorder Successor in BST

1.12
Search in rotated sorted array
Longest consecutive sequence
Largest Rectangle in Histogram

1.13
Invert Binary Tree
Populating Next Right Pointers in Each Node
Flatten Binary Tree to Linked List
Maximum Binary Tree，这个是构建Cartesian Tree，可以通过找LCA来search range minimum queries，有O(n^2) recursion做法，也有O(n)单调栈做法
Valid Binary Search Tree

1.13
Maximal rectangle
Pairs of Songs With Total Durations Divisible by 60
Max Area of Island