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

之前刷了20题，现在计划每天刷1-3题，另外找学习塔子，请私信联系方式。

补充内容 (2023-07-20 06:46 +08:00):

刷题参考：https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E7%9B%AE%E5%BD%95.md

补充内容 (2023-07-20 06:50 +08:00):

貌似上述url需要手动粘贴复制

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月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月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月4日刷题一道： leetcode153. Find Minimum in Rotated Sorted Array
note1: 具体代码的错误为，TIME LIMIT EXCEED 第一个需要注意的是，if condition 不是固定和固定的最右边的值的比较，而是和最新的high index 比较，因为整个数据段落是一段焦距更小的段落；第二个错误是while condition 多加了一个等号，使其陷入无限循环
note2: 该题比较特殊，因为只有可能是如下两种case(见截图)
Untitled (1).png

7月5日刷题一道：leetcode34. Find First and Last Position of Element in Sorted Array
note1：需要用两次binary search, 否则如果找到左边或者右边等于target, 然后逐次加减一来找另外一个边界（或者middle 刚好等于target 也需要左边右边同时扩展，比较复杂），而且如果左边和右边间隔距离很长，then it is O(N) instead of O(logN)
note2: 找左边端点和右边端点并不是完全对称的做法，时刻谨记infinite loop 的问题
note3: 感觉二分法有点像数学证明题缩放，既要高效，又不能缩过头了

7月6日刷题一道：leetcode 241. Different Ways to Add Parentheses
(1) 这道题属于divide and conquer, 和之前学习的recursion 非常相似; 【类似想法】就是我只关注汇总结果，剩下的sub-task 交给其他人做
(2)第一次提交忘记非常重要的一点，就是设置base case, 即剥洋葱到最后一层，程序应该怎么做，没有写，所以返回的结果全部是空集 ，即需要加下面的代码
//非常奇特的一点是，如果string的长度是1 或者2 ，形式不可能是1个数字加operator，只能是纯数字
        if(n==1 ||n==2){
            result.add(Integer.parseInt(expression));
        }
(3) 分解的左边的sublist 和右边sublist, 需要一个for-for loop like a grid , 求出current operator 的result list

7月7日没有刷题

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

7月8日刷题 1 道 leetcode 95. Unique Binary Search Trees II
note 0. 不要被题目output 的形式吓到，就是list of treenode, 即是各种可能tree 的结构的集合
note 1. 95 题和241 题的区别是额外引入了BST，这个结构的特点是左边的值要比current 小，右边的值要比current 大( 即 The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key.)
note 2. 鉴于上面的性质，这个必须要新增一个函数，方便有一个（low,high）的区间才可以满足上述BST 的性质
note 3. base case 是两个，一是当low<high（即没有点，那么就是null） , 二是当low==high(即只有一个点)
note 4. 小细节，这里的low , high 是取值（即node 里面的int val）,那么low初始设置为1  instead of 0 since it is not index
note 5. 进一步理解这个for-for 循环，如果是第一层分配的话，每一次这个for-for 循环 result.add(a); 是增加一种可能性（增加可能的解到这个list）
for (int p=0;p<left.size();p++){
                for(int q=0;q<right.size();q++){
                    TreeNode a= new TreeNode(k, left.get(p), right.get(q));
                    result.add(a);
                    //增加一种可能性（可能的解到这个list）
                }
            }
note 6. 示意图如下
Screen Shot 2023-07-08 at 7.02.49 PM

2023年7月9日刷题 1 道

BFS traversal 基础知识
(0) url: https://www.geeksforgeeks.org/br ... or-bfs-for-a-graph/
        ^ 搜索原理比较清楚
(1)需要下列两个数据结构来实现BFS
队列：用来存储每一轮遍历得到的节点；[用作while 循环]
标记：对于遍历过的节点，应该将它标记，防止重复遍历。
(2)队列（queue）后面进，前面出，用的是linkedlist
(想像数据结构的课，这种操作用array做，有点麻烦，因为去除前面第一个元素，需要依次挪动后面的元素，费时间；
如果是doubly-linked list 应该是非常简单的，因为标记了head node and tail node)
(3)具体java methods: queue.add();       queue.poll();
        ^ https://docs.oracle.com/javase/8 ... til/LinkedList.html
(4)标记：有一种case是   boolean visited[] = new boolean[V];//V是需要遍历点的个数
        ^ 默认初始值均为false
(5)BFS用途：求最短路径
(6)Pair<Integer, String> 是一种数据类型; ,methods -> p.getKey();  p.getValue();
        ^ https://www.geeksforgeeks.org/pair-class-in-java/
        ^ 感觉这个pair class 有点像python 里面的dictionary

------------------------
[类别 BFS]
leetcode 1091. Shortest Path in Binary Matrix(Medium)

note1. 由于这道题是网格，所以放进队列（queue）的是Pair class（代表网格坐标）, 该class的第一个元素和第二个元素可以分别由getKey() 和getValue 获得
note2. 这道题最经典的地方是使用两个while 循环，外面的循环是整个queue的长度，里面的循环是当下这一层（layer）的遍历，即第二个while解决了【如何确定开启了新的一层layer??】确定这个很重要，因为每一层，就是一个长度阶梯加一
note3. 这道题的陷阱，即第一个元素（index is （0，0））可能为1， 直接return -1
note4. 层数（layer个数）就是最短路径的探索，想象为水面一圈圈荡开的波纹

[类别 BFS]
2023年7月10日刷题 1 道
279. Perfect Squares

note1. 按照1091题的方法，会出现time limit exceed when n=7168; 想到的两个改进方法，一是不需要Pair class 来记录分离出来的数，只需要记录剩下的值的大小即可，比方12，我之前记录的点是(1,11)(4,8)(9,3),其实不需要pair,只需要记录剩余值即可，即 11,8,3；二是按照cyc2018的办法来产生perfect square
note2. 改进了第一个，并没有提速；改进第二个，用加法来增加(即每次增加substract, 而sub之间的diff每次用2递增)
note3. 还是超时，发现cyc 是一次性把n 下面的square numbers全部产生了，这样就不用每次再额外生产了
note4. 最后写的比较复杂，第一是把第一次加的东西放在两个while 循环外面，这样有点冗余；第二对于linkedlist,还有一个contains的方法来检查，residual 是否存在0，如果是的话，没有必要继续寻找，直接返回layer即可

7月11日-7月14日 因考试复习暂停刷题

题主可以一起～我也是最近刚开始

saysomething8 发表于 2023-7-12 23:37
题主可以一起～我也是最近刚开始

有邮箱吗

saysomething8 发表于 2023-7-13 02:37
题主可以一起～我也是最近刚开始

可以可以，可以就用这个帖子打卡，或者也可建一个群