| by YoungTimes | No comments

Ubuntu 18.04安装微信和迅雷

由于开发需要,个人电脑上只安装了Ubuntu系统,但是很多软件并不支持Ubuntu系统,所以再网上找了很多安装微信和迅雷的方法。

1、XwareDesktop(迅雷)

XwareDesktop是网上讲的比较多的一款软件,不过作者已经弃坑了。项目的Github地址: https://github.com/Xinkai/XwareDesktop 。项目的资料比较完整,各个环节的问题和说明也比较详细。

由于作者长时间不维护了,最近的更新在五六年前。按照项目中Ubuntu编译打包安装之后,始终无法启动,所以放弃了。

2、Deepin wine for Ubuntu and[……]

继续阅读

Read More
| by YoungTimes | No comments

C++多线程编程-揪出高CPU占用的线程

在工程实践中,有很多对性能要求比较苛刻的场景,要求CPU的占用不能超过指定的阈值,以保证系统整体的实时响应。本文主要记录下如何抓出CPU占用高的线程。

假设有如下业务代码:

代码编译:

g++ cpu.cpp -o cpu -pthread -g

1.定位线程

使用top命令,定位高占用的进程。

$top
2988 xxx   20   0   32564   1860   1708 S  99.3  0.0  24:27.84 cpu         
20178 xxx   20   0 5067244 195804 118856 S   1.7[......]

继续阅读

Read More
| by YoungTimes | No comments

计算机视觉-Camera标定

1、像素坐标系与图像坐标系之间的关系

假设每一个像素在u轴和v轴方向上的物理尺寸为dx和dy

2、图像坐标系到相机坐标系

3、世界坐标系到相机坐标系

于是,从世界坐标系到像素坐标系的转换关系:

4、其他情况

考虑像素坐标系坐标轴不垂直的情况(实际相机由于制造工艺上的问题,导致物理成像坐标轴不是绝对垂直),如下图所示,假设O1在UV坐标系下的坐标为(u0, v0),像素的物理尺寸仍然为dx,dy,则有

矩阵形式如下:

世界坐标系与像素坐标系转换关系:

[……]

继续阅读

Read More
| by YoungTimes | No comments

计算几何-凸包(Convex Hull)

凸包(Convex Hull)是计算几何中的一个经典常用的算法。它解决的问题在于给定空间一堆离散的点,计算包含所有点的凸多边形。

凸的定义

凸是指图形内任意两点的连线都不经过图形内部。

计算凸包时要考虑一些特殊情况,比如凸包上多点重叠,凸包上多点共线,通常我们会倾向于用最少的点来描述凸包。

凸包算法伪代码

凸包算法C++实现

算法时间复杂度

由于做了一次排序算法的时间复杂度O(NlogN),两个for循环的时间复杂度为O(N),所以整体的时间复杂度为O(NlogN).

[……]

继续阅读

Read More
| by YoungTimes | No comments

数据结构与算法-计算二叉树的深度和最大宽度

在数据结构中,二叉树是一种非常基础的数据结构,无论是在面试中,或者实际应用中,都有非常普遍的用途。

1.数据结构定义:

2.二叉树的深度

二叉树的深度:

根结点所在的层数为1,根结点的孩子结点所在的层数为2,以此类推,深度是指所有结点中最深的结点所在的层数。

3.求解思路:

我们可以从根节点和左右子树来理解二叉树的深度。对于任意一棵非空二叉树,有如下四种情况:

1) 如果二叉树只有一个节点,它的深度是1;

2) 如果根节点只有左子树而没有右子树,那么二叉树的深度应该是其左子树的深度加1;

3)如果根节点只有右子树而没有左子树,那么二叉树[……]

继续阅读

Read More
| by YoungTimes | No comments

数据结构与算法-计算二叉树中节点的最大距离

1.问题定义

如果把二叉树看做无向图,我们姑且定义二叉树的“距离”为节点之间边的个数。现在要计算二叉树中相距最远的两个节点之间的距离。

二叉树的节点距离计算有几种情况:

1) 根节点为空,路径长度为0;

2) 根节点非空的情况下,分为两种情况:

情况A: 路径经过左子树的最深节点,通过根节点,再到右子树的最深节点。

情况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者。

只需要计算这两个情况的路径距离,并取其大者,就是该二叉树的最大距离。

2.代码实现(c++版本)[……]

继续阅读

Read More
| by YoungTimes | No comments

动态规划-最长公共子序列

1.公共子序列

给定两个字符串m和n,如果它们的子串a和b内容相同,则称a和b是m和n的公共子序列。子串中的字符在原字符串中不要求连续,只要保持原有相对顺序即可。

例如,字符串“abcfbc”和“abfcab”,其中“abc”同时出现在两个字符串中,因此“abc”是它们的公共子序列。

2.算法求解

动态规划问题一般具备两个特征:

1) 最优子结构;

2) 重叠子问题;

设 X=(x1,x2,…..xn) 和 Y={y1,y2,…..ym} 是两个序列,将 X 和 Y 的最长公共子序列记为LCS(X,Y)。

最优子结构

首先考虑X的最后一个元[……]

继续阅读

Read More
| by YoungTimes | No comments

数据结构与算法-并查集

并查集(Disjoint set或者Union-find set)是一种树型的数据结构,常用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。

1.基本操作

并查集是一种非常简单的数据结构,它主要涉及两个基本操作,分别为:

A. 合并两个不相交集合

先设置一个数组Father[x],表示x的“父亲”的编号。 那么,合并两个不相交集合的方法就是,找到其中一个集合最父亲的父亲(也就是最久远的祖先),将另外一个集合的最久远的祖先的父亲指向它。

C语言代码如下:

B. 判断两个元素是否属于同一个集合

寻找两个元素的最久远祖先是否相同。寻找[……]

继续阅读

Read More
| by YoungTimes | No comments

计算几何-线扫描算法计算矩形并集面积

本文是扫描线算法的具体的应用。

1.问题描述

给定N个矩形,矩形的边均平行于X坐标轴或者Y坐标轴,矩形之间也可能存在互相压盖重叠,计算矩形并集的面积。

2.问题解法

矩形表示:[左下角点,右上角点]

将矩形按照X坐标排序,想象一个竖直的扫描线从左向右扫描,遇到矩形的左边界,则把矩形加入与扫描线相交的矩形集合;遇到矩形右边界,则把矩形从与扫描线相交的集合中剔除。

扫描线移动过程中,覆盖区域的面积=Δx * Δy。其中Δx是扫描线两个相邻节点的距离,Δy是竖直扫描线被矩形区域截取的长度。

如何计算竖直扫描线被矩形区域截取的长度?同样用扫描线从底部向上扫描,[……]

继续阅读

Read More
| by YoungTimes | No comments

计算几何-最近点对问题

1.问题描述

最近点对问题是指求解平面点集中距离最近的两个点间的问题。

2.蛮力求解法

对平面中的所有点两两计算距离,然后通过比较获取最小距离。在具体的计算过程,可以通过一定的策略优化,比如避免计算A与B的距离和B与A的距离这样的重复计算,计算距离不用开方等。但总体的时间复杂度为O(N^2)。

3.线扫描算法

首先将点集按照x坐标值排序,然后按照从左向右进行线扫描。

假设我们已经遍历过1:N-1,h是1到N-1个点中最近点对的距离,对于第N个点,只有与第N个点的距离小于或者等于h的点我们才需要考虑,其余的点都可以过滤掉,所以只需考虑x坐标位于[x(N)-h,[……]

继续阅读

Read More