零基础转码，刷题打卡

8：00~8：34
1011. Capacity To Ship Packages Within D Days
昨天的二分法
8：36~10:53
42. Trapping Rain Water
暴力/备忘录/双指针
10：54~11：30
26. Remove Duplicates from Sorted Array
13：30~13:50
83. Remove Duplicates from Sorted List
14:20~16:00
5. Longest Palindromic Substring
双指针
16：00~16：30
55. Jump Game
16：40~17：35
45. Jump Game II
贪心算法
18：56~21：00
435. Non-overlapping Intervals
贪心算法，二维数组排序
21：00~21：30
452. Minimum Number of Arrows to Burst Balloons
贪心  注意：用comparator排序时尽量用大于小于号，不要用减号，以免溢出
21：40~22：16
20. Valid Parentheses
stack 以前做过

8:00~21:27'
今天就搞了一题，搞出来的还有bug。。。。。
855. Exam Room

12:00~15:49
855. Exam Room
终于把昨天的题搞透彻了。没有用labuladong的解法，参考了官方的解法。代码省了很多。利用TreeSet来维护动态的座位。TreeSet相对于二叉堆读取更方便一点
15：50~20：55
130. Surrounded Regions（DFS）
20：55~22：28
990. Satisfiability of Equality Equations
union-find   还有bug
今天算是把labuladong书上的题都刷完一遍了，比原计划ddl 7.10晚了一天。接下来开始要反复总结复习这本书上的题和解法了，之后刷新题的速度可能要缓一缓了

12：20~12：32
debug完昨天的990. Satisfiability of Equality Equation

目前在leetcode上面提交的题数是110题，大部分的题基本上只是按照书里给的思路和代码过了一遍，距离自己能独立写出一题medium还需要更多的总结，接下来需要做的：
1. 总结labuladong这本书上所有的模板，重复地多刷几次这边的题，要做到看到题能想到思路，然后还能把思路语言表达出来（英语最好），再根据自己的思路把代码敲出来，每一题还要能分析出复杂度
2. 看YouTube上一些英文博主的mock interview和讲题，练习用英文表达上述思路
3. 刷新题（目前决定用这个tag来刷，大概300题    https://github.com/resumejob/Leetcode-retag）
4. 做项目，目前尽快先把这个java web项目完成

老哥， 给你点个赞，有计划有行动

断更了几天，这几天去把牙齿弄了下，从今天开始又要开始打卡了
复习旧题：
14：00~14：58
509. Fibonacci Number
brutal recursion  time complexity O（2^n）节点数*子问题需要时间 space complexity O(n)
recursion with memo  time complexity O(n) memo数组的元素个数 space O（n）
iteration with db table  time complexity O(n) dp数组的元素个数    space O（n）
15:00~15:50
322. Coin Change
brutal dp recursion  time O(k*n^k) k为可选coin数量 space O(n)
16:00~ 16:55
dp recursion with memo(HashMap)   time O(kn) space O(n)
17:00 ~17：38
dp iteration dp table int[amount + 1]  time O(kn) space O(n)
18:24~19:40
46. Permutations  利用linkedlist记录路径
20:00~20:58
46. Permutations  利用Collections.swap()
21:00~22:11 新题
47.Permutations 2    排序之后处理重复元素剪枝

今天就搞了个 回溯法 N皇后。。。。debug了一天。。。一直有bug。。。。有大佬可以帮忙看看吗？

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new LinkedList<>();
        LinkedList<StringBuilder> track = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append('.');
        }
        for(int i = 0; i < n; i++){
            track.add(sb);
        }
        backtrack(solutions, track, 0);
        return solutions;

    }
    public void backtrack(List<List<String>> solutions, LinkedList<StringBuilder> track, int row){
        if(row == track.size()){
            LinkedList<String> list = new LinkedList<>();
            for(int i = 0; i < track.size(); i++){
                list.add(track.get(i).toString());
            }
            solutions.add(new LinkedList<>(list));
            return;
        }
        for(int col = 0; col < track.get(0).length(); col++){
            if(!isValid(track, row, col)) continue;
            track.get(row).setCharAt(col, 'Q');
            backtrack(solutions, track, row + 1);
            track.get(row).setCharAt(col, '.');
        }
    }
    public boolean isValid(LinkedList<StringBuilder> sb, int row, int col){
        for(int i = 0; i < row; i++){
            if(sb.get(i).charAt(col) == 'Q')
            return false;
        }
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(sb.get(i).charAt(j) == 'Q')
            return false;
        }
        for(int i = row - 1, j = col + 1; i >= 0 && j < sb.get(0).length(); i--, j++){
            if(sb.get(i).charAt(j) == 'Q')
            return false;
        }
        return true;
    }
}

ilove1919 发表于 2021-7-18 11:40
今天就搞了个 回溯法 N皇后。。。。debug了一天。。。一直有bug。。。。有大佬可以帮忙看看吗？

class S ...

track.add(sb);  --> track.add(new StringBuilder(sb));