Wonderland
Search
K

# 2022-05-16

## ​977. Squares of a Sorted Array​

### Description

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints:
• `1 <= nums.length <= 10^4`
• `-10^4 <= nums[i] <= 10^4`
• `nums` is sorted in non-decreasing order.
Follow up: Squaring each element and sorting the new array is very trivial, could you find an `O(n)` solution using a different approach?

### Solution

func sortedSquares(nums []int) []int {
length := len(nums)
left, right := 0, length-1
res := make([]int, length)
for pos := length - 1; pos >= 0; pos-- {
if l, r := nums[left]*nums[left], nums[right]*nums[right]; l > r {
res[pos] = l
left++
} else {
res[pos] = r
right--
}
}
return res
}

## ​189. Rotate Array​

### Description

Given an array, rotate the array to the right by `k` steps, where `k` is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
• `1 <= nums.length <= 105`
• `-231 <= nums[i] <= 231 - 1`
• `0 <= k <= 105`
• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with `O(1)` extra space?

### Solution

func rev(nums []int) {
length := len(nums)
for i, j := 0, length-1; i < length/2; i++ {
nums[i], nums[j-i] = nums[j-i], nums[i]
}
}
func rotate(nums []int, k int) {
k %= len(nums)
rev(nums)
rev(nums[k:])
rev(nums[:k])
}