qq_40143611的博客

原创 学生信息

中山大学软件工程 15级 林润清 15331203

原创 课程学习自我总结

通过这次项目开发，我们组把课程中学习到的一些对项目的管理知识用到了实践中。在分析阶段，我们小组进行了需求分析，画出UML图，撰写接口文档，设计规范；在开发阶段，我们编写代码，进行测试。这使我们对软件开发有了一个粗浅的认识，而不是只停留在理论上。在这门课程的大作业中，作为团队中的测试成员，我没有参与到项目的前端和后端管理和开发。我主要参与了分析商家需求，数据库模型的分析、设计和建立，绘制了数据库...

原创 系统分析与设计 第九次作业

使用 ECB 实现 make reservation 用例的详细设计（包含用例简介，顺序图，类图）利用课程上的酒店订房的例子，画出用例图得到顺序图设计类图包图...

原创 系统分析与设计 第八次作业

描述软件架构与框架之间的区别与联系    区别软件架构：软件架构描述的对象是直接构成系统的抽象组件以及各个组件之间的连接，这些连接明确和相对细致地描述组件之间的通讯。在实现阶段，这些抽象组件被细化为实际的组件，比如具体某个类或者对象，组件之间的连接通常用接口来实现。软件框架：​软件框架描述了该领域的共性部分，并提供了一些定义良好的可变点以保证灵活性和可扩展性。软件框架是领域分析结果的软件化...

原创 系统分析与设计 第七次作业

原创 系统分析与设计第五次作业

一.领域建模a.阅读 Asg_RH 文档，按用例构建领域模型。 按 Task2 要求，请使用工具 UMLet，截图格式务必是 png 并控制尺寸 说明：请不要受 PCMEF 层次结构影响。你需要识别实体（E）和 中介实体（M，也称状态实体） 在单页面应用（如 vue）中，E 一般与数据库构建有关， M 一般与 store 模式 有关 在 java web 应用中，E 一般与数据...

原创 系统分析与设计 第六次作业

1）使用 UML State Model建模对象： 参考 Asg_RH 文档， 对 Reservation/Order 对象建模。建模要求： 参考练习不能提供足够信息帮助你对订单对象建模，请参考现在 定旅馆 的旅游网站，尽可能分析围绕订单发生的各种情况，直到订单通过销售事件（柜台销售）结束订单。2）研究淘宝退货流程活动图，对退货业务对象状态建模...

原创 系统分析与设计 第四次作业

一、用例建模1. 阅读 Asg_RH 文档，绘制用例图。 按 Task1 要求，请使用工具 UMLet，截图格式务必是 png 并控制尺寸2. 选择你熟悉的定旅馆在线服务系统（或移动 APP），如绘制用例图。3. 对比两个时代、不同地区产品的用例图，总结在项目早期，发现创新的思路与方法从两个例子的对比中，不难发现新时代的预订系统功能更加丰富，为客户提供了更多的预订信息，帮助客户更容易地筛选出合适...

原创 系统分析与设计——第三次作业

Tensorflow 布置一个CNN网络周三晚上面试，周四开始填坑。。。。。。。。。。。。。

原创 系统分析与设计——第二次作业

简述瀑布模型、增量模型、螺旋模型（含原型方法）的优缺点。瀑布模型优点：1.降低软件开发的复杂程度，提高软件开发过程的透明性，提高软件开发过程的可管理性                        2.推迟软件实现，强调在软件实现前必须进行分析和设计工作                        3.以项目的阶段评审和文档控制为手段有效地对整个开发过程进行指导，保证了阶段之间的正确衔接，能够及...

原创 系统分析与设计——第一次作业

软件工程的定义：将系统化的、规范的、可度量的方法用于软件的开发、运行和维护的过程，即将工程化应用于软件开发中。阅读经典名著“人月神话”等资料，解释 software crisis、COCOMO 模型：software crisis指的是随着计算机性能的急剧上升以及待解决问题的复杂度的增加，在规定时间内编写出可用并且高效的软件出现了很大的困难。随着软件复杂性的增加，现有的方法是不足以应对，导致许多软...

原创 547. Friend Circles 【Medium】 并查集

题目：给出N个学生之间是朋友的邻接矩阵，互为朋友的学生之间组成一个朋友圈，求出朋友圈的数量。思路：就是要把N个学生划分到不同的集合中，集合中的人互相直接或间接是好朋友。若用DFS的办法来做，划分学生的过程可能复杂度会比较高。这里采用了并查集的做法。初始时，每个节点自成一个集合。然后对N个节点的任意两个节点都要进行合并。每次合并两个节点x,y之前，先把x和y自身的先继和他们的先继节点

原创 743. Network Delay Time【Medium】 最短路径

