Algo

归并排序

思路

• mergeSortC 对数组的子数组进行排序，当 len(子数组) == 1 的时候，这个数组就是有序的，此时就是递归出口
• merge 对有序的子数组进行合并。 0. left, right 两个子数组内部的元素是有序的
  1. 就像交换需要创建 tmp 变量。merge 时 先创建 tmp 数组
  2. 将 left, right 两个子数组的元素 有序 放入 tmp 中
  3. 将子数组中剩余的部 …

题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。

新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。

复制链表中的指针都不应指向原链表 …

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = …

题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3 输出：5

示例 2：

输入：n = 1 输出：1

提示：

1 <= n <= 19

解题思路

这个题目主要的难度在公式推导上，我们可以用动态规划的思路来求解。

• 令 \( G(N) \) 表示 n 互不相同的整数组 …

二分查找的注意点

1. 循环的条件: left <= right
2. mid 计算方法:

# 用移位预算速度更快
mid = left + ((right-left) >> 1))

3. left 和 right 的更新方法

left = mid + 1
right = mid - 1

// BinarySearchLastV2
/**
## 功能

返回 arr 中最后一个 == …

背景

哨兵，现实中是用于解决国家之间的边界问题。

在算法程序中，我们设置一些冗余的变量，让算法程序处理边界问题时更加容易，这些变量就被称为哨兵。

本文将会举例说明，哨兵变量在算法程序中的应用。

插入排序

插入排序是一种常用的排序算法，它的思路是

1. 用 i 从 1 开始遍历数组中每个元素
2. 从后往前遍历 1-i 的每个元素，找到第一个比当前元素小的元素，将其插入到该元素之后
   • Note: 先挪位置，循 …

简介: 利用Go语言实现二叉搜索树并为其编写单元测试