221202 :: [leetcode] Count Largest Group, Minimum Moves to Equal Array Elements II, Longest Common Subsequence

Count Largest Group

 

You are given an integer n.

Each number from 1 to n is grouped according to the sum of its digits.

Return the number of groups that have the largest size.

 

Example 1:

Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9].
There are 4 groups with largest size.

Example 2:

Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

 

Constraints:

• 1 <= n <= 104

 

/**
 * @param {number} n
 * @return {number}
 */
var countLargestGroup = function (n) {
    let arr = [];
    let nums = [];
    for (let i = 1; i <= n; i++) {
        let sum = +String(i)
            .split("")
            .reduce((a, b) => +a + +b);
        if (arr.includes(sum)) {
            nums[arr.indexOf(sum)] += 1;
        } else {
            arr.push(sum);
            nums.push(1);
        }
    }
    let max = Math.max(...nums);
    let num = 0;
    for (let k = 0; k < nums.length; k++) {
        if (nums[k] === max) {
            num++;
        }
    }
    return num;
};

 

Minimum Moves to Equal Array Elements II

 

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

 

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

 

Constraints:

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function (nums) {
    nums.sort((a, b) => a - b);
    const mid = nums[Math.ceil(nums.length / 2) - 1];
    let sum = 0;
    for (const num of nums) {
        sum += Math.abs(mid - num);
    }
    return sum;
};

 

Longest Common Subsequence

 

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

 

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

 

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

 

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    if (text1.length == 0 || text2.length == 0) return 0;
    let m = text1.length,
        n = text2.length;
    let dp = new Array(n + 1).fill(0);

    for (let i = 1; i <= m; i++) {
        let prev = dp[0];
        for (let j = 1; j <= n; j++) {
            let temp = dp[j];
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[j] = prev + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }
    return dp[n];
};