3.设计模式概述
月上柳梢头,人约黄昏后。
——欧阳修《生查子》
1. 什么是设计模式
解决某一类问题行之有效的方法;设计模式主要强调的是思想,不是代码,就像建房子需要现有地基,然后需要房梁,需要如何建造一个框架,设计模式就是我们要编程过程中解决某类问题可以采用的思路和方法。
2. 设计模式概述
设计模式(Design pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 毫无疑问,设计模式于己于他人于系统都是多赢的,设计模式使代码编制真正工程化,设计模式是软件工程的基石,如同大厦的一块块砖石一样。项目中合理的运用设计模式可以完美的解决很多问题,每种模式在现在中都有相应的原理来与之对应,每一个模式描述了一个在我们周围不断重复发生的问题,以及该问题的核心解决方案,这也是它能被广泛应用的原因。
<< 设计模式>> 是经典的书,作者是 Erich Gamma、Richard Helm、Ralph Johnson 和 John Vlissides Design(俗称 “四人 ...
30.二分查找算法
二分查找算法1. 二分查找算法介绍
二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找。
二分查找法的运行时间为对数时间 O(㏒₂n) ,即查找到需要的目标位置最多只需要㏒₂n 步,假设从[0,99]的队列(100 个数,即 n=100)中寻到目标数 30,则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)
2. 二分查找算法(非递归)代码实现
数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找, 要求使用非递归的方式完成.
12345678910111213141516171819202122232425262728293031323334353637public class BinarySearchNoRecur { public static void main(String[] args) { int[] arr = {1,2,3,5,7,8,9,76}; int binarySearch = binarySearc ...
31.分治算法
分治算法1. 分治算法介绍
分治法是一种很重要的算法。在计算机科学中,分治法是构建基于多项分支递归的一种很重要的算法范式。
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……
但在这广义之下,所有使用递归或循环的算法均被视作“分治算法”。
1.1 分治算法可以求解的一些经典问题
二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔
1.2 分治法在每一层递归上都有三个步骤
分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题。
解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题。
合并:将各个子问题的解合并为原问题的解。。
2. 分治算法最佳实践-汉诺塔2.1 汉诺塔的传说
汉诺塔:
汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时 ...
32.动态规划算法
[toc]
动态规划算法1. 应用场景-背包问题
背包问题:有一个背包,容量为 4 磅 , 现有如下物品
要求达到的目标为装入的背包的总价值最大,并且重量不超出
要求装入的物品不能重复
2. 动态规划算法介绍
动态规划(Dynamic Programming)算法的核心思想是:将 大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。
动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 )
动态规划可以通过填表的方式来逐步推进,得到最优解。
3. 动态规划算法最佳实践-背包问题3.1 思路分析和图解
背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分 01 背包和 完全背包(完全背包指的是:每种物品都有无限件可用)
这里的问题属于 01 背包,即每个物品最多放一个。而无 ...
33.KMP算法
[toc]
KMP算法1. 应用场景-字符串匹配问题
有一个字符串 str1= "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好"
和一个子串 str2="尚硅谷你尚硅你"
现在要判断 str1 是否含有 str2, 如果存在,就返回第一次出现的位置, 如果没有,则返回-1。
2. 暴力匹配算法
如果用暴力匹配的思路,并假设现在 str1 匹配到 i 位置,子串 str2 匹配到 j 位置,则有:
如果当前字符匹配成功(即 str1[i] == str2[j]),则 i++,j++,继续匹配下一个字符。
如果失配(即 str1[i] != str2[j]),令 i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为 0。
用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。
2.1 代码实现1234567891011121314151617181920212223242526272829303132333435363738394041424344454 ...
34.贪心算法
[toc]
贪心算法1. 应用场景-集合覆盖问题
假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台,让所有的地区都可以接收到信号;
2. 贪心算法介绍
贪婪算法(贪心算法)是指在对问题进行求解时, 在每一步选择中都采取最好或者最优( 即最有利) 的选择,从而希望能够导致结果是最好或者最优的算法。
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。
3. 贪心算法最佳应用-集合覆盖
思路分析:
如何找出覆盖所有地区的广播台的集合呢,使用穷举法实现,列出每个可能的广播台的集合,这被称为幂集。假设总的有 n 个广播台,则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算 10 个子集, 如图:
使用贪婪算法,效率高:
目前并没有算法可以快速计算得到准备的值, 使用贪婪算法,则可以得到非常接近的解,并且效率高。选择策略上,因为需要覆盖全部地区的最小集合。
遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区,但没有关系)
将这个电台加入到一个集合中(比如 ...
4.Java中IO异常处理
剪不断,理还乱,是离愁。别是一般滋味在心头。
——李煜《相见欢》
IO异常的处理1. JDK7前处理
我们知道Java中异常处理有两种方式,一种是throw,一种是try-catch,我们首先要知道这两种方式的使用。
throw 异常之后,后面的代码将不会执行
try-catch时,即使catch到了异常之后,后面的代码还是会继续执行
刚学习的时候为了方便我们经常使用throw将异常抛出,而实际开发中并不能这样处理,建议使用 try…catch…finally 代码块,处理异常部分。
123456789101112131415161718192021222324public class HandleException { public static void main(String[] args) { // 字符输出流 声明变量 FileWriter fw = null; try { //创建流对象 fw = new FileWriter("f ...
4.List接口及其实现类
凝碧旧池头,一听管弦凄切。多少梨园声在,总不堪华发。
——韩元吉《好事近》
List接口及其实现类1. List接口介绍
java.util.List 接口继承自 Collection 接口,是单列集合的一个重要分支,习惯性地会将实现了 List 接口的对象称为List集合。
在List集合与set集合不同允许出现重复的元素,所有的元素是以一种线性方式进行存储的,在程序中可以通过索引来访问集合中的指定元素。另外,List集合还有一个特点就是元素有序,即元素的存入顺序和取出顺序一致。
JDK API中List接口的实现类常用的有:ArrayList、LinkedList和Vector。
2. List接口中常用方法
List作为Collection集合的子接口,不但继承了Collection接口中的全部方法,而且还增加了一些根据元素索引来操作集合的特有方法,如下:
public void add(int index, E element) : 将指定的元素,添加到该集合中的指定位置上。 将当前位于该位置的元素(如果有)和任何后续元素(向其索引添加一个)移动。
public ...
4.MySql高级之触发器
渐写到别来,此情深处,红笺为无色。
——晏几道《思远人》
## MySql高级之触发器
1. 介绍
触发器是与表有关的数据库对象,指在 insert/update/delete 之前或之后,触发并执行触发器中定义的SQL语句集合。触发器的这种特性可以协助应用在数据库端确保数据的完整性 , 日志记录 , 数据校验等操作 。
使用别名 OLD 和 NEW 来引用触发器中发生变化的记录内容,这与其他的数据库是相似的。
现在触发器还只支持行级触发,不支持语句级触发。
触发器类型
NEW 和 OLD的使用
INSERT 型触发器
NEW 表示将要或者已经新增的数据
UPDATE 型触发器
OLD 表示修改之前的数据 , NEW 表示将要或已经修改后的数据
DELETE 型触发器
OLD 表示将要或者已经删除的数据
2. 创建触发器
语法结构 :
12345678910111213create trigger trigger_name before/after insert/update/deleteon tbl_name [ for each row ] -- ...
4.JavaScript 事件的三个阶段
前端–JavaScript 事件的三个阶段1. addEventListener绑定事件
btn.addEventListener 绑定事件,只支持高版本的浏览器。
第一个参数:事件的类型,一个不带on的字符串类型的数据
第二个参数:事件处理函数
第三个参数: true,false.布尔类型的数据,false:事件冒泡 true:事件捕获。
btn.attachEvent();绑定事件,只支持ie10以及以下的版本。
当给同一个对象绑定多个相同事件的时候,ie8及以下,乱序的执行。
1234567891011121314151617181920212223242526<button id="btn">按钮</button><script> // onclick事件 同一个对象只能绑定一个事件触发的函数会覆盖。 // var btn=document.getElementById("btn"); // btn.onclick=function(){ // al ...