刷题打卡记录（找学习搭子）

yiest 发表于 2023-7-19 15:35
可以可以，可以就用这个帖子打卡，或者也可建一个群

楼主我有个群，能发我邮箱联系我一下吗，我share二维码过去，邮箱 david.chrisk.6654  at gmail.com

补充内容 (2024-03-18 11:13 +08:00):

解散了谢谢

7月19日刷题一道
Leetcode 127. Word Ladder

note1. 跟前面2道BFS思路非常类似[套路即：标记+队列 <- key words and key words of BFS]
note2. ***再次理解这种题型，
        2.1 outer while loop是保证队列一直不为空（这个的意义就是在遇到最小值，即最优解以前，确保所有的可能的趋向最终结果的解都能遍历，即穷尽所有可能）
        2.2 inner while loop 用size 这个变量（i.e. int size = queue.size();）来控制这个层级的循环完毕（像金字塔一样，确保该层遍历）[对于inner loop 这个size 是很重要的一个变量]
        2.3 在inner while loop里面就要边找边看有没有正式的解，如果有，就提前退出循环
note3. 写代码细节问题：求长度的三种方法 length, length(),size()
note4. 写代码细节问题：Character and Char 是两种data type in java
note5. 写代码有个小逻辑错误，然后把整段代码粘贴复制到online java compiler 去debug[另外online java compiler 好像不认识Chinese comment]
note6. 写代码细节问题：有些special case 看左边题目要求，或者可以省略，比方明确说了，beginWord != endWord

DFS概念总结
1. 需要用到以下两个数据结构：
        1.1 栈(stack)：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
        1.2 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。
2. Pseudocode (recursive implementation)
        ^ https://www.programiz.com/dsa/graph-dfs
        ^ 所以是有两种完成方式吗？？？[目前大致看了一下答案，好像都是recursive, 会不会overstackflow?]
3. DFS 和BFS 的差异在于，深度优先搜索在得到一个新节点时立即对新节点进行遍历 [目前看代码是BFS是下一层的新节点是放在queue,即排队，放在后面；而DFS每次是把更新的东西放在前面，即stack]
4. 从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。[可达性又可以转换为是否联通的connected]



7月21日刷题一道
leetcode 695. Max Area of Island

note1. 这个题大致在学校见过的，而且跟那到ink blur题几乎一摸一样
note2. 这里有两个维度要考虑，一个是坐标（i,j）,一个是坐标对应的数值（即0 or 1）
note3. 实际的做法暂时没有用到stack（why?？）, 就是用到了recursive 的做法，首先创建一个dfs函数，这个函数内部不断重复呼叫自己(dfs)，而且有几点需要注意
        3.1 针对这道题，函数传入参数有3个，dfs(int[][] grid, int i, int j), grid 是需要传入的，因为已经visited的地方，就不要重复visited,即grid是动态变化的
        3.2 也需要传入i,j(即坐标), first to check the validity of i and j, if out of boundary then it means that it reaches the boarder and then it can return 0 (走到边界的地方就开始收网往回走)
        3.3 去过的地方，要进行标记（这里的标记非常粗暴，直接就是把数值由1改为0）[标记的功能由grid代替]
        3.4 针对这道题的循环（或者stack 功能，像一个串上的蚂蚱拉起一窝），是再次利用dfs循环呼叫上下左右四个方位的框框
        3.5 因为这道题有两个数值维度，即需要考虑check validity of i,j, 也需要check坐标对应的数值（0，1）
        3.6 这个dfs 函数的意义： this is the dominion card game and returns the final result of the area before it has explore all the possibilities（即获得局部的最终面积，not 最终）

7月22日刷题3道

leetcode 200. Number of Islands

note1. String is double quotes, and char is single quote
note2. How to compare two chars? NOT Character class, just use ==
note3. 跟上一题非常非常类似，一个是counter, 一个是面积的叠加
        3.1 check the validity of i and j
        3.2 check the value of that box(if it is '1', check the surrounding, which is 4 directions; if it is '0', skip)



Leetcode 547. Number of Provinces


note0. 由题意，这个矩阵应该是正方形
note1. 想到这个有点像线性代数, 好像一个矩阵半边（左下三角）的数据都是重复的（而且对角线也是没有用的，因为自己总是和自己链接）
        ^ 上面两个结论判断出i,j的循环range
