This is the second day of my participation in the August Text Challenge.More challenges in August

Square an ordered array

Given an array of integers sorted in non-descending order, nums returns a new array of the squares of each number, also sorted in non-descending order.

Example 1: input: nums = [-4,-1,0,3,10] output: [0,1,9,16,100] explanation: after square, array becomes [16,1,0,9, 9,100] after sort, array becomes [0,1,9,16,100]Copy the code

Answer key

Turn the problem into the minimum position and sort it in order. First square the array, and then find the location of the smallest value. Put the minimum in a new array.

With the merge sort core, the left and right Pointers traverse the array, moving from the smallest to the two ends, putting the smaller ones into the new array. Returns a new array.

After finding the minimum position, l and R Pointers are on the left and right sides. Compare the values of both positions, place the smaller values in the new array, and move the corresponding Pointers one step.

When one of the left and right hands comes to the end, traverse the side that does not come to the end alone.

code

var sortedSquares = function (nums) {
    let min = 0
    for (let i = 0; i < nums.length; i++) {
        nums[i] = Math.pow(nums[i], 2)
        min = nums[min] > nums[i] ? i : min
    }
    let arr = []
    arr[0] = nums[min]
    let l = min - 1, r = min + 1, index = 1
    while (l >= 0 && r < nums.length) arr[index++] = nums[l] > nums[r] ? nums[r++] : nums[l--]
    while (l >= 0) arr[index++] = nums[l--]
    while (r < nums.length) arr[index++] = nums[r++]
    return arr
};
Copy the code

Rotate the array

Given an array, move the elements of the array k positions to the right, where k is non-negative.

Example 1: input: nums =,2,3,4,5,6,7 [1], k = 3 output:,6,7,1,2,3,4 [5] : spin to the right step 1:,1,2,3,4,5,6 [7] spin to the right step 2: [6,7,1,2,3,4,5] 3 steps to the right: [5,6,7,1,2,3,4]Copy the code

Answer key

Use a new array and push the reciprocal k numbers into the new array (nums. length-k +1), and then push the 0 to nums. length-k numbers into the array in sequence. Finally, the new array is returned.

Idea 2:

On the original array, the last number is pushed off the stack, stored using a variable, and then pushed in from the head, repeating k times.

Idea 3:

Let’s do a function that reverses the array from I to j. Let’s start by reversing the whole array. Then, separate from k and reverse both sides.

code

Idea 3:

var rotate = function (nums, k) {
    reverse(nums, 0, nums.length - 1)
    reverse(nums, 0, (k % nums.length) - 1)
    reverse(nums, (k % nums.length), nums.length - 1)
    return nums
};
function reverse(nums, i, j) {
    while (i < j) {
        swap(nums, i++, j--)
    }
}
function swap(nums, i, j) {
    let temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}
Copy the code

LeetCode