2014年3月5日

题目描述:
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

思路:

我们可以使用分治法或者减治法来处理这个问题。

分治法    
目标:把1个大问题分成2个小问题,2个小问题还可以再分,直到问题规模小的可以简单解决。

将该数组等分成两个子数组,假如知道左右两侧两个数组的各自的最大子数组和,那么整个数组的最大子数组和可能为三种情况:

  • 右侧数组的最大子数组和
  • 左侧数组的最大子数组和
  • 左右两侧数组中间毗邻位置连接形成的子数组的和的最大值(如-6,4,-3,2####5,-6,9,-8,左侧最大值为4,右侧为9,中间毗邻位置从2和5向两侧相加,得到中间毗邻子数组4,-3,2,5,-6,9和为11,三者比较得最大子数组和为11)。

递归到数组中只包含一个数字。

这种思路也是可行的。进行ln(n)次拆分,每次拆分后进行n次比较,所以算法复杂度为n*ln(n)。但还达不到题目的要求。

java代码:

 1 package com.island.info;
 2 /**
 3  * <p>Title: TestMaxArray.java</p>
 4  * <p>Description: 分治法求解连续和最大</p>
 5  * @date 2014-3-05
 6  *
 7  */
 8  
 9 public class MaxSub {
10         static int arr[] = {4,-3,5,-2,-1,2,6,-2};    //也可以随机生成
11         public static void main(String args[]){
12             System.out.println(max(arr));
13         }
14  
15         //包装函数
16         public static int max(final int[] arr){
17             System.out.println("(1)*****arr.length-1----------------->:"+ (arr.length-1));
18             return max(arr,0,arr.length-1);
19         }
20  
21         //核心代码:递归调用max()
22         public static int max(final int[] arr,int leftIndex, int rightIndex){
23             System.out.println("(2)*****leftIndex--------rightIndex--->:"+leftIndex+"|***************|"+rightIndex);
24             int sum = 0,leftHalfMax = 0, rightHalfMax = 0;
25             if (rightIndex-leftIndex==0){
26                 return arr[rightIndex];
27             } else {
28                 int center = (leftIndex+rightIndex)/2;//2分查找中间节点
29                 int maxLeft = max(arr,leftIndex,center);//左边最大的
30                 int maxRight = max(arr,center+1,rightIndex);//右边最大的
31                 //以下是查找跨越中间点的最大子序列
32                 //从中点到左侧:
33                 for (int i=center;i>=leftIndex;--i){
34                     sum+=arr[i];
35                     if (sum>leftHalfMax){
36                         leftHalfMax = sum;
37                     }
38                 }
39                 System.out.println("左边的sum----------->:"+sum);
40                 sum=0;
41                 //从中点到右侧
42                 for (int i=center+1;i<=rightIndex;++i){
43                     sum+=arr[i];
44                     if (sum>rightHalfMax){
45                         rightHalfMax = sum;
46                     }
47                 }
48                 System.out.println("右边的sum----------->:"+sum);
49                 return max(maxLeft,maxRight,leftHalfMax+rightHalfMax);
50             }
51         }
52  
53         //三者取最大值
54         public static int max(int a,int b,int c){
55             return a>b?(a>c?a:c):(b>c?b:c);
56         }
57     }

减治法

目标:将问题规模不断减小,直到可以简单处理为止。

假设我们已知一个数组的最大子数组和,现在在该数组后面增加一个数字,新数组的最大子数组和可能是什么呢:

  • 原数组的最大子数组和;
  • 新增加的数字为正数,和最右侧的子数组形成了一个新的最大子数组和(所以为了通过一次遍历完成,我们需要保存最右侧的子数组的最大和)。

然后将两个数字进行比较即可。

所以减治至数组只包含最左侧一个数字,我们知道它的最大子数组和和最右侧子数组最大和都为还数字,逐次加1个数字直到整个数组即可。

java代码:

 1 package com.island.info;
 2  
 3 /**
 4  * <p>Title: TestMaxArray.java</p>
 5  * <p>Description: 分治法求解连续和最大</p>
 6  * @date 2014-3-05
 7  *
 8  */
 9 public class MaxSubArraySum {
10  
11     private static long getMax(long a, long b) {
12         return a > b ? a : b;
13     }
14      
15     /** 
16     * 获得连续子数组的最大和 
17     * @param array 
18     * @return 最大和,此处用了Long型是为了表示当参数为null或空时,可以返回null,返回其它任何数字都可能引起歧义。 
19     */ 
20  
21     public static Long getMax(int[] array) {
22          
23         if (array == null || array.length <= 0) {
24             return null;
25         }
26          
27         long maxSum = array[0]; //所有子数组中最大的和 
28         long righteEdge = array[0]; //右侧子数组的最大和
29         for (int i = 1; i < array.length; i++) {
30             //当右侧子数组的最大和为负数时,对于新数组,右侧子数组的最大和为新增加的数。  
31             if (righteEdge < 0) {
32                 righteEdge = array[i];
33             } else { //为正数时,对于新数组,右侧子数组的最大和为新增加的数 + 原来的最大和。  
34                 righteEdge += array[i];
35             }
36             //所有子数组中最大的和  
37             System.out.println("righteEdge-------------maxSum:"+righteEdge+"****************"+maxSum);
38             maxSum = getMax(righteEdge, maxSum);
39         }
40         return maxSum;
41     }
42  
43     public static void main(String[] args) {
44         int[] array = {1-2310-472-5};
45         //int arr[] = {4,-3,5,-2,-1,2,6,-2};  
46         System.out.println("Max sum: " + MaxSubArraySum.getMax(array));
47     }
48  
49 }

posted @ 2014-03-05 11:47 dongisland 阅读(1700) | 评论 (0)编辑 收藏

Ajax的原理就是:通过javascript的方式,将前台数据通过xmlhttp对象传递到后台,后台在接收到请求后,将需要的结果,再传回到前台,这样就可以实现不需要页面的回发,页是数据实现来回传递,从页实现无刷新。 
Ajax的原理简单来说,实际上就是通过XmlHttpRequest对象来向服务器发异步请求,从服务器获得数据,然后用javascript来操作DOM而更新页面。 
这其中最关键的一步就是从服务器获得请求数据。要清楚这个过程和原理,我们必须对 XMLHttpRequest有所了解。 
我们可以看出,XMLHttpRequest对象完全用来向服务器发出一个请求的,它的作用也局限于此,但它的作用是整个ajax实现的关键,我们可以把服务器端看成一个数据接口,它返回的是一个纯文本流,当然,这个文本流可以是XML格式,可以是Html,可以是Javascript代码,也可以只是一个字符串。这时候,XMLHttpRequest向服务器端请求这个页面,服务器端将文本的结果写入页面,这和普通的web开发流程是一样的,不同的是,客户端在异步获取这个结果后,不是直接显示在页面,而是先由javascript来处理,然后再显示在页面。

posted @ 2014-03-05 11:27 dongisland 阅读(597) | 评论 (0)编辑 收藏

内连接:INNER  JOIN或者JOIN,把两个表中数据对应的数据查出来。 
外连接:OUTER  JOIN,以某个表为基础把对应数据查出来,分为左外连接和右外连接。 
左外连接:LEFT  JOIN或者LEFT  OUTER  JOIN,以某个表为基础把对应数据查出来。 
右外连接:RIGHT  JOIN或者RIGHT  OUTER  JOIN,以某个表为基础把对应数据查出来。 
全连接:FULL  JOIN,以多个表为基础

例子:   
   a表      id   name    
              1   张3                 
              2   李四                  
              3   王武                 

    b表     id     job   parent_id   
              1     23     1   
               2     34     2   
              3     34     4  
  a.id同b.parent_id   存在关系   
内连接   
  select   a.*,b.*   from   a   inner   join   b     on   a.id=b.parent_id   
 结果是     
  1   张3          1     23     1   
  2   李四         2     34     2   
 左连接   
  select   a.*,b.*   from   a   left   join   b     on   a.id=b.parent_id   
结果是     
  1   张3           1     23     1   
  2   李四          2     34     2   
  3   王武          null  
右连接   
  select   a.*,b.*   from   a   right   join   b     on   a.id=b.parent_id   
  结果是     
  1   张3            1     23     1   
  2   李四           2     34     2   
  null                 3     34     4   
  完全连接   
  select   a.*,b.*   from   a   full   join   b     on   a.id=b.parent_id  
  结果是     
  1   张3            1     23     1   
  2   李四           2     34     2   
  null                 3     34     4   
  3   王武           null

posted @ 2014-03-05 11:26 dongisland 阅读(165) | 评论 (0)编辑 收藏

一、Collections类和Collection接口

     Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

    Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的 类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

二、现在来谈谈Java集合的一些实现类。

Collection
List

ArreyList 

Vector

LinkedList

│└Stack

└Set

HashSet
LinkedHashSet

│└TreeSet

List代表有序、重复的集合

1.ArrayList类
  ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。
size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
  每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法 并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
  和LinkedList一样,ArrayList也是非同步的(unsynchronized)。

2.Vector类
  Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。

3.LinkedList类
  LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。
  注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:
    List list = Collections.synchronizedList(new LinkedList(...));

4.Stack 类
  Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set代表无序、不可重复的集合
HashSet和TreeSet的区别
HashSet无序,TreeSet有序,两者均不能有重复的对象

Map
HashMap

Hashtable

TreeMap
└WeakHashMap

Map没有继承Collection接口

1.Hashtable类
  Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。Hashtable是同步的。

2.HashMap类
  HashMap和Hashtable类似,不同之处在于 HashMap是非同步的,并且允许null,即null value和null key。,但是将HashMap视为Collection时 (values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要 将HashMap的初始化容量设得过高,或者load factor过低。

3.WeakHashMap类
  WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。

三、集合类的遍历

遍历通用Collection

Iterator it = collection.iterator(); // 获得一个迭代子
  while(it.hasNext()) {
   Object obj = it.next(); // 得到下一个元素
}

posted @ 2014-03-05 11:07 dongisland 阅读(253) | 评论 (0)编辑 收藏

1) 在Action实现类方面的对比:Struts 1要求Action类继承一个抽象基类;Struts 1的一个具体问题是使用抽象类编程而不是接口。Struts 2 Action类可以实现一个Action接口,也可以实现其他接口,使可选和定制的服务成为可能。Struts 2提供一个ActionSupport基类去实现常用的接口。即使Action接口不是必须实现的,只有一个包含execute方法的POJO类都可以用作Struts 2的Action。 
2) 线程模式方面的对比:Struts 1 Action是单例模式并且必须是线程安全的,因为仅有Action的一个实例来处理所有的请求。单例策略限制了Struts 1 Action能做的事,并且要在开发时特别小心。Action资源必须是线程安全的或同步的;Struts 2 Action对象为每一个请求产生一个实例,因此没有线程安全问题。 即struts1每个action只有1个实例,struts2每一个请求都会new一个实例,所以struts2是线程安全的
3) Servlet依赖方面的对比:Struts 1 Action依赖于Servlet API,因为Struts 1 Action的execute方法中有HttpServletRequest和HttpServletResponse方法。Struts 2 Action不再依赖于Servlet API,从而允许Action脱离Web容器运行,从而降低了测试Action的难度。 当然,如果Action需要直接访问HttpServletRequest和HttpServletResponse参数,Struts 2 Action仍然可以访问它们。但是,大部分时候,Action都无需直接访问HttpServetRequest和HttpServletResponse,从而给开发者更多灵活的选择。 
4) 可测性方面的对比:测试Struts 1 Action的一个主要问题是execute方法依赖于Servlet API,这使得Action的测试要依赖于Web容器。为了脱离Web容器测试Struts 1的Action,必须借助于第三方扩展:Struts TestCase,该扩展下包含了系列的Mock对象(模拟了HttpServetRequest和HttpServletResponse对象),从而可以脱离Web容器测试Struts 1的Action类。Struts 2 Action可以通过初始化、设置属性、调用方法来测试。 
5) 封装请求参数的对比:Struts 1使用ActionForm对象封装用户的请求参数,所有的ActionForm必须继承一个基类:ActionForm。普通的JavaBean不能用作ActionForm,因此,开发者必须创建大量的ActionForm类封装用户请求参数。虽然Struts 1提供了动态ActionForm来简化ActionForm的开发,但依然需要在配置文件中定义ActionForm;Struts 2直接使用Action属性来封装用户请求属性,避免了开发者需要大量开发ActionForm类的烦琐,实际上,这些属性还可以是包含子属性的Rich对象类型。如果开发者依然怀念Struts 1 ActionForm的模式,Struts 2提供了ModelDriven模式,可以让开发者使用单独的Model对象来封装用户请求参数,但该Model对象无需继承任何Struts 2基类,是一个POJO,从而降低了代码污染。 
6) 表达式语言方面的对比:Struts 1整合了JSTL,因此可以使用JSTL表达式语言。这种表达式语言有基本对象图遍历,但在对集合和索引属性的支持上则功能不强;Struts 2可以使用JSTL,但它整合了一种更强大和灵活的表达式语言:OGNL(Object Graph Notation Language),因此,Struts 2下的表达式语言功能更加强大。 
7) — 绑定值到视图的对比:Struts 1使用标准JSP机制把对象绑定到视图页面;Struts 2使用“ValueStack”技术,使标签库能够访问值,而不需要把对象和视图页面绑定在一起。 
8) 类型转换的对比:Struts 1 ActionForm 属性通常都是String类型。Struts 1使用Commons-Beanutils进行类型转换,每个类一个转换器,转换器是不可配置的;Struts 2使用OGNL进行类型转换,支持基本数据类型和常用对象之间的转换。 
9) 数据校验的对比:Struts 1支持在ActionForm重写validate方法中手动校验,或者通过整合Commons alidator框架来完成数据校验。Struts 2支持通过重写validate方法进行校验,也支持整合XWork校验框架进行校验。 
10) Action执行控制的对比:Struts 1支持每一个模块对应一个请求处理(即生命周期的概念),但是模块中的所有Action必须共享相同的生命周期。Struts 2支持通过拦截器堆栈(Interceptor Stacks)为每一个Action创建不同的生命周期。开发者可以根据需要创建相应堆栈,从而和不同的Action一起使用。 
11) 捕获输入:Struts1 使用ActionForm对象捕获输入。所有的ActionForm必须继承一个基类。因为其他JavaBean不能用作ActionForm,开发者经常创建多余的类捕获输入。动态Bean(DynaBeans)可以作为创建传统ActionForm的选择,但是,开发者可能是在重新描述(创建)已经存在的JavaBean(仍然会导致有冗余的javabean)。Struts 2直接使用Action属性作为输入属性,消除了对第二个输入对象的需求。输入属性可能是有自己(子)属性的rich对象类型。Action属性能够通过 web页面上的taglibs访问。Struts2也支持ActionForm模式。rich对象类型,包括业务对象,能够用作输入/输出对象。这种 ModelDriven 特性简化了taglib对POJO输入对象的引用。

posted @ 2014-03-05 10:52 dongisland 阅读(164) | 评论 (0)编辑 收藏


仅列出标题  

posts - 5, comments - 0, trackbacks - 0, articles - 0

Copyright © dongisland