Recreation
What is the sum of the coefficients of
(1 − 3x + 3×2)743(1 + 3x − 3×2)744 after expanding and collecting terms?
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 1
Copyright By PowCoder代写 加微信 powcoder
CS61B Lecture #5: Arrays
• An array is a structured container whose components are
– length, a fixed integer.
– a sequence of length simple containers of the same type, num- bered from 0.
– (.length field usually implicit in diagrams.)
• Arrays are anonymous, like other structured containers. • Always referred to with pointers.
• For array pointed to by A,
– Length is A.length
– Numbered component i is A[i] (i is the index )
– Important feature: index can be any integer expression.
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 2
int[] x, y, z;
String[] a;
x = new int[3];
a = new String[3];
a[1] = “Hello”;
A Few Samples
q=newint[] { 1,2,3 };
// Short form for declarations: int[]r= { 7,8,9 };
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 3
Example: Accumulate Values Problem: Sum up the elements of array A.
static int sum(int[] A) { int N;
for (int i = 0; i < A.length; i += 1)
N += A[i];
// For the hard-core: could have written
for (i=0, N=0; i
arr[i] = arr[i-1];
/* Alternative to this loop:
System.arraycopy(arr, k, arr, k+1, arr.length-k-1);*/
arr[k] = x;
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 5
(Aside) Java Shortcut
• Useful tip: Can write just ‘arraycopy’ by including at the top of the
source file:
import static java.lang.System.arraycopy;
• This means “define the simple name arraycopy to be the equivalent
of java.lang.System.arraycopy in the current source file.”
• Can do the same for out so that you can write
out.println(…);
in place of
System.out.println(…);
• Finally, a declaration like
import static java.lang.Math.*;
means “take all the (public) static definitions in java.lang.Math and make them available in this source file by their simple names (the name after the last dot).”
• Useful for functions like sin, sqrt, etc.
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 6
gazelle into
hartebeest
A: bear gazelle
hartebeest
Growing an Array
Problem: Suppose that we want to change the description above, so that A = insert2 (A, 2, “gnu”) does not shove “skunk” off the end, but instead “grows” the array.
/** Return array, r, where r.length = ARR.length+1; r[0..K-1]
* the same as ARR[0..K-1], r[k] = x, r[K+1..] same as ARR[K..]. */
static String[] insert2(String[] arr, int k, String x) { String[] result = new String[arr.length + 1]; arraycopy(arr, 0, result, 0, k);
arraycopy(arr, k, result, k+1, arr.length-k); result[k] = x;
return result; }
Why do we need a different return type from insert2?? Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 7
Example: Merging
Problem: Given two sorted arrays of ints, A and B, produce their
merge: a sorted array containing all items from A and B. A: 0 2 3 6 9 11 B: 1 4 5 7 8
result: 0 1 2 3 4 5 6 7 8 9 11
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 8
Example: Merging Program
Problem: Given two sorted arrays of ints, A and B, produce their merge: a sorted array containing all from A and B.
Remark: In order to solve this recursively, it is useful to generalize the original function to allow merging portions of the arrays.
/** Assuming A and B are sorted, returns their merge. */
public static int[] merge(int[] A, int[] B) { return mergeTo(A, 0, B, 0);
/** The merge of A[L0..] and B[L1..] assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1) {
int N = A.length – L0 + B.length – L1; int[] C = new int[N];
if (L0 >= A.length) arraycopy(B, L1, C, 0, N); else if (L1 >= B.length) arraycopy(A, L0, C, 0, N); else if (A[L0] <= B[L1]) {
What is wrong with this implementation?
} else { C[0] =
A[L0]; arraycopy(mergeTo(A, L0+1, B, L1), 0, C, 1, N-1); B[L1]; arraycopy(mergeTo(A, L0, B, L1+1), 0, C, 1, N-1);
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 9
A Tail-Recursive Strategy
public static int[] merge(int[] A, int[] B) {
return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0);
/** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ ...
This last method merges part of A with part of B into part of C. For example, consider a possible call mergeTo(A, 3, B, 1, C, 2)
A: -1 0 2 3 6 9 B: 1 4 5 7 8
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 10
C: ? ? 3 4 5 6 7 8 9 ? ? k
A Tail-Recursive Solution
public static int[] merge(int[] A, int[] B) {
return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0);
/** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (??) {
} else if (??) { C[k] = A[L0];
return mergeTo(A, ??, B, ??, C, ??) } else {
C[k] = B[L1];
return mergeTo(A, ??, B, ??, C, ??) }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 11
A Tail-Recursive Solution
public static int[] merge(int[] A, int[] B) {
return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0);
/** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (??) { C[k] = A[L0];
return mergeTo(A, ??, B, ??, C, ??) } else {
C[k] = B[L1];
return mergeTo(A, ??, B, ??, C, ??) }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 12
A Tail-Recursive Solution
public static int[] merge(int[] A, int[] B) {
return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0);
/** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) {
C[k] = A[L0];
return mergeTo(A, ??, B, ??, C, ??) } else {
C[k] = B[L1];
return mergeTo(A, ??, B, ??, C, ??) }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 13
A Tail-Recursive Solution
public static int[] merge(int[] A, int[] B) {
return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0);
/** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) {
C[k] = A[L0];
return mergeTo(A, L0 + 1, B, L1, C, k + 1); } else {
C[k] = B[L1];
return mergeTo(A, ??, B, ??, C, ??) }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 14
A Tail-Recursive Solution
public static int[] merge(int[] A, int[] B) {
return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0);
/** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) {
C[k] = A[L0];
return mergeTo(A, L0 + 1, B, L1, C, k + 1); } else {
C[k] = B[L1];
return mergeTo(A, L0, B, L1 + 1, C, k + 1); }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 15
Iterative Solution
In general, we don’t use either of the previous approaches in languages like C and Java. Array manipulation is most often iterative:
public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; // mergeTo(A, 0, B, 0, C, 0)
int L0, L1, k;
L0 = L1 = k = 0;
while (??) {
if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) {
C[k] = A[L0];
C[k] = B[L1];
return C; }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 16
Iterative Solution
In general, we don’t use either of the previous approaches in languages like C and Java. Array manipulation is most often iterative:
public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; // mergeTo(A, 0, B, 0, C, 0)
int L0, L1, k;
L0 = L1 = k = 0;
while (L0 < A.length || L1 < B.length) {
if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) {
C[k] = A[L0];
C[k] = B[L1];
return C; }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 17
Iterative Solution
In general, we don’t use either of the previous approaches in languages like C and Java. Array manipulation is most often iterative:
public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; // mergeTo(A, 0, B, 0, C, 0)
int L0, L1, k;
L0 = L1 = k = 0;
while (L0 < A.length || L1 < B.length) {
if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) {
C[k] = A[L0];
L0 += 1; k += 1;
C[k] = B[L1];
L1 += 1; k += 1;
return C; }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 18
Iterative Solution II
The same, with a for loop:
public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; int L0, L1;
L0 = L1 = 0; for(intk=0;k