有两个编程题 各位大哥帮看看 绝对给分 信誉第一

Question

1。设一个双向循环链表L，用代码实现在链表的给的定节点p后加入一个节点q， 和删除节点p的操作，要求用类L，节点Node，以及方法add（），delete（）2。设一个整数数组int[]array，长度为M，该数组中任意连续X（1<=X<=M）个元素可以组成一个子数组，每个子数组的所有元素的和为Si。求Si最大的子数组的起始下标值以及截止下标值

Answer 1

第一个：public class L
{
private java.util.LinkedList list; public java.util.LinkedList getList()
{
return list;
}
public void setList(java.util.LinkedList list)
{
this.list = list;
}
public L()
{
list = new java.util.LinkedList();
for (int i = 0; i < 10; i++)
{
Node node = new Node("name" + i, "value" + i);
list.add(node);
}
}
public void add(Node node, Node position)
{
int index = list.indexOf(position);
list.add(index + 1, node);
}
public void add(Node node, int position)
{
list.add(position, node);
}
public boolean delete(Node node)
{
return list.remove(node);
}
public String toString()
{
StringBuffer sb = new StringBuffer();
sb.append("The list is: {");
java.util.Iterator i = list.iterator();
while (i.hasNext())
{
Node tmp = (Node) i.next();
sb.append("[" + tmp.getName() + "," + tmp.getValue() + "]");
}
sb.append("}");
return sb.toString();
}
public static void main(String[] args)
{
L l = new L();
System.out.println("Begin: " + l);
l.add(new Node("csdn", "中国软件开发网"), 3);
System.out.println("after add 1: " + l);
l.add(new Node("java","www.java.sun.com"),new Node("csdn","中国软件开发网"));
System.out.println("after add 2: " + l);
l.delete(new Node("name5", "value5"));
System.out.println("after delete: " + l);
}
}class Node
{
private String name;
private String value; public String getName()
{
return name;
}
public void setName(String name)
{
this.name = name;
}
public String getValue()
{
return value;
}
public void setValue(String value)
{
this.value = value;
}
public Node(String name, String value)
{
this.name = name;
this.value = value;
}
public boolean equals(Object node)
{
if ((name.equals(((Node) node).getName())) && (value.equals(((Node) node).getValue())))
return true;
return false;
}
}

Answer 2

public class Untitled1 {
    public Untitled1() {
    }
    public static void getMax(int[] array){
        int max=array[0];
        int begin=0;
        int end=0;
        for(int i=0;i<array.length;i++){
            int sum=array[i];
            for (int j = i + 1; j < array.length; j++) {
                sum+=array[j];
                if(sum>max){
                    max=sum;
                    begin=i;
                    end=j;
                }
            }
        }
        System.out.println(max);
        System.out.println("起始位置为:"+begin);
        System.out.println("末位置为:"+end);
    }
    public static void main(String[] args) {
        int[] array={1,-1,3,4,0,-8,10,3,20};
        Untitled1.getMax(array);
    }
}
没有考虑到效率问题,时间为n平方,同时还有个问题就是如果有几个子数列都是最大值,那只能得到第一次遇到的数列.不过这个可以解决.
有时间可以优化,比如如果max为负值,可以直接break了,如果有错误,请大家指教.

Answer 3

