我的2020开启的第一个打卡记录贴

今天开始我的第一个打卡记录贴， 以此来记录自己的进度和题目理解及反思
今天开始脸书的锁题， 三中等2简单
238 product of array except self; 左右各走一遍，还是O(2n), 不能用除法就用分两半相乘，不用extra space 就在上面累积 或用一个变量来记录帮助来减少空间的利用。
56 merge intervals 相对简单（）-》 {} arrayint [][] sort 一下， 然后用stack 如果后面的在之间， 那就并， 不在直接push进去， 这样就得到了merge完的结果在stack 里面了
253 meeting roomII  我用了日常生活的思路， 什么时候我需要再申请一个房间， 想到用一个小q 来存finish time。 排除null，先要先来后到的安排决定， 一开始至少需要有一个房间， 预约结束时间存进去， 如果下一个人， 他的开始时间 比q的第一个结束时间大， 那么那个结束任务， 用同一个房间开启新任务； 如果不是这样，那就是都占了，只能新开一个房间。

可以先平常想， 然后一般sort 之后方便操作。 用小q的好处是， 虽然可能好几个q中的任务都结束了，但我只要看最小的，只要有一个可以空出来，我就不用再开房间。 而不用考虑几个重叠的厚度。
需要再加，有点greedy的感觉， 每一步一步做一个决定。
时间复杂度是nlog（d） q最多这么深。 Nlog（n） 最差

前三道 9个月前做过，不知道是以前的印象 还是今天思路清晰， 都自己想出来了，很开心呐， 我想以后再遇到，应该也不会全部忘记。


653 verify alien dic  
多次要同一个值就用hashmap， 都是字母用int【26】    mapping[order.charAt(i) - 'a'] = i; 这种比Integer 之类省空间 这里犯了错误，
比大小； index从0到后面，
1) 只要有一个小/大就定了， 只有一直一样才 要到不一样为止来决定（app==app, app<apple, appa<appb）
2) charAt, 注意可能indexoutofbound。 要保证min（lena，lenb），而不是返回-1， 找indexof 才-1.

for 循环 O（n） 相邻都小就过下一个， 不然就false。

125 valid palidrome
12321
刚开始用  s.split("[\\W+]")
[\\p{Punct}\\s]+
这样空间时间都多
看了讨论 其实有一个函数 Character.isLetterOrDigit()  要是知道这个， 那我就用两头指针法 O（n） while（i<j）{ while while} 的方式直到找到两个字母或数字的比较
注意特殊“。，” 这种会找不到数字字母， 用charAt会报错， 所以里面while多一个条件（l《r） 这样既不多走路又不超过



整体反思 ：
双指针， 略过 尽量O（n） 想想sort， chatAt 注意，q stack 活用， 平常greedy想思路。

待锻炼：
正则不太会， string的函数不太行， 比大小本质要注意，一定要比， 知道函数有的时候会方便很多，所以要多做题。字母map用int【26】

总结愉快的第一天

昨天前天
33 search inrotate array
这里肯定要利用sorted 事实， 然后binary search logn
怎么找pivot， 注意有可能没rotate的情况和只有一个元素的情况，
所以也是 binary 找更快， 总是偏左， 所以排除一个元素的特殊情况， 总有一个在mid 右边， mid》mid+1， pivot=mid+1；
不然 缩小空间 index，接着找， 直到找到就return， 不然没找到说明没有rotate，return=0（或者一开始最左边比最右边小， 一定没rotate，直接return0）
while（l《=r）， 这样，一个元素也可以

接下来， pivot分成两个sorted list， 所以可以分别binary search， 直到找到，l《=r，
还有一个 直接target和最左， 最右比， 可以知道是哪个接着search。

答案one pass bs， mid 看是不是rotate，
Algorithm
Initiate start to be equal to 0, and end to be equal to n - 1.
Perform standard binary search. While start <= end:
Take an index in the middle mid as a pivot.
If nums[mid] == target, the job is done, return mid.
Now there could be two situations:
Pivot element is larger than the first element in the array, i.e. the part of array from the first element to the pivot one is non-rotated.
If the target is in that non-rotated part as well: go left: end = mid - 1.
Otherwise: go right: start = mid + 1.
Pivot element is smaller than the first element of the array, i.e. the rotation index is somewhere between 0 and mid. That means that the part of array from the pivot element to the last one is non-rotated.

