- 博客(43)
- 收藏
- 关注
RSS订阅原创 汉诺塔
汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。 问应该如何操作？从图中可以看出A柱上的N圆盘是最大的，又因为小圆盘上不能有大圆盘，大圆盘上可以放小圆盘。所以N圆盘上可以放其他所有的任意圆盘，这样的话我们完全.
2021-03-30 19:39:30
716
1
原创 Flink学习（二）
WindowFlink处理的流式数据是指一种不断增长的本质上无限的数据集，而 window 是一种切割无限数据为有限块进行处理的手段。Window 是无限数据流处理的核心，Window 将一个无限的 stream 拆分成有限大小的”buckets”桶，我们可以在这些桶上做计算操作。切割拆分的时候有两种拆分方法，一种是按数据集大小拆分，即按数量拆分CountWindow。还有一种是按照时间划分区间TimeWindow。对于 TimeWindow，可以根据窗口实现原理的不同分成三类：滚动窗口（Tumbli
2021-03-09 20:31:04
354
原创 Flink学习笔记（一）
什么是FlinkApache Flink是由Apache软件基金会开发的开源流处理框架，其核心是用Java和Scala编写的分布式流数据流引擎Flink可以做什么Flink以数据并行和流水线方式执行任意流数据程序，Flink的流水线运行时系统可以执行批处理和流处理程序。此外，Flink的运行时本身也支持迭代算法的执行。实时推荐系统实时报表实时数仓与ETL实时欺诈与实时信用评估大数据安全监测等等目前，阿里巴巴、腾讯、美团、华为、滴滴出行、携程、饿了么、爱奇艺、有赞、唯品会等大厂都已经将
2021-03-09 16:55:31
228
原创 SparkML（五）
聚类k-means算法k-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据它们的属性分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。k-means算法的基本过程如下所示：任意选择k个初始中心c1,c2,…,ckc{1},c{2},…,c_{k}c1,c2,…,ck 。计算X中的每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；重新计算每个中心对象CiC_{i}Ci的值计算标准测度函数，当满足一
2021-02-10 16:11:41
193
1
原创 SparkML（四）
回归回归问题其实就是求解一堆自变量与因变量之间一种几何关系，这种关系可以是线性的就是线性回归，可以是非线性的就是非线性回归。按照自变量的多少有可以分为一元线性回归，多元线性回归。线性回归线性回归，顾名思义拟合出来的预测函数是一条直线，数学表达如下：h(x)=a0+a1x1+a2x2+…+anxn+J(θ)其中 h(x)为预测函数， ai(i=1,2,…,n）为估计参数，模型训练的目的就是计算出这些参数的值。而线性回归分析的整个过程可以简单描述为如下三个步骤：寻找合适的预测函数，即上文中的h(x
2021-02-10 15:41:58
545
原创 SparkML（三）
分类逻辑回归在spark官方文档中，逻辑回归又分为二项式逻辑回归和多项式逻辑回归。逻辑回归本质是线性回归，只是在特征到结果的过程上加上了一层映射。即首先需要把特征进行求和，然后将求和后的结果应用于一个g(z)函数,g(z)可以将值映射到0或者是1上面，这个函数就是Sigmoid函数，默认分类的值是0.5，超过0.5则类别为1，小于0.5类别为0。如下图例子import org.apache.spark.ml.classification.LogisticRegression// Load t
2021-02-09 15:52:37
417
原创 SparkML（二）
有监督学习概念：通过已有的训练样本去训练得到一个最优模型，再利用这个模型将所有的输入映射为相应的输出，对输出进行简单的判断从而实现预测和分类的目的，也就具有了对未知数据进行预测和分类的能力。简单来说，就像有标准答案的练习题，然后再去考试，相比没有答案的练习题然后去考试准确率更高。监督学习中的数据中是提前做好了分类信息的， 它的训练样本中是同时包含有特征和标签信息的，因此根据这些来得到相应的输出。有监督算法常见的有：线性回归算法、BP神经网络算法、决策树、支持向量机、KNN等。分类和回归有监督分为分
2021-02-08 15:02:51
163
原创 SparkML（一）
什么是机器学习百度：机器学习是一门多学科交叉专业，涵盖概率论知识，统计学知识，近似理论知识和复杂算法知识，使用计算机作为工具并致力于真实实时的模拟人类学习方式，并将现有内容进行知识结构划分来有效提高学习效率。在我看来机器学习就是给你的计算机一套逻辑（建模训练），让他根据这套逻辑去对数据进行处理（测试）。Spark MLSpark MLlib是Spark的机器学习（ML）库。它的目标是使实用的机器学习可扩展且容易数据处理spark ML有2种类型局部向量：dense和sparse。 稠
2021-02-08 12:51:57
2027
原创 SQL优化（三）
group bygroup by一般分两种，一种是使用索引分组（又有松散的索引扫描和紧凑的索引扫描两种），一种使用临时表分组。其中走索引的分组时间消耗会小的多，所以我们应该尽量让sql走索引。在MySQL8之前，分组默认是排序的，8之后不在排序。索引分组使用索引分组又有两种，分别是松散的索引扫描和紧凑的索引扫描。在索引中的列是已经按照索引的顺序进行分组的数据。松散的索引扫描根据group by后面的列取出索引中对应的列，再根据where条件进行筛选。紧凑的索引扫描先根据where条件进行筛
2020-12-14 11:33:50
80
原创 SQL优化（二）
order by排序方式一般分两种，在索引中排序（索引里面数据有序），在内存中排序（内存不够的话会产生临时文件辅助排序）。其中走索引的排序会快很多。索引排序既然我们知道排序走索引会快很多，那我们排序时应该尽量让排序走索引。那什么情况下排序会走索引呢？我们知道查询排序语句一般由这几个部分构成：select +where+order by+limit…等等。所以SQL走不走索引主要由这几部分的限制决定。...
2020-12-13 16:06:37
81
原创 SQL优化（一）
减少select *的使用select * 会增加网络IO压力，查询时间，内存等等。因为select* 是查询所有列，MySQL会把查到所有列发送给客户机，如果查询无用列增多，会增加网络IO的压力。Joinjoin可以看做是两个表做循环 ，表A为驱动表，表B为被驱动表。扫描将表A的数据循环一遍，每一条表A的数据都和表B所有数据进行链接。驱动表选择结果集少的小表一趟for循环的代价+大表上使用B+树索引的代价<大表一趟for循环的代价+小表使用B+树索引的代价如果表A有10条数据，表B有2
2020-12-03 21:10:41
124
原创 虚拟机非正常关机导致不能启动
状态1打开虚拟机一直黑屏，关闭提示该虚拟机繁忙。解决办法：用管理员身份调出cmd输入netsh winsock reset重启电脑状态2解决办法问题是虚拟机在运行的时候，会锁定你的虚拟机的文件，防止系统被更改，如果系统突然崩溃了的话，那么虚拟机没法给已经锁定的文件解锁，那么在启动的时候就没法使用虚拟机。找到虚拟机所在的文件夹，删除所有以.lck结尾的文件。注意，在一个虚拟机里面可能有1多个lck文件。删除之后再尝试开虚拟机即可...
2020-12-02 20:19:20
717
原创 建造者模式-23种设计模式系列
介绍定义： 将一个复杂的对象与他的表示分离，使同样的构建过程可以创建不同的表示主要作用： 在用户不知道创建过程和细节的情况下就可以直接创建复杂的对象。何时使用： 一些基本部件不会变，而其组合经常变化的时候。如何解决： 将变与不变分离开。关键代码： 建造者：创建和提供实例，导演：管理建造出来的实例的依赖关系。应用实例： 1、去肯德基，汉堡、可乐、薯条、炸鸡翅等是不变的，而其组合是经常变化的，生成出所谓的"套餐"。 2、JAVA 中的 StringBuilder。优点：产品的建造和表示分离，实
2020-06-07 23:07:05
203
原创 工厂模式-23种设计模式系列
什么是工厂模式？定义： 工厂模式又称为创建模式，它是建对象的一种最佳方式。工厂模式的本质就是用工厂方法代替new操作创建一种实例化对象的方式。一句话中总结就是方便创建 同种类型接口产品 的 复杂对象。核心：实现了创建者和调用者分离实例对象不用new，而用工厂方法代替将选择实现类，创建对象统一管理和控制。从而将调用者和我们的实现类解耦三种模式：简单工厂模式：用来生产同一等级结构的任意商品（对于增加新的商品，需要修改已有代码）工厂方法模式：用来生产同一等级结构中固定商品（支持增加任意产品）
2020-06-03 17:54:24
439
原创 PTA 7-2 旅游规划
题目描述有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、
2020-05-24 05:58:54
477
原创 PTA 7-1 哈利·波特的考试
题目描述哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。
2020-05-23 09:42:23
4362
原创 单例模式-23种设计模式系列
什么是单例模式单例模式（Singleton Pattern）是 Java 中最简单的设计模式之一。这种类型的设计模式属于创建型模式，它提供了一种创建对象的最佳方式。这种模式涉及到一个单一的类，该类负责创建自己的对象，同时确保只有单个对象被创建。这个类提供了一种访问其唯一的对象的方式，可以直接访问，不需要实例化该类的对象。注意：1、单例类只能有一个实例。2、单例类必须自己创建自己的唯一实例...
2020-05-04 20:09:05
221
原创 PTA 7-1 修理牧场
题目描述农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，...
2020-05-02 23:06:20
3713
原创 PTA 7-1 平衡二叉树的根
题目描述将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。输入格式:输入的第一行给出一个正整数N（≤20），随后一行给出N个不同的整数，其间以空格分隔。输出格式:在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。输入样例1:588 70 61 96 120输出样例1:70输入样例2:788 70 61 96 12...
2020-04-23 17:47:30
6377
5
原创 PTA 6-11 二叉树的非递归遍历 (25分)
本题要求用非递归的方法实现对给定二叉树的 3 种遍历。函数接口定义：void InorderTraversal( BinTree BT );void PreorderTraversal( BinTree BT );void PostorderTraversal( BinTree BT );其中BinTree结构定义如下：typedef struct TNode *Position...
2020-04-20 19:01:03
4636
原创 线索二叉树
二叉树线索化的原理二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息n个节点的二叉树中含有n+1个空指针域。利用二叉树中的空指针域 来存放在某种遍历次序下的...
2020-04-11 17:29:06
459
原创 二叉树交换子树
题目描述以二叉链表作为存储结构，编写算法交换二叉树每个结点的左孩子和右孩子。思路分析设置两个临时树初始化为NULL，用来保管左右子树，随后将原树的左右子树等于NULL，再把保存左子树的临时树放到右子树上，保存右子树的临时树放到左子树上，最后递归交换每一个左右子树。源代码BinTree LeftToRight(BinTree BT){ BinTree BL=NULL,BR=NULL...
2020-04-10 21:52:24
714
原创 PTA 7-4 列出叶结点
题目描述对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。输入格式：首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-”。编号间以 1 个空格分隔。输出格式：在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多...
2020-04-09 11:57:44
3834
原创 PTA 7-3 树的遍历
题目描述给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式：在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。输入样例：72 3 1 5 7 6 41 2 3 ...
2020-04-09 11:17:46
2832
2
原创 二叉树的四种遍历函数
二叉树二叉树结构定义如下typedef struct TNode *Position;typedef Position BinTree;struct TNode{ ElementType Data; BinTree Left; BinTree Right;};四种遍历方式分别是 中序，先序，后序，层序。具体例子如下：二叉树图解：四种遍历输出：Inor...
2020-04-04 20:19:39
1216
原创 KMP算法
引入学习一个算法要先知道它是什么，KMP算法是一种改进的字符串匹配算法。那么之前我用什么做字符串匹配呢？暴力破解，一直DF。假设主串是ababababca,模式串是abababca。DF算法（暴力匹配）让模式串和主串从第一个开始匹配，如果相同，就接着比较后面的，如果不同模式串下标回到0，主串下标回到第一个匹配的位置的下一个接着比较。算法复杂度最后为 O(m*n)KMP算法KMP...
2020-03-29 17:07:05
1242
原创 Scala和Java详细对比
Scala是什么百度百科：Scala是一门多范式的编程语言，一种类似java的编程语言 ，设计初衷是实现可伸缩的语言 、并集成面向对象编程和函数式编程的各种特性。我的理解：Scala是java的强化版，也是基于jvm的编程语言，可以直接调用所有java的库资源，同时其具备函数式编程的特性以及脚本语言的特性，语法更加简洁，功能更加强大相比java的优点优雅：这是框架设计师第一个要考虑...
2020-03-17 16:34:21
2072
原创 PTA 7-3 银行排队问题之单队列多窗口服务
题目描述假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。输入格式:输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾...
2020-03-17 00:26:28
10199
2
原创 PTA 7-4 列车调度
题目描述火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？输入格式：输入第一行给出一...
2020-03-15 20:52:04
1465
2
原创 PTA 7-5 括号匹配
题目描述给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。输入格式:输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。输出格式:如果括号配对，输出yes，否则输出no。输入样例1:sin(10+20)输出样例1:yes输入样例2:{[}]输出样例2...
2020-03-15 17:37:23
4750
1
原创 PTA 7-6 出栈序列的合法性
题目描述给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, …, N 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M=5、N=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。输入格式：输入第一行给出 3 个不超过 1000 的正整数：M（堆栈最大容量）、N（入栈元素个数...
2020-03-15 16:42:17
13077
6
原创 一个数组空间存两个栈
题目描述思路分析定义两个指针，一个在最后，一个在最开始同时向中间指。栈满就说明数组空间满了，头指针挨着尾指针了。太简单了，主要是给女朋友讲的源代码#include <stdio.h>#include <stdlib.h>#define max 100typedef struct{ char date[max]; int top1...
2020-03-13 19:11:54
197
原创 后缀表达式求值
问题描述输入一个后缀表达式，求出改表达式的最终结果。输入格式在一行中输入后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。输入格式先输出输入的后缀表达式，再输入=和最终结果。输入样例2 3 7 4 - * + 8 4 / +输出样例2 3 7 4 - * + 8 4 / +=13思路分析这个题需要用到堆栈思想，我使用一个顺序数组表示。先将输...
2020-03-12 20:50:00
1519
1
原创 PTA 习题3.11 表达式转换
题目描述算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。输入格式在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。...
2020-03-12 20:15:07
2749
1
原创 找链表最小值，并判断奇偶，对链表进行不同操作
题目描述设有一一个由正整数组成的无序单链表,编写算法实现下列功能:1.找出最小值结点，且显示该数值。2.若该数值为奇数,则将其与直接后继结点的数值交换。3.若为偶数，则将其直接后继结点删除。输入57 5 4 8 657 5 3 8 6输出最小值为：47 5 4 6最小值为：37 5 8 3 6解题思路在链表结构体中存两个值，一个为下标，一个为对应的值。一开始...
2020-03-06 20:49:49
1397
原创 单链表逆转
题目描述设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。输入51 2 3 4 5输出5 4 3 2 1解题思路由于规定了算法复杂度，而且不能再申请空间，所以只能在原链表上操作。先把原链表的值一个一个取出来后，用前插法插入原链表即可。前插法源代码#include <stdio.h>#include <stdlib.h&...
2020-03-06 20:34:08
765
原创 多项式的表示及相加
问题描述数据结构（C语言）用单链表存储一元多项式，并实现两个多项式的相加运算基本要求（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，……，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；（3）多项式a和b相加，建立多项式a+b。思路分析由于多项式有指数和系数，所以结构体中应该定义三个值：指数，系数，n...
2020-03-06 16:42:26
1072
原创 约瑟夫环
[问题描述]约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。[基本要求]利用单...
2020-03-06 16:22:18
819
原创 PTA 两个有序序列的中位数（详解）
问题描述已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即[(N+1)/2]个数（A0为第1个数）。输入格式:输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。输出格式:在一行中输出两个输入序列的并...
2020-03-02 21:20:55
9655
7
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人