- 博客(40)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 华为机试3——工程最大利润
华为机试3——工程最大利润题目描述现有若干工程项目，你可以选择最多P项，你有初始资本W。每一个工程 i 有净利润（除去成本）profit_i，但是你选择的工程需要至少有 capital_i 的原始资本。请你选择工程 使得总利润最高，需要注意的是，一个工程只能选择一次。输入第一行输入一个值P第二行输入一个值W第三行输入一行若干个数，用逗号隔开，第 i 个数表示对应第 i 个工程能够获取的净利润；第四行输入一行若干个数，用逗号隔开，第 i 个数表示对应第 i 个工程所需要的资本；输出输出一个
2021-03-18 15:18:05
420
原创 华为机试1——最长子串
华为机试1——最长子串### 题目描述：给定一个字符串String，求取该字符串满足条件的最长子串的长度。条件：该子串中各字符最多出现两次。### 测试用例：输入：abcabcbb输出：6说明：子串abcabc每个字符出现的次数都小于等于2，满足条件且为最长，输出长度6。机试时答题情况：import java.util.Scanner;import java.lang.Math;import java.util.HashMap;public class Main{
2021-03-18 11:12:24
2124
原创 华为机试2——比赛顺序
华为机试2——比赛顺序题目描述有n个人进行1v1的比赛，为增加观赛效果，主办方要求：排名第一的和排名最后的一组、排名第二的和排名倒数第二的一组，以此类推，如n=4，则第一轮比赛应该为(1,4)，(2,3)。其中(1,4)表示1,4比赛的胜利者。要求经过若干轮比赛后，输出最后的获胜者。输入：输入一个n值。（题目保证输入的n值为2的幂次方）；输出：每两测试用例1输入：2输出：(1,2)说明：只有两个人比赛，结果用括号括起来，中间用逗号隔开，表示最终的胜利者；测试用例2输入：4输出：((
2021-03-18 11:11:40
427
3
转载 Java 如何重写对象的 equals 方法和 hashCode 方法
前言前言：Java 对象如果要比较是否相等，则需要重写 equals 方法，同时重写 hashCode 方法，而且 hashCode 方法里面使用质数 31。接下来看看各种为什么。提示：以下是本篇文章正文内容，下面案例可供参考一、需求：对比两个对象是否相等。对于下面的 User 对象，只需姓名和年龄相等则认为是同一个对象。二、解决方案：需要重写对象的 equals 方法和 hashCode 方法package com.yule.user.entity;import org.springf
2021-03-10 23:06:42
205
原创 Android Activity启动方式
Android Activity启动方式android的activity具有以下4种启动模式：standardsingleTopsingleTasksingleInstance默认启动模式是standard我们可以通过在AndroidManifest.xml文件中的activity标签下更改启动方式：android:launchMode="这里填入以上4种方式的一种的名字"如代码所示：<activity android:name=".MainActivity"
2021-03-10 16:10:18
805
原创 Android SQLite数据库基本操作
Android SQLite数据库基本操作android SQLite是Android内置的小型数据库，支持标准的SQL语法，还遵循数据库的ACID事务。SQLite与单独的大型数据库相比更加简单，不需要设置用户和密码。与SharePerences相比 SQLite更加符合关系数据库的模型，能够储存更多更复杂的数据。Android为了让我们能够更加方便地管理数据库，专门提供了一个soL toPenHeere帮助类，借助这个类就可以非常简单地对数据库进行创建和升级。既然有好东西可以直接使用，那我们自然
2021-03-10 15:30:20
778
原创 Python一些有趣的地方 小细节
写在前面最近一个朋友在学编程学py，然后他经常会遇到一些问题来问我怎么办，在这个过程中，我发现了Python有趣的东西（也可能是我水平太菜了不知道），跟其他几门语言不太一样的；今天做一个整理和对比；一、for循环循环变量的固定性Python在for循环过程中，用作循环判断的变量（姑且称之为循环变量，有的称之为索引变量）在循环内部发生改变的时候不会影响到下一次循环；描述很抽象，直接上例子代码：for i in range(0,10): print(i)这样2行很简单的代码，所有与人都知道
2020-05-11 22:16:55
427
原创 Web开发实训——学生信息管理系统（JSP+Servlet+Ajax+MySQL）
Web开发实训——学生信息管理系统（JSP+Servlet+MySQL）核心思路前端HTML页面，构成JSP页面后端Servlet管理后端使用JDBC连接数据库开发环境Dreamweaver CC 2018Eclipse EEMySQL 5.7完成结果实现学生信息管理系统，能够对学生信息进行查看、增加、修改、删除、搜索、排序等功能；不包含任何框架，如JQurry；...
2020-01-09 15:19:52
3364
2
原创 OpenGL绘制任意阶次B样条曲线
OpenGL绘制任意阶次B样条曲线写在前面最近开始新学习OpenGL绘图编程，在学习绘制B样条曲线时，遇到了很多问题，我在CSDN上搜索阅读了基本上所有有关B样条曲线的绘制，但感觉说的都不是很全面，这篇讲了一个点，那一篇又讲了另一个点。而且大部分博客所讲的都是三次均匀B样条曲线的绘制，不太符合我想要的任意阶次的B样条曲线，固定次数也就算了，原理也基本没有讲清楚，都是公式直接往上一套得出答案。因...
2019-11-20 10:34:30
3731
原创 Python爬虫实践——静态网页抓取
Python静态网页抓取最近学习了利用Python爬虫进行静态网页的抓取，并进行一点简单的分析保存。下面是整个学习的过程：实践要求目的访问豆瓣电影Top250的网页https://movie.douban.com/top250，并爬取所有电影的电影名、导演、主演、上映年份、电影分类和评分。并将结果保存到Excel中。爬取过程利用Python中的requests库，可以直接爬取网页的源代码...
2019-09-02 21:17:56
4531
1
原创 贪心算法——最小生成树Kruskal算法
最小生成树Kruskal算法最小生成树（MST）是图论当中一个重要的算法，在实际生活中具有广泛的应用。有多种算法可以解决最小生成树问题，这里介绍Kruskal算法问题描述在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树...
2019-08-27 23:51:26
4578
原创 贪心算法——最短路径问题Dijkstra算法
Dijkstra算法求图的最短路径问题具有很强的现实意义，在实际生活的很多方面都有应用。同时也有很多种算法解决该问题，这里我们讨论Dijkstra算法。问题描述已知加权图G=(V,E)G=(V,E)G=(V,E)，求G（结点和路径组成的)中任意结点之间的最短路径。分析设计解决最短路径问题最常见的有两种算法，Floyd算法和Dijkstra算法。Floyd算法详见博客https://bl...
2019-08-23 23:38:34
17291
1
原创 贪心算法——最小生成树Prim算法
最小生成树Prim算法最小生成树（MST）是图论当中一个重要的算法，在实际生活中具有广泛的应用。有多种算法可以解决最小生成树问题，这里讲解Prim算法。问题描述在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。最小生...
2019-08-22 16:54:53
3581
原创 分支界限——01背包问题
01背包问题背包问题是著名的NP完全问题，在实际生活中有广泛的应用。01背包是背包问题中的一种，也是较简单的一种，有很多种算法可以求解01背包问题，这里介绍利用分支界限的算法。问题描述设有n个物品，他们具有各自的重量w和价值v；给定一个具有一个容量W的背包，求将物品有选择的放入背包中，使得装入的物品的价值之和最大？01背包：物品是完整个体，只存在放或不放两种状态，不能放入一部分。分析设计...
2019-08-21 16:31:34
4678
2
原创 回溯法——图着色问题
图着色问题“四色问题”一直是数学方面一个重要且困难的问题，直到计算机的发明才得以侧面证明，如何求一个图的着色色数，可以通过回溯法来解决。问题描述已知一个图G和m种颜色，在只准使用这m种颜色对G的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢？这个问题称为m-着色判定问题。可对图G着色的最小正整数m，称为图G的色数。分析设计图的表示我们采用二维数组邻接矩阵的形式存储。颜...
2019-08-21 15:24:17
2585
原创 回朔法——n皇后问题
n皇后问题n皇后问题是利用回朔法解决的经典问题之一。问题描述在国际象棋中，皇后的位置很重要，设在n*n的棋盘上要放置n个皇后，使得任意一个皇后都无法直接吃掉其他皇后：任意两个皇后都不能在同一行或同一列或同一斜线上。求满足上述条件的n个皇后的位置。分析设计这个问题如果我们采用暴力穷举的方法甚至是贪心算法的话，4皇后问题就会有1820种情况；8皇后问题就会存在131198072种情况，显然...
2019-08-21 10:39:55
526
原创 动态规划——矩阵连乘问题
矩阵连乘问题矩阵在实际生活中极为重要，但其中的矩阵间乘法的步骤却非常繁琐，当遇到许多个矩阵连乘时，如何减小计算时的代价尤为关键，动态规划可以有效解决该问题。问题描述给定n个矩阵A1，A2……An，且保证Ai能够和Ai+1相乘。由于矩阵乘法满足结合律，可以具有不用的运算顺序，求解使矩阵连乘次数最小的结合律所花费的代价。分析设计已知数学矩阵的定理：若矩阵A的列等于矩阵B的行，则A和B是可...
2019-08-13 17:33:10
1406
原创 动态规划——最优二叉检索树问题
最优二叉检索树问题二叉检索树是二叉树当中经典的应用之一，广泛应用于实际生活的检索当中。如何构建一棵二叉树使得检索时的平均代价最低即构建最优二叉检索树，是一个问题。通过动态规划的思想可以对其进行解决。问题描述给定n个结点，构造一棵二叉检索树，使得检索的代价最低，即最优二叉检索树。分析设计二叉检索树的原理、特点、概念及代价在这里不再论述和证明，默认为已知。要想使二叉检索树的检索代价最低，就...
2019-08-10 21:36:57
1603
1
原创 动态规划——01背包问题
01背包问题背包问题是著名的NP完全问题，在实际生活中有广泛的应用。01背包是背包问题中的一种，也是较简单的一种，利用动态规划的思想可以寻求01背包的解。问题描述设有n个物品，他们具有各自的重量w和价值v；给定一个具有一个容量W的背包，求将物品有选择的放入背包中，使得装入的物品的价值之和最大？01背包：物品是完整个体，只存在放或不放两种状态，不能放入一部分。分析设计动态规划求解问题需要...
2019-08-09 15:39:11
786
原创 动态规划——字符串比对问题
字符串比对问题字符串比对问题是利用动态规划求解的经典问题之一。比对问题在实际生活中应用广发，如DNA串的比对。问题描述给定两个字符串，对其相同字符的程度及位置进行比对。求两个字符串的最小错位程度。错位程度（想要对齐两个字符串的代价）：将两个字符串相同字符对齐在一起，不齐的地方用空格补充；最终无法对齐的部分被称为错位（mismatch），找出两个字符串的最小mismatch。如：字符串...
2019-08-02 16:16:25
2550
原创 动态规划——有向加权图最长路径问题
有向加权图（DAG）最长路径问题有向加权图最长路径问题是图论中一个重要的问题，可以通过动态规划的思想进行解决。问题描述给定一个有向加权无环图G，从G中找出无入度的顶点s，求从s出发到其他顶点的最长路径。下文源代码运行结果参照此图设计分析首先，对于一般的图来说，求最长路径不像求最短路径那样简单，最长路径没有最优子结构。实际上，最长路径属于NP-hard问题。其次，图不能存在环路，如...
2019-08-02 10:13:51
11669
2
原创 动态规划——计算二项式系数问题
计算二项式系数问题二项式是数学中常用的数学式子，动态规划可以很好的解决求解二项式的结果。问题描述已知在n个元素集合中挑选出k(0≤k≤n0\leq k \leq n0≤k≤n)个元素组合的数量，记作C(n,k)C(n, k)C(n,k)，或CnkC_n^kCnk。已知二项式系数有如下性质、关系：(a+b)n=Cn0an+Cn1an−1b+...+Cnian−ibi+...+Cnnbn...
2019-08-01 21:47:56
2104
原创 动态规划——最短路径问题Floyd算法
Floyd算法Floyd算法是求加权图最短路径的经典算法之一，利用了动态规划的思想解决。算法描述最短路径问题：设有一加权图G，从G中某个顶点出发达到另一个顶点，所经过边的权值之和最小的路径，被称为最短路径。Floyd算法是解决加权图（图可以是有向也可以是无向，可以存在负权）中任意两点之间的最单路径的一种算法。基本思路：通过Floyd算法计算最短路径时，图一般采用二维数组，邻接矩阵的...
2019-08-01 19:20:59
5378
原创 动态规划——多段图问题
多段图问题多段图问题是利用动态规划思想解决的经典问题之一，在日常生活中应用广泛。问题描述若存在一个有向加权图G，且G能分出起点和终点以及中间的n的阶段，求起点到终点的最短（长）距离。分析设计通过上图我们可以很容易知道，如果用穷举的方法是没有办法求解的，问题规模实在太大，我们需要使用其他更为高效的算法：动态规划。动态规划解决该问题的主要思想：n个阶段的大问题很难求解，可以将其进行划分成...
2019-08-01 11:04:55
11624
原创 分治法——最近点对问题
最近点对问题最近点对问题是利用分治法解决的经典问题之一。问题描述设在一个点集S中存在n个点，找出距离最相近的一对点p1和p2，最近点对可能不止一对，输出一对即可。分析设计在n个点中找出距离最近的一对点，我们首先可以想到的方法就是暴力穷举的方法：遍历整个点集，计算每一对点之间的距离d，就能找出最短距离dmin。显然这样的方法时间复杂度为O(n2),时间复杂度太高，若问题规模较大，穷举的算...
2019-07-31 16:18:03
3129
1
原创 分治法——k小元素问题
求第k小元素问题k小元素问题是利用分治法进行求解的经典问题之一。问题描述已知一个长度为n的数组，返回数组中的第k小的元素。分析设计要想找出第k小的元素，我们首先想到的方法肯定是先将数组进行排序，返回第k个元素即可，然而利用排序的方法求解时间复杂度至少为O(nlogn)，是否存在一种算法使得时间复杂度为O(n)？分治法当数组长度，即问题规模很大时，分治法是一种很好的算法解决该问题。当问...
2019-07-31 09:48:29
10927
4
原创 分治法——循环日程赛问题
循环日程赛问题循环日程赛是利用分治法解决的经典问题之一。问题描述设有n = 2k 个选手参加比赛，要求设计一个日程赛安排表，满足：每个选手都与其他n-1个选手各自比赛一次；每个选手每天只比赛一次；比赛进行n-1天。设计分析设计日程赛安排表可以用一个n行n-1列的二维数组来表示，a[i][j]即表示第i个选手在第j天遇到的对手。要想利用分治法解决该问题，就必须将整个问题进行划分...
2019-07-30 23:24:13
2136
原创 RSA加密算法及一般攻击方式
RSA算法RSA公钥加密算法是RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。1987年7月首次在美国公布，当时他们三人都在麻省理工学院工作实习。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数...
2019-07-24 09:29:44
15272
1
原创 排序算法比较、总结
各种排序算法的比较与总结排序算法是算法中一种最为基础、普遍的算法，在实际生活中应用广泛。针对不同的数据类型，特点，选择合适的排序的算法能够获得很高的程序效率。经过这几天对各个排序算法的学习，复习，现在对其进行比较和总结。常见的10种排序算法详见：快速排序插入排序归并排序冒泡排序选择排序堆排序希尔排序计数排序桶排序基数排序各种排序算法的比较排序算法最优时间复...
2019-07-22 21:57:24
163
原创 排序算法——希尔排序
希尔排序希尔排序是插入排序的一种，但它是普通插入排序经过一定改进后的一种更为高效的算法，也被成为缩小增量排序。希尔排序的主要思想：通过记录待排序列下标的增量进行分组，对每一个子序列采用插入排序，不断减少增量，当增量为1时2，整个序列被分为一组，即已经被排好。希尔排序算法的时间复杂度为O(n^2)。伪代码SHELLSORT(A) d=A.length do d = d/2 ...
2019-07-22 16:39:16
409
原创 排序算法——基数排序
基数排序基数排序与桶排序非常容易混淆，他也是通过桶来排序，不同的是，基数排序的过程与桶排序有所不同，且只需要0-9号10个桶即可。基数排序的主要思想：将待排序列从低位开始排序，放入对应桶中，得到第一次子序列，再把这个子序列根据十位放入桶中，再得到子序列，以此循环，直至排完最高位，即得到最终的排序序列。根据序列从高位开始拍，或从低位开始拍，基数排序又分为：LSD——从低位开始MSD——从高...
2019-07-21 15:33:00
1646
1
原创 排序算法——桶排序
桶排序桶排序又称箱排序，其主要思想近乎分治法的思想。其原理是：讲待排序列（集合）中的元素分到数量有限的桶中，每个桶在进行排序。桶排序不属于比较排序的一种，因此不受排序算法时间复杂度下限nlogn的限制。桶排序算法的时间复杂度为O(n)。是所有排序算法中最快的，但桶排序的空间复杂度也对应较高，是以空间换时间的排序算法。同时，需要注意的是，桶排序对数据进行了一定的要求和限制，并不是所有情况下都能...
2019-07-20 17:24:06
1790
原创 排序算法——计数排序
计数排序计数排序是一种基于分配而非基于比较的排序算法，因此不受比较排序时间复杂度下限nlogn的限制。其主要思想是：对于一个待排序列中的任意一个元素，只要确定了有多少个小于该元素的值，即可确定该元素的位置。例如，要找出待排序列中x的位置，且该序列中只有6个元素小于x，则x的位置即为7。计数排序对待排序列的数据有一定的要求：待排序列中的元素必须为自然数。计数排序算法时间复杂度为O(n+k),...
2019-07-16 15:16:07
218
原创 排序算法——堆排序
堆排序堆排序是通过堆这种特殊的数据结构进行排序的一种排序算法。堆：由完全二叉树构成，且具有一定的大小关系；二叉树根为最小值的堆被称为小顶堆，反之，根节点为最大元素的堆被称为大顶堆。对于一个堆，按层进行编号，根节点为0号，依次往下编号，对应于一个序列（集合）的下标。堆的两个重要性质：1、结点i的父节点为i/2；2、结点i的左子节点为2i，右子节点为2i+1。堆排序的基本思想是：设给待排...
2019-07-14 22:30:33
698
原创 排序算法——选择排序
选择排序选择排序是一种非常直观的排序方法。其原理是：对于一个待排序列，每一次从其中选出最大（小）的元素，存放在序列的起始位置，直至整个序列全部排序完成。选择排序与插入排序的思考方向正好相反，选择排序是对于固定位置，找对应元素；插入排序是对于固定某一元素，找对应位置。方法不同，但结果都是一样的。选择排序算法时间复杂度为O(n^2)。伪代码SELECTIONSORT(A) for j = ...
2019-07-14 16:59:02
186
原创 排序算法——冒泡排序
冒泡排序冒泡排序是一种简答的排序方法，其模拟了较大的数会慢慢“浮”到最开始一端（或慢慢“沉”到结尾的一端）。其基本原理是：比较相邻的两个数，如果前一个比后一个大，则交换这两个元素。一轮排序过后，就能找出该序列中最大（小）的数，且放在了正确的位置。不断循环，找出第二大的数，第三大的数······，直到整个数组遍历完没有任何一对元素需要交换。冒泡排序算法的时间复杂度为O(n^2)。伪代码BU...
2019-07-14 16:06:16
158
原创 排序算法——归并排序
归并排序其基本思想是：对于两个有序序列（集合），将其融合在一起得到一个新的有序序列，又被称为二路归并。因此，归并排序的过程就是：首先将一个待排序列不断划分，划分为原来的一半，直至子序列只有一个元素为止，此时，每一个子序列只有一个元素，也就是每个子序列都是有序的。这个过程被称为分。再将子序列对应融合，按照一定的大小顺序合并在一起，最终得到有序序列，这个过程被称为合。归并排序是分治法的经典问题。...
2019-07-14 10:44:41
256
原创 排序算法——插入排序
插入排序其基本思想是：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序。即将一个元素插入到已排好序的序列中，从而得到一个新的排好序的序列，完成排序。对于一个待排序列A，构造一个与之长度相等的空序列B作为排序序列，将A中的每一个元素依次插入到B中，通过与B中元素比较大小来确定该元素的位置。插入排序和冒泡排序较为类似。插入排序算法时间复杂度为O...
2019-07-13 18:07:22
174
原创 排序算法——快速排序
快速排序其基本思想是：通过一趟排序，将整个待排序列分为两部分：1、该部分所有数都小于等于整个序列的某一个元素；2、该部分所有数都大于整个序列的某一个元素。改元素被称为哨兵位。然后按照此方法再对两部分子序列进行快速排序，直至整个序列达到有序为止。很明显，该算法可以用递归的思想实现。每一趟排序的过程叫做PARTITION：每次选取序列的第一个元素作为哨兵位；两个指针分别指向待排序列的首和尾；通过比...
2019-07-13 16:11:22
148
原创 二分查找&三分查找
二分查找&三分查找二分查找（折半查找）是查找算法中一种有效的算法：输入一个有序序列（数组）和一个元素，如果该元素包含在改有序序列中，则返回其位置，若不存在，则返回**-1**（或NULL）。二分查找的原理：对于一个有序序列，每次选择中间的那个元素，与欲找出的元素进行比较，若比该元素大，则查找范围变为序列的前一半；反之，若中位元素比查找元素小，则将下一次的查找范围变为序列的后一半；若中位...
2019-07-12 21:37:11
4349
Web开发实训——学生信息管理系统（JSP+Servlet+Ajax+MySQL）
2020-01-09
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人