听寒's Blog

　　Ctrl+C和Ctrl+Z都是中断命令，但作用不同。

　　Ctrl+C是发送SIGINT信号，终止一个进程。

　　Ctrl+Z是发送SIGSTOP信号，挂起一个进程，将作业放置到后台（暂停状态）。与此同时，可以通过fg重启前台被中断的任务，也可以通过bg把中断的任务放到后台执行。

　　Ctrl+D表示一个特殊的二进制值EOF，代表输入完成或注销。

http://t.zoukankan.com/diantong-p-5566305.html

模板lower_bound & upper_bound

“搜索区间”定义为等于target的区间，对于upper_bound，它的结果是搜索区间外的下一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    // 所有可能性：left: [0, n]  right: [-1, n-1] mid: [0, n-1]
    if (left >= nums.length || nums[left] != target) 
        return -1;
    return left;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况，见下图
    if (right < 0 || nums[right] != target)
        return -1;
    return right; // 若要求upper_bound（下一个不等于target的位置）则是return left;
}

1、为什么 while 循环的条件中是 <=，而不是 <？

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

leetcode560. 和为 K 的子数组
https://leetcode-cn.com/problems/subarray-sum-equals-k/
难度：中等

== 支配理论 ==
假设有递归关系式 $T(n) = a T\left(\frac{n}{b}\right) + f(n)$，其中$ a \geq 1 \mbox{, } b > 1$

其中，n 为问题规模， a 为递归的子问题数量，$\frac{n}{b}$ 为每个子问题的规模（假设每个子问题的规模基本一样），f(n) 为递归以外进行的计算工作。

=== 情形一 ===
如果存在常数$ \epsilon > 0 $，有

$ f(n) = O\left( n^{\log_b (a) - \epsilon} \right)$（可不严谨地视作多项式地小于）

则: $ T(n) = \Theta\left( n^{\log_b a} \right) $

=== 情形二 ===
如果存在常数$ \epsilon\ge0 $，有: $f(n) = \Theta\left( n^{\log_b a} \log^{\epsilon} n \right)$

则: $T(n) = \Theta\left( n^{\log_b a} \log^{\epsilon+1} n \right) $

=== 情形三 ===
如果存在常数$ \epsilon > 0 $，有: $ f(n) = \Omega\left( n^{\log_b (a) + \epsilon} \right) $（多项式地大于）

同时存在常数$c < 1$以及充分大的$n$，满足:$a f\left( \frac{n}{b} \right) \le c f(n)$

则:$T\left(n \right) = \Theta \left(f \left(n \right) \right)$

== 常用算法中的应用 ==

经典题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

注意：题目要求子数组最少包含一个元素，所以返回结果可能为负（若所有元素负，则将返回最大的一个负数）。倘若允许子数组为空（结果为0），则要怎么修改？

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

https://leetcode-cn.com/problems/maximum-subarray/

解1 动态规划：

1
2
3
4
5
6
7
8
9
10

int maxSubArray(vector<int>& nums) {
    if(nums.empty()) return 0;
    size_t n=nums.size();
    vector<int> ans(n); // 代表以nums[i]为结尾的连续最大和
    ans[0]=nums[0];
    for(int i=1;i<n;i++) {
        ans[i]=max(ans[i-1]+nums[i],nums[i]);
    }
    return *max_element(ans.begin(), ans.end());
}

刻画解的状态结构：f(i)代表以nums[i]为结尾的连续最大和
状态转移方程：f(i)=max{ f(i-1)+nums[i], nums[i] }
解释：选择是将nums[i]以nums[i-1]为结尾的最优解，或是选择以nums[i]单独成为解

注：我在第一次尝试解答时，将状态结构f(i)构造为了 代表以nums[1]…num[i]可以包含的最优解，
然而后续遭遇了困难，因为我无法简单确定nums[1]…num[i-1]的最优解位置，可能不在末尾而在中间，难以继续转移。
以后要注意不同的结构构造方法，并且注意怎样构造才更方便更简洁。

解2 分治法：

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

