0%

发表于 更新于 分类于 阅读次数：
本文字数： 853 阅读时长 ≈ 1 分钟

2020年3月12日 上午11:37

力扣：字符串的最大公因子题解

结合这个道题，我说说我在编程中证明充要条件的意义

  1. 首先，我们需要有一个可能正确的假设。这道题中有下面这三个：
    1. 前缀串的长度必然要是两个字符串长度的约数才能满足条件，否则无法经过若干次拼接后得到长度相等的字符串
    2. 如果存在一个符合要求的字符串 X，那么也一定存在一个符合要求的字符串 X’，它的长度为 str1 和 str2 长度的最大公约数
    3. 如果 str1 和 str2 拼接后等于 str2和 str1 拼接起来的字符串（注意拼接顺序不同），那么一定存在符合条件的字符串 X
  2. 为什么需要证明充要性？
    1. 要理解充分这个词的意思：——条件的充分性
      1. 我这个条件已经充分的包括了所有可能得出结论的情况。
      2. 换句话说，我这个条件之外的情况，一定不会得出结论
    2. 在编程中的意义？
      1. 充要性保证了得出结论，对应入口的唯一性
      2. 否则，如果还有其他入口可以到达结论，那么你的程序就是错的，考虑的不全面。
    3. 避免：我的确说的是真话，但是我真话没说全。
  3. 为什么要证明必要性？—条件的必要性
    1. 要理解必要这个词的意思：
      1. 要得到当前结论，这个条件是必要的，也就是不是多余的，可有可无的
    2. 在编程中的意义：
      1. 避免条件的冗余，明确目标，尽量的少考虑不必要的东西
    3. 避免：这个人废话太多，让人抓不到重点
  4. 相同点：
    1. 必要性和充分性，都是对条件的要求，不是针对结论的！

定义：

维基百科：充分必要条件

  • 充分必要条件（英语：sufficient and necessary condition）简称为充要条件
  • 当命题“若P则Q”为真时，P称为Q的充分条件，Q称为P的必要条件

例题：

怎样区分充分性、必要性 - 知乎

  • 充要条件证明题的叙述方式一般有这两种：一是“求证：A是B的充要条件”；二是“求证：A的充要条件是B”。由条件出发推出结论就是证明充分性，反之就是证明必要性。
  • 把这两种方式中加粗的字重读出来，哪个是“条件”是不是一目了然了呢。在一中，A是条件，由A推出B就是证明充分性，反之由B推出A就是证明必要性；在二中，条件是B，所以由B推出A就是证明充分性，反之由A推出B就是证明必P要性

发表于 更新于 分类于 阅读次数：
本文字数： 659 阅读时长 ≈ 1 分钟

2020年3月11日 下午12:02
1366. 通过投票对团队排名

  • return 1:第一个元素在前
  • return 0:第二个元素在前
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
    public:
        string rankTeams(vector<string>& votes) {
            int m = votes.size();
            string v = votes[0]; // 准备1：排序对象
            map<char, map<int, int>> f; // 准备2：排序根据

            // 统计：Build array rank where rank[i][j] is the number of votes for team i to be the j-th rank.
            for (auto s : votes)
            {
                for (int i = 0; i < s.size(); ++ i)
                    f[s[i]][i] ++;
            }
            sort(v.begin(), v.end(), [&](char a, char b) -> bool
            {
                // 思考，有哪些条件就可以返回了？
                for (int i = 0; i < v.size(); ++ i)
                {
                    if (f[a][i] > f[b][i]) return 1;// 返回条件1
                    if (f[a][i] < f[b][i]) return 0;// 返回条件2
                }
                return a < b; // 返回条件三
            });
            return v;
        }
    };

发表于 更新于 分类于 阅读次数：
本文字数： 4k 阅读时长 ≈ 4 分钟

2020年3月8日 下午8:38

总结：
——再次整理:添加——

