自己监督自己的刷题打卡贴

加过两个刷题群，但是都是不知为何群都是无疾而终。刷过一些题，但是感觉自己刷题的质量并不好。一个人刷题也很容易懒散。话说好久都没刷了。要开始刷题了，要好好加油，为了更好的生活。💪加油。此贴发给自己，记录一下每天刷题的进度，希望起到监督的作用。

给楼主点赞，楼上说的对，努力的人都值得尊敬~ 最近我也在刷题，进度很慢，看着楼主的帖子也算是对自己的激励啦~

336  Palindrome Pairs
用了dfs 然后就tle了 只写dfs用了一个小时。。。理解九章的答案花了。。一个半小时。。。
九章的解法是用trie 来解决。把words都放在trie上，然后如果相加的结果是palindrome的话，比如123（idx 0） 和4321(idx 1) 就应该可以4321从后往前遍历在trie上在123的那个node停住，然后剩下的4本身是palindrome的。
因为所有都是先加入
而且加入的时候都是从前往后的顺序，所以query的时候的那一方肯定是从后往前的遍历。
比如4321 和 123
加入（左到右是自上而下的tree的层级）
       4 3 2 1
       1 2 3
遍历的时候 查找1234 和321 是找的到滴（因为 1234找到123）
然后 123 和 4321 能找到吗还。。
加入 1 2 3
       4 3 2 1
遍历的时候 查找 321 和1234 这时候。。可以找到到滴（1234 找到123）
说明和遍历先后顺序没有什么关系，不需要reverse这种情况就可以找到啦。这种reverse后不对称了所以也不会多加。

所以可以直接加入到顺序里啦。然而这只是一个pair如果互相可以组成两个pair呢？
比如 ab ba 一般这种情况都其实长度相等（吧？）
然后查找的时候找到一次
加入 a b
       b a
