221118 :: [leetcode] Minimum Difference Between Highest and Lowest of K Scores, Intersection of Two Arrays II, Jump Game II

Minimum Difference Between Highest and Lowest of K Scores

You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

 

Example 1:

Input: nums = [90], k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
- [90]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.

Example 2:

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.

 

Constraints:

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= 105

 

Solution:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

var minimumDifference = function (nums, k) {
    nums.sort((a, b) => a - b);
    let left = 0,
        right = k - 1;
    let minNum = Number.MAX_SAFE_INTEGER;
    while (right < nums.length) {
        minNum = Math.min(minNum, nums[right] - nums[left]);
        left++;
        right++;
    }

    return minNum;
};

• 포인터 2개로 nums 배열 탐색 (left와 right)
• 각 값의 차가 더 적은 수일 때 minNum을 업데이트하고 minNum 반환

 

Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

 

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

 

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

 

Solution:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    let arr = [];
    let p1 = 0;
    let p2 = 0;

    while (p1 < nums1.length && p2 < nums2.length) {
        if (nums1[p1] === nums2[p2]) {
            arr.push(nums1[p1]);
            p1++;
            p2++;
        } else if (nums1[p1] < nums2[p2]) {
            p1++;
        } else {
            p2++;
        }
    }
    return arr;
};

• nums1과 nums2를 정렬하고 각 인덱스를 포인터로 지정
• 값이 같으면 배열 arr에 push 하고, 값이 크거나 작으면 포인터를 옮겨서 다시 조건문 수행

 

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

 

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
    let left = 0;
    let right = 0;
    let jump = 0;

    while (right < nums.length - 1) {
        let max = 0;
        for (let i = left; i < right + 1; i++) {
            max = Math.max(max, i + nums[i]);
        }
        left = right + 1;
        right = max;
        jump++;
    }
    return jump;
};