在职刷题打卡，目标工作日一天2题，周末一天5题

一直在刷题，但是速度不尽人意，上个月只进步了30多题而已。立贴打卡刷题，写上今日刷题题目和小心得总结，月底目标是完成90题。
刚刚刷了一题Set Matrix Zeroes。继续继续～
第一次发帖不知道活动是怎样搞，有人愿意一起的话欢迎就在这里打卡啦。


补充内容 (2019-8-1 15:41):
这个活动结束啦，大家不要再加入了。明天开下一期，也是一个月～

今日刷了三题，临时出了点事儿耽搁了，明天加油。现在在刷presum专题，基本上就是subarray sum的各种follow-up。
lintcode: Submatrix Sum
使用一个pre-sum matrix来做预处理，然后用一种把当前matrix拍扁的做法来使用pre-sum中的map找到答案。
leetcode 560. Subarray Sum Equals K
这题要新引入一个思考用变量t，在t这个时间点上，满足条件左边开始点有多少个，res就加上多少个；加完以后再把当前sum加入counter內，这样就不会多计算终点比起始点小的情况。
Set Matrix Zeroes
这题的trick在于，如何明智的使用第一行来存 当前列是否要置0 的信息。所以先扫一遍第一行，记录下是否有0；然后扫完整个matrix，把0都提到第一行；挨个遍历行，有0置0 or 第一行有0置0.最后处理第一行是否置0.

xsijg8 发表于 2019/07/05 15:13:42
今日刷了三题，临时出了点事儿耽搁了，明天加油。现在在刷presum专题，基本上就是subarray sum的各种follow-up。
lintcode: Submatrix Sum
使用一个pre...

同刷题加油

今日完成目标，5题，终于结束了一个专题进入了下一个。
presum的follow-up专题：
523 Continuous Subarray Sum
先是用dp写了这题，但是非常的慢，再用dp写下一题就TLE了；所以还是要使用presum最快。
继续灵活使用presum数组，这次是用了mod+n来填充presum。当当前mod存在过当时候，意味着从上一次出现到当前位置的区间，和可以整除k。
974 Subarray Sums Divisible by K
跟上一题很像，继续用mod+n来填充presum。去除了区间长度必须大于2的限制，另外也要考虑时间变量t，因为当mod出现过多次的时候，当前时间出现过的mod次数都应该加入最终次数。
开始做quick select专题：
215 Kth Largest Element in an Array
使用partition方法来逐渐缩小上下界，如果返回pos比k-1小，说明太靠前，则左边界设为pos+1；反之太考后，右边界设为pos-1。直到pos等于k-1，这个位置的当前元素就是第k大的元素。
414 Third Maximum Number
写完上一题后水了一题easy，数组很小的时候写法可以很巧妙。一一比较大小然后把元素整体后移即可，等于自己手动维护一个pq。
intcode508. Wiggle Sort
使用partition，同时调整上下界直到返回mid。这时所有左边的元素都小于等于右边的元素，那么如果数组长度为奇数，右边从末尾开始；偶数则从末尾前一位开始。左边从1开始，左右交换，step为2。停止条件是左边小于等于mid，而且left坐标小于right坐标，保证不会再把右边的元素换回去。

ZZ_2315 发表于 2019-7-5 20:16
同刷题加油

加油加油，欢迎监督

今日完成目标，5题，同切换了专题。
Quick sort专题：
Nuts & Bolts Problem 经典题，两个数组的quicksort。从螺母nuts中取最左边元素，然后拿它对螺钉进行partition；获取到partition的位置后，再取该位置的螺钉，拿去对螺母nuts进行partition。这样进行一次partition以后，当前位置的左边就全是小于它的元素，右边是大于它的元素，而且左侧的螺钉螺母总体是相契合的。接下来就是递归，对当前位置左侧和右侧分别进行partition了。
Flatten 一个nestList，要求不使用递归：
lintcode22 Flatten List
lintcode601 Flatten 2D Vector
173 Binary Search Tree Iterator
341. Flatten Nested List Iterator
方法基本都一样，使用堆栈就好啦，python使用deque更加方便。binary search tree则其实就是一个in-order遍历，先一路向左压入堆栈，然后弹出时候检查是否有右child，有则继续一路压入堆栈。

加油加油
我之前也是这个计划 然后五月和六月咸鱼了两个月😂

今天只刷了两道题，解法和思路就不写了，免得剧透：）

Pacific Atlantic Water Flow,        417
Moving Average from Data Stream, 346

找了一个专题分类，查看了一下，目前还没有覆盖到的专题有：string，segment tree，bit & math，graph & Topological Sort，接下来一一复习。
今天只刷了，一题半。。。没有偷懒，卡在Sudoku Solver上了，搞了半下午一晚上，也只能写到 “如果所有小九宫格只缺一个数，能solve出来” 的程度。
324 Wiggle Sort II
partition到中位数在mid位置上。跟上一题不一样的地方在于，奇偶数组的分开处理并且要成山形状的递增（小于mid的数组从小到大填写，大于mid的数组反向从小到大填写），这样保证差值最大的大小值处于结果数组的中间，就不会出现相邻元素相等的情况。结果数组用mid数填满来初始化，这样漏掉的1个元素刚好是mid。
37. Sudoku Solver
写写画画半下午一晚上也没写出来= =，明天先做valid sodoku再做这题吧。

flyingingray 发表于 2019-7-8 11:24
今天只刷了两道题，解法和思路就不写了，免得剧透：）

Pacific Atlantic Water Flow,        417

点赞！欢迎加入，一起加油～