周五闲来无事，基于上一篇关于初探12306售票算法（一）-理论，进行了java编码实践供各位读者参考（以下为相关代码的简单描述）1.订票工具类 1.1初始化一列车厢的票据信息/*** 生成Ticket信息* * @param train* @return*/public static List<Ticket> initTicketList(Train train) {List<Ticket> result = new ArrayList<Ticket>();Map<String, Integer> seatMap = train.getSeatTotalNum();for (Entry<String, Integer> entry : se...
深度优先搜索算法（DFS）要理解深度优先搜索必须理解递归的本质，递归的核心思想在于在一个函数还没有执行完成的时候就调用自身，这样就会形成一个树状的结构，从而使其可以一直延伸下去，进而覆盖所有可能的分支。直到某一层递归条件满足，才开始收敛。 Figure 1 递归Note：图中序号相同而且用虚线相连接的一个方块和圆圈对表示一次函数调用 从图中可以看出递归具有很强的可回退性和选择性，图中的2和2’是一次递归的不同分支，3和...
奈何能力不够，用欧拉回路DFS解题，但是Memory Limit Exceed了，晚上回来再学用并查集。题目描述： 假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。 假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于...
递推算法:递推算法使用"步步为营"的方法,不断利用已有的信息推导出新的东西.-顺推法:是指从已经条件出发,桌布推算出要解决问题的方法.例如:斐波那契数列就可以通过顺推法不断递推出新的数据.-逆推法:是从已知的结果出发,用迭代表达式逐步推算出问题开始的条件,既顺推法的逆过程.? ? ?? ? ? ? ? 顺推实例:题目：兔子的繁殖过程?? ? ? ? ? Java代码描述:? ? ? ? public static void main(String[] args) {int n = 10;System.out.pri...
密码学简介据记载，公元前400年，古希腊人发明了置换密码。1881年世界上的第一个电话保密专利出现。在第二次世界大战期间，德国军方启用“恩尼格玛”密码机，密码学在战争中起着非常重要的作用。随着信息化和数字化社会的发展，人们对信息安全和保密的重要性认识不断提高，于是在1997年，美国国家标准局公布实施了“美国数据加密标准（DES）”，民间力量开始全面介入密码学的研究和应用中，采用的加密算法有DES、RSA、SHA等。随着对...
【120-Triangle（三角形）】【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】原题 Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle[[2],[3,4],[6,5,7],[4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to...
1. 算法一：快速排序算法快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。算法步骤：1 从数列...
本篇为关于模拟退火算法的个人笔记。因为网上的资料不够综合，所以自己写了一份。会根据自己的见解持续更新。名称来源退火指物体逐渐降温冷却的物理现象。温度越低，物体的能量越低，在结晶状态时系统的能量状态到达最低。在自然中，缓慢降温（退火）可以导致结晶，而与之相对的快速降温（淬火）会导致不是最低能态的非晶体形态。该算法的名称借用了这个说法。符号说明$E$ 物体的能量$T$ 物体的温度$k$ 玻尔兹曼常...
写一个系列的经典算法，共同学习！1.快速排序基本思想：1.先从数列中取出一个数作为基准数。2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3.再对左右区间重复第二步，直到各区间只有一个数。在网上看到一篇博客，把快速排序命名为 挖坑填数+分治法，感觉很有道理，所以等会程序就按这两部来写。先说说挖坑填数的思想：1.i=L;j=R; 将基数挖出形成第一个坑a[i].2.j--由后向前找出比它的小的数，找到...
大数乘法：模拟乘法手算累加:和小学生一样竖式计算，逐位相乘，结果相加(很麻烦)改进：先不算任何进位，只保存每一位结果，最后从右到左相加int result[num1.length+num2.length]; //结果不会比俩数长度加起来还长 for(int i=0; i<num1.size(); i++) {for(int j=0; j<num2.size(); j++) { //不考虑进位，先乘了再说result[i+j+1] += num1[i] * num2[j];//+1位给最后最高位进位留空间} }//单独处理进位 for(int k = result.size()-...
LinkSolution随便状压就可以了，设f[S]为答案，g[S]为S的最大独立集点数。对于每个S，枚举其点集内每个点作为p[1]，那么选了这个点之后与其相连的所有点（记作rel[i]）都不能选，是个递归过程。 转移有 \(f_S=\frac{\sum\limits_{i\in S}f_{S-rel[i]}\times [g[S-rel[i]]+1==g[S]]}{|S|}\)Code原文：https://www.cnblogs.com/fruitea/p/12023944.html
该题是求两点间的最短路问题，用Dijkstra算法比较快 ，跑了0.003s 。方法很简单，将圆看成结点，直接判断两个圆是否相交，如果相交距离为0，否则距离为圆心间距离减去两圆半径。 起点和终点也可以看成是一个半径为0的圆 。这样就变成了两点间的最短路问题，适合用Dijkstra算法求解。 比较坑的是该题说了数据范围n最大100，但是我开了105竟然RE ，看成505就过了 。 所以在占用内存不多的情况下还是开大一点好 。细节参见代码：#in...
#include<iostream> usingnamespace std;/*交换排序--冒泡排序 基本思想：在要排序的一组数中，对当前还未排序的全部数，自上而下对相邻的两个数依次进行比较和调整， 让较大的数往下沉淀，较小的数往上冒对冒泡排序法的改进方法是加入一标志性变量exhange，用于标志某一趟排序中是否有数据交换，如果进行某一趟排序 没有进行数据交换，则说明数据已经按要求排列好了，可立即结束排序。//设置一标志性变量pos,用于记录每趟排序中最...
一、图像梯度算法1、图像梯度-Sobel算子 dst = cv2.Sobel(src, ddepth, dx, dy, ksize)ddepth:图像的深度dx和dy分别表示水平和竖直方向ksize是Sobel算子的大小 1# *******************图像梯度算法**********************开始 2import cv23# import numpy as np 4 5 img = cv2.imread(‘pie.png‘,cv2.IMREAD_GRAYSCALE)6 cv2.imshow("img",img)7cv2.waitKey()8cv2.destroyAllWindows()910# 显示图像函数11def cv_show(img,name):...
#include <stdio.h>#include <stdlib.h>#include <string.h>void get_next(char T[100],int *next);int Index_KMP(char S[100],char T[100],int pos);int main(){ int n; char S[100],T[100]; gets(S);//直接用字符串决定了字符数组从0开始而非1 gets(T); n=Index_KMP(S,T,2); printf("%d",n); return 0;}void get_next(char T[100],int *next){ int j,i; int t; next[0]=-1;//因为next函数定义中当...