我自己写的一个链表、给妳参考下
public class Node {
private int linkData; private Node linkNext; private Node linkBefore; public Node(int data) {
linkData = data;
linkNext = null;
linkBefore = null;
} public Node(int data, Node next, Node before) {
linkData = data;
linkNext = next;
linkBefore = before;
} public void setData(int data) {
linkData = data;
} public int getData() {
return linkData;
} public void setBefore(Node before) {
linkBefore = before;
} public Node getBefore() {
return linkBefore;
} public void setNext(Node next) {
linkNext = next;
} public Node getNext() {
return linkNext;
}
}public class LinkList {
public Node linkFirstNode; public Node linkEndNode; public LinkList() {
linkFirstNode = null;
linkEndNode = null;
} public LinkList(int data) {
linkFirstNode = new Node(data);
linkEndNode = new Node(data);
Node next = linkFirstNode;
while (next != null) {
linkEndNode = next;
next = next.getNext();
}
} public int returnFirstNode() {
Node before = linkFirstNode;
int head = before.getData();
System.out.println(head);
return head;
} public int returnEndNode() {
Node next = linkFirstNode;
int end = 0;
while (next != null) {
end = next.getData();
next = next.getNext();
}
// Node next = linkEndNode;
// int end = next.getData();
System.out.println(end);
return end;
} public boolean addFirstNode(int data) {
Node next = linkFirstNode;
Node newFirst = new Node(data);
if (next == null) {
linkFirstNode = newFirst;
} else {
next.setBefore(newFirst);
newFirst.setNext(next);
linkFirstNode = newFirst;
}
return true;
} public boolean addEndNode(int data) {
Node next = linkFirstNode;
Node newEnd = new Node(data);
if (next == null) {
linkFirstNode = newEnd;
} else {
while (next.getNext() != null) {
next = next.getNext();
}
next.setNext(newEnd);
newEnd.setBefore(next);
}
return true;
} public boolean addNode(int one, int data) {
Node next = linkFirstNode;
Node newAdd = new Node(data);
while (next != null) {
int m = next.getData();
if (m == one) {
if (next.getNext() == null) {
addEndNode(data);
return true;
} else {
next.getNext().setBefore(newAdd);
newAdd.setNext(next.getNext());
next.setNext(newAdd);
newAdd.setBefore(next);
return true;
}
} else {
next = next.getNext();
}
}
return false;
} public boolean delNode(int data) {
Node next = linkFirstNode;
while (next != null) {
int m = next.getData();
if (m != data) {
next = next.getNext();
} else {
if (next.getBefore() == null) {
linkFirstNode = next.getNext();
next.setBefore(null);
return true;
}
if (next.getNext() == null) {
next.getBefore().setNext(null);
return true;
} else {
next.getBefore().setNext(next.getNext());
next.getNext().setBefore(next.getBefore());
return true;
}
}
}
return false;
} public boolean visitAllNode() {
Node next = linkFirstNode;
while (next != null) {
next = next.getNext();
}
while (next != null) {
next = next.getBefore();
}
return true;
} public boolean searchNode(int data) {
Node next = linkFirstNode;
while (next != null) {
if (next.getData() == data) {
System.out.println(next.getData());
return true;
} else {
next = next.getNext();
}
}
return false;
} void showAll() {
Node next = linkFirstNode;
while (next != null) {
System.out.print(next.getData() + " ");
next = next.getNext();
}
System.out.println();
}
}

Answer 4

这是测试用的、妳可以用下
public class Test { public static void main(String args[]) {
LinkList list = new LinkList();
list.addFirstNode(11);
// list.delNode(11);
// list.showAll();

list.addFirstNode(12);
list.showAll();
list.returnFirstNode();
list.returnEndNode();
// list.delNode(12);

// System.out.println(list.linkFirstNode);

// list.addEndNode(12);
// list.showAll();
//
// list.addFirstNode(22);
// list.showAll();
//
// list.addEndNode(23);
// list.showAll();
//
// list.addNode(12,31);
// list.addNode(23,32);
// list.showAll();
// list.searchNode(23);

// list.addNode(11,0);
// list.addNode(12,11);
// list.delNode(11);
// list.delNode(12);

// list.returnFirstNode();
// list.returnEndNode();
// list.addFirstNode(1);
// list.addEndNode(2);
// list.showAll();
}
}

Answer 5

1题，lz可以参考下面的例子：
public class LinkListApp {
public static void main(String[] args) {
LinkList theList = new LinkList();theList.insertFirst(22,2.99);
theList.insertFirst(44,4.99);
theList.insertFirst(66,6.99);
theList.insertFirst(88,8.99);
theList.displayList();
while(!theList.isEmpty()){
Link aLink = theList.deleteFirst();
System.out.print("Deleted");
aLink.displayLink();
System.out.print(" ");
}
theList.displayList();
}
}
class Link {
public int iData;
public double dData;
public Link next;
public Link(int id,double dd){
iData = id;
dData = dd;
}
public void displayLink(){
System.out.println("{" + iData +"," + dData + "}");
}
}
class LinkList {
private Link first;public void LinkList(){
first = null;
}
public boolean isEmpty(){
return (first == null);
}
public void insertFirst(int id,double dd){
Link newLink = new Link(id,dd);
newLink.next = first;
first = newLink;
}
public Link deleteFirst(){
Link temp = first;
first = first.next;
return temp;
}
public void displayList(){
System.out.print("List(first-->last):");
Link current = first;
while(current != null){
current.displayLink();
current = current.next;
}
System.out.println("");
}
}

Answer 6

