Castria-CSDN博客

说明此博客内容为哈工大2022春季学期软件构造Lab1:Fundamental Java Programming and Testing，文章为个人记录，不保证正确性，仅供练习和思路参考，请勿抄袭。实验所需文件可以从这里获取（若打不开可以复制到浏览器）。实验环境：IntelliJ IDEA 2022.1(Ultimate Edition)一、Magic Squares给定一个矩阵，判断其是否是一个幻方。矩阵以文件形式给出，同一行数字之间用制表符分隔。幻方需要满足：（1）它是一个nnn阶方阵，且元素

2022-04-27 21:31:49 2094 1

原创 Graham扫描法求解二维凸包问题

问题定义（文章内容来源于算法导论）点集QQQ的凸包是一个最小的凸多边形PPP，满足QQQ中的每个点都在PPP的边界上或者在PPP的内部。现给定一个点集，求解其凸包（即构成凸包的点集）。Graham扫描法Graham扫描法可以以O(nlogn)O(nlogn)O(nlogn)时间复杂度求解凸包问题，其中nnn为点集大小。以下是算法的伪代码：令p0为Q中具有最小纵坐标的点（或等价地，具有最小横坐标的点）;令<p1,p2,...,pm>为......

2022-04-27 16:00:02 1311

原创哈工大计算机系统Lab3.优化程序性能

