学习笔记

算法与数据结构脑图

算法与数据结构脑图

LeetCode_26_18

题目：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解法一

思路

看到这道题的第一反应就是和覃超老师PPT_Day-1-2中第24页Array实战的第1题_remove zero的解题思路很相似。可以用两个游标来解这道题，一个负责遍历数组，一个负责做特殊的工作，remove zero是把非0数放入该游标指向的位置，而这题是把不重复的数放入该游标指向的位置。

解题过程

1. 一开始使用了和remove zero很类似的代码，结果出现的数组越界的问题:

class Solution {
    public int removeDuplicates(int[] nums) {
        int nonDuplicatesIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[i + 1]) {
                nums[nonDuplicatesIndex++] = nums[i];
            }
        }
        
        return nonDuplicatesIndex;
    }
}

这时候的思路是，碰到第一个不重复的元素，我就把他放在第二个游标nonDuplicatesIndex指向的位置，然后让它向后移一位，同时第一个游标继续往后查。
但是这样就会导致遍历到最后一个元素的时候就会越界。

2. 于是就想，要么就比较游标i和它前一个元素，先解决越界的问题。同时，我也就要从下标1开始遍历，否则又得越界，那用人话来解释从1开始的话......又想了下，因为，数组第一个绝对就是不重复的呀，那放在nonDuplicatesIndex的位置天经地义啊，好了，逻辑自洽了。。。

class Solution {
    public int removeDuplicates(int[] nums) {
        int nonDuplicatesIndex = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[nonDuplicatesIndex++] = nums[i];
            }
        }
        
        return nonDuplicatesIndex;
    }
}

这次的提交结果，耗时是3ms，只打败了50%多的人，说明时间还可以优化。

3. 于是就想到了用如下的方式试一下，耗时居然提升到了2ms。。。不知道是瞎猫碰到死耗子，还是本身就有精度的误差，其实没什么区别。。。

class Solution {
    public int removeDuplicates(int[] nums) {
        int nonDuplicatesIndex = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            nums[nonDuplicatesIndex++] = nums[i];
        }
        
        return nonDuplicatesIndex;
    }
}

收获

当看完题目后，直接O(1)的从脑子里就闪出了remove zero的解题思路，当时感觉那叫一个爽啊。切身体会到五毒神掌，多做题真的很有用，让大脑形成了一种对某种题目的认知框架，可以辅助自己迅速找到解决问题的方案。

LeetCode_242_18

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

说明:

你可以假设字符串只包含小写字母。

解法一

思路

上来看到两个数比较，控制不住脾气，就是一顿两个for的嵌套。不过耗时1000ms+，有很大的优化空间。

解题过程

话不多说，就是干：

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] tc = t.toCharArray();
        for (char sc: s.toCharArray()) {
            for (int i = 0; i < tc.length; i++) {
                if (sc == tc[i]) {
                    tc[i] = '#';
                    break;
                }
            }
        }
        
        for (char c: tc) {
            if (c != '#') {
                return false;
            }
        }
        
        return s.length() == t.length();
    }
}

因为有两个for嵌套，所以时间复杂度是O(n^2)，效率不高。

解法二

思路

两个字符串的比较，其实也可以想成是组成的字符个数的比较，可以用一个map来统计两个字符串中各个字符的个数是否相等。

解题过程

这个话也不多说了，继续干：

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<String, Long> map = Arrays.stream(s.split("")).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        for (String ts: t.split("")) {
            if (map.containsKey(ts)) {
                map.put(ts, map.get(ts) - 1);
                continue;
            }
            return false;
        }
        
        for (Long value: map.values()) {
            if (value != 0) {
                return false;
            }
        }
        
        return true;    
    }
}

因为时间复杂度是O(n),所以时间确实是从一开始的1000ms缩短到了300ms不到，但是仍然只打败了5%的人,而且因为使用的是String，空间也多占用了20M。。。还可以优化。

解法三

思路

先在解法二的基础上，优化下空间大小，那就使用char数组。

解题过程

public class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Integer, Long> map = s.chars().boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        for (char c: t.toCharArray()) {
            int ci = (int)c;
            if (map.containsKey(ci)) {
                map.put(ci, map.get(ci) - 1);
                continue;
            }
            return false;
        }

        for (Long value: map.values()) {
            if (value != 0) {
                return false;
            }
        }

        return true;
    }
}

执行后，空间和解法一少了1M左右，同时速度比解法二也提升了，140ms了，但是还是只打败了5%，还可以优化。

解法四

思路

在想出以上3种解法后，挣扎了10分多种，没再能想出更好的方法，于是使用五毒神掌第一式，看solution：

解题过程

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        Arrays.sort(cs);
        Arrays.sort(ct);
        return Arrays.equals(cs, ct);
    }
}

看完代码，就想自己怎么这么蠢，现成的好东西不用。。。

解法五

思路

继续找solution中的好解法：

解题思路

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        int[] countArr = new int[26];
        
        for (int i = 0; i < cs.length; i++) {
            countArr[cs[i] - 'a']++;
            countArr[ct[i] - 'a']--;
        }
        
        for (int i: countArr) {
            if (i != 0) {
                return false;
            }
        }
        
        return ture;
    }
}

发现solution的第2个解法与我之前想的第2、3种很像，但它没有使用map来映射，而是直接使用arr[index] - 'a'的方法，巧妙的利用数组下标来映射字母并计数。提交后速度变得只有几ms了，提升的非常明显。这个方法的时间复杂是O(n)。

收获

通过5种解法的摸索和学习过程，有两点的收获：

• 感觉把题目提交并成功，而且每一次都比上一次更优化的时候，这种反馈确实会上瘾，现在感觉每次空下来，都想刷道题爽一下了。
• 在自己尝试了3种解法之后，开始搜寻和学习网上优质解法的时候，在看的时候，可以结合自己的思维过程，更好的体会到别人解法的思路，学习起来更有效率了，而且也更容易记忆。

LeetCode_1047_18

题目

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

解法一

思路

因为是比较相邻的两个字符是否相等，而且是在删去重复地内容后，继续不断比较地过程，所以非常像栈的push和pop的过程，所以想到了用栈来解决这道题(其实主要是题目分类在栈分类里：D)

解题过程

1. 用一个栈来进行对字符数组遍历过程中压栈和出栈的过程；
2. 每次压栈之前都判断栈是否为空，或者栈顶字符是否与当前遍历元素相同；
3. 如果不同且非空，就压栈；
4. 否则就出栈，然后循环往复，直到遍历结束；
5. 之后再遍历一下这个栈，拼出字符串后得到结果。

class Solution {
    public String removeDuplicates(String S) {
        if (S == null || "".equals(S)) {
            return S;
        }
        
        Stack<Character> stack = new Stack<>();
        for (char c: S.toCharArray()) {
            if (stack.isEmpty() || stack.peek() != c) {
                stack.push(c);
            } else {
                stack.pop();
            }
        }

        StringBuilder result = new StringBuilder();
        for (Character c: stack) {
            result.append(c);
        }

        return result.toString();
    }
}

提交结果后，耗时只打败了50%的人，可以继续优化。

解法二

思路

在国际站看到了一个使用双游标的解法，发现自己是被作业的分类限制了思考，其实题目的解法和26题比较相似。

解题过程

1. 使用两个指针
2. nonDuplicatesIndex游标用来指向保存没有被对对碰掉的元素所保存的位置
3. i指针用来遍历整个数组
4. nonDuplicatesIndex指针是从-1开始的，思路和我26题从1开始比较类似，区别在于最后new String的时候需不需要+1
5. 然后遍历的时候就判断是否为-1，或者是否不相同
6. 如果满足就++nonDuplicatesIndex，并将i遍历到的元素，写到nonDuplicatesIndex所指向的位置
7. 否则就让nonDuplicatesIndex回退，这样就相当于两个一样的元素对对碰掉了

class Solution {
    public String removeDuplicates(String S) {
        if (S == null || "".equals(S)) {
            return S;
        }
        
        char[] cs = S.toCharArray();
        int nonDuplicatesIndex = -1;
        for (int i = 0; i < cs.length; i++) {
            if (nonDuplicatesIndex == -1 || cs[nonDuplicatesIndex] != cs[i]) {
                cs[++nonDuplicatesIndex] = cs[i];
            } else {
                nonDuplicatesIndex--;
            }
        }
        
        return new String(cs, 0, nonDuplicatesIndex + 1);
    }
}

收获

这道题的收获：

1. 面对题目时候，通过形成的认知框架迅速解题固然很好，但是也不能让自己被框架限制住思维，否则就像这道题一样只能想到栈的方式(可能只是因为自己做的太少，框架太差了。。。)。
2. 加深了双指针的使用方法。
3. 熟悉了栈的相关类型的解题思路。

LeetCode_441_18

题目

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

n 是一个非负整数，并且在32位有符号整型的范围内。

示例 1:

n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.

示例 2:

n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.

思路

看到这题，看着一层层的往后推的图的样子，脑子里就直接想到了下面四段话：

