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

今天
71 simplify path
不会unix 路径，不过以后就知道了，
string题目 string【】 “xx“.split ("/") 大法好，
其实要简略，就是要把没必要的不加入，所以 肯定分段符号，然后自己决定那些加，那些不加， 所以这样
然后注意名字命名随意（home..） ... 也是名字，
然后找到特殊情况 ，..   . 分别进行什么操作，
simplify 就体现在。。 可以少一个文件夹， 所以用到stack 多pop一个就好了。666

最后special case 要注意（/。。/） 如果结果empty 要 return”/“


767 reorganaize string
aab bab 可不可以 一样的不重复
和 昨天一样，
map heap sort 多的先，
needfill 来判断能不能，不能返回，能再生成string
我的写法是分成maxcount part
Stringbuilder【】ss=new StringBuilder[], 快
然后for循环夹在每一个string part后面，下一个赋值的ss【 z%s.length】
最后再连起来。
但其实还有一种方法， 因为就是间隔，所以可以+2， index来给，
这样就能保证一样的都是隔一个，
vvvlo   vlvov
还有一种是，pop两个， 安排，再count--，再push回去， 最后可能剩下，剩下的肯定只有一个。
答案666
int【26】
count+=100
count【i】+=i
因为100》》26
所以不会影响count sort
所以ct=count【i】/100
char=（char）（count%100+‘a’）

426 convert bst to dll
昨天的一样， O（h），必然要recursive，stack，
只要初始化，然后得到head
需要before cur Node
初始化before 进入while 循环，before cur 互联前 先stack update，保证第一个都是最小的。 这样cur right 才能和之前一样， 用完之后再赋值更新，
最后出来， cur就是最大的 ，再和head 连

结束战斗
注意如果leaf :  root.left=root; root.right=root, return root

答案还有， recursive 本质， dll 已经直到全部信息， 尤其是头尾， 直言
base case null
root 互联自身， 然后connect 左dll root， 右dll
完美

注意 Node before=。。。
before的功能就是 数组的index， 指针到哪里， 他自身傀儡代表进行操作，
然后 指针指下一个。

278 first bad version
binary search 简单
但是用helper 不好在于空间多了recursive stack
我这里其实只要缩小空间，index
所以只只要
if left=mid
else
right=mid+1
之类的， 直到left==right结束
所以判断条件是while（left《right）



反思：
String split 分隔符，关键点 特殊情况， 能返回判断的先返回， 再生成
间隔 分半， 两两占用， greedy体现在maxfre先， index+2， 只要填充了 就好了， 不一定一样
int【26】 code/100 %100 大法好 100》26， 不影响排序

before cur head
或者recursive 再connect 左答案 右答案

binary search 可以不用helper 直接挪指针， 本质就是缩小空间啊

今天都写出来了
虽然都有错 但是思路对的
之后要加强检查 ， 再 运行
别依赖有错再找， 争取会的都写对，注意小细节。


preorder inorder postorder
体现在root位置
前 中 右
其他总是左右

今天
721 Account merge
没想出来
看答案后总结 graph + dfs/bfs   or  union find
凡是这种merge connect的题， 解法一定是 build graph 因为graph 不会凭空出现， 要你的理解，抽象什么作为node，什么作为edge就是什么 时候有edge，
connect 体现在有关系， 形同或者什么的就有connect

这题， node 一般是 小细节的小元素， 这里就是email， 所以  建立图， 本质是edge， edge一般是用adjacent list 来体现edge
a在b的hashset里，b在a里 就是a-b 有edge。
然后图， connected component 一定小心circle 导致死循环， 所以一定有visited hashset，
都先要判断，这个node 没visited过，就是没处理或者加入过， 我才进行他的操作， 不然就是死循环，
然后先加入 visited 才后续childern 或者neibor操作。

dfs 也是先not in visited， 才操作， 操作中先add visited 才recursive neibor， 把neibor 都recursive 完了 才回去母recursive， 这里体现dfs， 通常需要list， 作为参数传入

uf， find parent 的parent 直到parent【x】==x
union（a，b）， 直接把parent union


