Ch1:
1.14:
public class OrderedCollection {
private Comparable[] comparables;
public Comparable[] getComparables() {
return comparables;
}
public void setComparables(Comparable[] comparables) {
this.comparables = comparables;
}
public boolean isEmpty() {
if (comparables == null || comparables.length == 0) {
return true;
}
return false;
}
public void makeEmpty() {
comparables = new Comparable[]{};
}
public void insert(Comparable comparable) {
int length = this.comparables.length;
Comparable[] comparables = new Comparable[length + 1];
System.arraycopy(this.comparables, 0, comparables, 0, length);
comparables[length] = comparable;
this.comparables = comparables;
}
public void remove(int index) {
if (index < 0 || this.comparables == null || this.comparables.length == 0) {
return;
}
int length = this.comparables.length;
if (index > length - 1) {
return;
}
Comparable[] objects = new Comparable[length - 1];
for (int i = 0; i < length; i++) {
if (i == index) {
continue;
}
if (i < index) {
objects[i] = comparables[i];
} else {
objects[i - 1] = comparables[i];
}
}
this.comparables = objects;
}
public Comparable findMax() {
if (comparables == null || comparables.length == 0) {
return null;
}
int maxIndex = 0;
for (int i = 0; i < comparables.length; i++) {
if (comparables[i].compareTo(comparables[maxIndex]) > 0) {
maxIndex = i;
}
}
return comparables[maxIndex];
}
public Comparable findMin() {
if (comparables == null || comparables.length == 0) {
return null;
}
int minIndex = 0;
for (int i = 0; i < comparables.length; i++) {
if (comparables[i].compareTo(comparables[minIndex]) < 0) {
minIndex = i;
}
}
return comparables[minIndex];
}
}
class Test {
public static void main(String[] args) {
OrderedCollection collection = new OrderedCollection();
collection.setComparables(new Comparable[]{1, 2, 3, 4, 5, 6, 7, 8});
collection.insert(9);
collection.remove(7);
System.out.println(collection.findMax());
System.out.println(collection.findMin());
for (Comparable comparable : collection.getComparables()) {
System.out.print(comparable + " ");
}
}
}
Ch2
2.7:
(1):
a:The running time is O(N)
b: The running time in Java is shown in the figure below
c: My analysis is basically consistent with the real running time
(2):
a:The running time is O(N2)
b: The running time in Java is shown in the figure below
c:My analysis is basically consistent with the real running time
(3):
a:The running time is O(N3)
b: The running time in Java is shown in the figure below
c: My analysis takes longer than the real run time
(4):
a:The running time is O(N2)
b: The running time in Java is shown in the figure below
c:My analysis is basically consistent with the real running time
(5):
a:The running time is O(N5)
b: The running time in Java is shown in the figure below. But this program takes too long for my computer to calculate
c:I think that my analysis takes longer than the real run time, but I didn't get the real time . So I have no facts to prove it
(6):
a:The running time is O(N4)
b: The running time in Java is shown in the figure below. But this program takes too long for my computer to calculate
c: I think that my analysis is basically consistent with the real running time. But I didn't get the real time. So I have no facts to prove it
2.11:
a:It takes 2.5ms(0.5ms * 5 = 2.5 ms)
b:It takes slightly more than 2.5ms(0.5ms * 5log5 >2.5ms)
c:It takes 12.5ms(0.5ms * 25 = 12.5ms)
d:It takes 62.5ms(0.5ms * 125 = 62.5ms)
2.17:
a:
public class Demo7 {
public static void main(String[] args) {
int[] arr = {0, 1, 2, -5, -7, 6, 8};
int minSeq = getMinSeq(arr);
System.out.println(minSeq);
}
public static int getMinSeq(int[] arr) {
int minSum = 0;
if (arr != null && arr.length > 0) {
minSum = arr[0];
int thisSum = 0;
for (int i = 0; i < arr.length; i++) {
thisSum += arr[i];
if (thisSum < minSum) {
minSum = thisSum;
} else if (thisSum > 0) {
thisSum = 0;
}
}
}
return minSum;
}
}
Running time analyses: The running time is O(N)
b:
public class Demo8 {
public static void main(String[] args) {
int[] arr = {2, -3, 8, -6, 12, 9, 5, -2};
int minPositiveSeq = getMinPositiveSeq(arr);
System.out.println(minPositiveSeq);
}
public static int getMinPositiveSeq(int[] arr) {
int minPosSum = 0;
int len = arr.length;
int[] newArr = new int[len];
for (int i = 0; i < len; i++) {
minPosSum += arr[i];
newArr[i] = minPosSum;
}
int[] newArray = new int[newArr.length];
System.arraycopy(newArr, 0, newArray, 0, newArr.length);
quickSort(newArr);
int min = newArr[0] >= 0 ? newArr[0] : newArr[len - 1];
for (int i = 1; i < len; i++) {
if (newArr[i] > newArr[i - 1]) {
int temp = newArr[i] - newArr[i - 1];
if (temp < min) {
int i1 = search(newArray, newArr[i]);
int i2 = search(newArray, newArray[i - 1]);
if (i1 > i2) {
min = temp;
}
}
}
}
return min;
}
public static int search(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key) {
return i;
}
}
return 0;
}
public static void quickSort(int[] array) {
if (array == null || array.length == 0 || array.length == 1) {
return;
}
sort(array, 0, array.length - 1);
}
public static void sort(int[] array, int left, int right) {
if (left > right) {
return;
}
int base = array[left];
int i = left, j = right;
while (i != j) {
while (array[j] >= base && i < j) {
j--;
}
while (array[i] <= base && i < j) {
i++;
}
if (i < j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
array[left] = array[i];
array[i] = base;
sort(array, left, i - 1);
sort(array, i + 1, right);
}
}
Running time analyses: The running time is O(NlogN)
C:
public class Demo9 {
public static void main(String[] args) {
int [] arr = {3,5,-4,8,7,-6,9};
int maxSeqMulti = getMaxSeqMulti(arr);
System.out.println(maxSeqMulti);
}
public static int getMaxSeqMulti(int [] arr){
int max = Integer.MIN_VALUE;
for(int i = 0;i<arr.length;i++){
int temp = arr[i];
for (int j = i+1;j<arr.length;j++){
max = Math.max(max,temp);
temp*=arr[j];
}
max = Math.max(max,temp);
}
return max;
}
}
Running time analyses: The running time is O(N2)