1. terminator
2. process
3. drill down
4. restore

然后就开始写：

class Solution {
    public int arrangeCoins(int n) {
        return doJob(0, 0, n);
    }
    
    private int doJob(int level, int sum, int n) {
        return sum + ++level > n ? --level : doJob(level, sum+level, n);
    }
}

满心等着ac，结果int类型溢出，导致虚拟机栈溢出。懵了。揉了揉脸，再看了下题目，差点抽自己耳光，最简单的数学题啊。。。真的是手里拿着锤子，看什么都是钉子。。。

于是又满怀信心的敲出了如下的代码：

class Solution {
    public int arrangeCoins(int n) {
        int i = 0;
        for (int sum = 0; sum <= n;) {
            sum = (1 + ++i) * i / 2;
        }
        return --i;
    }
}

结果超时。。。

解法一

思路

1. 其实明显不用从1开始算，直接使用求根公式就可以算出那个值
2. (m + 0.5)^2 = 2 * n - 0.25 =》 m = sqrt(2 * n - 0.25) - 0.5
3. 然后再求小于这个整数中最大的那个就可以了

解题过程

class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.sqrt(n * 2 + 0.25) - 0.5);
    }
}

坑爹，结果又没注意整数类型溢出，又报错，那就只能先转成double了：

class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.sqrt(n * 2.0 + 0.25) - 0.5);
    }
}

这样问题就解决了。但压根没用到作业分类的二分法啊，所以要继续找答案。

解法二

思路

在网上的留言讨论里找到了一个大开眼界的方法：

1. 这个解法从两头来处理这个n
2. 一头是从0开始，存做c，先用c和n作比较，如果小于n就c++
3. 但不是应该用总和来和n作比较吗？而且为什么要先比较再++呢？
4. 因为他另一头做的事情才是关键，他直接把c从n中减去
5. 然后用c再和被减去c的n再进行比较
6. 这样的原因是只要一直减去c，最终都会遇到最后一行作比较的时候，如果大于n了，那就说明n不够分配下一组+1的数了，c就是最后的行数。

解题过程

理解了思路，做起来就方便了

class Solution {
    public int arrangeCoins(int n) {
        int c = 0;
        while(c < n) {
            n -= ++c;
        }
        return c;
    }
}

但效果没有刚才直接使用求根公式的算法好。但是分类要求的二分查找是怎么玩的呢？

收获

1. 体会到数学是算法的基础，有时候直接拿数学简化公式以后，算起来会更快
2. 感觉先好好想一下怎么解题的思路，等想清楚了再做题，做题的感觉反而更爽，不过思考的过程确实很累，结合之前不断试错修改的过程，两种方式都有锻炼自己的地方。

LeetCode_104_18

题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

解法一

思路

使用分治的思路

1. terminator：root为null的时候，返回当前层数；
2. prepare：层数加1；
3. subproblems下钻到当前节点的左右子树；
4. process & generate：比较左右子树返回的层数，向上返回最大值。

解题过程

因为思路中涉及到了层数的概念，所以就需要新建一个函数，入参增加一个层数用来下钻的时候传递。

class Solution {
    public int maxDepth(TreeNode root) {
        return doSearch(0, root);
    }
    
    private int doSearch(int level, TreeNode root) {
        //terminator
        if (root == null) {
            return level;
        }
        //prepare 
        level++;
        //subproblems  & prepare & generate result
        return Math.max(doSearch(level, root.left), doSearch(level, root.right));
    }
}

通过样板很快就写出了可以执行的代码，然后又再精简了一下

public class LeetCode_104_18 {
    public int maxDepth(TreeNode root) {
        return doSearch(0, root);
    }

    private int doSearch(int level, TreeNode root) {
        return root == null? level: Math.max(doSearch(++level, root.left), doSearch(level, root.right));
    }
}

收获

具体题目和样板之间有时候并不能完全匹配，但是在做题的过程中能够体会到大致的思路是可以通过样板来指导的。通过做题进一步的熟练了分治的思考和代码的编写，写的速度比以前明显感觉快了。

LeetCode_189_18

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

思路

首先想到的就是较为暴力的方法：

1. 移动k次
2. 每次移动一个数，时间复杂度是O(n)

解法一

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        for (int i = 0; i < k; i++) {
            doMove(nums);
        }
    }
    
    private void doMove(int[] nums) {
        int store = nums[0];
        for (int i = 0; i < nums.length - 1; i++) {
            int tmp = store;
            store = nums[i + 1];
            nums[i + 1] = tmp;
        }
        nums[0] = store;
    }
}

doMove函数负责定义每次移动的逻辑，代码中需要使用一个变量来保存需要移动的数。但这样的时间复杂度事O(n^2)

解法二

从上面的解法中可以发现：

1. 解法一每次只走一部，重复走了k次，但其实可以一步到位，这样可以减少一层循环嵌套。
2. 从第一个元素开始遍历整个数组
3. 第i个元素会放在i+k的位置
4. i+k的元素则保存下来，i+2k的位置
5. 以此类推
6. 但是会有一个特殊情况，就是在过界以后，会进行%的处理，如果处理结束后回到了第一个元素的位置，那么因为第一个位置的元素已经去到该去的位置了，所以就从第二个元素开始继续。

对于为什么回到第一个元素的位置后，就特殊处理为从后一个元素开始，没法很好的理解。

2. 碰到如下情况则可以直接返回：
3. 数组的长度小于等于1；
4. k==0的时候;
5. k是数组长度的整数倍。

class Solution {
    public void rotate(int[] nums, int k) {
        if (k == 0 || nums == null || nums.length <= 1 || (k % nums.length == 0)) {
            return;
        }
        
        int index = 0;
        int start = 0;
        int store = nums[index];
        for (int i = 0; i < nums.length; i++) {
            index = index + k >= nums.length ? (index + k) % nums.length: index + k;
            int tmpStore = store;
            store = nums[index];
            nums[index] = tmpStore;
            if (index == start) {
                start = ++index;
                store = nums[index];
            }
        }
    }
}

收获

从这道题中学到的：

1. 前置条件检验的好，可以避免异常，同时能够提高效率。
2. 解法二思考了很久，无论是看题解还是自己思考，都debug了很久才了解了大概的意思，自己禁不住要人肉在脑中算一下整个过程，否则没办法很好的理解。这一点不知道该怎么克服，但至少找到了一个问题，也算是收获。

分治，动态规划，贪心 三个概念的区别
之前因为这三个算法都会用到递归的编程技巧，所以这三个概念有些混淆，经过整理脑图，对这三个有了比较清晰的认识。
（1）分治：把问题划分为多个规模比较小子的问题，根据这几个子问题的结果对原问题的结果进行求解。一般的步骤分为 终止条件，对当前数据的处理，递归这三个步骤。
（2）动态规划：一般分为 终止条件，状态定义，状态转移方程，递归，恢复原状。其中恢复原状是可以可无的一部，取决于是否需要输出具体步骤的细节。如果只是计算个数的话，这一步可以没有。
（3）贪心算法：是一种特殊的动态规划。局部最优值代表全局最优值的话，可以用贪心算法来解决。

数据结构与算法思维脑图：https://blog.csdn.net/qq_23589557/article/details/91356646

第一周的学习总结：
在做算法的时候，一开始我会想着自己去做，但是花了不少时间，后来想到老师所说的五毒神掌的第一步，我就按照老师的步骤来做，确实会理解了很多，做起来也想到了很多的思路，想到算法确实是思维上的一种突破，也会去参考其它人的解题思路，首先这样的话，第一步就迈出去了。
然后紧接着，我会去从时间复杂度和空间复杂度不断的去优化代码，不断的尝试时间和空间的交换，来达到一种平衡状态，这个感觉还是蛮不错的，希望接下来继续不断的实战这一个过程。

• 总结
  第一周的学习主要针对作业中的五大部分（数组、链表；Map & Set；堆栈、队列；二分查找；递归）逐一选择较为容易的题目进行解题，完成“五毒神掌”前两掌。

  由于题目难易程度为简单，再则知道题目所考查的范围，在做题的过程中完成解题较为容易。再联想实际解题的过程，我发现自己现阶段的学习要注重对数据结构和算法基础知识的梳理（脑图），有了清晰的认识，可以帮助我们选定知识运用的边界，不至于手足无措。

• 脑图
  数据结构与算法脑图

这周整理了覃超老师线下两天讲解的所有题目，有当时听得懂的，也有没听懂的，计划这个月把这些题目弄完。

另外，这周赶上端午节（参加算法训练营之前就计划好出去玩的），耽误了一些时间，周末回来刷了几道题，有一道题目一开始是 143ms，后来被优化到 1ms，慢慢掌握了优化优化再优化的好习惯，而不是简单随便做出来就完事了，也知道认真分析其时间复杂度和空间复杂度。

接下来的时间，继续加油，这一个月，我的心里只有算法！