说明至少用一种CPU优化方法和Cache优化方法，优化图像平滑函数，对于图像的每个long型像素点dst[i][j]，执行如下操作(dst为平滑后的图像)：dst[i][j] = (src[i][j - 1] + src[i][j + 1] + src[i - 1][j] + src[i + 1][j]) / 4;性能测试方法这里利用C标准库中的clock()函数进行测算。void testfunc(void (*flatten)()) { clock_t t1 = clock(); int

2022-04-22 16:01:13 3349

原创哈工大计算机系统Lab2.二进制炸弹

给定一个可执行目标文件bomb，共有6个阶段，需要用gdb/objdump等程序分析反汇编，以获取每个阶段对应的密码。若密码输错则炸弹爆炸。其中一个炸弹可以从这里获取。

2022-04-02 17:18:01 7509 6

原创 LeetCode 1703.得到连续 K 个 1 的最少相邻交换次数

题意给定一个仅包含000和111的数组，仅能交换其中相邻的两个数字，问至少多少次这样的操作可以使得至少kkk个111相邻。题解取数组中任意kkk个相距最近的111，设它们出现的下标分别为a1,a2,...,ak.a_1,a_2,...,a_k.a1,a2,...,ak.考虑将它们交换多少次可以使得它们聚成连续的kkk个111。有这样一个常用结论：对于数轴上的点a1,a2,...,aka_1,a_2,...,a_ka1,a2,...,ak，使它们移动到一处的最小代价当它们都移动到该序列的中位

2022-03-30 13:47:31 1687

原创 LeetCode 44.通配符匹配（ε-NFA解法）

题意给定一个字符串 (sss) 和一个字符模式 (ppp) ，实现一个支持 ′?′'?'′?′ 和 ′∗′'*'′∗′ 的通配符匹配。'?' 可以匹配任何单个字符。'*' 可以匹配任意字符串（包括空字符串）。如："∗a∗b""*a*b""∗a∗b"可以匹配"adceb""adceb""adceb"(第一个∗*∗为空，第二个∗*∗为dcedcedce)限制字母表为小写字母。题解因为这学期正好在学形式语言与自动机这门课，这道题显然是一个正则表达式的问题，就尝试模拟了一下正则表达式转ϵ−NFA\

2022-03-28 15:44:23 459

原创 LeetCode 233.数字1的个数

题意给定一个正整数nnn，计算[1,n][1,n][1,n]中所有整数出现的111的个数之和。题解设nnn的数字长度为www，n=dwdw−1...d1.n=d_wd_{w-1}...d_1.n=dwdw−1...d1.考虑依次对这www位进行计数。若现在正考虑从右向左第iii位：v=cwcw−1...ci+11ci−1...1.v=c_wc_{w-1}...c_{i+1}1c_{i-1}...1.v=cwcw−1...ci+11ci−1...1.设左边的w−iw-iw−i位(cw...

2022-03-26 20:32:30 380

原创斐波那契堆的C++实现

本文改编自《算法导论》第三版第19章：斐波那契堆。

2022-02-15 01:26:55 2360 1

原创 python实现简易聊天室程序

本文为计算机网络学习过程中随笔，程序如有bug或设计不当之处还请指正。1.服务器端程序1.1基本思想主线程：一个while True循环，每次接受一个TCP连接，为每个客户单独创建一个线程。该部分代码：import threadingfrom socket import *IP = '**.**.**.**'#改为服务器的内网IPserverPort = 12000#服务器端要开放该端口MAX_CONNECTION = 5serverSocket = socket(AF_INET, SO

2022-02-12 00:55:47 7838 3

原创哈工大2021年秋季学期数据结构期末试题

因为考完试没有收演草纸，所以题中数据与考试差距不大。选项顺序可能略有差异；选择第5题希尔排序的序列数据是后编的；简答第3题B-树的插入序列顺序可能不同，但是考察的点是一样的。其他题的数据基本可以保证和原题一样。一、选择题111.以下代码的时间复杂度是for(int k=1;k<=n;k++) for(int j=1;j<=n;j++) count++;A.O(n) B.O(nlogn) &

2021-11-29 12:26:22 3422

原创跳表的C++实现

跳表(Skip List)是在链表基础上进行改进的一种有序的数据结构，它为了便于查找，在插入过程中随机地将一些元素提升为高度为1~r的索引，以此来加快之后的操作。索引可以分为多层，一般而言，层数越高的索引个数越少。下面的图是一个跳表示例（隐去表头，上面的为高层）为了方便下面对代码实现的说明，先给出各数据类型的定义。template<typename T> class skiplist{ private: static constexpr int MAX_LEVEL = 16; s

2021-11-07 17:51:13 2417 5

原创 Clion环境Qt简单示例程序:计算器

效果预览：1.新建项目Qt CMake前缀路径选择Qt路径下面的mingw文件夹。2.新建Qt UI类3.用Qt Designer对界面进行布局（对于QtDesigner如何添加到Clion中，可以参考这篇博客）布局如下，其中上面的文字框是Line Edit控件，按钮为Push Button。对每个控件进行调整、命名：可以调整按钮及文本框中的字体及大小、对齐方式：这里文本框选择右下角对齐。对.ui文件运行UIC（添加UIC与添加QtDesigner类似，可以自行搜索）

2021-10-16 20:38:40 618

原创 KMP字符串匹配算法

字符串的模式匹配是以下的一种常见问题：给定字符串sss(主串)和ttt(模式串)(∣s∣=n,∣t∣=m,m≤n)(|s|=n,|t|=m,m\leq n)(∣s∣=n,∣t∣=m,m≤n)，求ttt在sss中第一次出现的位置。如:s="ababcabcacbab"s="ababcabcacbab"s="ababcabcacbab"t= "abcac"t=\ \ \ \ \ \ \ \

2021-09-12 11:03:28 141

原创二项队列介绍及其实现

注：此博客改编自《数据结构与算法分析：C语言描述》中二项队列一节。

2021-07-15 22:30:27 1032

原创计蒜客-42578 And and Pair

题目大意对于一个非负整数nnn(以二进制给出),找出满足以下条件的(i,j)(i,j)(i,j)对数:::0≤j≤i≤n;0\leq j \leq i \leq n;0≤j≤i≤n;i&n=i;i\&n=i;i&n=i;i&j=0.i\&j=0.i&j=0.输出答案模109+710^9+7109+7的结果。输入21111010输出1415题解对于一个二进制数，i&n=i\&n=i&n=且i≤ni\leq

2021-07-15 20:20:55 135

原创扩展欧几里得、中国剩余定理和扩展中国剩余定理

1 扩展欧几里得算法扩展欧几里得算法主要可以解决：·求乘法逆元·求解同余方程/二元一次方程其中,求乘法逆元可以转化成求解同余方程。1.1求解方程ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b)的一组特解先考虑以下二元一次方程：ax+by=gcd(a,b) (1)ax+by=gcd(a,b) \qquad\qquad\qquad\qquad\qquad\ \ \ (1)ax+by=gcd(a,b) &n

2021-07-07 18:33:39 346

原创 Python request库爬取有道翻译中英互译

import requestdef GetTranslate(sentence): url = 'http://fanyi.youdao.com/translate?smartresult=dict' extra = {'smartresult':'dict&rule'} form = {'i': sentence,'from': 'AUTO','to': 'AUTO','smartresult':'dict', 'client': 'fanyide

2021-06-18 21:28:01 510 1

原创 Python绘制三维函数图像

from matplotlib import pyplot as plotimport numpy as npimport mathfrom mpl_toolkits.mplot3d import Axes3Dfigure = plot.figure()axes = Axes3D(figure)X = np.arange(-10,10,0.25)Y = np.arange(-10,10,0.25)#前两个参数为自变量取值范围X,Y = np.meshgrid(X,Y)Z = np.s

2021-06-18 21:18:18 7091 4

原创洛谷P2345 [USACO04OPEN]MooFest G

题目大意有nnn头牛(n≤20000)(n\leq20000)(n≤20000),每头牛都有属性vi,xiv_i,x_ivi,xi,求∑1≤i,j≤nmax{vi,vj}∣xi−xj∣\sum_{1 \leq i,j \leq n}max\{v_i,v_j\}|x_i-x_j|∑1≤i,j≤nmax{vi,vj}∣xi−xj∣的值.题解采用类似归并排序统计逆序对的思想，由于式子中的max{vi,vj}max\{v_i,v_j\}max{vi,vj}不好处理，可以先将奶牛对vvv进行排

2021-04-05 20:09:18 219

Castria的博客

原创哈工大2022机器学习实验三&四：KMeans&PCA

原创哈工大2022机器学习实验二：逻辑回归

原创哈工大2022机器学习实验一：曲线拟合

原创计算建模之EM算法

原创典型相关分析(CCA)及其python实现

原创主成分分析法(PCA)及其python实现

原创 Python实现聚类K-means算法

原创使用Python爬虫和C++搭建离线IP库

原创哈工大2022软件构造Lab3

原创软件构造：设计模式总结

原创哈工大2022软件构造Lab2

原创哈工大2022计算机系统大作业:Hello‘s P2P

原创一种期望边数为O(nlogn)的随机联通图生成方法

原创哈工大计算机系统Lab4.Tiny Shell

原创哈工大2022软件构造Lab1