- 博客(29)
- 收藏
- 关注
RSS订阅
原创 BFS的理解和应用
BFS（Breadth First Search）之前写了DFS理解和应用，这次来写写BFS。● BFS是方向发散的找，就是1变4，4变16这个意思，类似于分身，不同的分身还可以继续分身。● 案例解释：找眼镜 你的眼镜掉在地上以后，你趴在地上找，你总是先摸到最接近你的地方，如果没有找到，再往远一点的地方找找。● BFS包括单向BFS，双向BFS....单向...
2018-08-08 16:16:42
22928
3
原创 DFS的理解和应用
目录DFS(Depth First Search)数塔问题Prime Ring Problem - HDOJ 1016 / UVa 524 /（紫书P194例题7-4）Zipper HDOJ - 1501（DFS+剪枝）Lake Counting POJ - 2386棋盘问题 POJ - 1321水果消除 HNUSTOJ团队程序设计天梯赛--L3-015球队“食...
2018-08-08 10:31:58
10657
13
原创 数据挖掘——几个算法的python实现
这个学期开了“数据挖掘”课程，学习了几个相关的算法，本着记录和验证一下学习成果的目的写了这篇文章~所谓是自己懂不算懂，能讲清楚让别人也懂才算懂~本文一共有四个算法的基本概念和实现，分别是KNN、ID3、C4.5、Apriori目录1. KNN算法1.1 算法介绍1.2 算法实现步骤1.3 算法的关键1.4 Python具体实现（电影分类）2. ID3算法2....
2019-11-17 21:23:15
5121
原创 STL（所见过的技巧和用法总结）
STL（Standard Template Library）在程序设计竞赛中，偶尔会碰到一些需要用特殊结构来解决的问题，这时，灵活运用STL库中的一些数据结构会加速问题的解决，这里，我写了一些我碰到过的应用案例，帮助理解STL的强大。虽然这些特殊的结构可以解决很多问题，但是性能较差，对于一些时间、空间性能要求比较高的题目并不适用。目录STL（Standard Template Li...
2019-07-26 00:16:25
593
原创 哲学家进餐问题--Linux下实现进程间的通信
问题描述：五个哲学家围坐在一张圆桌，每个人面前都有一份食物，一共只有五个筷子（本来是叉子，可我觉得相比叉子而言，筷子才是没有办法只用一支就可以进餐的吧~），如下图所示（图片来源于百度）。哲学家有三个状态：1. 思考（thinking）2. 饥饿（hungry）3. 进餐（eating）只有在同时拿到两支筷子的时候，哲学家才可以开始进餐。这个问题可能出现的情况就是：每个人手...
2019-06-23 13:54:42
2396
11
原创 C语言实现读者写者问题（读者优先）
最近在做操作系统课程设计，碰到了这个问题，在解决的过程中也有找过不少别人的代码来做参考，但是在看他们代码的输出时，总感觉结果怪怪的。。后来还是自己琢磨了一个。我在代码中加入了一些语句，把中间结果输出来，这样就能明确看到各线程的状态。这结果应该是没有问题的了。如果有路过的大牛发现问题，欢迎在评论区留言向我反馈~非常感谢！读者优先的伪代码：void Reader(){ while(...
2019-06-19 10:37:30
12075
13
原创 小程序调用接口实例
附：这个例子调用的接口是自己写的一个接口，因为仅用于单纯的测试，所以并没有备案，但如果是没有备案的接口，需要在小程序里勾选不检验合法域名，即下图所示（这个选项在项目设置里面）做好这步之后，再在test.js里面写onLoad方法，如下所示onLoad: function (options) { var that = this; wx.request({ u...
2019-05-07 18:24:01
14250
2
原创 [Leetcode] -- Search Insert Position
题目链接分析：就是找到第一个大于或等于给出数字的位置。代码一，直接按照这个逻辑实现：class Solution {public: int searchInsert(vector<int>& nums, int target) { int i; for(i=0;i<nums.size();i++) {...
2019-04-19 19:38:11
125
原创 [Leetcode] -- Implement strStr()
题目链接分析：找haystack里面有没有needle，有就返回子串起始位置，没有就返回-1，若needle是空串就返回0用C++调用string.find(string)的代码如下，很容易写，但是效率。。可以说是很低。class Solution{public: int strStr(string haystack, string needle) { ...
2019-04-17 00:29:55
84
原创 [Leetcode] -- Remove Duplicates from Sorted Array
题目链接分析：给出一个升序序列，找到不同的数字数量cnt，并且要处理这个序列，使得序列结果为这些数字的排列。然而题目中还有一句话：It doesn't matter what values are set beyondthe returned length.那就意味着，只要前cnt个是目标序列就可以，后面的数字可以不用处理。class Solution {public:...
2019-04-15 23:40:19
91
原创 [Leetcode] -- Merge Two Sorted Lists
题目链接分析：新开一个链表 l3，作为结果记录的链表，再开一个链表指针cur用于操作 l3。合并的时候先将两个链表指向的下一个数进行比较，把较小的插到 l3中。最后，把 l1或 l2未合并的部分放到结果链表表尾。另加一个判断语句，在进入函数的时候就判断有没有空链表，如果有，就直接返回另外一个链表。/** * Definition for singly-linked list. * s...
2019-04-14 12:28:55
76
原创 [Leetcode] -- Valid Parentheses
题目链接分析：用stack来存左括号，用map存左右括号，比普通的判断方便一点。每遇到一个右括号，就取栈顶的符号now，如果now与此右括号不匹配，那这个字符串就是不合法的，否则就继续往后遍历。遍历到最后，如果stack里面还有没有被匹配到的左括号，那么这个字符串也是不合法的。class Solution {public: bool isValid(string s) { ...
2019-04-14 10:59:32
90
原创 数独求解
题目链接分析：数独的详细规则请参照--百度百科（这里就不设传送门啦，有兴趣的同学自行前往~）。简单来说就是每一行、每一列都要有1~9的每个数字，既然是每个都要有，意味着不能重复。然而还有一个隐藏特征，就是九宫格（3*3）里面也得刚好是1~9.用DFS试探和回溯就可以求出来，详细注解见代码。#include <iostream>#include <cstdio&g...
2019-04-14 00:39:45
1124
原创 [Leetcode] -- Longest Common Prefix
题目链接分析：题目意思很简单，就是找到所有string的最长相同前缀，需要注意的是处理结果这一块。用stringstream存答案（为什么用stringstream，因为string不可变哇！！我一开始忘记了，而且函数返回就是string，所以就被带偏了。。），最后再把它转成string返回。这里还要注意一点，就是当函数输入的vector为空时，需要返回空串，而且这个要单独处理，否则就...
2019-04-13 11:52:39
84
原创 [Leetcode] -- Reverse Integer
题目链接分析：就是将数字反转输出，不用考虑前导零。但是要注意！！如果这个结果，注意，是结果，大于2^31-1（INT_MAX）小于-2^31（INT_MIN），应输出0。（就因为这个条件WA了好几次没弄出来。。）下面是我的代码：class Solution {public: long long reverse(long long x){ long long ...
2019-04-09 23:27:12
87
原创 [Leetcode] 入门篇 -- Two Sum
一直都知道Leetcode这个平台，最近才开始刷题路，后悔也太晚了呀。。进到Problems的第一个问题就是Two Sum，看了看题目，唔，不难，看了看代码段。。崩溃。。以前从来没有这样写过呀，突然间就要这样还真不太习惯，那么！下面就开始我的摸索之路~题目链接分析：因为数组里面的数有正也有负，而且也不知道最大的数会有多大，所以就只能用map来存，如下：class Solution...
2019-04-09 00:17:51
131
原创 最短路径
最短路径算法是算法竞赛中经常出现的一种算法，关于它的应用非常丰富，在这里我收集了一些我遇到的比较好的题目。紧急救援--天梯赛题目链接题意分析：这题不仅要找到最短路径，还要找到与最短路径长度相同的路径有多少条，另外，还要找到能召集的最大救援队数量。用Dijkstra算法找最短路径，在找的同时记录最短路径的数量，以及不断更新能召集的最大救援队数量。代码参考自https:/...
2019-03-29 23:16:26
159
原创 小技巧~
偶尔看到一些比较好的技巧，会有原出处注明，旨在分享目录NO.1 N进制的本质NO.2 鹰蛋问题NO.3 疯狂的位运算之移位运算NO.4 疯狂的位运算之与运算NO.5 疯狂的位运算之异或运算NO.6 二分计算二进制的前导零NO.1 N进制的本质-->>有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是...
2019-03-27 23:02:45
211
原创 并查集的理解与应用
并查集一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。算法的实现主要包含两个部分：find函数，用于查询根节点，merge函数，用于合并具有相同根的两个子树。基本题型：给出一系列的点，并给出该点所属的团体，有时还会给出团体之间的联系，问：<1>有多少个团体<2>问还需要再建造多少媒介才能使所有团体之间都可以两两联...
2019-03-27 22:22:06
165
原创 JUnit单元测试——学习笔记
JUnit 是用于测试 java程序的一个工具，是在软件开发中非常重要的技术。JUnit的用处：这个工具可以针对特定的java程序生成对应的测试程序，在测试程序里用正确答案和java程序跑出来的答案做对比，一定程度上可以检验java程序的正确性。为什么要用JUnit?我们在编写程序的时候，常常需要在写完一个函数或者方法之后，检验它的正确性。在最基础的编程阶段时，我们写的程序通常也不...
2019-03-04 17:11:03
1498
原创 莫队算法 -- BZOJ2038小Z的袜子
题目链接分析：我们将问题抽象为：从某个已知区间里询问，任取两个数，这两个数相等的概率。假设这个区间为[L,R]，这个区间里一共有n个不同的数字a1,a2,...,an，n个数字对应其个数b1,b2,...,bn，那么可以根据组合排列，求出这个概率。关于这个公式的解释：其实就是排列组合的结果，参考公式 从每一个数字集（例如2,2,2）中随机抽取两个数，这两个数有多少种相等的...
2018-11-30 18:05:07
155
原创 POJ - 2184 Cow Exhibition（01背包）
题目题目意思就是要求出smartness和funness之和的最大值，同时这两个分别也大于或等于零。一个变形的01背包问题。这个题目纠结了很久，翻了挺多博客，看完都是一知半解，后来看到了一个代码很清晰的博客，才慢慢理解大概是怎么解的。下面是我对这个代码的理解，可以结合代码来看一下。 先开一个很大的数组，一分为二，左边的一半存负数的情况，右边的一半存正数的情况，取中间值shif...
2018-08-20 09:42:37
105
原创 hnustOJ - 1695: 跳格子
题目描述逸夫楼的大厅的地面有10行10列的石砖，我们用坐标(x,y)来表示石砖的位置。如图示：一天lxl在逸夫楼大厅玩跳格子游戏，跳格子游戏有7个动作：1.向左转，2向右转，3向后转，4向左跳一格，5向前跳一格，6向右跳一格，7向后跳一格。游戏前，lxl在(1,1)处并面向y轴正方向，他会做n次动作，若某个动作会让lxl跳出逸夫楼大厅则原地不动，每一次动作后都需要你输出lxl当前的位置...
2018-08-07 22:00:06
478
原创 万年历--格式愁死人系列
万年历，格式参考日历，可以打印出一定范围年份的全年日历（忘记是什么范围了。。题目找不到啦。。。aaaaaaa）#include<stdio.h>int is_rn(int x){ if((x%4==0&&x%100!=0)||(x%400==0)) return 1; else return 0;}int m...
2018-08-07 21:51:02
341
原创 hnustOJ - 1693: 原石法阵
题目描述WZH有一个由原石构成的n阶三角形魔法阵，三角形魔法阵如下图:但是WZH现在想要将这个魔法阵改造成一个n阶五边形魔法阵，五边形魔法阵如下图:WZH发现并不是每一个n阶三角形魔法阵和n阶五边形魔法阵所用的石头都是一样的,所以WZH想知道将现在的n阶三角形魔法阵改造为n阶五边形魔法阵还需要多少原石?不过他觉得这会是一个天文数字,所以只要告诉他对3733取模后的数字就好了!...
2018-08-07 21:46:27
359
原创 hnustOJ-1741: 好友互动标识
题目描述 QQ有一个有趣的功能即显示好友互动标识，它的规则是这样的，如果两个人之间互发消息连续3天以上（包含3天）则出现擦出火花的标识，如果互发消息连续30天以上（包含30天）则出现聊得火热的标识，当出现了聊得火热的标识时，原来的擦出火花标识会被替换成聊得火热标识。如果两个人已经连续互发消息3天以上（包含3天）或者30天以上（包含30天），之后的一天没有互发消息，那么无论是擦出火花还...
2018-08-07 21:38:11
491
原创 hnustOJ-1448-有理数个数
问题 V: 有理数的个数 题目描述任何一个有理数都可以表示成M/N的形式（M,N均为正整数）。例如1/2,2/4,3/6都是等值的有理数。给定若干有理数，等值有理数的值只能算一个，问这些有理数含有多少个值，并按从小到大输出各值及该值的有理数个数。输入第一行是整数n,表示随后有n组测...
2018-07-22 23:05:57
325
原创 HDOJ-2068-RPG的错排（错排）
RPG的错排Problem Description今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜，第一次猜：R是公主，P是草儿，G是月野兔；第二次猜：R是草儿，P是月野兔，G是公主；第三次猜：R是草儿，P是公主，G是月野兔；......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动...
2018-07-22 22:53:53
147
原创 HDOJ-2048-神、上帝及老天爷（错排）
神、上帝以及老天爷HDU 2006'10 ACM contest的颁奖晚会隆重开始了！为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；然后，待所有字条加入完毕，每人从箱中取一个字条；最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”大家可以想象一下当时的气氛之热烈，...
2018-07-22 22:36:15
214
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人