我把这次叫做重拾数据结构和算法，最大的体会是太过高估自己了，这次做了也就前两道题目，没有实实在在去写程序的时候会觉得这题目比较简单，但是真正去实施的时候就发现一推基本功上面的问题。
一开始上手的时候就直接敲，觉得路子可以，可是一敲一敲的时候，发现完全不行，还出现一些边界下标处理不过的问题。
例如去重这道题目，一开始自己捣鼓一通，发现路子不行，之后看了其他人的解法自己再去解的。
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
反转数组问题，这次涨了点经验，我先试着把数组往后面挪动一位，其实会发现一直移动位置的话要从最后的元素去移动，而且还要临时把元素保存起来，加到第一项；
做完这件事情之后，我发现移动K个位置的话，是可以多移动几次的。这种方式比较挫，每次要移动n次，k次就k*n的操作次数,k这里是随着元素个数增加的，所以实际复杂度是 O(N^2)级别,
后面看了大神的解法，发现可以直接算出交换的位置，这块还在接着看，但是有了点优化的意思了。
https://leetcode-cn.com/problems/rotate-array/

第一周做作业比较乱，回家初始化环境，注册账号，早上看王争老师视频，一道题目花费的时间多一些，两道题目量还是完成了，最大的体会就是自己应该是笨鸟级别的，要有大一点的突破只能是花时间了。

另外脑图我也根据上课讲的内容画了一下：
https://blog.csdn.net/zhuxuemin1991/article/details/91294044

主要练习了数组和链表的习题，每道题都会根据所学思考不同的算法解法。数组和链表树所有数据结构和算法的基础，用数组和链表去实现其他的数据结构，如堆、栈、树等等，手写一遍代码 ，会更加加深自己对于其中数据结构和算法的掌握。

在平时的工作之中，自己会刻意地去想有没有更好、更优化的解决方案，这个业务的时间复杂度是多少、空间复杂度是多少，有没有更加优化的解决方案，可以减少内存占用或者服务器资源占用，自己会更多地去思考这方面的问题，这对于自己的平时工作也是一个很的提升。

本周联系的题目不算多，但是自己对于每一个题目的思考有很多，不只是每道题目的解法算法，还有不同的思路，自己选择的算法与数据结构，开拓了自己从前没有思考过的思维，并且能够把这种思维应用到实际的业务和场景中，这是自己最大的收获。

要求

1. 每周至少完成给定题目中的两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章（字数不限）

注意事项

1. 下面列出的题目中，按照知识点进行了简单分类，但并不意味着使用相应的数据结构或算法一定是解决该题目的最优解，这样分类只是为了方便大家有针对性的练习；
2. 有的题目可能需要结合多个算法或数据结构进行求解。

第二周题目

哈希表

简单：https://leetcode-cn.com/problems/two-sum/
简单：https://leetcode-cn.com/problems/valid-anagram/
中等：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
中等：https://leetcode-cn.com/problems/top-k-frequent-words
困难：https://leetcode-cn.com/problems/number-of-atoms/

二叉树

简单：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
简单：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
中等：https://leetcode-cn.com/problems/symmetric-tree/
中等：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
中等：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
困难：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

二叉搜索树

简单：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
简单：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
中等：https://leetcode-cn.com/problems/validate-binary-search-tree/
中等：https://leetcode-cn.com/problems/range-sum-of-bst/
中等：https://leetcode-cn.com/problems/contains-duplicate-iii/
困难：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

作业提交规则

1. 在提交作业之前，请先阅读这里的 README 文档：
   https://github.com/algorithm002/algorithm/blob/master/README.md
2. 然后在此 Issues 下按照如下格式回复（示例见一楼）:

#作业提交
学号：
username：
代码作业：（填写自己仓库下对应的作业链接即可，同时记得给本仓库提交 pull request）
学习总结：发表自己本周的学习感言 issues，并提交链接，issues 标题格式：“【学号后三位-week1】+文章标题”，格式参考：#1
使用语言：

对数组和递归又多了一些认识，不过从解题思路到实际coding的过程还存在不少困难，比如内置方法的掌握程度，有时候使用了js 内置的数组和集合的内置操作，感觉确实很方便，不过最后写出来的代码实测效率比较低，算法效率有待改进啊。
处理无序字符数组的时候先排序这个确实是不错的技巧。

1. 我的刷题思路
刷题顺序：优先刷medium难度的题目，对于自己的弱点递归和动态规划等项目从easy难度的题目刷起，并增加刷题量。对于做错的题目，或者参考discussion 或solution有更好的题解，在leetcode上建立我个人的list（我的错题），多回顾。最后有多余的时间再尝试解决hard的题目。

刷题效率：老师的五毒法是先看题目5min后如果没有思路直接看题解。我觉得这个方法还是不错的，有助于提升自己的做题效率。我这次刷题就有点没按照套路来，导致有些题目花费的时间太长。5min对我来说还是有点短暂，我打算把这个延长到一个番茄时钟20min到25min，如果没有思路，直接看题解。刷题非常需要专注力，如果做题的时间太长就很容易分心，导致效率很低，我在做LCATree236这道题，递归没想好，暴力超时，但一直困在那，耽误了很多时间。我觉得适当限制自己focus到某道题的时间有助于整个效率的提升。

刷题问题：部分题目没尝试多种解法，有些题目自己的效率很高就不去看解答了，没有学习其他人的思路。另外没有尝试重复的做题。我理解重复的做题是“在某些条件下你做对了，但你实际上没有真正理解透”，所以需要通过重复做题，让自己完完全全吃透这道题。我的办法是先focus我的错题，多刷自己的错题，再重复刷其他题目。

2. 下周需要改进的地方
重复刷上周错题和其他题目，将其他未完成的题目做完，尝试解决难题。
使用番茄时钟提升刷题效率。

算法练习的一些感悟

• 数组的题，一般比较常规，都是swap就可以；
• 链表的题本质上不难，都是套路题，最重要的就是画图
  • 比如swap nodes in pairs，这道题思路不难，就是写了很久，终止条件判断、谁先指向谁，很容易乱，画图比较直观
• 栈、队列还要深入练习，不能只用于最简单的Valid Parentheses；
  • 比如可以利用栈生成tree、利用栈实现递归改循环（几个进几个出并不那么直观）、利用栈做dfs搜索
  • 可以利用队列实现bfs
  • JavaScript并没有实现成熟的堆栈类，都是得用数组去模拟，很多时候得培养自己的堆栈意识，而不是笼统的认为pop、shift只是数组的API，随便拿来用

关于递归的一些看法

• 正向思维很容易想到递归的方法
• 但是很容易超时(并且边界条件搞不定)
• 不一定所有的递归都好加记忆化（变量过多的时候不适合）
• so 动态规划得好好练习

Tree

• 树其实很好理解，但是题真的不好做
• 递归、迭代法都需要做一遍，通过迭代法练习通过栈、队列进行循环处理
• 树的题很容易和DFS/Bfs一起出现，需要格外关注这类型的题
• 边界处理（关注根节点的特殊性）

其他

• 仔细审题
• 一些思路很顺的题目，终止条件、边界条件判断很容易出错
• 并且边界判断很容易写的繁杂、冗余，得多看别人的代码是如何应对多种边界的情况的

脑图梳理
https://github.com/zyziyun/algorithm/blob/week1/Week_01/id_39/%E7%AE%97%E6%B3%95%E4%B8%8E%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.png

感谢大佬们分享

1. 自己属于菜鸟一枚, 所以看到大佬们的各种思路有的激动, 这周写的题目不多, 只是完成了任务, 但是一题多解让我感觉到思考比答案更重要, 自己通过不断的看高手的解题, 不断加深自己的脑图,
   但是发现自己看到题目不会那么懵逼, 可以先遍历自己大脑思考一下

2. 希望自己多多抓紧时间刷题, 尽量提早完成作业, 附上自己未完善的脑图, 会继续完善
   ALgorithm.pdf

1.数组和链表是数据存储的物理结构，其他数据结构是数据存储的逻辑结构，物理实现可以是数组，也可以是链表
2.栈通常用于对“历史”的回溯，函数的递归调用就是用栈实现的；而队列通常用于对历史的回放，也就是按照原始顺序重演一遍
3.双端队列综合和栈和队列的优点，队头和队尾都可以入队和出队

这周主要在看动态规划与链表的题目。

链表

链表的题目的解法基本很固定，有很多题目都是使用快慢指针来解决，例如检测是否有环，链表倒数第几个节点，链表问题理解不清的时候把就要把节点，节点指针画在纸上便好理解。
链表的题目需要注意的问题就是边界的判断，以及不要让一个指针成为“僵尸指针”。指针变换的步骤瑶注意。

动态规划

主要针对第84题，这道题主要**就是对于每一个柱子，找到包含其的最大面积，那么找最大面积就转变为了找左右比他矮的柱子。我的理解中，栈的作用就是存储了左右比他矮的柱子的位置，对应着动态规划中，搜索结果时，保存状态。
这道题中，对于边界的处理，我想到了一种tricky一些的方法，在数组中前后各加入一个高度为0的元素，这样一来便不用判断边界，栈底始终为0，进栈出栈时不用判断是否为栈底元素，最后也不用判断栈是否为空，因为最后一个元素必为0，必要将栈清空，省去很多判断步骤，让我的代码看起来更整洁，开心。