int maxCrossingSubArray(vector<int>& nums, int left, int mid, int right) {
    int leftSum=0;
    for(int i=mid-1, sum=0; i>=left; i--) {
        sum+=nums[i];
        if(sum > leftSum) {
            leftSum = sum;
        }
    }
    int rightSum=0;
    for(int i=mid+1, sum=0; i<=right; i++) {
        sum+=nums[i];
        if(sum > rightSum) {
            rightSum = sum;
        }
    }
    return leftSum+nums[mid]+rightSum;
}
int maxSubArray(vector<int>& nums, int left, int right) {
    if (left==right) {
        return nums[left]; // base case
    }
    int mid = (left+right)/2;
    int rLeft = maxSubArray(nums, left, mid);
    int rRight = maxSubArray(nums, mid+1, right);
    int rMid = maxCrossingSubArray(nums, left, mid, right);
    return max(max(rLeft, rRight), rMid);
}
int maxSubArray(vector<int>& nums) {
    return maxSubArray(nums, 0, nums.size()-1);
}

注：
maxCrossingSubArray的实现
注意左右的最大和要分开计算。想想若使用同一个sum变量会发生什么？
要注意解中肯定可能包含负数，并非遇到负数就要中断。如3 -1 5肯定比3大。

解3 分治：
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
著作权归作者所有。

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

struct Status {
    int lSum, rSum, mSum, iSum;
};

Status pushUp(Status l, Status r) {
    int iSum = l.iSum + r.iSum;
    int lSum = max(l.lSum, l.iSum + r.lSum);
    int rSum = max(r.rSum, r.iSum + l.rSum);
    int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
    return (Status) {lSum, rSum, mSum, iSum};
};

Status get(vector<int> &a, int l, int r) {
    if (l == r) {
        return (Status) {a[l], a[l], a[l], a[l]};
    }
    int m = (l + r) >> 1;
    Status lSub = get(a, l, m);
    Status rSub = get(a, m + 1, r);
    return pushUp(lSub, rSub);
}

int maxSubArray(vector<int>& nums) {
    return get(nums, 0, nums.size() - 1).mSum;
}

该解采用了不同的分治设计，具体可以参见LeetCode答案。

借助归并排序分治问题，在合并解的阶段计数。

归并排序每次将数据分解为nums[p…q]和[q+1…r]，分别求解子问题，然后合并。
在合并的过程中可以完成对逆序对的计数，合并过程逐个从左右区间未选取的元素中选取最小的元素放入结果。
我们可以想到：

• 由于子问题求解完毕后左、右子区间[p…q]、[q+1…r]有序，任意剩余子区间[p+i…q]、[q+1+j…r]也必然有序，所以拿取的最小元素必然是其中一个剩余区间的第一个元素
• 若元素是从左区间拿取，由于它是最小且在所有左侧、右侧剩余元素的最前，所以与该元素不存在相关的逆序对
• 若元素是从右区间拿取，由于它是最小且在所有右侧剩余元素的最前，所以左侧剩余元素nums[q+1+j]与右侧第一个剩余元素nums[q+1+j]构成全部相关的逆序对

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

class Solution {
public:
    inline int merge(vector<int>& nums, size_t p, size_t q, size_t r) {
        if(!(p<=q && q<r)) return 0;
        int numRev=0;
        size_t n1 = q-p+1, n2 = r-q;
        vector<int> A(n1), B(n2);
        for(size_t i=0;i<n1;i++) A[i]=nums[p+i];
        for(size_t i=0;i<n2;i++) B[i]=nums[q+1+i];
        size_t i=0, j=0;
        for(size_t c=p;c<=r;c++) {
            // 注意判定边界。
            // 另外不可以用哨兵值的方法，因为此题输入可能会包含int的最大值
            if (i>=n1) {
                // 左区间全部用完了，复制右区间
                nums[c] = B[j++];
                // 此处也不需要增加numRev，左侧已经用完，没有元素再与右侧构成逆序对，numRev增量必然是0
            } else if (j>=n2) {
                // 右区间全部用完了，复制左区间
                nums[c] = A[i++];
            } else {
                // 都没用完，正常对比
                if(A[i] <= B[j]) {
                    nums[c] = A[i++];
                } else {
                    nums[c] = B[j++];
                    //if (A[i] != B[j])
                    numRev += n1-i; // 左侧全部剩余元素A[i...n1]与右侧第一个剩余元素B[j]构成全部相关的逆序对
                }
            }
        }
        return numRev;
    }
    int solve(vector<int>& nums, int p, int r){
        if(p>=r) return 0;
        int q=(p+r)/2;
        int cnt=0;
        cnt+=solve(nums,p,q);   // 不要忘记加上子问题时发现的逆序对
        cnt+=solve(nums,q+1,r); // 不要忘记加上子问题时发现的逆序对
        cnt+=merge(nums,p,q,r); // 合并同时也求解本层上的逆序对
        return cnt;
    }
    int reversePairs(vector<int>& nums) {
        vector<int> copy(nums);
        return solve(copy, 0, nums.size()-1);
    }
};

