有两个编程题 各位大哥帮看看 绝对给分 信誉第一
1。设一个双向循环链表L，用代码实现在链表的给的定节点p后加入一个节点q， 和删除节点p的操作，要求用类L，节点Node，以及方法add（），delete（）
2。设一个整数数组int[]array，长度为M，该数组中任意连续X（1 <=X <=M）个元素可以组成一个子数组，每个子数组的所有元素的和为Si。求Si最大的子数组的起始下标值以及截止下标值
[解决办法]
数据结构的问题，不敢瞎说，等高手的优秀代码
估计第二题得三层循环
[解决办法]
第一个：
public class L
{
private java.util.LinkedListlist;
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 Stringname;
private Stringvalue;
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;
}
}
[解决办法]
upup
[解决办法]
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了,如果有错误,请大家指教.
[解决办法]
第一题，没注意，还以为用C！
第二题，难道是所谓的“贪心法”？！
[解决办法]
我自己写的一个链表、给妳参考下
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();
}
}
[解决办法]
老大都写了。哈
[解决办法]
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( " ");
}
}
[解决办法]
第二个实际上是组合的问题
////////////////
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++;
}
}
[解决办法]
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;
}
[解决办法]
imA(男的不会，会的不男) 好高的信誉值啊～ ｀
[解决办法]
第二题从倒数第m个往前遍历吧
[解决办法]
第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;
}