1249 minimum remove valid （）
没写出来， 因为陷入stack， 从前题目的限制， 总觉得要这么想，所以有的时候做过类似，可以这么想，但不要限制住。
配对之类的题目。 一定是1， -1， 》0， 《0，==0，0
所以（==+1， ）==-1，
如果和till（index）《0， 肯定要把），删了， 因为他肯定多， 这是最少的remove， 然后 if 和==0， 结束， 》0， （ 多，
一种是反正走一遍， 删（， 第二种是多的肯定在最右边
结束战斗

这种配对题，一定for循环， 可以计入删除的index， 最后再O（n）一边得到结果， 也没慢多少，
一边不行 试试正反两边走， 可莪能就得到结果了

211 add search word data stcuture design
没写出来，
这种 common prefix 的题 一定是 trienode，
树 就体现在他的内容里还是自身的array， 这样不断连接下去， isword 的作用是判断是不是word，
abc ab应该return false， 因为他只是prefix而不是exactly word！！ isword 重要。
public class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public boolean isWord;
    }

好处是 abcd abcf abcg  找abcg的时候 不用 重复abc 3次， 而是for循环真正需要for循环match的
而且，凡是for循环match的题，肯定可以recursive ， 当前的和 之后的， base case 就是最后长度一样的是不是isword
if（node.children[i] != null && match(chs, k + 1, node.children[i])）
   
    private TrieNode root = new TrieNode();

278 first bad version binary search
while（l《r）
也是left right 直到肯定left==right 停止， 因为mid=l+（r-l）/2，所以重复自身
return left


总结 今天的是好题，

connect merge， graph， bfs， dfs， recursive， both visited，
先 if not in visited
操作
    add to visited
   后续（recursive， with list） or bfs


graph node element adjacent


正反走两边， 删除记录， 配对，+1，-1，0，==0，》0，《0

trienode
【】， isword
common prefix

binary 《， ==，

早点补上少的12题

今天 863 node in bst k distance
bfs， 距离
3路， l，r，parent
第一遍recursive，找parent， hashmap里，dfs好（parent，next，h）
然后target bfs， queue里target， 这里可以巧妙， null，来分层level结束，作为标点， null，target，

还有我的方法， 找到path ，
1， k target，
2 每一层上溯，parent， recursive，就-1， 注意visited 直接return， 不然死循环，

path to
dfs， stack， add root， 初始化 之后while， right， left， peek子子子
新加到list， in visited 就pop， removelast 来统一对应[b][/b]


133 clone graph
new Node
hashmap 旧的，新的， 这样新的细节属性update， 立刻找到，
visited 运用，防止circle，死循环，
防止没有circle， 只能树， 所以 add 关系，要在 if not visited 的外面
没clone 就 h.putIfAbsent(k,new());
然后处理 该add add
dfs 也可以

636 exclusive time
stack before cur 关系
start push，，end pop
如果
s： s s t1-t2
    e  s  ， stack 空， 空闲，不空t1-t2-1 累积到stacckpeek里
e： e e -
     s e t1-t2+1

987 vertical bst

简单， recursive l r +1， -1
priorityqueue 排序
new int【】， 直接
解决

总结：

dfs， recursive， parent， bfs，distance， 手几只，if not
dfs stack r，l if visited   pop removelast 路径

bfs queue size， /null 分层

putifabsent
然后处理




分类

今天
785 is bi graph
简单， 染色， bi， +1， -1， int[] 初始化0；
注意， 可以有多个connect component，
也依然是bi，

所以 for 每一个node， 如果 没有visited h 过， 那就重新 new 一个 bfs q， 或者 dfs， stack， 的过程，
只有子 不在里面， 才put 对面颜色， 然后add q/stack 里。

最后 不行就return


523 continue sum array  %k
注意 我只想到了 sum【i】-sum【j】
但是更好的是， 直接 remainder 放到 hashmap 里， 如果 后面又出现， 直接就是找到了，
（a-b）%k==0   a%k==b%k

3%-4= -1.。。-1
7%-4=-2.。。-1

4%-4=-1.。。0

所以 不管+- 都可以

本质在于+ 部分， 地位一样 - 前面， 抵消前面

304 rectager array
想到 记录 colsum 然后 O（col 数）

答案666， dp， 几何知识， 区域面积， +-多+补 初始 dp【r+1】【c+1】， 这样 初始化就是0； 给一个多的基础， 然后 dp
     

      dp = new int[matrix.length + 1][matrix[0].length + 1];
    for (int r = 0; r < matrix.length; r++) {
        for (int c = 0; c < matrix[0].length; c++) {
            dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
        }
   }