第二周学习内容：

第二周习题训练以下3种很重要的数据结构

1. 哈希表  HashMap
2. 二叉树  Binary Tree
3. 二叉搜索树   Binary Search Tree

哈希表  HashMap

1. 定义

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

2. 特性

哈希表  插入和查找的平均时间复杂度为 O(1) 
在做leecode题目的时候，经常使用哈希表保存中间结果，使算法的时间复杂度降低一个数量级,或者在递归中使用哈希表做缓存，减少重复计算，降低算法复杂度。还可以使用哈希表做两个元素的匹配。
常见题目：leecode 1 two sum ， leecode 242 valid-anagram 等

二叉树  Binary Tree

1. 定义

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

2. 特性

二叉树  有三种遍历方式：前序、中序和后序
在做leecode题目的时候，绝大多数二叉树的题目都是用递归来解题的，代码格式十分统一。
同时深度优先遍历DFS和广度优先遍历BFS也常在leecode二叉树题目中使用到。
常见题目：leecode 102 等

二叉搜索树   Binary Search Tree

1. 定义

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；

2. 特性：

二叉搜索树中序遍历的内容是一个从小到大排序的数组。
在做leecode题目的时候，通过这个特性我们可以解决很多关于二叉搜索树的算法题。
常见题目：leecode 98 等

一周自己的刷题，挺有意思，开始在做觉得有意义的事情。 虽然刷题有时候比较枯燥，但当自己仔细思考题目与解法的时候，有在努力的做这一件事情，一开始都是脑海里闪出的第一想法，比如说暴力法。 有第一种方法出现的时候，再思考第二种与第三种。 每次提交代码时，都会非常的注意到执行完成的时间与使用的内存，再看看自己战胜了多少人。 我给自己自己定的目标是，超过 80% 的提交者，这样的话我觉得这个代码算是比较好的。 如果是只有超过 30% 及以下的提交者，那我会觉得这个代码会很low，往往是暴力法来解决的问题，会尝试着寻找新的满意的答案。 当发现自己有时焦头烂额想不到好的办法的时候，阅读一下别人写的好的代码，那样的感觉 so cool. 代码简洁而优雅，像是欣赏一位美丽优雅的女子一样，自己表现的专注而有神。

在学习数据结构与算法的过程当中，我觉得最重要的事情是 开拓了自己的思维。 以前自己想问题都是从前往后的线性结构，通过学习算法之后，学到了另外三种思维的方式。 1、从后往前；2、从中间向两端延伸；3、从两端向中间夹。

总结就一句话: 多写题目。 特别是 递归和动态规划
脑图

LeetCode174 题目

这个题目主要利用动态规划，
需要反过来想，状态方程为：

 dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);

leetCode368 题目

这个题目利用了stack 这种数据结构
时间复杂度为 0(n)
计算栈内数据的时候，有两个触发条件，当前数据并栈顶元素小了。或者到了最右端。
栈里面的元素是数据的下标，其实是用来计算矩形的宽度的。矩形的高度在出栈的时间就计算处理了。

1. 对于数组循环边界的判断
   比如for(int i=0;i<nums.length;i++)这里可以想象nums.length是数组最后又加了一个元素的位置,这样i<nums.length的判断语句就更好理解 。 如果不这样理解，就得用i<=nums.length-1的方式比较啰嗦。

2. 虚拟节点
   链表可以使用dummy node来简化操作。如果不使用虚拟节点，需要许多额外的操作。

3. 如何编写递归代码
   写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
   如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
   编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

学习心得：
以前算法对我来说是一个很大的概念，经常拿到算法题都是一脸懵逼，学习完线下课之后让我对算法有了更为系统的了解。
第一周目标就是先迈出第一步，不要像之前那样无从下手。这一周学习了线上的一些基础理论课再结合线下课的内容，再加上看了很多大神们的代码，觉得对自己的思维方式、角度都有很大的帮助。这周做的题不多，但都力争一道题用多种方法去解决，用复杂度分析找出算法最优的那个方法。希望下周可以渐入佳境，多多刷题~
脑图：
https://github.com/flamencoy/algorithm/blob/master/Week_01/id_33/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E8%84%91%E5%9B%BE.png

第一周实践下来，感想有些复杂，更多是针对个人学习方法改善方面的。对于我第一个问题，说起来有点儿奇怪，刷题（可能是简单的题）对我来说是一个上瘾的事情。别的是那种感觉靠自己能解决的题，自己不但会长时间的花时间思考解决或者优化的方案，而且还不愿意看答案。而看了答案以后，还会去考虑答案说的对不对……总之感觉刷题效率不是很高，没有严格按照超哥说的那种五分钟看答案的套路，但是太早看答案就不甘心。还好第一周工作强度不是特别大，有时间给可以这么刷题。第二周可能要考虑更高效率的刷题，毕竟超哥给的作业里就看到1000+编号的题目了。另一个感受是，对于这部分知识的掌握不能操之过急，每一个知识背后都有很多细节可以挖掘，特别是再看了其他玩家的分享之后，无论是在思路上，还在实现的语法细节上都有很大的收货，并且可以进一步的深挖。

技术方面第一周刷下来，有几个小的知识点可以分享一下。

1. python比java慢10倍这个说法，至少在leetcode跑测试里可以明显的感受到。
2. 在python实现里，list下标访问要比dict的hash快的太多，很多题用dict会超时，而list则可以通过。这个跟java也差距很大。
3. 有防御式的代码，或者处理边界问题，最好提早进行处理，让后续算法实现的时候更简洁高效，也减少错误。
4. 哨兵的技巧真的很好用
5. python中交换变量的值很好用a, b = b, a
6. 两个变量进行比较操作，并且如果后续还有递归或者循环，可以先做好变量的交换，可以很大程度简洁代码。

学习总结

这周我提交了2题代码。

• 三数之和

• 连接两个有序链表

现在我还原现场，记录下当时我的状态。
我第一个做的是 连接两个有序链表。
一遍审题下来，基本理解题目，说的是有两个有序链表，我们需要写代码将其连接起来，结果还是要有序的。
接着开始思考可行的算法，首先觉得来个for循环，将B链表中的值插入到A链表中，结束后，需要判断下哪个链表还咩有遍历结束，就将它连接到已经结束的链表后，这个算法可行，O（n）的时间复杂度也OK。
我也未曾考虑其他的算法，于是开始码了起来。
一阵噼里啪啦结束后，代码已经写好，于是我自信满满地点下了测试的按钮。
红色的提示语出现，说我的代码超出的时间。
在修改了几遍无果之后，我无奈的查看了解题。
官方的解题给了两种思路。

• 递归

1. 设置边界条件
   if(l1==null) return l2;if(l2==null) return l1;
2. 处理当层数据 and 进入下一层
   if(l1.val < l2.val) { l1.next = mergeTwoList(l1.next,l2); return l1; }
if(l1.val >= l2.val) {l2.next = mergeTwoList(l1,l2.next);return l2;}

说起来，使用递归确实代码简介，不过到底哪种题型要使用递归呢？我这会还不知道，想来不过见多识广这几个字吧。

• 迭代
  这个方法与我的思路一致，只是我的代码实现功底不厚，没有能够很好的实现出来，憾矣。

学号：027
username:Srussianalfred
代码作业：https://github.com/russianalfred/algorithm/tree/master/Week_01/id_27
学习总结：#77
算法脑图：https://github.com/russianalfred/algorithm/blob/master/Week_01/id_27/123.jpg
使用语言：C++

学习过程中，你遇到哪些问题，都可以在此条 issue 下提问，我们的讲师或者其他学员看到你的问题后会帮你解答。

学习心得：
这周主要挑了几套hash表和二叉树的题目。对于hash表，个人的感觉是一定要理清楚hash表的定义，因为一个好的hash表对解题是由事半功倍的效果的。
比如：Leetcode#242 有效的字母异位词
这道题目的难点在于单词中可能存在多个相同的字符，常用的简单KV需要使用整数来表示value
而对于二叉树，怎样抽象递归地模板，怎样高效地利用递归来处理问题也是一个难点。
比如：Leetcode#236 二叉树的最近公共祖先
这道题本来的解法是这样的，相当于要双重递归了，先DFS每个根节点，然后对每个根节点的左右子树，分别再使用DFS来判断目标节点是否包含在书中。就算使用了一些剪枝的技巧，也超时。然后就想了，是否可以一次递归就搞定，答案是肯定的。优化的思路在于，节点一定都存在，所以只要right == null，就可以断定都在left中，并且祖先就是left。反之亦然，后期还是需要多多练习。

#作业提交
学号：020
username：hz019
代码作业：https://github.com/algorithm002/algorithm/tree/master/Week_01/id_20
使用语言：Python,javascript