另外在算法导论（第3版第2章思考题2-4.d.）或部分题解上，在merge过程中可能使用了一个极大数作为哨兵值来判断是否其中一个区间已经消耗完毕。

然而，由于题目没有说明数据范围的情况下，我们必须假设输入是全范围的，
也就是说输入可能包括int的最大值2147483647（实际上leetcode上此题测试用例确实包含这个）

因此不可以用大数作为哨兵值的方法

（虽然发现有时测试数据不够强也可能萌混过关）

剑指 Offer 5

1.单选题
有些工程产品(如DDT)在技术上是成功的,但在生态上是失败的。这句话的含义是:(D)
A 产品没有实现预期目的
B 产品亏损,经营难以为继
C 产品技术性能不如意
D 产品技术性能达到预期,但在生态效应方面却造成危害。

2.多选题
工程师容易忽视利益冲突的影响原因在于( BC)
A 认为只要遵循职业伦理章程的规范要求去行动,就不会造成利益冲突
B 可能会否认实际的存在利益冲突
C 可能高估自己处理利益冲突的能力
D 认为按照约定俗成的标准或以往的经验从事职业活动,就不会造成利益冲突

3.单选题
以下观点属于契约论的是( B)
A 关注的主要是人的内心品德的养成,而不是人外在行为的规则。
B 通过一个规则性的框架体系,把个人行为的动机和规范伦理地看作是一种社会协议。
C 关注人们行为的动机,强调行为的出发点要遵循道德的规范,体现人的义务和责任。
D 最好的结果就是达到“最大的善”,只有当一个行为能够最大化的

4.判断题
信息技术从业人员将所发明出来的信息技术开发成新产品、新服务后,往往会遭遇“制度真空”或“法律真空”地带,因此,加强信息技术从业人员的伦理意识培养、制定并执行职业规范非常重要。(对)

5.多选题
环境工程师一般建议遵守以下哪些准则(ABCD)
A 仅在他们有能力胜任的领域内从事工作。
B 仅以客观的和诚实的方式发表公开声明。
C 作为忠诚的代理人和受托人为雇主和客户从事职业工作。
D 将公众的安全、健康和福祉置于首位。

6.多选题
弱势人群包括(BCD)。
A 领导者
B 少数民族
C 妇女
D 儿童

7.判断题
在全球化情境下,只有充分重视工程的全球性特征,在尊重民族文化特色和地域文化前提下,工程实践才能有序运行。(对)

8.单选题
人与自然和谐发展是处理工程与自然关系的基本原则,其要求工程的决策者、设计者、实施者以及使用者都要了解和尊重自然的内在发展规律,不仅注重自然规律,更要注重(C)
A 经济规律
B 社会规律
C 生态规律
D 技术规律

9.多选题
影响核事故信息公开的主要因素包括(ABD)。
A 经济因素
B 社会因素
C 人文因素
D 政治因素

10.多选题
维护河流健康生命的原则包括:(ABCD)
A 补偿与损害等容
B 近期与远期统一
C 开发与保护并重
D 局部与整体协调

11.判断题
在讨论工程设计理念时,只需要工程师代表参与决策。(错)

12.多选题
跨文化工程伦理规范的国际运用涉及跨国企业的社会责任管理实践,其实质在于强调跨国企业不能只关注自己的经济利益,也应该致力于解决当地的社会问题。以下属于企业社会责任运动的实践成果的是:(ABCD)
A 社会责任国际组织的《社会责任国际标准》
B 联合国的《全球契约》
C 《中国对外承包工程行业社会责任指引》
D 国际标准化组织的《社会责任指南》

13.多选题
环境工程的主要任务有(ABCD)
A 治理污染
B 改善环境质量
C 提高生活水平
D 恢复生态

14.判断题
核安全基本原则主要涉及管理责任,纵深防御和基本技术原则。(对)

