Interview Questions (Shell Written Test) :

Given a sequence, adjust the values in the sequence so that the sequence becomes a strictly ascending and descending sequence (strictly ascending and descending, means that adjacent numbers are not equal, there must be a size relationship). When adjusting values, you can only increase them to find the minimum increment that satisfies the strict ascending and descending sequence.

Example:

  1. After the sequence [1, 2, 8, 8, 4, 3] is adjusted to strictly increasing and decreasing sequence, the minimum increment sum is 1, and then the sequence becomes [1, 2, 9, 8, 4, 3].
  2. After the sequence [1, 4, 2, 3, 5] is adjusted to strictly increasing and decreasing sequence, the minimum increment sum is 6, and then the sequence becomes [1, 4, 5, 6, 5].

A. the b. the C. the D. the

Analysis of ideas:

  1. The core idea of this problem is to change the sequence into a strictly increasing and decreasing sequence, so the position of the maximum value in the adjusted sequence must be between the second and the penultimate position (2 ~ ary.length-1).
  2. Assume the location of the maximum value, traverse the array, adjust the sequence to become an increasing and decreasing sequence, and find the increasing sum.
  3. Strict increment decreasing sequence has ary. Length – 2 cases, find the minimum increment sum can be.

Implementation code:

var ary = [1, 4, 2, 3, 5];
function changeAry(ary) {
    var minSum = -1;
    for(var i = 1, len = ary.length; i < len - 1; i++) { var sum = 0; var tempAry = ary.concat(); // The increment partfor (var m = 0; m < i; m++) {
            if(tempAry[m] >= tempAry[m + 1]) { var diff = tempAry[m] - tempAry[m + 1]; tempAry [m + 1] += diff + 1; sum += diff + 1; }} // Decrement partfor (var n = len - 1; n > i; n--) {
            if(tempAry[n] >= tempAry[n - 1]) { var diff = tempAry[n] - tempAry[n - 1]; tempAry[n -1] += diff + 1; sum += diff + 1; }}if(i == 1) {
            minSum = sum;
            console.log(tempAry);
            console.log(minSum);
        } else {
            if(minSum > sum) {
                minSum = sum;
                console.log(tempAry);
                console.log(minSum);
            }
        }
        tempAry = null;
    }
}
changeAry(ary);
Copy the code

Note:

  1. The reason why a set of numbers is copied in the code is because changes to the array values will affect the next iteration.
  2. Array.concat()Method, which makes a copy of the array. Changes to the copy do not affect the value of the original array.

Scan the qr code below, pay attention to my public account [front-end name lion], more exciting content to accompany you!