以前為了準備面試有在 LeetCode 上面刷過 100 多道題目左右。當初為了趕時間一天刷好幾十題，現在基本上都忘記了。
深深的感覺到算法必須要養成習慣每天練習，而不是面試前零散抱佛腳，不然面試完就會忘光。

数组、链表

數組與鏈錶是非常容易考出來的題目。雖然結構並不複雜但是解法卻有非常多種。需要多加練習，體會不同解法的優缺點，才能真的融會貫通。

遞歸

遞歸開始要想出一個遞歸模板不太容易，需要多一點練習，模板出來之後就很容易把問題解出來。

Go

由於之前是寫 JavaScript 的。使用 Go 語言來寫算法，會需要查閱很多資料。這也讓我學習到跟多關於 Go 指針的相關操作與底層結構實現。

学习笔记

26.删除排序数组中的重复项

一开始我自己写的时候写了两个循环，一个循环i，一个循环，结果提交失败。看了别人的解题思路才知道，用双指针思路即可。一个快指针，一个慢指针。慢指针不用循环遍历，只要快指针的判断条件到了，就更新慢指针

189. Rotate Array

这道题看似是数组移位问题，实际上是数据的翻转问题。我一开始傻乎乎地用移位来写，结果超时。后来才醒悟原来是数组翻转问题，移几位就是数组前面几位翻一下，剩下几位翻一下，再总的翻一下 #2 #30

什么是Stack？

堆栈（Stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。按照后进先出（LIFO, Last In First Out）的原理运作。

Stack的实现？

堆栈常用一维数组或链表来实现。
堆栈使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

• 推入：将数据放入堆栈顶端，堆栈顶端移到新放入的数据。
• 弹出：将堆栈顶端数据移除，堆栈顶端移到移除后的下一笔数据。

Stack在算法题中的作用

由于栈后进先出的特性，常被用于匹配类型的问题上，常见的匹配类型我总结如下：

1.  找到相邻配对元素操作

   典型的例题为 leecode 1047和leecode 20，都可以通过栈来匹配最后节点与当前节点是否匹配来完成。

2.  找到数组中递增或递减位置序列

   典型的例题为 leecode 84，leecode 42和leecode 239，可以通过栈的这种特性以O(N)复杂度完成。

Stack特殊场景下变形

当遇到相邻元素配对问题，我们会第一时间想到栈这个数据结构。但是当我们发现栈中的元素只有一种的情况下，可以对这个栈再做简化，方法为使用一个int来记录这个内容的数量，通过加法模拟栈的push操作，减法模拟栈的pop操作，从而模拟整个栈的操作，这样可以进一步优化性能。
典型例题：leecode 1021

数据结构和算法知识脑图

链接如下：
https://www.yuque.com/james_ren/algorithm/mindmap

因为老师的算法课知道了刷题这种学习方式。从最开始的看到题目一脸懵，到现在慢慢学会了读题、思考、暴力解法，然后再通过review其他前辈的解法。给我最大的收获就是不是我一个人在学习中遇到同样的问题，遇到问题只要开始思考，哪怕最复杂的暴力法都行。
解题过程中我也慢慢形成了：1.检查参数；2.过程处理；的深刻记忆。
pow算法的二分法的O(logn)时间复杂度给我很多启发，之前我都是直接调用现成方法，并没有想过他是如何实现以及优化的。
数据结构与算法思维导图：https://github.com/liujianbo/algorithm/blob/master/Week_01/id_38/数据结构与算法总结.xmind

hash表(map/set)

CPP有unordered_map和map两种，分别对应hashmap和红黑树。常用于2个字串的比较，比如anagram等。
set常用于dfs的判重，比如isVisited。
此外还有set_union并集，set_intersection交集，set_difference差集

二叉树BT

特点是：每个节点最多有2个子树，left和right。
如果非二叉树，比如B+ tree，就会有更多结点，比如linux的idr对应32个子结点。
支持BFS，DFS，查找最小深度BFS更方便。其他情况比如遍历所有结点，用DFS写起来更简单。

二叉搜索树BST

特点是：

1. 左子树上所有节点的值均小于根节点的值。
2. 右子树上所有节点的值均大于根节点的值。
3. 左右子树也都是二叉搜索树BST。
   常用于一个数组，找到比某个值小（或者大）的一些复杂情况的解法。

要求

1. 每周至少完成给定题目中的两道算法题
2. 围绕每周重点学习的算法知识点，撰写一篇有观点和思考的技术文章（字数不限）
3. 第一周作业特别要求：根据你的理解和掌握程度，绘制一张属于你自己的数据结构和算法知识脑图。脑图请放在学习总结中一起提交。

注意事项

1. 下面列出的题目中，按照知识点进行了简单分类，但并不意味着使用相应的数据结构或算法一定是解决该题目的最优解，这样分类只是为了方便大家有针对性的练习；
2. 有的题目可能需要结合多个算法或数据结构进行求解。

第一周题目

数组、链表

简单：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
简单：https://leetcode-cn.com/problems/rotate-array/
简单：https://leetcode-cn.com/problems/merge-two-sorted-lists/
简单：https://leetcode-cn.com/problems/merge-sorted-array/
中等：https://leetcode-cn.com/problems/swap-nodes-in-pairs/
中等：https://leetcode-cn.com/problems/3sum/

Map & Set

简单：https://leetcode-cn.com/problems/valid-anagram/
中等：https://leetcode-cn.com/problems/group-anagrams/

堆栈、队列

简单：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
简单：https://leetcode-cn.com/problems/remove-outermost-parentheses/
困难：https://leetcode.com/problems/largest-rectangle-in-histogram/
困难：https://leetcode.com/problems/trapping-rain-water/

二分查找

简单：https://leetcode-cn.com/problems/arranging-coins/
中等：https://leetcode-cn.com/problems/powx-n/
困难：https://leetcode-cn.com/problems/dungeon-game/

递归

简单：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
简单：https://leetcode-cn.com/problems/symmetric-tree/
简单：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
简单：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
简单：https://leetcode-cn.com/problems/binary-tree-paths/
简单：https://leetcode-cn.com/problems/range-sum-of-bst/
中等：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

作业提交规则

1. 在提交作业之前，请先阅读这里的 README 文档：
   https://github.com/algorithm002/algorithm/blob/master/README.md
2. 然后在此 Issues 下按照如下格式回复（示例见一楼）:

#作业提交
学号：
username：
代码作业：（填写自己仓库下对应的作业链接即可，同时记得给本仓库提交 pull request）
学习总结：发表自己本周的学习感言 issues，并提交链接，issues 标题格式：“【学号后三位-week1】+文章标题”，格式参考：#1
使用语言：

第二周调整了刷题的策略，先从难题开始做，然后再做中等，最后做简单的题。这样个调整对我个人感觉非常有效，第一周先做简单题并且纠结于多种实现方式，到最后时间不够又剩下了难题，心态上就十分焦躁，总感觉没有完成核心的任务。本周同样遇到时间不够的情况，但最后剩下都是简单的题，极大的减轻了心理负担。

不过这样依然还是有一定的心理负担。虽然先做的难题，但是我个人感受难题未必真的难，有可能只是步骤复杂代码量较大，感觉LeetCode(国内)上讨论的解法都大同小异。反倒是有些中等甚至简单的题，很多神奇的解法更加让人震惊，比如这次的220题，深深的震撼了我。没能把超哥布置的所有题都刷掉，还是心有不甘，只希望自己训练营结束以后依然能够继续坚持刷题。

这周有一个好的趋势，我在公司宣传刷题的时候成功吸引了两个同事一起入坑，大家刷的十分投入。缺点是有点儿耽误工作，我右边的哥们一个题卡了快一下午……我还得想办法控制控制局面。

下面分享一些新学到的技巧，对我比较有价值。

1. 超哥强调的『先读题』很重要，我在297这题上犯了错误，看见二叉树和数组就想当然的以为是实现2n,2n+1的玩法。结果完全错误……

2. python中在对数字进行逻辑判断的时候，如果相对None进行判断，最好还是老老实实的写 if n is None，否则会在0的处理上踩坑。

3. python中没有『异或』，但是可以使用 bool(n1) != bool(n2) 来曲线救国。

4. Iterator 是个好东西，在某些递归父问题与子问题共同迭代同一个数据结构，并且父在子的迭代下标基础上继续迭代到时候，很好用。例如这次的726。

5. python是有整除的， n1 // n2 。

6. 220这个题的O(n)解法真的太酷了……

7. python的标准库似乎没有 链表、平衡查找树等数据结构，都是基于数组的……如果想直接用，还是Java方便一些。

学习笔记

LeetCode_1

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一

思路

1. 2个for循环嵌套，暴力
2. 时间复杂度O(n^2)
3. 空间复杂度O(1)

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[2];
        }
        
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        
        return new int[2];
    }
}

解法二

思路

