sbw Blog - 程序设计
  • 来源: sbw Blog | 浏览: 84 | 评论: 1 | 时间: 2019-08-09
    “Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.”——这是 LeetCode 上的一道 Hard 级别的题,是说将多个已经排序的有序序列合并成一个大的有序序列。使用优先队列的方式完成了这个题目,时间应该是 O(nm)。
  • 来源: sbw Blog | 浏览: 322 | 评论: 0 | 时间: 2019-04-13
    了解过 C 语言的应该都知道,在 C 标准库中的 rand 函数实际上是一种伪随机数生成算法。它使用“线性同余”算法进行一个迭代计算,这样计算的结果虽然分布上是满足随机分布的,但在得知具体算法及观察了当前数据之后,后续的随机数是可“预测”出来的。为了尽可能得到更“随机”的随机数,有很多种办法,而使用 CPU 内置的硬件随机数生成指令就是其中一种。
  • 来源: 石博文博客 | 浏览: 456 | 评论: 4 | 时间: 2019-03-31
    最近把自己的博客网站使用 Rust 语言重写了,利用的是 actix-web 这个框架。然后就一直想实现文章评论的回复邮件提醒这个功能,由于是自己写的网站,而且 actix-web 也没有提供像 wordpress 那样丰富强大的插件系统,所以这个需求就只能自己实现了。查了一圈之后,发现 lettre 这个库的 API、doc 什么的都比较完善,甚至直接提供了一个发邮件的 example,于是就准备利用这个库来实现一个发邮件的功能。
  • 来源: 石博文博客 | 浏览: 353 | 评论: 0 | 时间: 2019-03-29
    上一篇已经成功深入到指令层面了,这一篇就开始使用 IRBuilder 对函数流程进行修改,使得“不安全”版本的除法函数也增加对除数的零检查。因为除法指令分为整数除法、浮点数除法等等,而例如整数除法又可以细分为有符号数除法、无符号数除法,同时每种除法又根据类型不同分为32位除法、64位除法....。这里为了演示效果,我们只实现了32位的有符号除法。仅仅满足了测试代码的要求,如果要真的在生产中实现这个功能,细节上的很多问题还是要仔细分类处理的。
  • 来源: 石博文博客 | 浏览: 292 | 评论: 0 | 时间: 2019-03-29
    上一篇中实现了一个简单的编译器插件,它的作用仅仅是在编译过程中输出所有函数的名称。那么这一篇就更深入一步来观察LLVM的中间代码及指令生成部分,从而确定应该如何修改并添加程序逻辑,以实现我们最初的“除法保护”的功能。本篇主要介绍了LLVM编译系统的一些特点及典型用法,包括LLVM的模块划分,IR中的SSA(静态单赋值)概念与 PHI 节点的概念,以及如何使用 LLVM 的 IR Builder 在编译过程修改或插入一些逻辑代码。
  • 来源: 石博文博客 | 浏览: 374 | 评论: 0 | 时间: 2019-03-28
    在上一篇中介绍了LLVM/Clang的编译器插件可以用来进行一些简单的编译器功能扩展,从这篇开始就一步步来实现这个编译器插件。本篇主要介绍了如何建立LLVM/Clang编译器插件的开发环境及开发目录配置,如何使用CMake编译系统组织起整个工程项目来,以及使用最基本的LLVM趟管理器遍历输出函数信息等。
  • 来源: 石博文博客 | 浏览: 309 | 评论: 0 | 时间: 2019-03-27
    LLVM/Clang 提供了编译器插件机制可供扩展编译器的功能,实际上 LLVM/Clang 本身的很多功能也是以插件方式注册到编译器系统中进行实现的。在一些对安全要求极端苛刻的环境下,或是一些特殊的硬件平台中,总有一些奇怪的需求,而这些定制化的功能如果不是很复杂,就没有必要大动干戈去修改编译器,可以使用编译器插件来完成。这个系列文章设想一种需要进行除法保护的应用场景,需要在编译层面对除法进行强制检查,以杜绝除零异常的发生。
  • 来源: 石博文博客 | 浏览: 318 | 评论: 0 | 时间: 2019-03-24
    POJ 1007 这个题是一个难度一般的算法题,核心是要计算每一个字符串的权值然后累加并排序。在本题中,这个权值是指为字符串中的每一个字母计算它后面有多个个字母比它小,即发生了多个次“反转”。从这个描述的一般认识来看,这是个 N^2 复杂度的模拟问题,核心在于算法优化及找模型。但由于题目的测试数据比较简单,使用 N^2 复杂度的简单方法也可以很容易通过。这就导致了这个题目的实际比赛难度其实很低。这里从解题思路及推导过程给大家做一个线性复杂度,O(N) 解题方法的分享。
  • 来源: 石博文博客 | 浏览: 400 | 评论: 0 | 时间: 2019-03-21
    POJ 1005,船屋。这是一道比较简单的几何相关的计算题,只需要推导出公式即可轻松解决。不过这个题的英文描述理解起来挺抽象,大概意思是:从坐标(0, 0)开始,有一个圆形的区域,第1年的时候,这个圆形的面积为0。这个圆形每年扩大,每年扩大的面积是50,问给定一个坐标(x, y),这个圆形多久能覆盖到这个坐标。
  • 来源: 石博文博客 | 浏览: 349 | 评论: 0 | 时间: 2019-03-19
    POJ 1003 Hangover,这道题的意思是说有一叠卡片放在桌子的边缘,要求卡片尽可能的有更多的部分伸出到空中,但卡片整体又不能掉下去。那么在只有 1 张卡片的时候,是一半在桌子上,一半在空中,伸出去的长度是 1/2。当有两张卡片时,最多能伸出 1/2 + 1/3 = 5/6。当 n 张卡片堆叠起来时,最多伸出的长度即为 1/2 + 1/3 + ... + 1/(n+1)。先不说这个公式是不是符合物理规律,从算法上来讲是一道很简单的模拟题,按照题目所给出的计算公式递推计算结果即可。
  • 来源: 石博文博客 | 浏览: 3601 | 评论: 3 | 时间: 2017-02-24
    Qt 中经常使用 Model-View 模型来创建列表等视图,这样设计程序结构的好处是能将数据部分和界面完全分离。其中 Model 负责数据的准备与加工,View 提供了具体的对外显示的 Widget,而 Delegate 用作在 View 上绘图的模块。而对于现代的图形程序设计,对动画效果的要求更多,需要这三个模块配合来创建动画效果。
  • 来源: 石博文博客 | 浏览: 2379 | 评论: 2 | 时间: 2017-01-24
    在 Leetcode 上看到一个题(原题地址),最长无重复子串。当时看的第一眼觉得或许可以用动态规划,今天空闲时间实现了一下。
  • 来源: 石博文博客 | 浏览: 2533 | 评论: 4 | 时间: 2016-05-28
    一系列平方数组成的排列,所有的数恰好将0~9使用了一遍,比如 0,1, 4, 9, 872356,或者4, 9, 361, 87025,或者 1436789025。它们分别是一系列平方数组成的排列,而且这个排列恰好把数字 0~9 使用了一遍,现在要编程求出所有的平方数数列。