On the way

Java 容器

《Thinking in Java》11章数组相同类型的，用一个标识符名称封装到一起的一个对象序列或者基本类型数据序列，可以通过方括号 [] 访问。 java的主要目标之一就是安全，所以不会有数组越界访问，并且数组都会被初始化。和其他容器的区别？数组需要设置大小，而其他容器类不需要。数组可以保存基本数据类型，其他容器类只能保存对象。定义： int[] a; // 这...

Posted by Xsp on January 7, 2018

快速排序

#include <iostream> #include <vector> #include <time.h> using namespace std; void Swap(int &s, int &t) { int tmp = s; s = t; t = tmp; } int Partition(vector...

Posted by Xsp on December 18, 2017

改进的归并排序

采用链表的形式，避免数组元素的频繁交换。 #include <iostream> #include <vector> #include <time.h> using namespace std; int InSort(vector<int>& A, vector<int>& Link, int low, int h...

Posted by Xsp on December 18, 2017

01背包问题求解

动态规划（dp解法只能求出一个解？）参照《算法竞赛入门经典》P169的图画的？考虑到空间复杂度为，如果物品的重量分布比较稀疏，比如就两个物品，重量为{1, 10000}, 则以上的解法二维数组会造成很大的空间浪费。优化如下：回溯法深度优先+剪枝（暴力求解+剪枝？）分枝限界法广度优先搜索+剪枝

Posted by Xsp on November 27, 2017

单源最短路径问题

关于图的单源最短路径的C++ 实现，以POJ 2387:Til the Cows Come Home 为例AC。其他练习：leetcode 743 network-delay-time Bellman-Ford算法思路：对每条边进行松弛，每松弛一次，相当于更改了一次该结点的父亲结点，所以总共最多松弛 V-1 次。可以有负边。其他：Bellman-Ford感觉和 Kruskal有点...

Posted by Xsp on October 31, 2017

Java概述

《Java 核心技术卷1》10th 学习笔记 Java是强类型、静态类型语言。弱类型、强类型、动态类型、静态类型语言的区别是什么？第二章环境一些缩写 JDK(Java Development Kit, Java开发工具包): 编写Java程序的程序员使用的软件。 JRE(Java Runtime Environment, Java运行时环境): 运行Java程序的用户所使用...

Posted by Xsp on September 9, 2017

凸包算法

定义凸包是包所有点的最小的凸状集合葛立恒（Graham）扫描法以逆时针/左转的方式穿过凸包选择y轴坐标最小的点（最低点）作为p点，即扫描的起始点，会发现从p点到其他每个点的向量的极角值递增。难点：如何找到最低点？对y坐标排序如何根据极角大小排序，以及如何比较这些点？如何判断两点间是否是逆时针旋转？计算凸包的主要部分就是排序。有一个好的排序...

Posted by Xsp on August 1, 2017

并查集

coursera课程笔记解决算法的一个步骤：问题建模，找到解决算法（可以使暴力解）。时间复杂度？空间复杂度？原因？（可以考虑用空间换时间，用时间换空间）优化注意边界条件（空值，极大/小值）关于并查集 - 维基百科主要有两个操作： Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union：将两个子集合并成同一个集...

Posted by Xsp on June 23, 2017

C++ struct 和 class的区别

struct是C原有的，C++为了兼容C而支持了struct。什么时候该用struct或者class没有明确的界限。语法角度的区别：默认继承权限不同。class是private，struct是public。成员的默认访问权限不同。class是private，struct是public。 struct不能作为模板参数，class可以。（这个有点不懂，为啥那个map的自...

Posted by Xsp on June 14, 2017

C++随机数

通过简单的C库函数rand来生成随机数，此函数生成均匀分布的伪随机数，每个随机数的范围在0和一个系统相关的最大值（至少为32767）之间（最大值是多少？INT_MAX？）首先初始化随机数种子，使程序每次运行时生成不同的随机序列。因为rand() 的范围是0~max，所以通过取余的方式来获取需要的范围内的随机数 srand(time(NULL)); rand() % 100; 其他：...

Posted by Xsp on June 14, 2017