查找的时候是 ba 找到了 ab也找到了。不需要reverse这种两个相互 组成pair的就可以加入两次了。那reverse了咋办，不是加了两倍吗？这个情况通过checkPalin(A, 0, i - 1))还有 boolean checkPalin(char[] A, int lo, int hi){
        if (reverse && lo > hi){
            return false;
        }
限定了hi是finder停止的位点，所以对于ab,bahi就是-1，此时直接+reverse， return false就不会多加了。


然而reverse的作用在哪儿。。。
看 1234 和 321 这一组呢
加入 1 2 3 4
        3 2 1
遍历的时候 查找 4321 和123。这时候就找不到了啊。
说明长的那一半如果在前面的那个片段里的时候，就find的片段比较长，因为前面的片段find的时候invalid是从中间多出来的部分开始开头的。所以这种情况需要reverse了。。。这样才能找得到啊。

337. House Robber III
写了20分钟，3rd submit的时候AC。用的recursion。但是是按着test case修改的。自己没想好test case。没有想全。

338. 35 min AC
不过写的没有九章的elegant。。被这个惊艳到： f[i&(i-1)]
写完这一道题开始写推荐信

339 10min AC

然后学习了50分钟其他的内容

锻炼一个小时

326 没写出来。答案太厉害了
327 没写出来。因为只是觉得binary indexed tree 的解法最符合心意。所以目前还没有关注别的解法。。但是这个题真的好难好难好难。。。
lower <= sum[i2] - sum[i1] <= upper (with i2 > i1)
可以变形为：lower + sum[i1] - 1 < sum[i2] <= upper + sum[i1] (with i2 > i1)
这个公式很像Prefix sum的解法，只需要找到
sum[i2] <= upper + sum[i1]找到个数
然后减去sum[i2]<= lower + sum[i1] -1的找到的个数的部分就好了
所以如果用binary indexed tree的解法的话
每个sum应该是在bit的array里的，因为要通过计算sum[i]的个数
然后upper + sum[i1]和 lower + sum[i1] -1都是划定的范围。那么其实这个坑其实也一定存在bit里，但是不要填坑，因为用来计算个数的只能是sum[i]本身，这两个只是一个范围。
所以所有的bit坑应该包括三种类型，upper + sum[i1]和 lower + sum[i1] -1还有sum[i] 因为我们要用范围计算所以bit本身的顺序就是计算出这三个值用大小排序。
知道了bit坑的组成（三个），应该填的类型（sum[i]），和序列（这三种坑在一起排序）。
那么填坑的时候的顺序应该怎样的呢？应该按照怎样的顺序insert，怎样的顺序query?
i2应该已经在bit上了，这样才能被一个i1的范围找出。
所以先把所有的sum都放在bit上，在sum上从左到右，依次（
因为i和自己减去是0，也没有任何意义，所以每次query前把本i从bit上去掉。）query
主要是利用query，在sum上i1在前i2在后，query的时候用i1找i2的数量，所以应该把所有的i2，也就是后边的元素都加上，然后每次i1减去i1本身，从i1的upper,lower来query i2的数量。这样来讲也就是说对于sum中的每一个元素从前往后，计算从以这个点开始，后边所有点结尾，符合这个range的公式的个数。然后到下一个元素开始，减去本元素本身，到下一个元素后边所有点的结尾，用自己的upperlower的界限来找到<=的值。
328 假AC。 为什么说假呢。因为一开始自己写的一直没有ac。。失去耐心。。看了答案之后改了改了之后才ac。。

跑步机上跑了2.0 distance ~    加油       。==感觉做题的时候还是不够专心。静心静心静心

318. Maximum Product of Word Lengths。没写出来。
解法真的太666了。完全没想到。只看了第一个解法
319. Bulb Switcher   没写出来。对于这种数学问题== 只能佩服那些想出来的人
320.想到backtrack 但是没想到正确的方式。也没写出来。

周日的一天，自己集中精力的能力真的很需要提高一下。。。

321.没写出来。看答案看了半天，这种一层一层的找max，最后合起来是总的max的解法。。只能佩服
323.AC
323.没写出来。不想用dfs了，想用union find。但是没有想起来具体union find怎么写==
324.没写出来。想到了大致解法，但是不是很自信。。直接看了答案没有自己写。应该好好写写的
325.AC但是 时间上来讲的复杂度是 O(n^2)。看了解答之后==。竟然没想起来可以用这种方法。key是把pSum2 - k = pSum1 写出来。这样每个pSum都会被依次calculate出来，iterate一遍，此时，对于一个2点想找之前是否有一个点pSum2 - pSum1 = k  的时候，instead of把前面的preSum都iterate一遍，最好的方法就是用hashmap直接找这个等式之后的Key，并且相同的之前的prefix会被重复的验证好几遍，寻找的key变了而已。

锻炼了一个小时~     加油

08/09/2018 昨天刷的忘了po出来了。。
329 longest Increasing Path in a Matrix 没写出来。想到dfs，但是没想到dp实践，应该不怕hard好好写写的，看见hard总是不敢费时间写。
330 patching array没写出来。借鉴的别人的解析：我们定义一个变量miss，用来表示[0,n]之间最小的不能表示的值，那么初始化为1，为啥不为0呢，因为n=0没啥意义，直接返回0了。那么此时我们能表示的范围是[0, miss)，表示此时我们能表示0到miss-1的数，如果此时的num <= miss，那么我们可以把我们能表示数的范围扩大到[0, miss+num)，如果num>miss，那么此时我们需要添加一个数
331 TLE 感觉自己写的是dfs版的recursion，leetcode的人po的recursion的版本是dp版本的recursion。。第一个stack的解法还没看

332 没写出来
333 ac 用recursion的方法写的
334 ac啦
335 没写出来。

340. Longest Substring with At Most K Distinct Characters
     27 min   2nd submitted. AC.
休息了15min
341. 写了45分钟。没写出来。失去耐心。

休息了40分钟。。。。。。。==

看341的就站答案 10min 。嗯。。自己这种题还是需要多练习几遍

342 15min. 9th submitted. AC. 看discuion的区域的答案比自己答案好，值得借鉴。看disccusion 15min.

休息了半个小时。。


343.20min AC.10th submitted.

休息了20分钟。。

344 3min AC
345 6min AC
346 7min AC
347 20min AC.  很神奇的map的entry可以这样用：
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<Map.Entry<Integer, Integer>>(
            new Comparator<Map.Entry<Integer, Integer>>() {
                public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
                    return e1.getValue() - e2.getValue();
看了10Min map.entry。这个是map interface里的一个interface。

休息了一个小时。。
348 20min AC 6th submitted
349 没写。。看见这个题就想起以前竟然载在这个题上。。心痛。15min看了看discussion。
350  10min.AC

15min study别的
锻炼了一个小时

昨天出门逛街。。没学习。。今天要开始继续打卡了

给你点赞