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)