note2. 忘记算孤立的岛！
note3. 思路也错了，对于这个例子isConnected =[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]
        我开始以为是上右三角画十字架（即第一个坐标变换，第二个坐标不动；然后第一个坐标不动，第二个坐标变化），但是，(0,3)and (2,3)is connected, but, (1,2)is also connected, so 画十字架是错误的，因为2一开始是横坐标，随后变为纵坐标
note4. 最后提交的runtime 和 memory 效果都不好，我的思维是，分为两个计数，一个count连在一起的cities,另外一个是标记已经被绑定的city(即孤立的city),然后把这两个数合并; 然后不仅仅是画十字的，交换i，j的位置，继续画十字架
        - dfs(isConnected,i,k,list);
        - dfs(isConnected,k,i,list);
        - dfs(isConnected,k,j,list);
        - dfs(isConnected,j,k,list);
note5. ***改进办法
        - cyc2018没有考虑矩阵，upper right triangle,而是把 **一对坐标(i,j)** 变为 **一个index(i)**
        - 好友关系可以看成是一个无向图，例如第 0 个人与第 1 个人是好友，那么 M[0][1] 和 M[1][0] 的值都为 1

note6. 需要重新做一遍



Leetcode 130. Surrounded Regions
note1. 【我的思路】比之前做的几道题多了几个变量，一是是否visited的矩阵图, 这个要跟原来board分开，因为board里面flip要遵守一定原则，在没有局部遍历万之前，不知道是否需要flip;另外还增加了一个变量LinkedList<Pair<Integer,Integer>> q，来记录是否需要flip的（记录着，以免可能需要flip）,即这个局部‘岛屿’没有挨到边缘,则flip这个linkedlist里面的坐标，如果挨到了，作废
note2. 提交以后，runtime and memory 非常不理想，看一下cyc2018的做法
        2.1 cyc是逆向思维，根据题意，找到四条外边，及四条边相邻的等于'O'的box
        2.2 把这些不要flip的box保护起来，即变为‘T’
        2.3 剩下把没有保护的‘O’进行flip, 有保护的box变为原来的‘O’ ，思路非常简便清晰

7月23日刷题2道

leetcode 417. Pacific Atlantic Water Flow

