堆只会两招:弹最值、塞新值。但配上贪心,这两招足以打穿一整个题库——反悔堆更是贪心流的后悔药,吃下去连悔棋都是 $O(\log n)$ 的。本合集收录堆类题目。

第 k 大/小

leetcode 264

最小堆解法:先把最小的丑数 1 入堆,每次弹出最小值 x,把 2x、3x、5x 入堆,用哈希表去重。弹 n 次即得第 n 个丑数。

leetcode 373

枚举所有点对至少 $O(n^2)$ 起步,必须利用两数组非递减的性质。想象一个矩阵:纵坐标是 nums1 下标,横坐标是 nums2 下标,矩阵值是数对和。这个矩阵每行非递减、每列也非递减,左上角 (0, 0) 是全局最小。

于...

Read more

二叉树


二叉树

树题是刷题修行的主线任务之一。本合集按套路分节收录二叉树题目:每题给出关键观察、做法与复杂度。

二叉搜索树

BST 的第一反应是中序遍历——中序遍历 BST 会得到一个严格递增的序列,大量题目围绕这条性质展开。

leetcode 2476

中序遍历得到递增序列,对每个询问在序列上做一次二分查找。时间复杂度 $O(n \log n)$。

leetcode 1932

合并 BST。需要先观察出两条性质:

  1. 根节点是唯一的。 能成为最终根的树,其根值没有出现在任何叶子上,也就无法「被」合并;如果这样的树不止一棵,最后不可能合并成一棵树。
  2. 合并方式是唯一的。 若一棵树能被多个叶子合并,假...

Read more

一文解决逆序数


一文解决逆序数

一道逆序数,四种写法,从面试到竞赛一网打尽。计算逆序数有两种思路:

  1. 归并排序:统计归并过程中「右边元素先出列」时跨过的元素数;
  2. 值域计数:按 rank 逐个把元素落位计数,当前元素的逆序贡献等于值域区间 $[rank+1, n]$ 上的计数和——需要单点修改 + 区间求和的数据结构。

leetcode 上有一道弱化的模板题,下面四份代码都以它为载体。

思路一:归并排序

面试版(切片归并)

一般来说面试写出这版就够了:

class Solution:
    def reversePairs(self, record: List[int]) -> int:
      ...

Read more

mmpretrain增加回归任务组件


mmpretrain 增加回归任务组件

mmpretrain 原生只服务分类任务。本文把它魔改出完整的回归能力:自定义数据集、预处理器、回归器、回归头、MAE 损失与评估指标、推理器,一路改到 gradio 演示,全程沿 mm 系列的注册器机制进行,不破坏框架原有结构。

openmmlab介绍

openmmlab系列框架在2023年全面进入2.0时代,官方把自监督mmselfsup和分类mmclassification两个项目合并成mmpretrain。
openmmlab 2.0系列底层是有一些变化的,最大变化是从mmcv中抽离出功能更强大的mmengine。新的项目我还没仔细看过,目...

Read more

nvidia TAO Toolkit使用总结


nvidia TAO Toolkit 使用总结

TAO 表示 train、adapt、optimize。TAO Toolkit 是 nvidia TAO 框架的低代码版本,主打使用者无需专业 AI 知识即可构建高准确度模型,在英伟达设备上做到训练部署一条龙。低代码不等于无坑,本文按流程走一遍,把每一步的暗雷标出来。

流程参考快速上手 tao toolkit

环境准备

1. 注册与登录 ngc

注册英伟达开发者账号(略),去 ngc 官网目录右上角用英伟达账号登录。

2. 生成 API Key

回到 ngc 首页,右上角点自己的账号,进 Setup,出现 Generate API Ke...

Read more

win10 python环境安装GPU版本opencv并简单使用


win10 python 环境安装 GPU 版本 opencv 并简单使用

pip 装的 opencv 是没有 CUDA 加速的,想在 Python 里用 GPU 版 opencv 只能自己从源码编译。本文记录 win10 下完整的编译安装流程,以及一组「GPU 未必比 CPU 快」的实测。

环境

  • python:anaconda base 环境,3.9.7
  • CMake:3.24.1(cmake 下载
  • opencv:4.6.0
  • vs:2019 社区版
  • CUDA Toolkit:11.3.1(cuda-toolkit 下载nvcc -V 查看版本)
  • cuDNN:8.2.1(cuDNN ...

Read more

django设置时区支持导致mysql查询报错


django 设置时区支持导致 mysql 查询报错

背景:为什么要开 USE_TZ

在 django settings 中设置 USE_TZ = True 是官方推荐的做法,也是 django 5.0 之后的默认值。官方文档的说明:

当启用对时区的支持时,Django 在数据库中以 UTC 为单位存储日期时间信息,在内部使用具有时区的日期时间对象,并在模板和表单中将其转换为最终用户的时区。

如果用户居住在多个时区,这会很方便:你要根据用户的时间来显示日期信息。

即使你的网站只在一个时区提供服务,在数据库中用 UTC 存储数据仍然是一个好的做法,主要原因是夏令时(DST)。许多国家都有...

Read more

yolov5 fp16动态输入转TensorRT部署到triton服务


yolov5 fp16 动态输入转 TensorRT 部署到 triton 服务

把 yolov5 训练出的 PyTorch 模型转换成 TensorRT 模型,扔进 triton 里部署。一条看似官方全程护航的流水线,实际每一步都有暗雷,本文按流程逐个排掉。

需求

  1. 为加快推理速度,把 fp32 精度的模型转成 fp16;
  2. 为支持 yolov5 动态 padding 和批推理,输入的 batch 和图片 size 需要是动态的。

版本

  • yolov5:v6.1
  • triton docker 镜像:22.08
  • TensorRT:8.4.2.4
  • cudnn:8.2.1.32
  • CUDA To...

Read more