1. 先遍历数组，把元素作为key，下标作为value，放入hash表，这样也做到了去重
2. 再遍历一遍数组，先计算target和当前元素的差，在hash表中查找这个差对应的下标，且不是当前元素的下标
3. 这样时间复杂度就是O(n)
4. 空间复杂度因为多了个map，所以是O(n)

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[2];
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int j = target - nums[i];
            if (map.containsKey(j) && i != map.get(j)) {
                return new int[]{i, map.get(j)};
            }
        }

        return new int[2];
    }
}

解法三

思路

1. 基于解法二，其实不需要先遍历一边数组，全部放到map里，可以边遍历变放
2. 这样也就不用判断是否重复使用当前元素
3. 最坏情况会遍历整个数组，所以时间复杂度是O(n)
4. 同样的空间复杂度和解法三类似，最坏情况下空间复杂度是O(n)

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[2];
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int j = target - nums[i];
            if (map.containsKey(j)) {
                return new int[]{i, map.get(j)};
            }
            map.put(nums[i], i);
        }

        return new int[2];
    }
}

收获

算法可以不断地迭代改进，像生物进化一样，非常有趣。

LeetCode_236

题目

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

解法一

思路

dfs路径上最早重叠的那个节点，就是它们的最早祖先节点。

1. 不断地向左右子节点搜索，如果找到返回true，否则false
2. 判断当前节点是不是p或q的一个
3. 如果以上三种情况有2种是true
4. 那么说明当前节点就是最早祖先节点

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        doRecurse(root, p, q);
        return result;
    }

    private boolean doRecurse(TreeNode current, TreeNode p, TreeNode q) {
        if (current == null) {
            return false;
        }

        int left = doRecurse(current.left, p, q) ? 1 : 0;
        int right = doRecurse(current.right, p, q) ? 1 : 0;
        int mid = current.val == p.val || current.val == q.val ? 1 : 0;

        if (mid + left + right >= 2) {
            result = current;
        }

        return mid + left + right > 0;
    }
}

解法二

思路

使用bfs查找两个节点，同时记录查找过程中的路过的父节点

1. 使用bfs标配的队列
2. 使用map记录路过的父节点，这样查询父节点的时间复杂度就是O(1)
3. 查找两个节点，当全部查到时开始生成查找p节点的父节点路径的集合
4. 再用这个集合去让q节点的父节点来匹配，第一个匹配上的就是最早祖先

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        Map<TreeNode, TreeNode> parents = new HashMap<>();
        
        stack.push(root);
        parents.put(root, null);
        
        while (!parents.containsKey(p) || !parents.containsKey(q)) {
            TreeNode current = stack.pop();
            
            if (current.left != null) {
                stack.push(current.left);
                parents.put(current.left, current);
            }
            
            if (current.right != null) {
                stack.push(current.right);
                parents.put(current.right, current);
            }
        }
        
        Set<TreeNode> pAncestors = new HashSet<>();
        while (p != null) {
            pAncestors.add(p);
            p = parents.get(p);
        }
        
        while (!pAncestors.contains(q)) {
            q = parents.get(q);
        }
        
        return q;
    }
}

解法三

思路

使用dfs非递归的方法(stack)：

1. 从左子树开始向下查找，同时更新当前节点的状态

• 左右都查过
• 左边查好了
• 还没查好

2. 通过栈不断地向下查，如果发现了和p或q相同的节点，就把它作为LCA，同时记录已经找到一个节点
3. 如果左边检查完，那么开始检查右边
4. 如果两边检查完，都没有找到全部两个目标节点，就把这个节点弹出，把这个弹出节点的父节点标记为LCA
5. 循环往复，直到找到两个节点为止

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode lca = null;

        boolean oneFound = false;

        Stack<Object[]> stack = new Stack<>();
        
        stack.push(new Object[]{root, 2});

        TreeNode childNode;
        
        while (!stack.isEmpty()) {
            Object[] parentArr = stack.peek();
            if (parentArr[0] == null) {return p;}
            TreeNode parentNode = (TreeNode) parentArr[0];
            int parentState = (int) parentArr[1];
            if (parentState != 0) {
                if (parentState == 2) {
                    if (parentNode == p || parentNode == q) {
                        if (oneFound) {
                            return lca;
                        } else {
                            lca = (TreeNode)stack.peek()[0];
                            oneFound = true;
                        }
                    }
                    childNode = parentNode.left;
                } else {
                    childNode = parentNode.right;
                }
                
                stack.pop();
                stack.push(new Object[]{parentNode, parentState - 1});
                
                if (childNode != null) {
                    stack.push(new Object[]{childNode, 2});    
                }
            } else {
                if (stack.pop()[0] == lca && oneFound) {
                    lca = (TreeNode) stack.peek()[0];
                }
            }
        }
        return lca;
    }
}

收获

熟悉了BFS和DFS的搜索方式，对递归有了进一步的理解。

LeetCode_111

题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

解法一

思路

使用dfs的递归方式

1. 一开始没有审清除题目，对于从根节点到最近叶子节点的最短路径上的节点数量没有理解
2. 叶子节点应该是没有左右子树的节点
3. 所以如果只有一个节点，那么只递归下钻有节点地一边，另一边就不管了
4. 然后只有当左右都为null的时候才开始计数
5. 然后开始返回，同时还要有一个变量存储左右节点的最小的那个值，初始的时候用int的最大值
6. 然后每一层返回的时候都需要+1，代表层数的累加。

代码

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        if (root.left == null && root.right == null) {
            return 1;
        }
        
        int depth = Integer.MAX_VALUE;
        if (root.left != null) {
            depth = Math.min(minDepth(root.left), depth);
        }
        
        if (root.right != null) {
            depth = Math.min(minDepth(root.right), depth);
        }
        
        return depth + 1;
    }
}

收获

审清题目很重要，就像理解需求一样，如果没搞清楚，搞半天也是瞎弄。

LeetCode_783

题目

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

示例：

输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意，root是树结点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

          4
        /   \
      2      6
     / \    
    1   3  

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。

注意：

二叉树的大小范围在 2 到 100。
二叉树总是有效的，每个节点的值都是整数，且不重复。

解法一

思路

二叉搜索树的两个定义，老师需要我们O(1)的时间复杂度来反应：

1. 所有的左子树都小于根节点，所有的右子树都大于根节点，循环往复
2. 中序搜索的路径是升序的
   所以直接就反应了使用dfs递归搜索的方式，但是没办法确定具体的逻辑，于是参考了国际站的方法：
3. 左边子树的差值就是上一个节点减去当前节点
4. 右边子树的差值就是当前节点减去上一个节点
5. 然后加上要记录的最小值
6. 于是涉及到的所有参数就是4个

• 当前节点
• 上一个节点(用左和右两个参数表示，因为不同的运算方式)
• 最小值

5. 然后就是递归运算，求左右子树返回的差值中的最小值

代码

class Solution {
    public int minDiffInBST(TreeNode root) {
        return doSearch(root, null, null, Integer.MAX_VALUE);
    }

    private int doSearch(TreeNode root, TreeNode leftNode, TreeNode rightNode, int min) {
        if (root == null) {
            return min;
        }
        
        int left = leftNode == null ? Integer.MAX_VALUE : leftNode.val - root.val;
        int right = rightNode == null ? Integer.MAX_VALUE : root.val - rightNode.val;
        
        min = Math.min(Math.min(left, right), min);

        int leftChild = doSearch(root.left, root, rightNode, min);
        int rightChild = doSearch(root.right, leftNode, root, min);
        return Math.min(leftChild, rightChild);
    }
}

收获

LeetCode_235

题目

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
``` 
说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

### 解法一
#### 思路
二叉搜索树的中序搜索是升序的，所以最早祖先就是
1. node >= q && node <= p
2. node <= q && node >= p
这样直接dfs就能查到这个节点
#### 代码
```java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (found(root, p, q)) {
            return root;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            
            if (node != null) {
                if (found(node, p, q)) {
                    return node;
                }

                stack.push(node.left);
                stack.push(node.right);
            }
        }
        
        return null;
    }
    
    private boolean found(TreeNode node, TreeNode p, TreeNode q) {
        return p.val <= node.val && q.val >= node.val || 
                p.val >= node.val && q.val <= node.val;
    }
}

解法二

思路

借鉴国际站的dfs递归解法，同时对解法一的代码进行了优化，速度快了很多，应该算是进行了剪枝。

1. 如果q和p的值都小于root，就搜索左子树
2. 如果都大于root就搜索右子树
3. 否则就说明当前节点一定是如下三种情况，且无论哪种情况，当前节点都是lca

• p是当前节点，且q也在这个路径上
• 如上，只是p和q换一下
• p和q分别在当前节点的左右子树的路径上

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int parentVal = root.val;
        int pVal = p.val;
        int qVal = q.val;
        
        if (pVal < parentVal && qVal < parentVal) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (pVal > parentVal && qVal > parentVal) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }  
    }
}

如下是对解法一的优化代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            if (node != null) {
                if (p.val < node.val && q.val < node.val) {
                    stack.push(node.left);
                } else if (p.val > node.val && q.val > node.val){
                    stack.push(node.right);
                } else {
                    return node;
                }
            }
        }

        return null;
    }
}