note1. 再次回顾一下，使用dfs的意义是求解 ***可达性***
note2. 基础知识，"Java: how do I initialize an array size if it's unknown?"
        array 和 list 是不一样的概念(url: https://stackoverflow.com/questi ... size-if-its-unknown)，url里面第一个解释很好，array如果要扩增size,就是**数据结构**里面学的，copy and paste everything to a new larger array,相较之下,arraylist(属于list)可以automatically resize
note3. 关于list of list的bebug
        ^ url: https://stackoverflow.com/questi ... aylist-of-arraylist
note4. [我的思路] 创建了一个grid形式的visited,创建了2个dfs(一个pacific, 一个Atlantic), 创建2个dfs的原因是同时到达两边不好标记是否visited,因为走一边不要走重复的路，但是两边交叉是可以走重复的点？
note5. 还是感觉有点神奇，这个也是应用于之前几道DFS,比方传入的一个int[][] heights, dfs以及下面延伸的dfs都可以对其(heights)进行修改
note6. runtime and memory非常不理想，对比cyc2018的答案
        6.1 cyc 又是进行了逆向思维，创建了2个boolean 形式的grid
                - boolean[][] canReachP = new boolean[m][n];
                    - boolean[][] canReachA = new boolean[m][n];
        6.2 然后分别从两端海岸线（低海拔）倒推水源的高海拔的坐标
        6.3 然后把两个grid重叠（即重叠canReachP and canReachA）
        6.4 我是传统的思路，循环整个网格，从高海拔到低海拔，如果低海拔靠到海边，就算能流过去（顺着题意做的）
note7. [基础知识] int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
                ^上述数据结构 + 搭配循环非常好用，for (int[] d : direction){}
note8. 按照cyc的方法重新做一遍

----------------------------------------------------------------

Backtracking 的基础知识

Backtracking（回溯）属于 DFS。

1. 普通 DFS 主要用在**可达性**问题 ，这种问题只需要执行到特点的位置然后返回即可。
2. 而 Backtracking 主要用于求解**排列组合**问题，例如有 { 'a','b','c' } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：
        - 1. 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
        - 2. 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。
----------------
[back to back swe]
1. 3 keys of backtracking : choices; constraints; goal
2. 演讲者的意思这个每一个都需要试错（一个grid），所以runtime 会是exponential
3. https://www.youtube.com/watch?v= ... kvnOCTI&index=9

--------------------------------------------------------------
leetcode 17. Letter Combinations of a Phone Number

Note1. 单单就针对这道题给的第一个例子而言，如果给2位数，那就是2重for循环，如果给3位数，那就是3重for循环，以此类推[但是这样解题肯定是不对的...]
Note2.
        2.1 Cyc2018的做法非常巧妙，正如他所说的，需要deep search的时候需要删减
        2.2 删减的原理配合back to back swe 画的树状图就懂了，往下走就增加append，往回走就删减delete，代码非常精妙
        2.3 配合swe说的，这个goal(3 keys中的一个)就是填满给定的digits, 所以goal就是我们的base case(有点像之前做的如果碰到边界，那么即可返回)
        2.4 代码非常简单，但是choice(3 keys中的一个)，就本题而言是for 循环三次
          for (char c : letters.toCharArray()) {      //选择，就本题而言，每个数字都是三种选择
                prefix.append(c);                         // 添加
                doCombination(prefix, combinations, digits); //前面一个digit 已经确定好了，剩下后面位数的digits的排列组合打包交给这个函数
                prefix.deleteCharAt(prefix.length() - 1); // 删除，这个删除是为了方便下一次循环使用这个slot
                    }

Note3. 写代码的细节
        3.1 cyc2018在呼叫函数的时候，传入参数直接就是一个new StringBuilder()
        3.2 如何char的single quote?  --> (2个char相减)'2'-'0' 这样可以得到int 2
        3.3 把一个string 变为array of char 有一个内置函数 letters.toCharArray()
        3.4 跟所有的recursive 函数一样，（?）感觉就是需要写一个局部处理措施，然后定好base case 知道在哪里停下来，剩下交给函数内部自己处理
        3.5 cyc 一一对应的index 细节也非常巧妙 因为根据题意，本来就是一一对应的，（ie: char cur_char = digits.charAt(partial_result.length());）

Note4. 理解Stringbuilder 和String 是类似的，也是一种class, 比string 高级的在于，有很多方法可以用，可以迅速修改string
        ^ https://www.geeksforgeeks.org/st ... java-with-examples/
        ^ https://docs.oracle.com/javase/8 ... /StringBuilder.html
        ^ 更多方法看官网介绍, 就这道题而言，因为最终函数返回的List<String>，所以还需要把stringbuilder class转化为string

7月29日 刷题1道

Leetcode 93. Restore IP Addresses
[类别： backtracking]

Note1. 回顾back to back swe 说的，3个基本要考虑的，constraint, goal(base case), choice
        - another is : choose -> explore -> unchoose
        - base case 有点像走到底部（触底），然后满足条件，记录，然后往回走
Note2. 有点困难的debug, 一个是因为不好想，放在java online complier 上面，[打印发现bug]为什么每个点前面都是1个数字，为什么没有2位数，3位数[感觉像是没有循环跑起来]

1. 1st problem found here is that we should minus one in *unchoosing* part
2. ^ the changed above triggers another problem that is indexOutOfBounds,
then we need to handle some special cases
3. then, 2nd problem, use print function to print out 2 states "before deleting" and "after deleting"
    - since the add pattern is "+digits+dot", then the delete pattern is same "-dot-digits"
    - from the print results, i found the *first* cause of the problem, (suppose s is "12345")the original is "1.2.34.5."
    - after deleting which should be "1.2.34.", however it prints "1.2.34"
    - the key problem here is that when I find the satisfying result, i delete the dot and add this to the final result data structure(main problem here!)
4. lastly, 3rd problem, valid_sub_digits function is not right
        public static boolean valid_sub_digits(String s){
                int number = Integer.parseInt(s);
                if(s.length()==1){
                        if(number>=0 && number<=9){
                                return true;
                        }
                }
                else {
                        if(number>=10 && number<=255){
                        return true;
                                }
                        }
                return false;
   
                    }
    -> in this function,023 is a valid substring which is not right bz leading zero
   
5. `partial_result.append(cur); partial_result.append("."); //line 1 dfs(partial_result,results,s); //line2 partial_result.delete(partial_result.length()-cur.length()-1,partial_result.length());`
    - ******we need be aware of this process, line2 would not change partial_result since dfs is a closed loop(it adds sth and then it deletes that stuff)
    - ******So line2 will give back partial_result as it was in line 1
6. how can we manipulate the string easily? --> string builder class

7月30日 刷题3道

Leetcode 79. Word Search
[类别： backtracking]

Note1. https://www.geeksforgeeks.org/ja ... the-output-console/
        ^ Arrays.toString(a_variable)
        ^ Arrays.deepToString(a_variable)
        ^ pls remember these methods! 这个是方便放在online java compiler 进行打印检查看每个步骤的问题
Note2. 跟上一道一样，总感觉思路是对的，但是预期output就是不对，然后放到online compiler 打印结果，发现是可以找到正确途径的，为什么base case 没有反馈抓到这个正确结果呢（即应该返回true, 为什么反馈false）
Note3. 进一步打印结果，发现flag 这个变量没有变成true,[这里有一个重大的知识漏洞]就是java is always passed by value, 除非特殊情况，如（https://stackoverflow.com/questi ... ce-or-pass-by-value）在某些情况下（例如上述网址第一个回答里的第二个例子一样）和在IP address 里面那道题一样，在main function 里面呼叫一个函数，是可能改变主函数内的变量（在IP address 这道题 cyc2018答案 里combinations 被函数doCombination 改变了 ）;其他情况下，函数传递值，传来传去应该就是function scope是不能改变的
Note4. [应该不是最简洁的方法]一样画葫芦，按照IP address那道题一样，设置了一个list data structure, 这样就可以通过函数之间的传递修改这个list （达成目的：通知main function ,我找到合适的解了）


===========


Leetcode 257. Binary Tree Paths
[类别： backtracking]

Note0. 审题及其他
        - all here mean exhaustion and permutation and combination
        - then all paths here it means backtracking
        - one question is that should we set the unvisited node? OR should one node be counted twice --> I think it can visit a node twice
        - 3 keys : constraints, goal(base case 这两个有点可以互换的意思), choice
Note1. 1个好奇的点，为什么它要写，Given the root of a binary tree [这个树上所有点都是root吗？]
Note2. 另外一个神奇的点是，TreeNode root 包含这个树的所有信息（？相当于是一个地图），但是我又可以设置一个TreeNode cur_node 来推进search or explore [这个想法错了! 看note3 不需要每次都传递1个fixed final root 作为map]
Note3. ***感觉这个和之前做的几道题不一样，很*新颖*的地方在于，之前是操作一个字符串，或者一个grid （有map可循）这个tree的思路变了，好像你给这个tree的**任意**一个点(node)，它自己（隐藏的背负了一个map）,可以知道往左走往右走的边界（自带一个map）
Note4. 其他技巧（如何计算一个整数的位数 or # of digits）
        - https://www.geeksforgeeks.org/pr ... -different-methods/
        - 参考上面网站，使用最后一个方法，即首先转换为string，然后再求string的长度
Note5. 技巧 class String 和 class StringBuilder 之间的转换

===========

Leetcode 46. Permutations
[类别： backtracking]
Note 1. 感觉这道题跟之前的题不一样的点，[not sure]这道题既需要用一个arraylist来标记path, 又需要用一个visited ds 来标记是否已经使用过这个点了 -->[事实证明是这样的]
Note 2. ***Met this twice, so strange[报错如下]:
        Incompatible Types.
        List<List<Integer>> output = new ArrayList<ArrayList<Integer>>();
        - https://stackoverflow.com/questi ... aylist-of-arraylist
Note 3. 出现一个bug,就是最后可以成功获取partial_array，但是加到final_results的时候应该是出现了问题，所以打印的东西像这样[[], [], [], [], [], []]
        见两个online compiler 的截图，打印结果都是非常奇怪？？？？
        - 技巧，如何给一个ArrayList<List<Integer>> final_results 这样的结构添加一个list[ANS: 直接就是add function 问题不出在这里]
        - 大概知道原因了，因为这个是***pass by reference*** 所以会有截图20230730_2的效果
        - 想起来，java 课写的作业有可能就是犯过同样的错误 ^

7月31日 刷题1道

Leetcode 47. Permutations II

[类别： backtracking]

审题
        - similar to last question
        - another lesson learnt from last question is to be aware of pass by reference
        - hashmap here is like visited before except it is more complicated than before

Note1. 如何创建一个类似像python里面dictionary(key-value pair) 一样的ds, one I can think of is pair class; 网上说用hashmap
        - https://stackoverflow.com/questi ... equivalent-to-idict
        - the url above mentioned hashmap
Note2. Another I ignore is that 做排列组合的时候，用arraylist的add, 还是可以让整个添加过程有顺序感，ordering
Note3. How to iterate through a keyset or value set, I have searched this a lot times. Still can not remember
        - https://www.geeksforgeeks.org/iterate-map-java/
        - 这个技巧除了做题，另外打印整个map,或者只打印map_key OR map_values 帮助bebug
        - hash map 可以直接用system.out 打印!!!!
         ^ https://www.geeksforgeeks.org/hashmap-remove-method-in-java/

Note4. 又出现了，打印出来空壳的情况，预期[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]], 可是打印的结果为[]
        - 做这个backtracking 思路是对的，但是处理数据（尤其参数传递）总是有问题
        - 用错hash map的方法，应该用put 去更新value, 望文生义的选用了replace