If target is in that non-rotated part as well: go right: end = mid + 1.

Otherwise: go left: start = mid - 1.

We're here because the target is not found. Return -1.

380 get delete getrandom aveO（1）
肯定用到， java.util.Random ran=new Random();
这样， 删除一定不能有index 空位， 不然 random nexInt（）， 不对，
所以删了的index 用last index填补， 挪位置 填空，
hashmap //val,loc get remove 都方便在hashmap， 然后list 存这样它通过index random 方便
因为虽然linkedlist arraylist 删除O（1）， 但是你要找到v=8， 还是得search，
所以O（n）， 除非你知道index，remove
或者dequearray 有removeLastOccurence（element） 不过不太好，时间

364 nested list sum II
简单， reverse， 所以巧妙利用数学depth（d+1） elementsum-正常顺序结果，
因为index，正反都是一样， 就是互为补充， 所以 反不方便就正

或者， bfs， 套着的解开，加到q 后面， 下一层的时候总是把虽有的pre 又加到total里，pre 不会重新为0，而累计了之前出现过的，
这样就保证，前面出现的加的层次多，d大

easy：
88 merge sorted list
直接一个一个比， 但是会有额外空间， 所以巧妙从后往前， 666， O（m）空间， 因为只要copy 被merge的， 然后就不用O（m+n） 空间
反向思想重要，'
O（m+n）
O（1） 空间

13 roman integer
hashmap 记录所有， IX 也是在里面H2， 这样先看两个， 那就i+=2， 不然i++，
注意index outofboundary， 所以
len==1，
不然len-2， 然后剩下一个   if(i>=c.length) return sum;
        else return sum+=h.get(""+c[c.length-1]);
有可能不剩下，或者剩下， 判断就好


716 max stack
popmax， 所以肯定知道之前的max堆，这样pop一个max才能知道在下一个max
这里就是一个dp感觉， 然后maxstack， 记录到目前的最大值，
pop一个就也pop一个
不用index 什么的记录太复杂

339 nested list sum
简单， 直接recursive， 然后 NestedList， 是integer，直接return不然
     List<NestedInteger>  curls=ls.getList();
        int sum=0;
        for(NestedInteger childls:curls){
            sum+=help(mylevel+1,childls);//elementSum,depth,
        }
        return sum;
就可以

53 maximum subarray
因为可能有-
因为不能 sum min 然后sum max， 因为还要保证sunmax 在summin 之后， 所以很麻烦，
这里 greddy， 因为有-；
过程中， global max ，这样就能one pass 所有potential sum，
如果这个sum before是+, 肯定sum=A【i】+sum前面的， 然后 global max
sum《0， 那肯定sun=A【i】， 这样重新开始的比累加跨的好， 所以 greedy
注意这里是sum 而不是元素， 因为可能
22-122. 跨可能更好



不然 肯定变小了


总结：
反向思想， 空间，
补充，填补位置思想
dp， 到目前遇到的最大值思想。
i++ i+2
if（特殊//一个） return
其他《= 找思想
没找到，最后return没找到
greedy， 更小， 下一个可能性， global比

还差3道medium 和之前的2easy 6 medium
2 easy 9 medim

今天 3中等1简单
560 subarray sum of K  这个 比较简单，找连续的subarray 和==k的有几个。 立刻想到memorization，只是三角 一般（int j=i ） O（n*n） 同一行的memo 加m【i-1】+nums【i】，
但是这样空间太多， outofmemory， 所以就用int[] instead of int[][], 这个也容易想到。 这种就得先for 一行全部初始化， 然后用这个来得到下一列。
m【j】=m【j】-num【i-1】 新一行 减掉到是同一个 所以是i-1

看了答案才发现， 太机智了。

我怎么没想到， 像加减乘除这种， 都可以由部分部分得到另一个部分的结果。sum【j】- sum【i】 就是（i，j）的sum
就用hashamp 记下frequency， 从前往后扫描， 保证sum-k 存在的话 出现几次 fre 就有几次（different i， same j）的组合 因为- + 耗时少
得到结果

