221201 :: [leetcode] Reverse Vowels of a String, Number of Islands, Maximum Length of Repeated Subarray

Reverse Vowels of a String

 

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

 

Example 1:

Input: s = "hello"
Output: "holle"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

 

Constraints:

• 1 <= s.length <= 3 * 105
• s consist of printable ASCII characters.

 

/**
 * @param {string} s
 * @return {string}
 */
let reverseVowels = function (s) {
    let result = s.split("");
    let left = 0;
    let right = s.length - 1;
    let vowels = ["a", "i", "e", "o", "u", "A", "I", "E", "O", "U"];
    while (left < right) {
        if (vowels.includes(s[left])) {
            let idx1 = left;
            if (vowels.includes(s[right])) {
                [result[idx1], result[right]] = [result[right], result[idx1]];
                left++;
            }
            right--;
        } else left++;
    }
    return result.join("");
};

 

Number of Islands

 

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

 

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let islands = 0;
    const fillIsland = (i, j) => {
        grid[i][j] = "2";
        if (i > 0 && grid[i - 1][j] == "1") fillIsland(i - 1, j);
        if (j > 0 && grid[i][j - 1] == "1") fillIsland(i, j - 1);
        if (i < grid.length - 1 && grid[i + 1][j] == "1") fillIsland(i + 1, j);
        if (j < grid[0].length - 1 && grid[i][j + 1] == "1") fillIsland(i, j + 1);
    };
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == "1") {
                fillIsland(i, j);
                islands++;
            }
        }
    }
    return islands;
};

 

Maximum Length of Repeated Subarray

 

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

 

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].

 

Constraints:

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

 

var findLength = function (nums1, nums2) {
    let n = nums1.length;
    let m = nums2.length;

    let dp = new Array(n + 1);

    for (let i = 0; i <= n; i++) {
        dp[i] = new Array(m + 1);
        for (let j = 0; j <= m; j++) {
            dp[i][j] = 0;
        }
    }

    for (let i = n - 1; i >= 0; i--) {
        for (let j = m - 1; j >= 0; j--) {
            if (nums1[i] == nums2[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
        }
    }

    let result = 0;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (dp[i][j] > result) {
                result = dp[i][j];
            }
        }
    }

    return result;
};