题目：给出网络中各点之间的网络延迟（即距离），算出从某个点发出的信号所有点都收到的延迟。思路：用迪杰斯特拉算法，求出网络中的所有点到当前点的最短路径，找出最大值就是答案。算法不难但是照着书来打，实现起来还是挺麻烦的。#define INFINITY 9999999class Solution {public: int pos_min(vector& dis, vector

原创 315. Count of Smaller Numbers After Self 【Hard】 分治？

题目：给一个数组nums，求每一个nums元素的右手边比它小的元素的个数思路：用一个数组pos给nums排序——把nums从右边的元素开始，一个个有序地插入到pos中，该元素的位置就是该元素在nums中右手边比它小的元素的个数。看博客才会的。class Solution {public: vector countSmaller(vector& nums) { i

原创 5. Longest Palindromic Substring 【Medium】 区间动归

题目：求一个字符串s的最长回文子串思路：动归解决，dp为一个二维数组，dp[i][j]表示s的第i到第j是否为回文串，若是则为长度此回文串长度（即i-j），若不是则为0状态转移方程：1.i=j则dp[i][j]=12.i=j-1则判断s[i]和s[j]是否相同，相同则dp[i][j]=2，否则dp[i][j]=03.i0，若是则dp[i][j]=j - i，否则dp[i][j]

原创 《算法设计》第8.8题 证明4SAT是NP-C问题

证明：1.首先证明4SAT是NP问题：假设现在有一个包含N个变量，M个子句的4SAT实例INS和一个变量的赋值ASS，当把这个ASS应用上去后，显然是可以在多项式时间内知道这个ASS能不能满足INS为真的。所以4SAT是NP问题。2.证明4SAT是NP-C问题。一个办法是用3SAT问题规约为4SAT问题。假设现在有一个3SAT的实例INS3，那么转化的4SAT的实例INS4可以

原创 650. 2 Keys Keyboard【Medium】可能是数学题

题目：屏幕上初始只有一个‘A‘字符，每一步操作可以：1.复制全屏字符串。2.粘贴。求得到N个‘A’的最小操作次数。思路：很自然地想到应该要得到N的因子，因为到N个A必须要先得到N的某个约数个'A'，然后再复制粘贴。先找到N的全部因子存在factors里，然后发现，不管从哪个因子开始，其操作次数都是该因子。比如，10有2个因子——2和5。从1到2要2次，从2到10要5次；从1到5要5次，

原创 740. Delete and Earn【Medium】 动归

题目：给一个数组nums，每次可以删除第i个数nums[i]，得到nums[i]分，但是同时必须把nums[i]+1和nums[i]-1的数也全部删去。问最多可以拿多少分。思路：和期中考试很像，就是相邻的数不能同时取，同一个数可以全部取得的问题。先把所有数组中相同的数累计起其数量存在counts数组里，然后用动归解决，i = 1~10000（题目里说明i最大只能到10000）dp[

原创 322. Coin Change【Medium】 动归

题目：给N种不同面值的硬币无限枚，用它们得到总额为K的硬币组，问这个组最多可以有多少枚硬币思路：动归，每次枚举一种硬币，然后找到目前为止可以达到的总额的最多硬币情况。状态转移方程：枚举到第i种硬币时，dp[j] = MIN(dp[j], dp[j - coins[i]] + 1)简单int MAX_VALUE = 9999999;class Solution {pub

原创 673. Number of Longest Increasing Subsequence【Medium】 一维动归

题目：给一个序列nums，求该序列有多少条最长子序列思路：最长子序列长度用动归的办法求出：序列对每一个位置i，dp[i]存的是序列从0到i的最长子序列的长度。状态转移方程： dp[i] = max{dp[k] + 1,  0 设最长的子序列长度为d求最长子序列有多少条的办法就是：对每一个dp[i] = d 的位置（即某个最长子序列的末尾），求出以其作为最长子序列

原创 312. Burst Balloons【Hard】 区间动归

题目：给一个数组nums，代表n个气球上每个气球的数字。现要求逐个扎破气球，每扎破第i个气球就取得nums[i - 1] * nums[i] * nums[i + 1]个金币（nums[-1]  = nums[n] = 1），然后第i个气球消失，nums[i - 1]和nums[i + 1]相邻。求最多可以获得多少金币。思路：区间dpdp[i][j]表示扎破第i到第j个

原创 718. Maximum Length of Repeated Subarray【Medium】 动归

题目：找两个数组的最长公共子数组方法：与寻找子串的算法一样：设A数组长度m，B数组长度n用dp[1~m][1~n]存当前位置到前面某个位置可以得到的最长子串长度dp[i][j] = 0                         --- A[i] != B[j]               dp[i-1][j-1] + 1   --- A[i] == B[j]最

原创 630. Course Schedule III 【Hard】 贪心

题目：给出若干课程，课程有2个信息，第一个是课程的持续天数，第二个是课程的截止日期。同一个课程必须是连续修的，在截止日期前上完课程算修完这门课程。求最多可以修的课程数。思路：贪心的思路先把课程按截止日期排序，然后从前到后遍历课程：若该课程可以修（即已修的课程的天数总和，加上这门课的天数不超过此门课程的截止日期），则选择这门课否则，把已修的课程里天数最多的与此门课比较，若前者

原创 310. Minimum Height Trees 【Medium】 树

题目：给出一个树，求出所有作为根节点时树的高度最小的节点思路：用剪枝的办法，每次剪掉叶子节点，最终剩下一个或者两个节点时结束。原理：一个节点的树的高度为该节点到最远的节点的距离，且此最远节点必为叶子节点。那么每一次剪枝后的图，剩余的节点对应的树的高度一定是未剪枝前的高度-1，即对于剪枝后的图，剩余节点之间树的高度的相互大小关系不变。叶子节点的高度必定大于其父亲节点，所以剪枝

原创 689. Maximum Sum of 3 Non-Overlapping Subarrays 【Hard】 动态规划

题目：从给定的一个长度为n的数组中，找出3个互不重叠的长度为k的子数组，使这3个数组的和最大。若有多组解，取最小下标的那组解。思路：动归解决。先以k个和把元素数组变成元素和数组A。用一个3*n的二维数组DP存数据，存的是有row个子数组的时候，每个位置之前所有子数组的最大的和。状态转移方程是：DP[i][j] = max{ DP[i][j - 1] , DP[i - 1

原创 514. Freedom Trail 【Hard】 动态规划

问题：给定一个圆环（初始字符为第一个）和一个字符串，进行如下操作直至打印出此字符串——操作一：打印出圆环的第一个字符操作二：把圆环顺时针或逆时针转一个位置问打印此字符串最少需要多少步操作？思路：用动归解决。将字符串拆分为单个字符，每一轮只考虑当前要打印的字符（假设为X）——对圆环上的每个X，求出其从上一轮到这一轮的最小距离dist（X）。距离指圆环上的顺时针or逆时针最

原创 55. Jump Game 【Medium】 贪心算法

思路：1、结束条件：当前能走的步数大于等于到终点的步数。2、若不能从当前直接到达终点，那么我们要选择下一跳的位置。选择下一跳的时候，用贪心的算法——选择当前点可达范围内的可以走得最远的点。若此点的范围小于等于当前点的范围，则返回不可能。3、循环直到找到结束条件的状态。很简单。。。bool findpos(vector& a, int cur, int l) {

原创 4. Median of Two Sorted Arrays 【Hard】 分治法

看了题解才会做。题解是把取中位数的问题转化为了取第k小的数的问题。题解的思路是：先判断两数组长度和m+n是奇数还是偶数。奇数则直接取两数组的第(m+n) / 2 + 1小的数，偶数则取第(m+n) / 2和第(m+n) / 2 + 1小的数取平均值。取第k小的数的办法是：给定两数组a（长度为m）和b（长度为n）和k。                                   

原创 210. Course Schedule II 【Medium】 拓扑排序

思路：若此图无环，则任意方式DFS这个图，把所有节点以post值从大到小顺序排列，必定得到一个拓扑序列。证明：首先，有环的图肯定不存在拓扑序列。排除有环的情况。无环即无back edge。           然后，从书上的定义可知，对于任意的图，只有back edge (u->v) 存在post(u)            那么对于这个无环图所有的edge (u->v)， 应

原创 207. Course Schedule【Medium】 DFS判断无环

一开始做这题的时候想用邻接矩阵来储存edge，后来发现bool类型是不能开2000*2000以上的二维数组的（上网查了查好像是因为栈的空间被编译器限制住了大小所以不能开这么大的二维数组），导致浪费了很多时间debug。后来用了邻接链表才解决了问题。思路就是课堂上讲的：要判断这个课程安排是否会冲突，就是看这个图是否存在回路（环路）。而存在环路的充要条件是DFS这个图后这个图不存在back

原创 629. K Inverse Pairs【Hard】 动态规划

作死试了一个看起来比较简单的HARD题，刚开始看到题目还觉得有点思路，然而后来却发现没法降低时间复杂度。我的思路如下：每次知道了第n个状态下所有k的情况（即知道所有a[1,2..n][k]），则n+1的情况便可求出来。  因为从n到n+1是相当于在原来的1,2..n的无序序列中加入n+1这个数，那么这个数，n+1，可以放置的位置有n+1位，  例如n=4时，n+1=5，加入5的