第二个实际上是组合的问题
////////////////
import java.util.ArrayList;public class Combination {
  private static int[] array = { 33, 2, 5, 7, 9, 10, 22, 8 }; // 在这里定义任意长度的数组
  static int M = array.length;
  static int X = 4;
  //-------------------
  private static ArrayList<Integer> v = new ArrayList<Integer>();
  private static int num = 0;
  private static int count = Cnm(M, X);
  private static int[] b = new int[count];
  private static String[] belong = new String[count];
  static int Max = Integer.MIN_VALUE;
  static int MaxIndex = -1;
  static String MaxBelong = "";  public static void main(String[] args) {
    find(0, M - X, X);
    System.out.println("*********************\n Result:");
    System.out.println("b[" + MaxIndex + "]=" + MaxBelong + "=" + b[MaxIndex]);
  }  public static int Cnm(int n, int m) {
    int ret = 1;
    for (int i = n; i >= n - m + 1; i--)
      ret *= i;
    for (int i = m; i >= 1; i--)
      ret /= i;
    return ret;
  }  private static void find(int ns, int ne, int step) {
    if (step == 0) {
      show();
      v.remove(v.size() - 1);
      return;
    }
    for (int i = ns; i <= ne; i++) {
      v.add(new Integer(i));
      find(i + 1, ne + 1, step - 1);
    }
    if (v.size() > 0)
      v.remove(v.size() - 1);
  }  private static void show() {
    int tot = 0;
    String ret = "";
    for (int k = 0; k < v.size(); k++) {
      int m = ((Integer) v.get(k)).intValue();
      tot += array[m];
      ret += "a[" + m + "]";
      if (k != v.size() - 1)
        ret += "+";
    }
    b[num] = tot;
    belong[num] = ret;
    System.out.println("b[" + num + "]=" + ret + "  = " + tot);
    if (b[num] > Max) {
      Max = b[num];
      MaxIndex = num;
      MaxBelong = ret;
    }
    num++;
  }
}

Answer 7