Note5. 感觉hashmap里面key-value中value值变化，增减，还是很有套路和实用的

8月5日 刷题2道
（但是对于这个choose explore unchoose 过程里面的choose步骤，非常困惑，如何可以免去重复 ，这两道题还需要回头看）

**leetcode [77. Combinations](https://leetcode.com/problems/combinations/)**

1. 这道题的原理仍然不明白，而且为什么（n-k+1）不会超出range右边界 => [因为] 右边界为n， (n-k+1)<n 是成立的
2. cyc2018的答案很简明，而且没有一个visited 之类的数据结构来标注是否来过这个点
3. [因为这道题默认就是线性往右边增加]大致感觉这道题 (^hat)的位置就是（n-k）起点长度；^（start_point）的意义为i最远能到达的位置，如果start_point跑到hat右边，那么就没有那么多k可以供选择
   
    见图：k and n relation.png
   
   
4. 这道题最精妙的地方是，在dfs方程里面，同时在n上加1，然后在k上减一，减一有一个好处，可以增加start_point的值
5. 原理还需要回想！！（这道题没有真正的懂）如果从实际数据倒推公式的话，（可能）是可以的，之前尝试了，但是有重复，对规律理解还是不够
   
    EX: n=5 c=3  _ _ _
   
    上述3 slot的index为0，1，2
   
    从最终结果看[index 0 对应树的第一层级；index 1 对应树的第二层级…]
   
    index 0 取值： 1 2 3
   
    index 1 取值：2 3 4
   
    index 2 取值：3 4 5
   
    见图：dfs binary tree.png
   
6. 另外cyc2018还提到了剪枝，这个是什么？
=================

leetccode 39. Combination Sum (Medium)

1. 咋一看这道题很简单，实际上不是，因为需要考虑如何避开重复的结果，例如[2,2,3],[2,3,2],[3,2,2] 实际上是三个同样的结果
2. 如果用hashmap 来装key-value是否会超时？不可能；因为每一个子结果都是一个hashmap 结构，这样看来太复杂
3. 思路跟上一题一样，序列是ascending 排列？尝试解决但是遇到一个bug, 应该是以前没有遇到过的，[java - Concurrent Modification exception - Stack Overflow](https://stackoverflow.com/questi ... ification-exception)
4. 还是出现了和77一样的问题，就是，简单的做题思维，并没有想清楚如何去除重复的值
5. CYC2018再一次用了减法(加法也没有问题)，就是不断的修改target, 然后提高i 的起始值，让i 的起始值越来越大
6. 看这个视频([L8. Combination Sum | Recursion | Leetcode | C++ | Java - YouTube](https://www.youtube.com/watch?v=OyZFFqQtu98))，有启发，一是binary tree, 第二个****思维模式***是对于每一个元素，考虑它是否Include或exclude（instead of原来的线性的叠加）【这个是另外一种方法，因为它用了两次DFS】
7. 关于cyc2018答案里面的start和i的for loop结构（下面截图假设选择就是4种，所以i的范围为[0,3]）我觉得这个for－loop结果比（选择用加法还是减法）重要许多
见图 start and i in recursion.png