目前遇到不会的题从哪里去找：

  1. 【正向】从具体case找切入点 —》归纳步骤 —》理性整理成代码的样子
  2. 【逆向】从常用的数据结构、算法中找切入点 —》用具体的case来验证
  3. 【改进】从BF下手，不断改进
  4. 【函数式编程】带着一些理想主义的态度去，模块化思考。【反面是正向的琐碎过程化思维】
  5. 【逻辑推理】在推理的过程中提示自己使用因为-》所以，也就是说等等提示器来作为【逻辑化的手段】
  6. 【数据结构的合理搭配使用】
  7. 【过程模拟】要学会分解问题(大问题分解成多个步骤，分块解决，前提任务是啥)，问自己：需要再上步骤中改变什么？
  8. 【数学归纳法，巧设变量解方程】
  9. 【归纳某一现象条件】在【过程模拟】【正向】尤其常见，提醒自己换换角度，看看还有哪些信息没有用？需不需要自己来统计一些标记条件。
  10. 【整理数据和过程的方式】假设是一个个的输入、对数据进行重排列、换个角度去使用数据。这可以是非常好的启发角度。例如dp的打标，我认为也是一种数据整理方式
    • huahua的一步步的Table
    • 数据整理成递归树的形式
    • DP的打表Table
    • 图形（树），不要一直在一个图上画，要化成一个系列，不断地简化，排除干扰。
    • 你现在有100个node，你们怎么组织他们之间的结构？你组织的结构会直接导致他们的子操作(查询、插入、删除)时间复杂度
      • 一串->串也有多种
      • 树->树也有多种
      • 根据node的特征，先进行分为多个小组，在对每个小组进行串/树等的选择设计
      • LFU就是一个好的例子
    • 上面的一定要在纸上用一个例子展现出过程，这样具体化的例子，容易整理思路，也让写代码的时候更加的踏实，因为这样才可以有具体的case
  11. 【空间换时间】空间换时间的本质其实就是：【复用，把重复的计算保存下来，下次直接用】，这个思想在递归中就非常常见了。另一种理解是：通过保存数据，使得遍历过程中的当下，可以直接获得更多的信息，以至于可以降低时间复杂度。这也提示我们可以反向思考，看看我们缺什么，然后再循环的之前就统计好。
    1. 能够空间换时间的标志：
      • 【思考：我i能不能偷个懒，利用前人的经验，加快自己的学习速度】
      • 【这道题的max函数，体现出线性递增的趋势】- 这样我们就可能【联系上下文进行推断、计算】
  12. 【设计变量语义】动态数组的题，【指针的语义是一个范围】，不是指单个位置。这提醒我们，在编程的时候要【设计变量的语义】，一个好的语义让你思路清晰，不纠结与假特殊case。就像设计数据的处理过程一样，关键在于认为的设计。
  13. 【设计数据结构】从UnionFindSet中我感受到【如何设计数据结构】–先想好你的基础语义动作是什么，然后选合适的基础数据结构来表示
    • 这些题的解题套路有两步：
      • 1.建立起元素之间关系
      • 2.在建立起的关系中进行查询
    • 这其中涉及到：【在这个思考的过程中，也要问问自己的数据结构能否方便的完成下面的操作】【当然，也可以作为寻找思路的启发点】
      • 1.关系的初始化
      • 2.关系的建立
      • 3.关系的合并
      • 4.关系的改变
  14. 【在循环中动态编程】对于这种动态编程的技巧【明确维护的空间范围是什么？抓住维护空间的边界条件】。eg：滑动窗口
  15. hard类型的题也分几个种类:
    1. 【难在题意上】题都读不懂：也就是说你连简单的暴力模拟都不知道怎么一步步的走。887. 鸡蛋掉落
    2. 【难在复杂上】需要你分解成多个子问题来分别解决：
    3. 【难在思路上】在写代码之前，需要你在纸上建模、得出结论、归纳总结：这些题写代码运用总结出的结论反而很简单 面试题 16.03. 交点
    4. 有一个技巧：
      1. 学会从简单的暴力模拟等方式开始思考，作为一个思考的跳板，千万不要死钻，也不要想着复杂度什么的，先做出来再说。
      2. 学会分解问题，拆解成多个子问题来解决，理清楚子问题之间的顺序关系
  16. 程序的正确性证明与能够顺利写出模拟的程序是共存的：
    1. 程序的正确性证明中，最重要的一点就是循环不变性是什么？
      1. 这里面最重要的就是定义好循环的单元，并且，每次新的循环中，可以保证循环单元是初始化到循环单元开始的位置的。
      2. 我们在递归中常常提及到子问题，其实循环也是寻需要设计子问题的，需要设计出口条件，只不过常常由于简单而忽略了
      3. 我们很容易犯的一个毛病是：没想到思路，就开始写代码，想着边写代码边设计思路；其实变量的语义、循环单元语义需要再编码之前设计好才可能作对，这些是需要设计的，从二分查找和二叉树的遍历过程，我们就可以认识到他们的重要性。所以，以后要培养：即使是简单问题，也要问问自己设计的语义是什么。你设计的语义，是你整理思路，写成代码，以及最终正确性证明的有效推理手段。有时候再想：写程序都说是一个逻辑性的活，那么我怎么体会不到。你连定义都没有，怎么进行推理！！
    2. 94. 二叉树的中序遍历在这道题中就体现出了设计循环不变性，循环子单元的重要性，直接决定了你能不能写出正确的代码。
  17. 找到做数学题的感觉：
    1. 【想数学证明需要什么(定义的变量，设计的逻辑，就要找到这种感觉)】
    2. 具体来说，最常遇到的情况是
      1. 设计定义变量的语义：二分查找，并在迭代中维护定义的区间[left,right]中有我们要找的target
      2. 定义变量的取值区间：eg: [0,~] 等等
        1. 34. 在排序数组中查找元素的第一个和最后一个位置
      3. 设计定义条件： 二叉树的最近公共祖先 我自己的方法
      4. 利用上面定义进行逻辑推理验证
      5. 每次新的循环开始，都是自带定义，说明当前变量满足的性质，这个性质使我们进行逻辑推理的关键。非常常用。
        1. 这个定义一般都是while(condition)中的condition，或者我在上次循环最后所限制的条件
        2. 从这里我们也能明确循环单元的重要性
  18. dp思路：
    1. 有几组状态？你做的这件事有几个因变量，也就是有哪些可能，这些【可能】可以分为几类
    2. 状态之间的关系？考虑到达当前状态有几种【可能】，我的目的是找最大的还是最小的
    3. 【dp其实就是在暴力枚举可能状态，他比纯暴力不超时的原因是，将题目中蕴含的上下文关系结合到了暴力的过程中。】
      1. 从纯暴力的枚举所有【case】，编程dp的枚举所有【状态】，注意这里case到状态的改变
    4. eg: 123. 买卖股票的最佳时机 III
      1. 一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过
      2. 所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]
  19. 暴力：不要觉得暴力很low，很多题在理解了题意之后，做一些针对性的整理，最后通过暴力来做出最后的结果。
    1. 这是我们这次周赛后感觉出的经验！
  20. 搜索：
    1. 这类题其实属于搜索这一大类，其中dp，深度搜索、广度搜索，暴力搜索，搜索的剪枝等等内容的本质就是搜索
    2. 在搜索的题中，关键的区别就是看是否能够找到题目本身的规律进行剪枝、优化、避免重复计算。
    3. 983. 最低票价
  21. 看实况，对我有重大启示：
    1. zerotrac的个人空间 - 哔哩哔哩 ( ゜- ゜)つロ 乾杯~ Bilibili
    2. 最大的收获：高手做题，一看题就会想这道题是在考那个知识点，我们就用哪个知识点进行解答。
    3. 对比我原先的方法：做了很多没有必要的思考，反而浪费的时间。
  22. 特征不明显的题，需要我们先去发现规律，然后根据规律的特征然后找到合适的算法。对于这样的题先从暴力开始下手是一个不错的建议，然后从暴力中寻找可以优化的规律。
  23. 递归的表达能力比迭代要强：
    1. 所有递归都可以改写成循环吗？ - 知乎
    2. 角度1：用循环压栈来避免递归也太搞笑了点吧，手工递归就不是递归了？
    3. 角度2：栈底不可预见的时候，递归是无法有效地化为循环的。
  24. 如何将递归写成迭代？或者递归和迭代的的区别？
    1. 148. 排序链表
      1. 准则：
        1. 准则1：一定要先写递归，在写迭代：递归的表达能力比迭代强，对于递归边界不明确的问题无法写成迭代
        2. 准则2：在递归中，我们确定基础动作有哪些，这些动作迭代中一定有
        3. 准则3：动作的执行方法变成交替进行 或者说 类似于dp的感觉：从最小的数据范围进行解决，然后不断的扩大数据的范围 ==》 最终完成所有的数据范围
          1. 抓住dp的感觉就对了：先彻底解决最小问题，然后不断扩大。这其中关键是：在这道题中是连接好子问题和大问题，对应到dp就是状态转移方程
          2. 这里与dp不同的一点是：
            1. dp的状态转移方程 =》 变成了一种链表之间的连接
            2. 状态变量 ==》dp是一层一层的，这里是树的一层一层的
            3. 他没有打表这么明确的因变量，以及打表的顺序方向(这么一说dp是不是特别简单)
    2. 【递归有点倒着写的感觉 ==》 当考察你对递归的理解：可以说(具有相同子问题 + 考虑有限的所有的情况)】
      1. 这里需要我们考虑所有的可能的情况，又和dp思路重合了
    3. 总结：
      1. 写递归更加容易，不容易被不断的迭代过程绕过去，有明显的步骤感，并且递归的能力比迭代强
      2. 当遇到时间、空间复杂度的时候，我们再尝试写成迭代的方式
        1. 在写的时候，我经验是别从递归改代码，而是当做一道新的模拟题去做，过程中可以把递归的基础动作当做是检验、提醒的作用
        2. 因为该的过程中，需要使用两种思维，容易绕住
      3. dp、递归、迭代这些算法思路可以相互的提醒、辅助
    4. 迭代的本质：先彻底解决最小问题，然后不断扩大。
    5. 递归的本质：直接解决大问题
    6. dp：先彻底解决最小问题，然后不断扩大。
    7. dp、递归、迭代 的共同本质就是题目中蕴含子问题这个概念，当出现子问题时，我们可以选择他们其中之一进行解决