注意： h.getOrDefault(sum,0)+1 的应用 和 初始 h。put（0，1） 是必须的， 1，1，1 k=1， 就需要这个初始，才能找到第一个1的存在（相当于给一个起跑点。）


973 kcloest point
见到 distance 函数， priorityqueue k， 先add size大于K 再pull 抛弃。
最后 return q.toArray(new int[K][2])的用法就不用又循环了
Nlog（K）
据说quick sort 能 O（N） 今天没来得及细看这个解法，明天解决

31 next permutation
这题我花的时间最久， 其实并不难，但是我一开始看到这题心里就觉得慌慌的， 因为换来换去的 情况很多， 总觉得像绕口令，一不小心自己就把自己绕进去了， 所以我特别不喜欢这类绕口令题目， 有畏繁情绪，尤其是在多种情况里， 要想办法找到一种统一处理解决的规律办法， 有的时候难归纳。
即使你找到了规律， 也有可能因为 index -1， +1 之类的不小心出错。

最后结果倒是不错 time 100% ， 虽然debug 了很久， 时间花了不少， 但最后终于！ 通过了， 开心

我想到先走一遍 不同例子
123 ，，，132
132，，，213
321，，，123

然后题目要求不用extra space void 在上面改， 时间又要快， 那肯定是需要 在之前 改变的基础上 接着改变的， 所以， 我就按平常的数学题想，下一个最大的， 肯定是前面的高位定， 低位变。 就可以把区间不断缩小---》 我怎么判断缩小到 哪里？ 变成 sub size problem呢？

然后我突然想到  从右边往左边走array nums， 记录下 遇到的rmax， （right side max）， 只需要满足 current index 处的值《 rmax， 那么我肯定可以有一种答案，就是把这个 rmax 换到cur 位置（当然 答案不一定是这个，但肯定有） 因为可能（3， 5 4 2---- 4，235）
这个例子可以发现， 235 是排序的， 3542（cur4》rmax2）----3524（5》4）---3245（3《5） 直接找到（左到右）第一个比cur 大的 他们两swap 就可以，  

就发现， 分类讨论
如果（cur《rmax） 前面右侧的肯定已经小到大排好， 找到swap 位置就可以return
cur》=rmax 排序 前面前移，cur,放最后，为后面结果做准备（ cur 肯定是最大的， 因为>rmax）
就解决了

321 自动就sort 成123 了

415 add String biginteger  不让用直接转成int
就算他让我直接转， 我对big Integer 也不熟， 特别不会long 之类和 超范围的处理， 每次都得google 里面的函数， long *， / double int  转之类的不熟悉

那肯定直接每位数 处理， 数学题解法思想，化大为小步的整合
up 是进位
charAt()-'0' 得到值 相加得到
取余数 进位 update

  add=num1.charAt(l1-1-i)+num2.charAt(l2-1-i)-'0'-'0'+up;
            if(add>=10) up=1;
            else up=0;
            re=add%10+re;

至于剩下不同len的怎么办，  如果最后up==0， 直接substring+re， return
不然就recursive 调用 （substring（l1-l2），“1”）
return

整体总结：
+-*/ 部分部分思想， memorize space省， string处理大integer的巧妙思想， 关键就在于 化大为小， integer 太大， 我就落脚于每一位， 总不会太大了吧。小化思路很重要。
不要怕麻烦繁杂， 列出不同情况， 用曾经基础， 找规律， 分类讨论再解决整合简化。 别想着一上来就是简洁解法， 结果debug， charAt -‘0’
list queue有函数直接转array  return q.toArray(new int[K][2])的用法就不用又循环了

有待锻炼：
bigIntger long Double 加减乘除之类的

还是自己写出来的，虽然有的花的时间久， 但结果令人满意，繁杂写多了， 也会又快又好
明天就要做到我最不喜欢的树的问题了
慢慢就好了
要加油呀

今天
254 factor combination
28； 224； 2222； 44；
本质backtracing
2222， 排列组合太多， 时间不好跳过，
set linkedlist 地址 不好
本质一定是recursive，只不过过程中 避免重复，

backtracing 本质 back 父母， 知道 每一个parent， parent 的parent， 所以dfs satck 感觉，
这里cur 进行一些操作，各种可能性， 这里探讨完了， remove last path element 可以 进行下一个