然后 只要O（1） 就可以

824 goat
简单
注意 for（char c: "aeiouAEIOU".toCharArray） set.add(c)
的巧妙
要比连续的几个0
m【i】==0&&m[i+1]==0
sb.deleteCharAt(sb.length()-1)

总结：
多个connect component， 注意， 每个部分都 bfs， dfs， +1， -1， 队
sum reminder ， hashmap， O（n）
注意 for（char c: "aeiouAEIOU".toCharArray） set.add(c)
的巧妙
要比连续的几个0
m【i】==0&&m[i+1]==0
sb.deleteCharAt(sb.length()-1)

昨天前天
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

今天
2easy 4 medium
256 paint house
经典dp问题， 其实我有往dp想，但是还是没想出来， 有点畏难，看了答案一个开头，确定是应用dp，我就立刻想出来了， 所以不要怀疑自己
dp， 本质能看成树的问题的都可以，本质就是treenode 值可以记录， 不用接着算
memo 和dp 有区别。
memo， 也可以是recur
sive中用， 就是算过的值，直接h。get， 不然再算， 这里recursive中就省了时间
dp， 是iterative， 体现在 本质sub 问题， 和我是一个问题， 只不过问的一个是n-1， 一个是n， 所以就是假设已经知道
n-1的结果， 怎么处理比较之类一下， 就得到n的结果， 在这个基础上进行initial， 就可以。这样的话，就是O（n） 一遍，一般
【r，g，b】 对应的到他为止的 花钱， 最后三种情况结束的min


optimal local == greedy or dp
dp=optimal local +overlap sub problem 因为用到了前面的， 那我就记录下来， 一般可以空间优化， 因为只要pre
Dynamic programming iterative
memoization, which is recursive.

152 maximum subarray product
这类continues subarray 肯定一般用到 到current index 为止的 product /sum
然后这里用了pre【】， 一个是 max， 一个是min，
然后处理cur《0， 一种update， cur》0， 一种update
注意 连续从0到cur product， 可能会有==0， 所以 0，6， 这种max 就要变成6， 才能分手开始新的potential恋爱
global 保存
if (a[i] >= 0) {
      max = Math.max(a[i], max * a[i]);
      min = Math.min(a[i], min * a[i]);
    } else {
      int tmp = max;
      max = Math.max(a[i], min * a[i]);
      min = Math.min(a[i], tmp * a[i]);
    }
   
    ans = Math.max(ans, max);
因为max》min 所以一个比就好
初始化一般初始化自己， 这样一个的情况不会错，都是0这种


366 findleaf
这题就是
isleaf
然后每次都 新的从 root 开始dfs， 新的stack， 然后 cur， 如果是left leaf， 就把parent。left==null， right 同理， 然后 加到stack， 这里不用 seen
这样知道， remove 到root 是 leaf

或者答案是 树就往depth 想， recursive 一般都是从null（leaf） 开始
然后 vlevel leaf==0，
level 上面一层就是1，
这样 parent level=max（llevel，rlevel）
解决

比我好， 因为visit 一次node 都有了

244 shortest word distance
aabbc
这种 可能a， b 都有多个
因为多次 repeated 就一般hashmap 省后续，
然后本质 利用sorted array， 你++， 他++
【1，4】【0，2，3】
就是找这个的abs min，
i，j
《 i++；
》j++


243 shortedst
a 1， b -1
如果是 记录pre 和 preindex
是 1， 1// -1，-1
直接update pre， 和preindex
不然sum=0； potential global比较， 是1， 直接返回，
解决

150 reverse polish notation
简单 一般用到stack， 括号配对组合问题
integer 到 stack 里， 遇到 op 就处理， 相当于（）， 算出结果， 然后push stack， 作为新的
这样 rpn本质就是 不用括号，1 2 + 就是op 在后面

j解决


总结：
dp， 树，recursive sub same problem， optn+（cur）=opt（n-1）  overlappiing iterative
memo recursive， hashmap， 不用又计算
也可以多个辅助pre dp min max 之类， 分手新开始的可能性， 0/《0

树， dfs ，bfs， level depth 的应用---》 recursive base--leaf/null ， paarent=process（lre，rre）
配对 op，组合（） stack

repeated hashmap sorted 你++， 他++

今天
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 注意是等于