错了，上面的是单链表的，下面是双链表的：
public class DoublyLinkedApp {
public static void main(String[] args) {
DoublyLinkedList theList = new DoublyLinkedList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);theList.insertFirst(11);
theList.insertFirst(33);
theList.insertFirst(55);theList.displayForward();
theList.displayBackward();theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);theList.displayForward();theList.insertAfter(22,77);
theList.insertAfter(33,88);theList.displayForward();
}}
class Link {
public long dData;
public Link next;
public Link previous;public Link(long d){
dData = d;
}
public void displayLink(){
System.out.println( dData + " ");
}
}
class DoublyLinkedList{
private Link first;
private Link last;public DoublyLinkedList(){
first = null;
last = null;
}
public boolean isEmpty(){
return first == null;
}public void insertFirst(long dd){
Link newLink = new Link(dd);if(isEmpty())
last = newLink;
else
first.previous = newLink;
newLink.next = first;
first = newLink;
}public void insertLast(long dd){
Link newLink = new Link(dd);
if(isEmpty()){
first = newLink;
}
else{
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
public Link deleteFirst(){
Link temp = first;
if(first.next == null){
last = null;
}
else{
first.next.previous = null;
}
first = first.next;
return temp;
}
public Link deleteLast(){
Link temp = last;
if(first.next == null){
first = null;
}
else{
last.previous.next = null;
}
last = last.previous;
return temp;
}public boolean insertAfter(long key,long dd){
Link current = first;
while(current.dData != key){
current = current.next;
if(current == null){
return false;
}
}
Link newLink = new Link(dd);if(current == last){
newLink.next = null;
last = newLink;
}
else{
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}public Link deleteKey(long key){
Link current = first;
while(current.dData != key){
current = current.next;
if(current == null){
return null;
}
}
if(current == first)
first = current.next;
else
current.previous.next = current.next;
if(current == last)
last = current.previous;
else
current.next.previous = current.previous;
return current;
}public void displayForward(){
System.out.print("List (first-->last):");
Link current = first;
while(current != null){
current.displayLink();
current = current.next;
}
System.out.println("");
}public void displayBackward(){
System.out.print("List (last-->first):");
Link current = last;
while(current != null){
current.displayLink();
current = current.previous;
}
System.out.println("");
}}

Answer 8

你要连续的，那就简单了
package combine;public class B {
private static int[] array = { 33, 2, 5, 7, 9, 10, 22, 8 }; // 在这里定义任意长度的数组
static int M = array.length;
static int X = 4;
//---------------------
static int se[] = new int[2];
static int Max = Integer.MIN_VALUE; public static void main(String[] args) {
System.out.println("X=" + X);
for (int i = 0; i + X - 1 <= M - 1; i++) {
int t = 0;
for (int j = i; j <= i + X - 1; j++)
t += array[j];
System.out.println("a[" + i + "]-->a[" + (i + X - 1) + "]=" + t);
if (t > Max) {
Max = t;
se = new int[] { i, i + X - 1 };
}
}
System.out.println("*******************\nResult:");
System.out.println("a[" + se[0] + "]-->a[" + se[1] + "]=" + Max);
}
}

Answer 9

楼上的 Max算的不对，改一下：
public class Test {
private static int[] a = { 33, 2, 5, 7, 9, 10, 22, 8 };
private static int n = 1;
static int max = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
int begin = 0;
for(int i = 0;i < a.length - n;i++){
int sum = 0;
for (int j = i;j < i + n;j++){
sum += a[j];
System.out.println("a[" + i + "]-->a[" + (i + n - 1) + "]=" + sum);
if (sum >= max){
max = sum;
begin = i;
}
}
System.out.println(begin + "@" + max);
}
}
}

Answer 10

void subdimen_Max(int * array,int m,int x,int stat,int end,int MAX)
// satrt:返回起始位置,end返回终止位置,MAX 返回最大和子数组的和
{
int  sumx[m-x+1];sumx[0]=0;
for(int i=0;i<x;i++){
   sumx[0]+=array[i];
}}for(int i=1;i<m;i++){
   sumx[i]=sumx[i-1]-a[i-1]+a[i+x];
}
MAX=-999999999;for(int i=0;i<x;i++){
    if(MAX<sumx[i]){
       MAX=sumx[i];
       start=i;     
    }
end=start+x-1;
}

Answer 11

imA(男的不会，会的不男) 好高的信誉值啊～　　｀

Answer 12

第2题sinba6628j() 的方法应当是比较好的，效率可以到O(M)的数量级吧，可惜用了指针来做反馈，当然在Java里头自己来定义一个Class来做为返回值也是很方便的。
如果那个题目中，对于那些求和相同的子数组只要求返回最前面的字数组的话，那个解法在存储空间上应当还可以优化吧。其实可以一边作求和一边就和前一次求和的结果作比较，这样的话，只需要2个存放Summary的变量(1个存放到目前为止的Max Summary, 1个存放前面一次子数组求和的结果，同时可以在前一次求和结果的基础上计算当前子数组的求和结果)就可以了。首先定义一个数据结构如下
    //存储列表中某个Sublist的求和内容
    class Summary {
        public int startIndex = 0;
        public int stopIndex = 0;
        public int summary = 0;
    }
    
    //将srcSummary中的内容复制到dstSummary。
    public static void CopySummary(Summary srcSummary, Summary dstSummary) {
        dstSummary.startIndex = srcSummary.startIndex;
        dstSummary.stopIndex = srcSummary.stopIndex;
        dstSummary.summary = srcSummary.summary;
    }...
然后定义算法
    
    // 求出aList[]中，长度为subListLength的最大的子列表，返回Summary对象。
    // 由于aList[]的长度可以通过aList.length获得，这里就不传入了。
    public static Summary GetMaxSummary(int aList[], int subListLength ) {
        //记录到目前为止Summary最大的SubList
        Summary maxSummary = new Summary();
        //记录本次求和的SubList
        Summary currentSummary = new Summary();
        //记录数组的长度
        int listLength = aList.length;
        
        //特殊情况处理
        if (subListLength> listLength) {
            //直接将全部数据求和返回。(根据需求也可以选择抛出异常)
            maxSummary.startIndex = 0;
            maxSummary.stopIndex = listLength -1;
            maxSummary.summary = 0 ;
            for (int i=0; i< listLength; i++) {
                maxSummary.summary += aList[i];
            }
            return maxSummary;
        }
        if (subListLength<=0) {
            //直接返回0，根据情况也可以抛出异常
            maxSummary.startIndex = 0;
            maxSummary.stopIndex = -1;
            maxSummary.summary = 0;
            return maxSummary;
        }
        
        //循环变量
        int i;        //计算最前面的subList的和
        currentSummary.startIndex =0;
        currentSummary.stopIndex = currentSummary.startIndex + subListLength -1;
        currentSummary.summary = 0;
        for (i= currentSummary.startIndex; i<= currentSummary.stopIndex; i++) {
            currentSummary.summary += aList[i];
        }
        //给max Summary 赋初值
        CopySummary(currentSummary, maxSummary);
        
        //开始循环计算当前sub list的和
        for(currentSummary.stopIndex++, currentSummary.startIndex++; 
                currentSummary.stopIndex<listLength;
                currentSummary.stopIndex++, currentSummary.startIndex++) {
            //之前已经计算了前一个数组的和了，因此可以在此基础上直接计算出当前数组的和。
            currentSummary.summary = currentSummary.summary 
                    + aList[currentSummary.stopIndex] 
                    - aList[currentSummary.startIndex-1];
            //比较currentSummary和maxSummary
            if (currentSummary.summary> maxSummary.summary) {
                CopySummary(currentSummary, maxSummary);
            }
        }
        return maxSummary;
    }