2，8 add re， remove 8， recursive  add path，
出来一层remove 两次注意， 这样i ++， path =null， 然后 path 过程中要是local全局变量

避免重复
n/i 》=i 才进行recursive， 不然步
i《n/i 是一定的
start 设置也这样。， 这都放置了重复
规定一定从大到小
  private void getFactors(int start, int n, List<Integer> path, List<List<Integer>> ret){
        
       for(int i = start; i <= Math.sqrt(n); i++){
           if(n % i == 0 && n/i >= i){  // The previous factor is no bigger than the next
               path.add(i);
               path.add(n/i);
               ret.add(new LinkedList<Integer>(path));
               path.remove(path.size() - 1);
               getFactors(i, n/i, path, ret);
               path.remove(path.size() - 1); // 删parent， i=3， path==null
           }
       }

235 lowest common ancestor node bst
general stack dfs peek 找path， 比较path，注意是peek 这样从left right 才root 还在path 里
但是这里没利用bst sort 的事实
其实只要， 》root 《toor returnroot
不然 左边 不然右， binary

这里可以 转成iterative， 本质是 这里 没有记录parent 的历史状况
而是直接抛弃历史， 所以直接缩小空间， parent， re 不用通过左右结果得到

空间好，不用recursive stack
This is possible without using a stack or recursion since we don't need to backtrace to find the LCA node.
不用知道parent


oa  fence part
1001，0，1
3*2=6
数学排列组合， 分隔问题
简单

991 broken calculat
巧 X *2 -1===》 y /2 +1
y只有偶数可以/2， 不能小数， 所以
y 一直缩小。 奇数+1
偶数/2
知道x》y
然后 +1 方式， 肯定不可能再/2

这种/2 *2 问题 想到奇数偶数分类讨论，对称思想，缩小空间 比较好

45 jump game
我的O（n*n） 找到 opt（n）=min（opt（0.。n-1）+1）
23114 return2

这里凡是找最短路径感觉的都可以转化成node bfs，
所以 q 分层 cover最后 结束

或者 greedy 最远 最之类的一定有最极致方法的 所以O(n)
213, 3
从 1 看最远 到哪里， 3 最远到哪里， 直到cover到最后 结束战斗
每个node 不往前， 而是往后， 大范围跳跃cover， 每个node 一次，因为不往前， 所以 O（n）


oa beautoful row 山峰
remove min cut
min
dp 对称， 拆成两个dp
一个 递增， 一个递减
O（n*n）
cur node 递增最长opt=max（opt（0，，n-1）+1）
同理，
结果for ， 两个和加起来的global 最大就是 结果， 这样就考虑了每一个人是山峰的情况， 注意特殊情况的判断 只一个递增

read email 简单， 连续的1 下一个， 不然一定跳出的比下一个好
pizza 简单， 注意亮点， 1， 1； 2，0； 凡是 奇偶数的， 40，31， 也可以完全等价为2，1；
remainder  自己0 rem=1； false
自己要的-rem==0 rem=0
==1， rem=1

prime string
凡是ascall 直接int 转， 总共26， 不如直接for找到 prime的， 然后prime的再找到就近的，因为本身递增解决


总结：
对称， 两个方向dp， 奇偶数， *2/2， +1， -1， 换对象， dpO（n*n）；
可能 greedy 最远 cover， jump cover
不重复， 从小到大， recursive 》 才进行
backtrace path parent 本质
iterative， 不用parent' 过去
最短距离 bfs 思想






至于factoer 一定是 2《=《=sqrtn 注意是等于

一起打卡鸭楼主～

shuabao 发表于 2020-1-15 12:02
一起打卡鸭楼主～

好的呀 哈哈

好吧， 我怎么没想到31 只要从右边往左边找第一个不递增的地方，
3，542， forO（n 找到4） swap 4，532， 这个时候，剩下的 就是 ， 后排序小到大排序， 3还是4， 并不会影响 ， 后面大到小的排序
所以这些大到小， 小到大的改变只要swap两边交换就好了

O(3n)
我的虽然是在前面排序的结果上， 但是有一点很不好 ， 就是但凡 每次array 整体shift 的肯定不好， 是O（n*n） ， 虽然 100%， 但本质还是不好的

总结 递增，找第一个不是的就找到了答案，再调整， 已排序的巧妙 利用， 补0 的方法很好。

2. add string, 其实可以前面补上0 成为一样长， 这样方便，不用比较哪个长， 就把 哪个一样的处理步骤复制一遍， 肯定不简洁。
而是， 直接carry =1， 就前面加1， 不然

今天
139  word break 一个月前做的， 今天又不会了， 有印象要用dp 和memorization， 但是最后还是time limit
看了答案恍然大悟， 明知道是O（n*n）的复杂度， 因为opt（i，j） eg（1，5）中有无数种分割组合分词的办法， 所以这个复杂度，那么只要想办法从前往后dp【】【】填充， 这里就体现了dp思想，
因为后面能不能是要依赖于前面的， 前面的true，后面才有可能true，（1，3） false （1，4） true 5 true 也可以true。
time n*n 但是space 确可以O（n）没毛病。
dp本质是解决的是同一个问题， 只不过大问题的过程中， 我先把小问题答案解决， 用小问题答案的组合，poly也可能来得到大问题的答案， 因为都memo， 所以省时间。
而且大问题=小问题综合结果+一小步真正进步细节的判定结果，
这道题里就是一个单词能不能组合， 就是把前面的和剩下一直到end 能不能是一个词来解决

两个for 一个for 到最后
一个for是里面的各种情况，有点recursive的意思

199 binary tree right view
第一反应， bfs， 然后就是用一个q， 一个总结束while 是q都空，结束战斗， 第二个while 就是while这一层， 干两件事， 1. 非null，子add， 2， 该干嘛干嘛
这里就是把第一个要的结果加进去

O（n） 因为遍历树

cc用了recursive，
我对recursive，尤其是树，有点虚，
但凡是树，一般都可以recursive， 因为树的本质就是大家地位都一样， 都是node， 大家都干同一件事，每个node在自己的世界里干同一件事，内容一样，只不过，一般有一个全局，
过程中，side effect 找到了最终全局要的结果。如下一题把所有情况都比较， 也就得到了 diameter最大值
这道题，每一个level只要一个树， 所以先右后左，如果找到了， 虽然不加入re， 但还是要进行下去遍历，注意后面可能需要贡献re的。
这里用全局的hashmap 保证只有一个数， 如果containskey， depth， 那我不加， 不然就把结果加进去。
用n+1 来连续链接parent和kid
结束
215 k largest element
minheap  一样 quick sort 能O（n） 还是没看，哎

543 简单题， diameter of tree
先像例子， 注意也有可能不过root， 本质是找两node之间最长的path， 但是一边肯定没两边加起来长， 只不过不一定通过root。
所以， recursive

凡是recursive 树， 肯定是子树，右树， 干一件事， 然后他俩结合一下， 比较或者加之类之类的， 把一个东西返回给parent， 作为桥梁， 这样就是实现从leaf到上的层层传达。

这里，parent就只需要知道l，r path（depth）的最大值， 把这个最大值+1， 就是parent返还给上面的
同时把r+l 是potential max， 和全局的max 比较更新
注意全局要用 max【】， 不是 max（除非在外面）
不然只传递值， 会出错。

所有都走一遍之后， 就返回max【0】， 就可以了。

67 add binary
和昨天一样， 不过不用leftPad 0， 要用第三方 package 不好，
其实只要，多加一个判断， 只有不超index 才加入add 不然0
根本不影响， 还有就是用StringBuilder， 比“aa”+“bb”快很多
要会用
sb.reverse().toString();


总结：
StringBuilder 快得多。string一般双指针， 或者各自for index char， 多加判断 indexoutofbound 注意
dp[0] dp[length+1](多加base 方便)
dp， 数组，真正一小步，dp[i]=dp[j]+h.contains(...) (j<i) 体现了用了， 体现了memo
return dp[N]

树
---bfs 2 while q size=q.size() ，
——recursive 同一件事，basecase ， if==null ， return 子树综合处理结果作为桥梁，全部比较得整个树的最
helper（root，全局，int， int[]）{
if(root==null) return 0;
if(....)
l=helper(root.left,...n+1)
r=helper(root.right..n+1)
(l,r)....
max=Math.max(max,l+r)...
return ;

}

加强：
recursive 思想 base 训练， 树 bfs 尤其dfs， 多写写 dfs instead of bfs （因为你的dfs 弱）
dp 【】【】 加强

加油呀

今天
621 task schedule  same cooling time n
我想到了用greedy的概念， max frequency 先操作，后面的塞进去
但是我就是最终没绕进去，没绕清楚
还有一点没想到的是， 当把必须的avail slot 利用尽的时候，其实如果还有多的话 肯定是可以直接塞在其他行后面的 这个时候也自动满足cool 条件，而且只加了一个最少的作业时间， 所以结果不会更坏， 那就是最优结果。

最后的结果就是int 加减一下 注意没利用完的至少的empty slot 还是要占位置的， 因为需要cooling

98 valide bst
这个简单的， recursive 遍历node，
桥梁？--valid left valid right 还要 左边最大《node《右边最小

这里就是用int【】 m 来更新 子树的 max 和min

然后分类的
1 base case 是leaf 这样好处理max min 值， 因为我不知道null 怎么处理 max min
2，左null
else if 右边 null
else 两边都不是null
注意每种情况都要由两边子树的max min 2 得到 parent的max min 更新parent 的 m【】 然后层层上去

986 interval intersection
这题我分类的情况太多了 没绕清楚， 显得很复杂 ， 虽然大概思路对的， 但是还是没写出来
一般这种的最优解法是O（n+m） 指针走每一个，
这题就是， 注意当你和他没交集的时候 下一个可能有交集， 下一个potential
你++， else 他 ++
直到有一个到最后了
关键注意， 你和他不交， 下一个可能交， 只不过看要进一步挪哪一个，
一般判断条件的都是while (i < A.length && j < B.length) {
相交的判断， 一定是缩小， 所以是 start 的最大 和end 最小， 如多 s《e 才交

680 valid palidrom II
简单 只能删除最多一个 ， 能不能是pali
明显O（len）
这里有两个选择， 快进左边，快进右边，
刚开始犯了错误， 用count 来保证只改变一次， 这样会导致快进左 右边不是并列同等的地位和可能性，
因为如果删了左边， continue 没有成功的话， 并不会去快进右边，而是直接return
所以后来改成 valid||valid 快进
这里注意不用substring 节省时间， 而是用 （s，int i，int j）

总结：
greedy， 尽量用， 满足条件就好， 不想复杂
recursive 分类没关系， if else 注意
不用substring 多用 （s，int i，int j）
找intersection 巧用大小s end time判断， 循环截至一般是while (i < A.length && j < B.length)

提高：
思路都是很接近的， 就是实现的分类不要太多，太细，太复杂， 一般肯定有只用一个细节判断的方法， 比如只由end time 判断下一步谁++

啊 为什么我刚刚码的反思 审核 然后就没了。。。。
难过
难道打卡不是这么直接回复的吗

今天 621 task schedule  same coolingtime
思路是对的， 但是最后没绕清楚。
greedy， 就是按照平常的解法来， max fre 先， 然后把 剩下能利用的都利用了， 没办法再加， 所以得到的一定是最opt
这里没想到： 当所有empty slot 都满了之后，其实有别的任务也直接安排再行后面，肯定也是满足条件的，
如果尽量利用empty 后 还有空的empty 也要加上， 因为是必要的coolingtime

98 valid bst
简单
桥梁--》 valid left && valid right && 左边最大《val《右边最小
所以需要int【】 m来记录 max min

base case leaf， 然后if 左null，else if 右null，else recursive

986 inteval intersection
思路基本对， 最后没成功写出来， 因为分类太多太细， 其实只要一些简单的细节， 就可以归纳
一般不会太复杂， 一般都是O（n+m），
结束条件一般是while（i<length&&j<len）,
然后注意你们两个没有相交，后面的可能相交， 而不能直接return， 然后注意思考下一个potential是什么

相交， 肯定是缩的，所以 start max， end min， 如果s<end, 才是相交的
一般i++else j++

680 valid palidrom II 快进最多一次， 能不能变成pali O（n）
简单， 这里注意犯了错误， 导致左快进和右边快进， 不是并列关系， 而如果左边不是， 不试右边直接返回， 导致错误
所以应该要 valid || valid

总结：
greedy， 塞，多加，不会变差，就是最好的opt
结束一般index 《len&&
注意并列情况用||， 别多想
找相交的办法， potential 思考来增量。

今天
438 find all anagram （sliding window，）
O（n+m） 本质优化在于计数判断过的不用for循环再多此一举， 利用已经算过的 只进行一次/少数判断，有点memo的感觉
p hashmap 存c几个a几个
初始化窗口，如果在里面-1，（需要的减少，如果==0，size--） 不在的不影响结果判断，反正不会误判
然后sliding 本质 进来一个新的，出去一个旧的， 如果旧的在里面， 现在没有了（+1） 从0变到1 表示size++， 如果旧的啥也不是，不影响，
for(char c:p.toCharArray()){
            h.put(c,h.getOrDefault(c,0)+1);
最后用size值来判断

还有一种 m int【26】的方法，用p初始化， need=p。length、
如果m【i】》0 表示还需要， m【i】--，need--；
m【i】--，need不变（因为我要的不是你）
最后也是sliding 用每一轮，每一个窗口的need==0 来判断

刚开始卡在了 总觉得跳一下好， 但其实在特殊情况里，最坏就要 O（nm）如果没有d，就没有memo，时间很差
所以好的就是O（n）

34 find first last index of target
O（n）简单，像这种sort array 和target， 只要想到有办法舍弃一半，减小size的，那就用binary search，好处就是好多都recursive， 都能减小proble size 那么在最后就是O（logn）
所以 int【】 来记结果，
mid=s+（e-s）》》2 这样 不会overflow！！
》》2==/2 快

《 舍弃右半边（nums，s，mid，t）
》 舍弃左（nums，mid+1，e，t）
==
左边 结果，右边结果综合，
左边的肯定是最小值， 右边只有最大值才是 -1的特殊情况
但可能138 （2，2）
9 10（-1，-1）

数组初始化： new int【】{-1，-1}；
int【】【】{{1，2}，{1，2}}；
或者，一个binary找最左边的，
一个找最右边
得到结果
2logn

173 bst  iterator
刚开始没看到follow up 对空间的要求，
不过最简单的当然就是遍历树 inorder
注意 凡是recursive 就是还有额外的空间function stack 要占用， O（h）
recursive 不能中间stop， 所以要自己控制就是custom stack recursive。 iterative

凡是树 本质离不开——》 //recursive 本质就一定用到stack，
这样实现了先到的 存在底下备用（后面信息， eg back track（本质是还有用的信息， 没有完全process 完的，要利用FILO的特点，滞留保存栈中， 只有全部利用完了， 才抛弃。））
stack 大法好， recursive 凡是先处理下面，才处理前面的都可以用stack。
pop 的是要的， 底下的是还有利用价值的， 扔掉的是真的没用的


每一步iterator 完， 要为下一个做准备， 以实现O（1）操作。
LinkedList  l。removeFirst（） removeLast(), O(1)复杂度。好，但是remove不是，
push/add pop （TreeNode not Integer才能保存所有信息）

349 intersection of 2 array， 找到一样的元素， 不重复就是要set
简单 set if inset 存进去， 注意 List.toArray(),  对list《Integer》Integer 不能用， 不会unboxing，  list《int【】》 是可以的
随意老实for 返回int【】

或者sort nlogn 》n 因为n很大时， logn》1
然后一样你大你++， 不然你++ 因为next potential 不一样， 直到一个到底结束， 这里不重复可以用 ！= re的最后一个。


注意：
树 recursive 可stop 可control iterative， stack 大法好。 pop 马上要的，丢掉彻底不要的，滞留还有利用价值的
sliding window，不要怕初始化， 然后处理，
二分法 sort target， == 特殊处理 综合两边， 或者单独分开 2* 不影响
不重复 set
new int[][]{{1,2},{1,2}}
new int[]{-1,-1}
for(char c:s.toCharArray()){
            h.put(c,h.getOrDefault(c,0)+1);

linkedlist 才有 getLast getFirst removeLast removeFirst
List<> l=new Linkedlist
l.... error
LinkedList<> l=new ...
correct