Make writing a habit together! This is the 9th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I plan to update the realization of all the code exercises of 23 Kingway data structure after class. Although the exam is generally written in pseudo-code, I still realized all of them because of obsessive-compulsive. The warehouse is here

  • The linear table

Then, 10

  • This real question is basically the same as the eighth question, we can directly copy over to change the parameters
  • So the first thing is brute force, just create a new array, copy it in.
  • This is order n in time, order n in space.
  • To save space, you can also create an array of size P to temporarily store the previous array [0, p-1], move the whole array to the left and then put it back in order. The space complexity will be reduced to O(p).
void change(SqList &list, int p, int n) {
  [p, n-1] [p, n-1] [p, n-1]
  SqList copied = list;
  int k = - 1;
  // 2. Copy them separately
  for (int i = p; i < n; i++) {
    copied.data[++k] = list.data[i];
  }
  for (int i = 0; i < p; i++) {
    copied.data[++k] = list.data[i];
  }
  // 3. New for old
  list = copied;
}
Copy the code
  • Four two dial a thousand jin, the whole inverse, and then respectively inverse
  • For example, [1, 2, 3, 4] is inverted to [4, 3, 2, 1], then one array [4, 3] is inverted to [3, 4], and the other array [2, 1] is inverted to [1, 2], resulting in [3, 4, 1, 2].
  • Time complexity O(n), space complexity O(1)
void reverse(SqList &list, int l, int r) {
  if (l > r || r > list.length) return;

  for (int i = 0; i < (r-l+1) /2 ; i++) {
    swap(list.data[l+i], list.data[r-i]); }}void change2(SqList &list, int p, int n) {
  // Pay attention to parameters
  reverse(list, 0, n);
  reverse(list, 0, p);
  reverse(list, p, n);
}
Copy the code

Then, 11

  • Find the median of the combination of two ordered sequences, and the violent solution just merges
  • We could just copy problem number 7 and go back(A.length + B.length)/2The number in the position will do
  • And then you realize that you don’t need to merge everything, you don’t need a secondary table to store the data, you just loop through this location
  • And notice they tell us that mid is going to be equal to(A.length + B.length - 1) / 2
  • Time complexity O(n), space complexity O(1)
int merge(SqList A, SqList B) {
  int i = 0, j = 0, k = - 1, mid = (A.length + B.length - 1) / 2;
  
  // The condition is not needed, because we find the median value and return directly
  while (1) {
    ++k;
    if (A.data[i] <= B.data[j]) {
      if (k == mid) return A.data[i];
      i++;
    } else {
      if (k == mid) returnB.data[j]; j++; }}}Copy the code
  • You can loop right to mid, you don’t have to do it every time==mid
int merge2(SqList A, SqList B) {
  int i = 0, j = 0, mid = (A.length + B.length - 1) / 2 ;
  while (i+j < mid) {
    if (A.data[i] <= B.data[j]) i++;
    else j++;
  }
  return A.data[i] < B.data[j] ? A.data[i] : B.data[j];
}
Copy the code
  • The examination does not suggest the optimal solution, the time cost is too high (except big guy), after all, the violence solution seems to have only 5 points gap at most, no need
  • I’m not going to write it down here, but I can look at the king’s answer