ARTS 20201208-1215

Algorithm: 每周至少做一个 LeetCode 的算法题
算法题:
1 剑指 offer 24: 翻转链表
递归法实现翻转链表
链表递归的基线条件(最简单情况): 没有节点或者只有一个节点
基线条件: 什么时候函数不再调用自己
递归条件: 什么时候函数调用自己

使用分治法看递归翻转链表
对数组元素实现快速排序时, 分治法的应用是将 数组根据 中枢 从左到右 拆分为左子数组, 中枢, 右子数组.
在分治法翻转链表时, 以 5->4->3->2->1 为例, 将链表分成 5 和 4->3->2->1 这两个链表, 即可理解.

    ListNode* reverseList(ListNode* head) {
        // 基线条件
        if (!head || !head->next) {
            return head;
        }
        // 对当前节点的后面的节点进行递归翻转, 最后得到一个翻转好的链表
        ListNode *newNode = reverseList(head->next);
        // 组合 5 和 翻转好的 4->3->2->1 这两个链表
        head->next->next = head;
        head->next = NULL;
        return newNode;
    }

总结: 递归时, 首要找到基线条件, 然后看怎么将对应的情况转化到基线条件上.
检验方法: 看递归的中间状态

2 剑指 offer 59-1: 滑动窗口最大值
知识点: 单调递减队列
1 使用 deque 实现一个单调队列
2 使用 双向队列实现对应的 滑动窗口最大值
每次元素进队的时候就保证能形成一个单调减的队列
类似题目: 实现含有 min 函数的栈.

3 剑指 offer 48: 最长不含重复字符的子字符串长度
1 动态规划法: 研究 s[i] s[j] 之间没有重复元素的长度关系.
2 使用哈希表和双指针法, map 中的键值对<char, int> 保存这个 char 最后一次出现的位置.

      int lengthOfLongestSubstring(string s) {
        int res = 0, leftIndex = -1, n = s.size();
        unordered_map<int, int> map;
        for (int i = 0; i < n; i++) {
            if (map.count(s[i]) && map[s[i]] > leftIndex) {
                leftIndex = map[s[i]];
            }
            map[s[i]] = i;
            res = max(res, i - leftIndex);
        }
        return res;
     }

Review: 阅读并点评至少一篇英文技术文章
1 Swift 中的可选链
2 Difference between Swift and Kotlin

Tips: 学习至少一个技术技巧
Swift 中 SnapKit 代码添加约束的理解与使用

Share: 分享一篇有观点和思考的技术文章
Flutter 不是 the next big thing
还是先不着急上手 flutter 吧. 完成携程的例子.