15.单选题
以下哪项是对马丁和辛津格的“利益冲突”定义的错误描述? (C)
A 工程师面对一种获得利益的可能性
B 这种转化是否能成功,取决于工程师的“行为”
C 是一种潜在利益冲突向实际利益冲突的转化的一种结果性情境
D 如果去追逐这种利益,那么可能就会使他们无法履行其对雇主或客户所应负有的义务

16.单选题
工程师在组织中的主要职能是(C)。
A 考虑所有相关的因素,维护组织利益
B 服从组织安排和上级命令,做好自己份内的工作
C 坚持职业标准,特别关注安全和质量标准
D 维护雇主和客户的利益

17.判断题
讨论工程的利益分配可以从宏观和微观两个层面来进行。宏观层面是指在企业内工程项目的活动情况。(错)

18.单选题
行业市场竞争不应该是(A)的竞争。
A 商业贿赂
B 技术
C 价格
D 服务

19.多选题
核工程师的培养,需重视培养他们的(AC)。
A 伦理道德
B 逻辑推理
C 社会责任感
D 学习能力

20.判断题
工程师的职业伦理标准中,要求当工程师发现任何形式的危害安全行为或不法行为时,要敢于采取应有的行动。(对)

21.单选题
工程实践全球化中工程师的伦理责任包括职业伦理责任、(D)、环境伦理责任、以及文化伦理责任
A 生态伦理责任
B 企业伦理责任
C 地球伦理责任
D 社会伦理责任

22.单选题
以下不属于安全文化的核心的是(D)。
A 人的安全意识
B 人的安全技能
C 人的安全知识
D 人的安全装备

23.单选题
涉及到人体的生物医学研究需要接受伦理审查,那么,伦理审查的最重要的目的是什么?(B)
A 保护研究者的权益
B 保障受试者权益
C 推进科研项目顺利开展
D 促进科学知识的增长

24.多选题
土木工程的伦理问题通常会涉及(ABC)等问题。
A 经济社会与环境可持续
B 利益分配公平与公正
C 安全与风险
D 公共治理。

25.判断题
环境问题主要指由于人类经济和社会活动引起的环境破坏,实质是经济发展与环境保护的冲突,是人与自然的失调。(对)

26.单选题
某跨国公司的工程师认为,分公司完全可以保持在自己国家行之有效的那套做法,不必根据新的跨文化环境进行调整。这种伦理立场属于:(C)
A 伦理拓展主义
B 伦理相对主义
C 伦理绝对主义
D 伦理关联主义

27.单选题
人的身份用来界定一个人是谁或者是什么,具有可识别性、独特性、唯一性。与人的身份不一样,数字身份具有多样性与(C),具有容易被盗用、容易被追溯等特点。
A 一致性
B 不变性
C 可变性
D 虚假性

28.多选题
狭义的工程概念认为,工程是以满足人类需求的目标为指向,应用各种相关的知识和技术手段,调动多种自然与社会资源,通过一群人的相互协作,将某些现有实体(自然的或人造的)汇聚并建造为具有预期使用价值的人造产品的过程。狭义的工程概念( ABCD)
A 强调多主体参与的社会性
B 包括“化学工程”“三峡工程”“载人航天工程”等
C 工程伦理所讨论的“工程”,主要指狭义的工程概念
D 主要指针对物质对象的、与生产实践密切联系、运用一定的知识和技术得以实现的人类活动

29.单选题
当某项工程在施工期间出现了技术规范所不允许的断层、裂缝、倾斜、倒塌、沉降、强度不足等情况时,监理工程师首先需要做的是?(A)
A 暂停该项工程的施工,并采取有效的安全措施。
B 要求承包人尽快提出质量事故报告并报告业主。
C 对承包人提出的有争议的质量事故责任予以判定。
D 对承包人提出的处理方案予以审查、修正、批准,并指令恢复该项工程施工。

30.判断题
目前对水利工程价值的伦理判断基本是遵循功利主义原则。(对)

31.单选题
2016年12月1日起实施的《中华人民共和国网络安全法》规定以下若干主体依法使用网络的权利受到国家保护。哪一个选项并未受到法律保护?(C)
A 其他组织
B 公民
C 实现自动驾驶的算法代码
D 法人

32.多选题
处理工程伦理问题的基本原则包括(BCD)
A 经济利益最大化原则
B 人与自然和谐发展原则
C 人道主义原则
D 社会公正原则