收获

用到了剪枝，优化的效果非常明显，也进一步熟悉了dfs的递归和非递归的用法

LeetCode_3

题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解法一

思路

首先吸取之前叶子节点审题不清的教训，分清除了子序列和子串之间的区别。这题是要计算最长的字串。所以不是简单的去重计算字符个数。

1. 使用hash表去重
2. 因为每次重复的时候，意味着从重复的那个字符的后一位开始重新计算长度，所以需要递归的重复计算subString那个字符后的新字符串
3. 然后递归返回的时候比一下这一层和返回的那层的长度最大值

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        }

        if (s.length() == 1) {
            return 1;
        }
        
        return doCheck(s);       
    }
    
    private int doCheck(String s) {
        Set<Character> set = new HashSet<>();
        char[] cs = s.toCharArray();
        for (char c : cs) {
            if (set.contains(c)) {
                return Math.max(set.size(), doCheck(s.substring(s.indexOf(c) + 1)));
            }
            set.add(c);
        }
        
        return set.size();
    }
}

收获

肯定可以优化呀，pr以后继续优化一下。

算法的思路就是，解决实际问题的多种解法，并且最好是最优解。在数组队列入栈出栈的算法题中。每次出栈一个，添加到元数组前面去，给几个参数添加几个。其实这个就是在一个闭环容器中。分前后的例子。联系生活后，这个直接用js中的数组切割和拼接两步就执行完毕。不用for循环。
通过这一个例子，始终让我坚信 《算法源于生活，算法服务生活》。
这周马上结束。下周每天一到算法题。练习思考的逻辑。没事走在路上思考下，解法挺有意思。这样还可以解决发呆的问题。真好

这一周主要是hash表、二叉树、二叉搜索树的练习。难度选择了在中等难度以上的题目进行练习。每道题目都会先自己思考，多多少少都会有一些想法和思路，但是在具体代码实现细节上面还有些欠缺，大部分题目还需要看过别人的讨论才有具体的实现思路。经过自己实现之后，对于同类型的问题做起来会更加有思路些，还是需要更多地练习。

Hash表的特点是使用hash函数构建键值对应关系，插入和查找的时间复杂度是O(1)，可以应用到字符串搜索、匹配、数据缓存等场景下。LeetCode第3题构建使用hash表，一次循环即可找到最长子字符串，也是一种空间换时间的解决问题思路。

更多的对于二叉树和二叉搜索树进行了练习。主要的解题思路是递归，从做题中发现技巧是对于前序、中序、后序遍历以及BFS、DFS的合理运用，可以解决很多问题，至少可以提供一种解题思路。通过做题也对树的上面的遍历方式的具体实现代码有了更熟练的运用。对于二叉搜索树的解题思路，更多运用到二叉搜索树特性：1.左<根<右；2.每一节点都是二叉搜索树；3.中序遍历是递增数列。应用这三点特性，遇到二叉搜索树的问题，还是能提供不少的解题想法的。

还需要更多地做题练习来打开自己的解题思维。

这周刚好遇到了公司年中大促，工作事情多了点，周末也是值班状态

做题的感受:
之前的课程和做算法的题目确实会拓宽自己的思路,总结如下：
1.关于位运算
这周重新看了位运算的章节，我记得有个n&=n-1;然后有道题目是求数字中
的1的个数吧,这道题目很自然就会想到bit去怎么操作了，但是其实我一开始做的时候发现负
数是有问题的，接着又去了解了java里面的存储体系，数字都是补码去运算的
而且在做减法运算时候转换为加法其实是做了一个取余上面的等价，然后舍去
高位的操作。
2.字符体系，
这次做了两道题目都有使用int[128]的数组来判断char的字符存
在情况，相当于map的的运算，但是效率比较高，这种做法的话确实见过了就是
会了，没见过怎么也想不到。
3.实际工作中我需要做一个applist去按照字典剔除的sql操作，按照我以往的
搞法我其实是会打宽之后去做join，但是现在就是觉得最好快一些，后面我直接
把字典cache到内存，去查询contains情况，爽了。
总体总结：
在算法学习过程中其实可以发现很多知识点其实就是应该掌握而没掌握的，在比较忙的
状态下统筹时间很重要，哪怕少花时间的时候，后面有空余时间就补上，切记不能完全不动！

学习笔记

本周回顾

本人非计算机专业出身，相比于其他同学而言基础会相对薄弱些。针对自己的能力特点，为自己设定了合理的学习计划和目标，并且于本周达成了三个小目标。

1. 算法图解图书阅读（核心内容笔记）：

   1. 二分查找的速度比简单（全局遍历）的查找速度快的多
   2. O(log n) 比O（n）快，需要搜索的元素越多，前者比后者越快
   3. 算法运行时间并不以秒为单位
   4. 算法运行时间是从其增速的角度衡量
   5. 算法运行时间用大O表示法来表示
   6. 需要存储多个元素时，可以用数组或链表
   7. 数组的元素都在一起
   8. 链表的元素是分开的，其中每个元素都存储了下一个元素的地址
   9. 数组的读取速度是很快的
   10. 链表的插入和删除速度是很快的
   11. 同一个数组中，所有元素的类型都必须相同
   12. 递归指的是调用自己的函数
   13. 每个递归函数都有两个条件：基线条件和递归条件
   14. 栈有两种操作：压入和弹出；并且栈是后进先出（LIFO）；队列是先进先出（FIFO）
   15. 所有函数调用都进入调用栈
   16. D & C (分治)将问题逐步分解，编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。
   17. 散列表合适用于模拟映射关系
   18. 一旦装填因子超过0.7，就该调整该散列表的长度
   19. 图的广度优先搜索支出是否具有从A到B的最短路径，如果有广度优先搜索将找出最短路径
   20. 面临类似寻找最短路径的问题时，可以尝试使用图来建立模型，再使用广度优先搜索来解决问题。
   21. 你需要按照加入顺利来检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
   22. 对于检查过的人，务必不要再去检查，否则形成无限循环。
   23. 广度优先搜索用于在非加权图中查找最短路径
   24. 狄克思算法用于在加权图中寻找最短路径
   25. 仅当权重为非负的时候，狄克思算法才管用
   26. 如果图包含负权边，请使用贝尔曼-福德算法
   27. 贪婪算法寻找局部最优解，企图以这种方式获取全局最优解
   28. 对于NP完全问题（Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题），还没有找到快速解决方案
   29. 面临NP问题的最优做法是使用近似算法
   30. 贪婪算法易于实现，运行速度快，是不错的近似算法
       31.在给定约束条件下优化某种指标的时候，动态规划很有用
   31. 问题可分解为离散子问题，可使用动态规划来解决
   32. 每种动态规划方案都涉及网络
   33. 单元格中的值通通常就是要优化的值
   34. 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题

2. Git视频课程30讲
   2.1 核心内容笔记：https://mubu.com/doc/21G3uNP1Lw

3. 算法视频课程20节

4. 算法习题2题

下周规划

1. 读完半本（200页左右）的算法与数据结构Python语言描述
2. 继续刷剩余的算法题（上周剩余及本周新增）

• 收获
  • 本周主要训练几个基础的数据结构和算法技巧，练习题本身难度不高，但是要短时间内全部自己思考出解决方案，还是有点难度，所以结合超哥提供的方法，不熟悉的题目直接看题解，记住思路，自己写一遍，然后过一天再练一遍。明显感觉学习效率提高了很多，而且记忆的也更深刻了
  • 有一些题目看到题目可以下意识的想到使用什么数据结构或者什么算法比较有效
    • 比如遇到查找元素，且复杂度要求log(n)，可以优先想到二分法
    • 遇到括号匹配、坐标容器问题、去除重复字母问题等等，需要跟上一个节点进行比较的问题，可以优先考虑使用堆栈
    • 需要穷举排列组合的问题，先考虑递归加剪枝
    • 遇到树的遍历问题，先考虑dfs或者bfs
    • 还有一些常遇到的解题套路，比如链表环的快慢指针解法等等
• 思维导图
  • http://oss.daoshengzhi.com/4a175ae708e48e222cb7d87e7afa9ab4.jpg

毕业十年后，重新学习算法这件事，对我来说就是 An Olympian Task。解算法题，是一件既要花费时间又要花费精力的事，也是一个自我否定和反复失望的过程。

上一份工作离职后，我一直处于远程工作状态，只跟业务打交道。之前偶尔写写代码，现在已经完全不写了。所以，这周的学习我是从刷 Python 极客专栏和官网教程开始的，进度比其他同学要缓慢很多。

上周参加线下课时，因为没有预习，也没有预习的能力，所以，第一天很出戏。题目切换到中文版后，真的是每个汉字都认识，连在一起就懵圈。到第二天上课，我才终于进入学习状态。覃老师的讲解，帮我建立了算法的知识框架，并指明了解题的基本方向。当然，框架中具体内容的完善，需要我自己去努力。