现在做的题多了，方法总结的也多了，我得想办法进行精简：

我觉得心里记笨方法比较有用，因为特别的方法，题目中的特征也比较明显，容易想到，【最怕的就是那种完全没有思路的！】

  1. 笨方法(无策时找到启发点)：
    • 【正向case】【BF】【过程模拟】==》 拿上case，一步不落的走走！【整理数据和过程的方式】
  2. 精益求精的方法(在有思路的基础上)：
    • 【其他的】
  3. 最关键的：就是【正确的思考角度 】+ 【归纳现象条件】，对零散的现象屡出个一二三类来的【逻辑思维能力】。不论哪种方法的核心都是这个

态度是最关键的：

1.提醒自己乐观、多角度的的尝试各种方法。脑子转的快一点。
2.不要眼高手低，落实到每一个步中，自然就会有感觉

水平高了之后:

不能满足于功能:

  1. 【思路层面】多种思路的时间复杂度
  2. 正确性证明
  3. 【代码层面】相同的思路,代码层面上如何设计简化

发表于 更新于 分类于 阅读次数：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

2020年3月7日 下午4:54

前序遍历

  • Process代表是我们第一次遍历树各个节点的顺序，也就是前序遍历
  • 第一次遍历树各个节点的顺序 = 前序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            if (root == NULL) return {} ;
            vector<int> ans;
            stack<TreeNode*> process;//记录路径点

            // 初始化：要初始化两个变量
            process.push(root); 
            ans.push_back(root->val); 
            TreeNode* cur = root->left;  
            // 循环不变式     
            while(1) {
                // 2.再反过头再检查！ 是否需要移动当前位置，如果找不到合适的位置，就结束程序！
                while (cur == NULL) {
                    if (process.empty()) return ans; 
                    cur = process.top()->right; 
                    // ans.push_back(process.top()->val);
                    process.pop();
                }
                // 1.先假装一切正常
                process.push(cur);
                ans.push_back(cur->val);
                cur = cur->left;
            }
            return ans;
        }
    };

