Leetcode-1038-把二叉搜索树转换为累加树

思路：反向中序遍历

题目描述

• 给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换成累加树（Greater Sum Tree），使得每个节点的node 的新值等于原书中大于等于node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

方法 : 反向中序遍历

• 关于二叉搜索树的问题，第一个想到的就是中序遍历，这是二叉搜索树的一个非常重要的性质
• 二叉搜索树的中序遍历是一个递增的有序序列

观察累加前中序遍历和累加后中序遍历，我们会发现，其实后者就是前者的一个从后的累加结果。

那么问题就迎刃而解了，我们秩序反向中序遍历即可，并且把每次的节点值进行累加，就能得到最终的累加树。并且保证了这样只会访问每个节点一次。

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;
    public TreeNode bstToGst(TreeNode root) {
        if(root != null){
            // 1. 如果是叶子节点的话
            // 进行反向的中序遍历
            bstToGst(root.right); // 递归右子树
            sum = sum + root.val; // 累加
            root.val = sum; // 更新节点的值
            bstToGst(root.left); // 递归左子树
        }

        return root;
    }
}

操作系统-10-进程同步和互斥

前言

partition-合集

前言

1. 什么是 partition ？

我们在学习 快速排序 的时候知道，可以选择一个标定元素（称为 pivot ，一般而言随机选择），然后通过一次扫描，把数组分成三个部分：

• 第 1 部分严格小于 pivot 元素的值；
• 第 2 部分恰好等于 pivot 元素的值；
• 第 3 部分严格大于 pivot 元素的值。
• 第 2 部分元素就是排好序以后它们应该在的位置，接下来只需要递归处理第 1 部分和第 3 部分的元素。

经过一次扫描把整个数组分成 3 个部分，正好符合当前问题的场景。写对这道题的方法是：把循环不变量的定义作为注释写出来，然后再编码。

Linux-09-进程调度算法

前言

• 进程调度算法也称 CPU 调度算法，毕竟进程是由 CPU 调度的。
• 当 CPU 空闲时，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配 CPU。

什么时候会发生 CPU 调度呢？通常有以下情况：

1. 当进程从运行状态转到等待状态；
2. 当进程从运行状态转到就绪状态；
3. 当进程从等待状态转到就绪状态；
4. 当进程从运行状态转到终止状态；

其中发生在 1 和 4 两种情况下的调度称为「非抢占式调度」，2 和 3 两种情况下发生的调度称为「抢占式调度」。

• 非抢占式的意思就是，当进程正在运行时，它就会一直运行，直到该进程完成或发生某个事件而被阻塞时，才会把 CPU 让给其他进程。
• 而抢占式调度，顾名思义就是进程正在运行的时，可以被打断，使其把 CPU 让给其他进程。那抢占的原则一般有三种，分别是时间片原则、优先权原则、短作业优先原则。

操作系统-08-进程调度

前言

操作系统-07-CPU调度

前言

1. 调度的基本概念

Leecode-18. 四数之和

思路：排序+双指针

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

1
2
3
4
5
6
7
8

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

操作系统-06-线程

前言

好文阅读-01-后端学习路线

前言

• 说到后端开发，难免会遇到各种所谓高大上的「关键词 」，对于我们应届生小白，难免会觉得比较陌生，因为在学校确实比较少遇见这些所谓高大上的东西，那么今天就带着学习的态度和大家分享这些看似可以装逼可以飞的带逼格的关键词吧。

操作系统-05-进程通信

前言

• 很明显，在这一场面试中， 张三在进程间通信这一块没复习好，虽然列出了进程间通信的方式，但这只是表面功夫，应该需要进一步了解每种通信方式的优缺点及应用场景。