目前拿到题目，我的第一反应是，能不能从数学角度推导出求解公式。譬如这个题目 https://leetcode-cn.com/submissions/detail/20284600/ ，我第一反应就是等差数列求解，范围内取极值，但又感觉很取巧。于是，我还是强迫自己先用程序的思维去解题，写出其他答案后，再来实现自己的推导公式。

现在没有优化的概念，基本就是把自己能想到的答案先码出来，除非题目特别要求，并没有认真计算解法的算法复杂度和空间复杂度。这周只完成了四道最简单的题目，希望下周每天都能打卡算法题，无论简单还是复杂，争取把它养成习惯。

Python 是一门很简洁的语言，我看了自己的解题代码，感觉很累赘，希望在这个月学习算法的过程中也能进一步深入学习 Python 。

    刚开始的第一周因为连着一个端午节，可能花在学习上的时间没有那么多，但是也算是一个不错的开端。这一周提交了3到算法题，每道题都会认真的去审题，思考，做题，如果做不出来的话就会去看别人的解题思路，然后用自己的代码写下来，能从中学到很多以前没有见过的：原来题目还有这种解法。
    比如第24题，我写了两种解法，一种是直接解法--就是直接把相邻的两个节点直接进行交换，另一种是运用递归的思路去解题。解答完之后不是说就完了，从上周的线下课中，跟着超哥学到了，一道算法题不仅要去解题还要思考这种方法的时间和空间复杂度。
   第49题，Group Anagrams题中，一开始也是怎么想不到太好的方法去解题，后来看到了别人实现的方式，然后认认真真的去照着实现了一遍，当然这也只是第一步，后面还会照着超哥的五毒神掌去练习算法题。
   第50题，Pow(x, n)，可能还是接触新的知识的方式比较少，比如我写迭代器的循环一直都是：

for (vector::iterator it = strs.begin(); it != end_it; ++it) {
const string& s = *it;
// Some code here...
}
然而看了代码之后才了解到原来新的C++11标准代码写起来这么简洁：
vector &strs;
for (const auto &s : strs){
//
}
以后还是去多阅读别人优质的代码，然后运用到自己的code中去。

第一周算法训练营学习总结

• 与题无关的一些感悟

从业务侧写代码的习惯来说，首先是可阅读性强，可扩展性强，并且还需要横向纵向兼容（纵向是指同接口向上兼容，横向是指服务边界方面的兼容），为了部分平衡可以牺牲部分性能。所以上来会使用一些设计模式去套路一下。刷 LeetCode 上来有时候一下就会想多，导致思绪混乱，后续有切换过来。

• 与题有关的一些感悟

LeetCode 的题如此简洁，就是实现功能，所以理解题是一个很重要的阶段。在理解题以后，有时候一下没有任何思路，有些懵逼（此处确实需要多练习）。在理解题以后，写代码的过程中不断去修正，如何把时间/空间复杂度降低一些，循环的减少，变量的复用（以及看他人的解法）都是手段之一。在刷题过程中，还有一点就是原子逻辑的抽离，可能使用一个最简逻辑实现，在逻辑的调用处做适当的变形，达到整理逻辑的简化。

LeetCode链接：https://leetcode.com/shockang/
本周主要针对性的在LeetCode上刷了关于数组和链表的题目，掌握了几个小技巧：
1.通过 a ^= b; b ^= a; a ^= b; 可以实现a,b交换，这在数组元素交换中经常可以用到；
2.数组不考虑重复的时候可以尝试将数组排序方便后续处理；
3.可以通过递归来解决链表问题；
4.可以通过素数相乘判断anagram;
5.数组合并的时候应该从后向前遍历；
6.链表的相关操作其实就是指针（引用）的传递，操作之前注意引用的备份。

思维导图：
思维导图

学习心得：
本周主要挑选了几道数组的题目，用来可以联系数组的一些操作。因为在之前本人的算法学习中，发现其实递归什么的虽然难，但是有了特定的模板后，基本面试做题不会懵。但是一些数组涉及到下标操作的（这些题目往往有特点是题目要求强调空间复杂度O（1）的原地操作），这些题比较绕，在面试的时候也比较容易卡壳。练习下来的心得是，可以适当地背一些题目的Code，尤其是一些数组边界条件的处理。

学习追踪：
搭建了一个博客，用来追踪算法刷题的进度，欢迎大家留言。（后面还准备更新这次极客大学的算法训练营的学习心得，也希望大家多多支持：P）
http://boyang918.com/2019/06/05/leetcode-array/

首先抱歉，好像有点晚了，向明天没精神工作的自己，公司和各位小伙伴。本周刷题重点突破了递归和 DP 两个点。

分别是 174 号的 dungeonGame 问题。哈哈哈，这题看这矩阵造型，求最优，必然是 DP 问题。接下来的问题是如何定义状态转移方程，哈哈，也很简单，骑士在矩阵的的任何一点，可以先下或向右移动，所以 i+1 ，或 j+1，然后选取两个的最小值。即 f(i,j)=max(1,min(f(i,j+1)-nums[i][j+1],f(i+1,j)-nums[i+1][j]))。如果骑士在边缘，则只能向下或向右。在调试过程中，记录骑士最开始并非是在 （0，0）可以想象成骑士在矩阵外，调到 （0，0）则减去 （0，0）处的矩阵值，其他同理。

然后就是 236 号的 lowest common ancestor 问题。说实话，问题是递归过程对递归函数的定义容易犯糊涂。
定义 find 函数：功能如下，在当前树下，找到左右子树找到的第一个 p 或者 q，如果没有则返回 null。如果左右都不为 null。则当前节点为最近父节点，退出递归，并且使用全局变量记录。如果一边为 null，则最近在另外一边。

其他问题：42 rain water 问题除了老师课堂上的解法。我自己构思了方法2：即找到数组中的最大值和第二大值，计算出其之间的雨水面积，等于 最低*宽度-中间元素高度之和。然后对左右数组进行递归。哈哈，下周一定实现。此处 flag。

接下啦是 同类型的条形图面积问题，想通了暴力解和如果不是最后以为，并且后面一位比其高，则放弃计算当前值。和使用minIndex 记录当前值往前的数组中的最小值，minIndex 前的数字使用 minIndex 一次计算。

额，之所以现在交作业，主要卡在一道自以为很简单的问题上。将数组向后移动 k 位。目前想法无法解决 k 大于数组长度问题。待突破。

其他软柿子就不提了哈。

重点学习了递归的知识，使用递归是一种非常简洁的编码技巧，特别适合机器的思维。但是困难的是递推公式很难写、终止条件容易遗漏，特别容易把自己绕进去。除此之外，递归代码还有一些弊端，堆栈溢出、空间复杂度高等问题。

递归一般需要搭配动态数组vector，或者队列queue、栈stack等其他数据结构一起来实现。用C写起二维动态数组来会比较繁琐，有很多指针，所以转向了CPP来实现。
递归代码阶段发现自己喜欢用DFS，记住terminator，process current, drill down, restore，写多了感觉慢慢熟练了几个步骤，terminator的return也不会忘了，但有些问题先看了答案，写出来有些细节还是会错，还要加强。BFS用的queue，貌似没有DFS简洁好写。
注意到了CPP的传值和传引用。传引用貌似比较常用些，直接把外面的值也改了。
递归的最坏时间复杂度，最好时间复杂度相对好分析些，但平均时间复杂度涉及到摊还分析，就感觉累一些。

这周题目涉及数组，链表，栈和队列，map，二叉树，二叉搜索树，递归和二分搜索，外加一道动态规划的 题目。
以前在做题的时候不大注重代码优化和反馈，往往题目通过了就结束了。通过上课，现在觉得反馈这部分还是比较重要的。在完成题目后看了其它优秀的代码，会发现原来还有很多特别的解法，有些非常简洁，但可读性会差一些，有些则是利用另一种思路降低了时间复杂度。
比如在3Sum这道题中，第一反应是枚举加二分，但是发现讨论区里有人利用了类似快速排序里面的**进行搜索，降低了时间复杂度。
GroupAnagrams这道题，一般是直接对单词进行排序，然后作为键值插入Map中，这涉及很多字符串比较的操作，比较费时。于是就有人选择用素数相乘生成键值。也有用计数排序来替代快速排序生成键值的方法。
largestRectangleArea利用栈的特性，始终在栈中维持一个单调递增的排列，来统计矩阵的面积的方法非常巧妙。
还有一些题目在做的过程中用到一些变量来存储，后来发现其实还有更简洁的写法不需要额外变量。lowestCommonAncestor这题我是会用两个数组记录各自的路径再比较，有另一种思路只需要三个整形就可以统计节点的访问情况。
总的来说，解题时还是需要多思考一些方法和学习其它解法来拓宽思路。
算法导图：链接

标题格式：【学号后三位+week1】（如果是第二周就是week2，以此类推）+文章标题

正文部分，字数不限。

写完之后请将本 issue 的链接和代码作业链接一并提交至第一周作业征集的 issue 内。