中序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == NULL) return {} ;
        vector<int> ans;
        stack<TreeNode*> process;//记录路径点

        // 初始化：要初始化两个变量
        process.push(root); 
        TreeNode* cur = root->left;  
        // 循环不变式     
        while(1) {
            // 2.再反过头再检查！ 是否需要移动当前位置，如果找不到合适的位置，就结束程序！
            while (cur == NULL) {
                if (process.empty()) return ans; 
                cur = process.top()->right; 
                ans.push_back(process.top()->val);
                process.pop();
            }
            // 1.先假装一切正常
            process.push(cur);
            cur = cur->left;
        }
        return ans;
    }
};

后序遍历：

我最成功的地方在于分解了问题：

  • 先可以正确的遍历
  • 因为是后序遍历，和中序遍历对比，从定义出发，猜测：在中序的基础上，把top顶去掉，在找合适的时候插进去就行
  • 这时，通过测试用例，先看看top是否拿出来了
  • 最难是判断何时将top再放进去：这个标志得自己做，我这里使用的是高度！
  1. 我不觉得从前序遍历 改到 后序遍历是一个好办法，其中太复杂了。主要目的还是锻炼一下自己的总结能力！
  2. 【太复杂了，都无法用循环不等式证明！！！！，只能通过case一个个的试了】
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            if (root == NULL) return {} ;
            vector<int> ans;
            stack<TreeNode*> process;//记录路径点
            
            stack<TreeNode*> top; // 把顶点位置保存起来，再看什么时候插入
            stack<int> top_high; // 相同高度的时候插入

            // 初始化：要初始化两个变量
            process.push(root); 
            TreeNode* cur = root->left;  
            // 循环不变式     
            while(1) {
                // 2.再反过头再检查！ 是否需要移动当前位置，如果找不到合适的位置，就结束程序！
                while (cur == NULL) {
                    if (process.empty()) {
                        //  结束程序的时候，top中剩下的记得放入
                        while(!top.empty()) {
                            ans.push_back(top.top()->val);
                            top.pop();
                        }
                        return ans;
                    }

                    cur = process.top()->right; 

                    // 相同高度的时候插入top中的数据
                    while (!top_high.empty() && process.size() == top_high.top()) {
                        ans.push_back(top.top()->val);
                        top.pop();
                        top_high.pop();
                    }
                    
                    if (cur == NULL) {// cur == NULL时，我们可以直接放入ans中
                        ans.push_back(process.top()->val);
                        process.pop();
                    }
                    else {
                        top.push(process.top());// cur != NULL时，我们需要先暂存到top中
                        process.pop();
                        top_high.push(process.size());
                    } 
                }
                // 1.先假装一切正常
                process.push(cur);
                cur = cur->left;
            }
            
            return ans;
        }
    };