33.单选题
违背水资源公正配置原则的是(B)。
A 重视生态
B 自由引水
C 尊重历史
D 临近优先

34.判断题
涉及到人体的医学研究均应该接受伦理审查。(对)

35.单选题
下列哪一项不属于工程实践全球性特征?(A)
A 社会性
B 深远性
C 生态性
D 整体性

36.判断题
伦理责任就是法律责任(错)

37.多选题
以下哪些工程没有遵循自然规律,成为生态上失败的工程。(AB)
A 三门峡水利枢纽
B 咸海水利工程
C 三峡水利枢纽
D 里海水利工程

38.多选题
强化(法治、管理、技术)_手段,保证数据安全,是大数据应用的重要伦理法则。
（此题务必注意区分法治、法制）
A 法治
B 管理
C 法制
D 技术

39.判断题
工程师个人的职业理想、标准及其道德准则应无条件地服从就职公司的组织目标、政策、标准和行为,这样就不会遭遇利益冲突和角色冲突,更不会发生个人对组织的不服从行为。(错)

40.多选题
吸收公众参与工程决策、设计和实施的全过程,其作用是:(ABCD)

三种遍历的大体流程是不一样的，主要的区别在于控制何时visit。

中序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

vector<int> inorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode *curr = root;
    while(curr || !s.empty()) {
        // Reach the left deep
        while(curr) {
            s.push(curr);
            curr = curr->left;
        }
        // Backtrack from the empty subtree and visit the node at the top of the stack; 
        // however, if the stack is empty you are done
        curr = s.top(); s.pop();
        ans.push_back(curr->val); // visit
        // We have visited the node and its left subtree. Now, its right subtree's turn
        curr = curr->right;
    }
    return ans;
}

前序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

vector<int> preorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode *curr = root;
    while(curr || !s.empty()) {
        // Reach the left deep
        while(curr) {
            ans.push_back(curr->val); // visit
            s.push(curr);
            curr = curr->left;
        }
        // Backtrack from the empty subtree and visit the node at the top of the stack; 
        // however, if the stack is empty you are done
        curr = s.top(); s.pop();
        // We have visited the node and its left subtree. Now, its right subtree's turn
        curr = curr->right;
    }
    return ans;
}

与中序的差别仅仅是访问的时机改到了Reach the left deep循环中，让左子树入栈前就可以先访问当前节点了。

后序遍历：

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

vector<int> postorderTraversal(TreeNode* root) {
    if(!root) return {};
    vector<int> ans;
    stack<TreeNode*> s;
    TreeNode *curr = root;
    TreeNode *lastvisited = nullptr;
    while(curr || !s.empty()) {
        // Reach the left deep
        while(curr) {
            s.push(curr);
            curr = curr->left;
        }
        // Backtrack from the empty subtree and visit the node at the top of the stack; 
        // however, if the stack is empty you are done
        curr = s.top(); // 不能在这弹出，要等到访问完右子树第二次经过父节点

        if(!curr->right || lastvisited == curr->right) {
            // 刚刚已经访问过右子树（根据lastvisited标记）或者没有右子树（所以没法产生lastvisited标记），现在访问当前节点（这是第二次经过）
            ans.push_back(curr->val);
            s.pop();
            lastvisited = curr;
            curr = nullptr; //  置为空，以便继续弹出父节点
        } else {
            // 右子树还没访问过，转向右子树
            curr = curr->right;
        }
    }
    return ans;
}

主要区别在于，由于是需要全部子树访问完再，所以对于同一个节点会经过两次，
第一次经过只是取出其右子树，
第二次从其右子树返回到当前节点才是应该访问的时机，

我们需要借助lastvisited判断当前是否是从其右子树返回的第二次经过，并在此时visit和pop。

不要忘记更新lastvisited，以当该结点是右孩子时协助其父节点更新，
不要忘记curr置空

很久没有打理博客了，将博客主题换成了Ayer，另外同样更换了评论系统为Valine，因为不需要额外加载站外js，相比Disqus更为流畅了。
旧评论的迁移上，写了个Disqus到Valine评论数据转换脚本转换。但由于Disqus不提供用户的邮箱地址和个人网站，这些数据无法迁移过来。

另外调整了博客架构，目前位于Github Page上使用GithubAction实现自动部署，免去了部署的烦恼，另外配合CDN实现了国内加速。