发表于 更新于 分类于 阅读次数：
本文字数： 171 阅读时长 ≈ 1 分钟

2020年3月6日 下午5:31

1
2
3
4
5
6
7
for GCM in $GCMS;do
  for SCEN in $SCENS;do
    mkdir -p $SCEN/$GCM
    echo "transferring $GCM $SCEN"
    RSYNC_PASSWORD='***' rsync -auvL hostname@ip:/work/*.nc $SCEN/$GCM/
  done
done

发表于 更新于 分类于 阅读次数：
本文字数： 500 阅读时长 ≈ 1 分钟

2020年3月4日 下午7:37
今天再看《算法图解》最后一页时，作者提到了牛B的线性规划！

线性规划定义：

线性规划 - 维基百科，自由的百科全书

  • 在数学中，线性规划（Linear Programming，简称LP）特指 目标函数 和 约束条件皆为 线性 的 最优化 问题。
  • 线性规划是最优化问题中的一个重要领域。在 作业研究 中所面临的许多实际问题都可以用线性规划来处理，特别是某些特殊情况，例如：网络流、多商品流量等问题，都被认为非常重要。目前已有大量针对线性规划 算法 的研究。很多 最优化 问题算法都可以分解为线性规划子问题，然后逐一求解。在线性规划的历史发展过程中所衍伸出的诸多概念，建立了 最优化 理论的核心思维，例如“ 对偶 ”、“ 分解 ”、“ 凸集 ”的重要性及其一般化等。在微观经济学和商业管理领域中，线性规划亦被大量应用于例如降低生产过程的成本等手段，最终提升产值与营收。 乔治·丹齐格 被认为是线性规划之父。

线性定义：

线性关系 - 维基百科，自由的百科全书

线性规划教程：

wiki最后还有很多
https://mat.gsia.cmu.edu/orclass/integer/integer.html

线性的定义：

线性关系 - 维基百科，自由的百科全书

发表于 更新于 分类于 阅读次数：
本文字数： 414 阅读时长 ≈ 1 分钟

2020年3月4日 下午4:25

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

发表于 更新于 分类于 阅读次数：
本文字数： 526 阅读时长 ≈ 1 分钟

2020年3月4日 下午4:19
力扣

数学的定义

数学是利用符号语言研究数量、结构、变化以及空间等概念的一门学科，从某种角度看属于形式科学的一种。数学透过抽象化和逻辑推理的使用，由计数、计算、量度和对物体形状及运动的观察而产生。数学家们拓展这些概念，为了公式化新的猜想以及从选定的公理及定义中建立起严谨推导出的定理。

数学的发展：

基础数学的知识与运用是个人与团体生活中不可或缺的一环。对数学基本概念的完善，早在古埃及、美索不达米亚及古印度内的古代数学文本便可观见，而在古希腊那里有更为严谨的处理。从那时开始，数学的发展便持续不断地小幅进展，至 16 世纪的文艺复兴时期，因为新的科学发现和数学革新两者的交互，致使数学的加速发展，直至今日。数学并成为许多国家及地区的教育范畴中的一部分。

应用数学于纯数学

今日，数学使用在不同的领域中，包括科学、工程、医学、经济学和金融学等。数学对这些领域的应用通常被称为应用数学，有时亦会激起新的数学发现，并导致全新学科的发展，例如物理学的实质性发展中建立的某些理论激发数学家对于某些问题的不同角度的思考。数学家也研究纯数学，就是数学本身的实质性内容，而不以任何实际应用为目标。虽然许多研究以纯数学开始，但其过程中也发现许多应用之处。